iOS源码解析—YYCache(YYMemoryCache)
概述
上一篇主要讲解了YYCache的文件结构，分析了YYCache类的相关方法，本章主要分析内存缓存类YYMemoryCache。该对象内部维护一个字典对象来存取缓存数据，同时支持缓存容量的限制，当缓存数据超过指定的内存容量大小的时候，会删除部分缓存数据。这主要是通过LRU算法实现的。
LRU
LRU全称是Least recently used，基于最近最少使用的原则，属于一种缓存淘汰算法。实现思路是维护一个双向链表数据结构，每次有新数据要缓存时，将缓存数据包装成一个节点，插入双向链表的头部，如果访问链表中的缓存数据，同样将该数据对应的节点移动至链表的头部。这样的做法保证了被使用的数据（存储/访问）始终位于链表的前部。当缓存的数据总量超出容量时，先删除末尾的缓存数据节点，因为末尾的数据最少被使用过。如下图：
2-1.png
YYMemoryCache内部维护了一个_YYLinkMap对象，_YYLinkMap对象负责实现缓存和LRU的功能。下面是代码注释：
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; //哈希字典，存放缓存数据
NSUInteger _totalCost; //缓存总大小
NSUInteger _totalCount; //缓存节点总个数
_YYLinkedMapNode *_head; //头结点
_YYLinkedMapNode *_tail; //尾结点
BOOL _releaseOnMainThread; //在主线程释放
BOOL _releaseAsynchronously;//在异步线程释放
}
@end
_dic是哈希字典，负责存放缓存数据，_head和_tail分别是双链表中指向头节点和尾节点的指针，链表中的节点单元是_YYLinkedMapNode对象，该对象封装了缓存数据的信息。
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; //前向前一个节点的指针
__unsafe_unretained _YYLinkedMapNode *_next; //指向下一个节点的指针
id _key; //缓存数据key
id _value; //缓存数据value
NSUInteger _cost; //节点占用大小
NSTimeInterval _time; //节点操作时间戳
}
@end
下面分析一下_YYLinkedMap对象的主要方法：
-
insertNodeAtHead:方法
该方法首先将需要新插入的数据节点存入字典中，以节点中的key作为字典的key。然后更新总大小_totalCost和节点总个数_totalCount，将节点置于链表头部。
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node { CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node)); //存入字典中 _totalCost += node->_cost; //更新总大小 _totalCount++; //更新总数 if (_head) { //节点置于链表头部 node->_next = _head; _head->_prev = node; _head = node; } else { _head = _tail = node; } } -
bringNodeToHead:方法
该方法将节点移动至链表的头部，因为调用该方法的场景是节点已经存在于字典中，所以不需要新加入字典中。
- (void)bringNodeToHead:(_YYLinkedMapNode *)node { if (_head == node) return; if (_tail == node) { _tail = node->_prev; _tail->_next = nil; } else { node->_next->_prev = node->_prev; node->_prev->_next = node->_next; } node->_next = _head; node->_prev = nil; _head->_prev = node; _head = node; } -
removeNode方法和removeTailNode方法
removeNode方法将数据节点从字典和链表中删除，同时更新总大小_totalCost和节点总个数_totalCount。removeTailNode方法将链表中的尾部节点删除，同时从字典中删除节点。
-
removeAll方法
该方法删除链表中所有节点，同时从字典中删除所有节点。
YYMemoryCache
YYMemoryCache实现了内存缓存的功能，下面是其维护的成员变量：
pthread_mutex_t _lock;
_YYLinkedMap *_lru;
dispatch_queue_t _queue;
_lock是互斥所，当涉及多线程执行代码的情况下，通过pthread_mutex_lock(&_lock)方法给下面的代码块加互斥锁，这样其它线程会被阻塞，直到pthread_mutex_unlock(&_lock)被调用。如下：
pthread_mutex_lock(&_lock);
//代码块1
pthread_mutex_unlock(&_lock);
pthread_mutex_lock(&_lock);
//代码块2
pthread_mutex_unlock(&_lock);
线程A执行代码块1，线程B执行代码块2，如果线程A先执行代码块1，_lock被锁住，这样线程B被阻塞，直到线程A执行完代码块1后，调用pthread_mutex_unlock(_lock)，线程B开始执行代码块2。由于执行缓存的操作很容易涉及到多线程调用，所以需要通过pthread_mutex_lock来控制，关于各种锁性能的测试，YYCache的作者ibireme大神在他的博客中进行了阐述。
_lru用来做数据缓存，实现了lru算法。下面分析一下YYMemoryCache主要的方法：
-
初始化
调用init方法进行初始化，创建了lru对象，进行了一些参数设置，包括缓存节点个数限制，总cost限制，时间戳界限，进行边界检测的间隔时长等等。如下：
- (instancetype)init { self = super.init; pthread_mutex_init(&_lock, NULL); _lru = [_YYLinkedMap new]; _queue = dispatch_queue_create("com.ibireme.cache.memory", DISPATCH_QUEUE_SERIAL); _countLimit = NSUIntegerMax; _costLimit = NSUIntegerMax; _ageLimit = DBL_MAX; _autoTrimInterval = 5.0; ... [self _trimRecursively]; return self; }这些limit参数如果不设置，默认值都是最大，且这些参数以及_trimRecursively方法是用来做缓存空间的边界检测，在下文中提到。
-
存储数据
调用setObject: forKey:方法存储缓存数据，代码如下：
- (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) { //如果能取到，说明链表中之前存在key对应的缓存数据 //更新totalCost _lru->_totalCost -= node->_cost; _lru->_totalCost += cost; node->_cost = cost; node->_time = now; //更新节点的访问时间 node->_value = object; //更新节点中存放的缓存数据 [_lru bringNodeToHead:node]; //将节点移至链表头部 } else { //如果不能取到，说明链表中之前不存在key对应的缓存数据 node = [_YYLinkedMapNode new]; //创建新的节点 node->_cost = cost; node->_time = now; //设置节点的时间 node->_key = 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]; ... } pthread_mutex_unlock(&_lock); //解锁 }首先判断key和object是否为空，object如果为空，删除缓存中key对应的数据。然后从字典中查找key对应的缓存数据，分为两种情况，如果访问到节点，说明缓存数据存在，则根据最近最少使用原则，将本次操作的节点移动至链表的头部，同时更新节点的访问时间。如果访问不到节点，说明是第一次添加key和数据，需要创建一个新的节点，把节点存入字典中，并且加入链表头部。cost是指定的，默认是0。
-
访问数据
调用objectForKey:方法访问缓存数据，代码注释如下：
- (id)objectForKey:(id)key { if (!key) return nil; pthread_mutex_lock(&_lock); _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key)); //从字典中读取key相应的节点 if (node) { node->_time = CACurrentMediaTime(); //更新节点访问时间 [_lru bringNodeToHead:node]; //将节点移动至链表头部 } pthread_mutex_unlock(&_lock); return node ? node->_value : nil; }该方法从字典中获取缓存数据，如果key对应的数据存在，则更新访问时间，根据最近最少使用原则，将本次操作的节点移动至链表的头部。如果不存在，则直接返回nil。
-
边界检测
YYCache通过LRU算法处理缓存数据是否超出容量的情况。首先在初始化时，调用_trimRecursively方法，通过dispatch_after方法默认每隔5秒重新调用。下面是代码注释：
- (void)_trimRecursively { __weak typeof(self) _self = self; dispatch_after(dispatch_time(DISPATCH_TIME_NOW, (int64_t)(_autoTrimInterval * NSEC_PER_SEC)), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0), ^{ __strong typeof(_self) self = _self; if (!self) return; [self _trimInBackground]; //在异步队列中执行边界检测 [self _trimRecursively]; //递归调用本方法 }); }_trimInBackground分别调用_trimToCost、_trimToCount和_trimToAge方法检测。
_trimToCost方法判断链表中所有节点占用大小之和totalCost是否大于costLimit，如果超过，则从链表末尾开始删除节点，直到totalCost小于等于costLimit为止。代码注释如下：
- (void)_trimToCost:(NSUInteger)costLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_totalCost > costLimit) { _YYLinkedMapNode *node = [_lru removeTailNode]; //删除末尾节点 if (node) [holder addObject:node]; } else { finish = YES; //totalCost<=costLimit,检测完成 } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }其中每个节点的cost是人为指定的，默认是0，且costLimit默认是NSUIntegerMax，所以在默认情况下，_trimToCost方法不会删除末尾的节点。
_trimToCount方法判断链表中的所有节点个数之和是否大于countLimit，如果超过，则从链表末尾开始删除节点，直到个数之和小于等于countLimit为止。代码注释如下：
- (void)_trimToCount:(NSUInteger)countLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_totalCount > countLimit) { _YYLinkedMapNode *node = [_lru removeTailNode]; //删除末尾节点 if (node) [holder addObject:node]; } else { finish = YES; //totalCount<=countLimit,检测完成 } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }初始化时countLimit默认是NSUIntegerMax，如果不指定countLimit，节点的总个数永远不会超过这个限制，所以_trimToCount方法不会删除末尾节点。
_trimToAge方法遍历链表中的节点，删除那些和now时刻的时间间隔大于ageLimit的节点，代码如下：
- (void)_trimToAge:(NSTimeInterval)ageLimit { BOOL finish = NO; ... NSMutableArray *holder = [NSMutableArray new]; while (!finish) { if (pthread_mutex_trylock(&_lock) == 0) { if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) { //间隔大于ageLimit _YYLinkedMapNode *node = [_lru removeTailNode]; //删除末尾节点 if (node) [holder addObject:node]; } else { finish = YES; } pthread_mutex_unlock(&_lock); } else { usleep(10 * 1000); //10 ms } } ... }由于链表中从头部至尾部的节点，访问时间由晚至早，所以尾部节点和now时刻的时间间隔较大，从尾节点开始删除。ageLimit的默认值是DBL_MAX，如果不人为指定ageLimit，则链表中节点不会被删除。
-
线程同步
YYCache通过在方法中添加互斥所的逻辑，来保证多线程操作缓存时数据的同步。例如在setObject:forKey:withCost:方法和objectForKey:中添加代码：
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost { pthread_mutex_lock(&_lock); //操作链表，写缓存数据 pthread_mutex_unlock(&_lock); } - (id)objectForKey:(id)key { pthread_mutex_lock(&_lock); //访问缓存数据 pthread_mutex_unlock(&_lock); }如果存在线程A和B，线程A在写缓存的时候，上锁，线程B读取缓存数据时，被阻塞，需要等到线程A执行完写缓存的操作，调用pthread_mutex_unlock后，线程B才能读缓存数据，这个时候新的缓存数据已经写完，保证了操作的数据的同步。
YYCache在每一个操作的缓存的方法中都是用了互斥所来保证多线程访问数据的同步性，保证代码执行过程中的安全性。
总结
YYMemoryCache操作了内存缓存，相较于硬盘缓存需要进行I/O操作，在性能上快很多，因此YYCache访问缓存时，优先用的是YYMemoryCache。
