---

前言

提示：这篇文章主要是学习YYCache的缓存策略算法。我们在刷题的过程中会遇到相关的算法题，那就来看看在具体的工程项目中是如何使用的吧！

---

一、YYCache的来源

YYCache是大神郭曜源开源的一个内存缓存实现，目的是为了做数据的持久化。关于数据持久化的探讨，大家可以参考博客iOS数据持久化设计探讨（NSCache，PINCache，YYCache，CoreData，FMDB，WCDB，Realm）. 这篇文章详细的介绍了为什么要做数据持久化，当前比较常见的数据持久化方案，也给出了很多非常有用的链接。

二、YYCache的结构

分为两部分：内存缓存(YYMemoryCache)和硬盘缓存（YYDiskCache）：

1. YYMemoryCache

Notice：这部分参考的文章是简书作者 @汉斯哈哈哈 的文章： YYCache源码解析（二）.
YYMemoryCache使用的缓存策略：LRU+ Dictionary 是这篇文章的重点。我们来一一讲解。

1.1 最近最少使用—LRU(Least Frequently Used)

因为缓存（cache）相对于硬盘，它的特点是：容量小，存取速度快。所以当cache容量满的时候，我们就需要相应的策略算法决定哪些数据该放到cache里面。主要使用的策略算法有：先进先出—FIFO(First in first out);最近最少使用—LRU(Least Recently Used); 最不常用—LFU(Least Frequently Used); 多队列—MQ(Multi Queue)等。
在YYMemoryCache中使用的是LRU+Dictionary的方式来实现替换策略。如图所示：（图片来源）

双向链表的节点定义如下：

@interface _YYLinkedMapNode : NSObject {@package// 指向前一个节点__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic// 指向后一个节点__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic// 缓存keyid _key;// 缓存对象id _value;// 当前缓存内存开销NSUInteger _cost;// 缓存时间NSTimeInterval _time;
}
@end

整个链表的定义如下：

@interface _YYLinkedMap : NSObject {@package// 用字典保存所有节点_YYLinkedMapNode (为什么不用oc字典?因为用CFMutableDictionaryRef效率高，毕竟基于c)CFMutableDictionaryRef _dic;// 总缓存开销NSUInteger _totalCost;// 总缓存数量NSUInteger _totalCount;// 链表头节点_YYLinkedMapNode *_head;// 链表尾节点_YYLinkedMapNode *_tail;// 是否在主线程上，异步释放 _YYLinkedMapNode对象BOOL _releaseOnMainThread;// 是否异步释放 _YYLinkedMapNode对象BOOL _releaseAsynchronously;
}
// 添加节点到链表头节点
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
// 移动当前节点到链表头节点
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
// 移除链表节点
- (void)removeNode:(_YYLinkedMapNode *)node;
// 移除链表尾节点(如果存在)
- (_YYLinkedMapNode *)removeTailNode;
// 移除所有缓存
- (void)removeAll;
@end

从以上的源代码和结构图可以得知YYMemoryCache中双向链表的结构就如图所示。

1.2 基于LRU的增删改查

对于数据的处理无非就是增删改查四种操作，那么这四种操作在YYMemoryCache中是如何实现的呢？
YYMemoryCache的增删改查的函数定义如下：

// 查找
- (BOOL)containsObjectForKey:(id)key;
- (nullable id)objectForKey:(id)key;
// 修改或者是新增
- (void)setObject:(nullable id)object forKey:(id)key;
- (void)setObject:(nullable id)object forKey:(id)key withCost:(NSUInteger)cost;
// 删除
- (void)removeObjectForKey:(id)key;
- (void)removeAllObjects;

这些是YYMemoryCache中增删改查的函数定义，之前也说过具体的实现是双向链表+哈希表实现的，所以我们先来看看双向链表中的增删改查操作是如何进行的。

1.2.1 增加数据

增加数据也就是插入一个新的双向链表节点，因为采用的是LRU算法，所以新增数据肯定是插入到头节点的位置，节点按照使用时间排序。这里需要注意的是：很多人在实现链表的时候会定义一个哨兵节点，也就是放在第一的位置，这样能避免单独考虑一些特殊情况，但是在_YYLinkedMap当中，是没有这个哨兵节点的，所以源代码如下：

// 添加节点到链表头节点
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {// 字典保存链表节点nodeCFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));// 叠加该缓存开销到总内存开销_totalCost += node->_cost;// 总缓存数+1_totalCount++;if (_head) {// 存在链表头，取代当前表头node->_next = _head;_head->_prev = node;// 重新赋值链表表头临时变量_head_head = node;} else {// 不存在链表头_head = _tail = node;}
}

图解（来源同上）：

1.2.2 删除数据

当需要缓存新的数据，但是缓存又是满的时候，根据LRU算法需要删除节点。因为LRU是最近最少使用，所以最后一个节点应该是需要删除的节点。
源代码如下：

// 移除尾节点(如果存在)
- (_YYLinkedMapNode *)removeTailNode {if (!_tail) return nil;// 拷贝一份要删除的尾节点指针_YYLinkedMapNode *tail = _tail;// 移除链表尾节点CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));// 减掉总内存消耗_totalCost -= _tail->_cost;// 总缓存数-1_totalCount--;if (_head == _tail) {// 清除节点，链表上已无节点了_head = _tail = nil;} else {// 设倒数第二个节点为链表尾节点_tail = _tail->_prev;_tail->_next = nil;}// 返回完tail后_tail将会释放return tail;
}

还有一种情况就是需要清空缓存，这个时候就需要删除所有的节点，源代码如下：

