RFMemoryCache 设计思路

缓存污染

通过研究我发现SDWebImage和Kingfisher是使用NSCache进行Memory Cache的，但是NSCache淘汰机制不透明，自动释放内存的算法是不确定的， 有时是按照LRU(最近最久未使用)释放，有时随机释放，所以会影响Cache命中率。YYCache缓存内部用双向链表和NSDictionary实现了LRU淘汰算法（如果你想了解这部分详情可以看看我之前的一篇文章用Swift实现Cache LRU （译文）），这有效的提高了命中率，但是会有一个问题，缓存污染。何为缓存污染？

对于单LRU队列，想象这样一个场景，用户进入了一个大量图片的页面后返回，大量的新图片涌入，直接将LRU队列清空。

为何避免缓存污染，我选择FIFO+LRU的方式，使用了二级内存缓存结构。

原理

Two queues（以下使用2Q代替）算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列（注意这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。其中FIFO队列和LRU队列都是使用向链表和NSDictionary实现的。

实现

数据第一次访问时，2Q算法将数据缓存在FIFO队列里面，当数据第二次被访问时，则将数据从FIFO队列移到LRU队列里面，两个队列各自按照自己的方法淘汰数据。详细实现如下：

1337859339_6844.png

1. 新访问的数据插入到FIFO队列；

2. 如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；

3. 如果数据在FIFO队列中被再次访问，则将数据移到LRU队列头部；

4. 如果数据在LRU队列再次被访问，则将数据移到LRU队列头部；

5. LRU队列淘汰末尾的数据。

用 DispatchSemaphore 来保证线程安全，ibireme在写不再安全的 OSSpinLock有做过各种锁的性能测试，如下图：

lock_benchmark.png

由于OSSpinLock不再线程安全，所以我选择了DispatchSemaphore，同时ibireme也提到有消息称，苹果在新系统中已经优化了 pthread_mutex 的性能，所以它看上去和 OSSpinLock 差距并没有那么大了。

public init(_ fC: Int = 400, lC: Int = 400) {
        
    FIFOQueue = FIFOCache<Key>(fC)
    LRUQueue = LRUCache<Key>(lC)
    NotificationCenter.default.addObserver(
        self, selector: #selector(clearMemoryCache), name: .UIApplicationDidReceiveMemoryWarning, object: nil)
}

当内存过低收到警告时清空FIFO和LRU队列。

使用

源码：RFMemoryCache

let cache = MemoryCache<Int>()
cache.set(0, val: 0)
cache.set(1, val: 1)
cache.set(2, val: 2)
cache.set(0, val: 0)

参考文章
缓存近期最少使用算法
不再安全的 OSSpinLock
如何打造易扩展的高性能图片组件