// 移除所有缓存
- (void)removeAll {// 清空内存开销与缓存数量_totalCost = 0;_totalCount = 0;// 清空头尾节点_head = nil;_tail = nil;if (CFDictionaryGetCount(_dic) > 0) {// 拷贝一份字典CFMutableDictionaryRef holder = _dic;// 重新分配新的空间_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);if (_releaseAsynchronously) {// 异步释放缓存dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();dispatch_async(queue, ^{CFRelease(holder); // hold and release in specified queue});} else if (_releaseOnMainThread && !pthread_main_np()) {// 主线程上释放缓存dispatch_async(dispatch_get_main_queue(), ^{CFRelease(holder); // hold and release in specified queue});} else {// 同步释放缓存CFRelease(holder);}}
}

1.2.3 查找修改数据

当cache中的某个节点的数据被使用的时候，根据LRU算法策略，需要将其修改移动到头节点的位置。
修改数据的源代码如下：

// 移动当前节点到链表头节点
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {// 当前节点已是链表头节点if (_head == node) return;if (_tail == node) {//**如果node是链表尾节点**// 把node指向的上一个节点赋值给链表尾节点_tail = node->_prev;// 把链表尾节点指向的下一个节点赋值nil_tail->_next = nil;} else {//**如果node是非链表尾节点和链表头节点**// 把node指向的上一个节点赋值給node指向的下一个节点node指向的上一个节点node->_next->_prev = node->_prev;// 把node指向的下一个节点赋值给node指向的上一个节点node指向的下一个节点node->_prev->_next = node->_next;}// 把链表头节点赋值给node指向的下一个节点node->_next = _head;// 把node指向的上一个节点赋值nilnode->_prev = nil;// 把节点赋值给链表头节点的指向的上一个节点_head->_prev = node;_head = node;
}

1.2.4 YYMemoryCache的增删改查

// 查找缓存
- (id)objectForKey:(id)key {if (!key) return nil;// 加锁，防止资源竞争// OSSpinLock 自旋锁，性能最高的锁。原理很简单，就是一直 do while 忙等。它的缺点是当等待时会消耗大量 CPU 资源，所以它不适用于较长时间的任务。对于内存缓存的存取来说，它非常合适。pthread_mutex_lock(&_lock);// _lru为链表_YYLinkedMap，全部节点存在_lru->_dic中// 获取节点_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));if (node) {//** 有对应缓存 **// 重新更新缓存时间node->_time = CACurrentMediaTime();// 把当前node移到链表表头(为什么移到表头？根据LRU淘汰算法:Cache的容量是有限的，当Cache的空间都被占满后，如果再次发生缓存失效，就必须选择一个缓存块来替换掉.LRU法是依据各块使用的情况， 总是选择那个最长时间未被使用的块替换。这种方法比较好地反映了程序局部性规律)[_lru bringNodeToHead:node];}// 解锁pthread_mutex_unlock(&_lock);// 有缓存则返回缓存值return node ? node->_value : nil;
}

// 添加缓存
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {if (!key) return;if (!object) {// ** 缓存对象为空，移除缓存 **[self removeObjectForKey:key];return;}// 加锁pthread_mutex_lock(&_lock);// 查找缓存_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));// 当前时间NSTimeInterval now = CACurrentMediaTime();if (node) {//** 之前有缓存，更新旧缓存 **// 更新值_lru->_totalCost -= node->_cost;_lru->_totalCost += cost;node->_cost = cost;node->_time = now;node->_value = object;// 移动节点到链表表头[_lru bringNodeToHead:node];} else {//** 之前未有缓存，添加新缓存 **// 新建节点node = [_YYLinkedMapNode new];node->_cost = cost;node->_time = now;node->_key = key;node->_value = object;// 添加节点到表头[_lru insertNodeAtHead:node];}if (_lru->_totalCost > _costLimit) {// ** 总缓存开销大于设定的开销 **// 异步清理最久未使用的缓存dispatch_async(_queue, ^{[self trimToCost:_costLimit];});}if (_lru->_totalCount > _countLimit) {// ** 总缓存数量大于设定的数量 **// 移除链表尾节点(最久未访问的缓存)_YYLinkedMapNode *node = [_lru removeTailNode];if (_lru->_releaseAsynchronously) {dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();dispatch_async(queue, ^{[node class]; //  and release in queue});} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {dispatch_async(dispatch_get_main_queue(), ^{[node class]; //hold and release in queue});}}pthread_mutex_unlock(&_lock);
}

2.YYDiskCache

YYDiskCache采用的是SQLite 配合文件的存储方式，在存取小数据 (NSNumber) 时，YYDiskCache 的性能远远高出基于文件存储的库；而较大数据的存取性能则比较接近了。但得益于 SQLite 存储的元数据，YYDiskCache 实现了 LRU 淘汰算法、更快的数据统计，更多的容量控制选项。LRU算法在之前也说过了，就不细说了。
不一样的点在于YYDiskCache并不是使用双向链表实现的LRU算法，而且很多的增删改查操作都是基于数据库的。我还没来得及看YYDiskCache中LRU算法的具体实现是什么，在哪儿，希望有知道的小伙伴可以一起讨论

总结

以上就是对于YYCache的缓存策略的学习啦，有不对的地方，希望大家指出来。

参考文章

1. YYCache阅读总结
2. 深入理解YYCache
3. iOS数据持久化设计探讨（NSCache，PINCache，YYCache，CoreData，FMDB，WCDB，Realm）
4. iOS缓存框架YYCache的学习
5. YYCache源码解析（二）