YYMemoryCache是YYCache中的内存缓存模块，是采用了LRU算法实现的经典源码。YYMemoryCache用一个字典对象来存取缓存数据，当缓存数据超过指定容量上限时，会删除部分缓存。
1、LRU
LRU全称是Least recently used，是一种常用的缓存淘汰算法，遵循最近最少使用原则，当发生内存警告或者缓存值达到上限,会优先淘汰时间戳靠前的对象,最近使用的不被淘汰。
常见的实现方式是使用双链表配合哈希表来存储缓存数据，哈希表保存key和节点，避免了遍历链表的耗时，双向链表控制节点顺序，当位置需要更改时，可以直接更改节点，避免遍历链表的耗时。
LRU结构图
当有新数据要缓存时，先将缓存数据包装成一个节点，插入双向链表的头部。如果访问链表中存在该缓存数据，将该数据对应的节点移动至链表的头部。这样的做法保证了被使用的数据（存储/访问）始终位于链表的前部。当缓存的数据总量超出容量时，先删除末尾的缓存数据节点，因为末尾的数据最少被使用过。
根据这个算法的原理，我们探索下YYMemoryCache的源码实现
2、YYMemoryCache
2.1 链表的实现
（1） _YYLinkMap
@interface _YYLinkedMap : NSObject {
@package
CFMutableDictionaryRef _dic; //哈希字典，存放缓存数据
NSUInteger _totalCost; //缓存总大小
NSUInteger _totalCount; //缓存节点总个数
_YYLinkedMapNode *_head; //头结点
_YYLinkedMapNode *_tail; //尾结点
BOOL _releaseOnMainThread; //在主线程释放
BOOL _releaseAsynchronously;//在异步线程释放
}
_YYLinkMap负责实现缓存和LRU的功能，其中使用了C语言中的CFMutableDictionaryRef来替代了OC中的NSMutableDictionary，主要原因有二：
- 速度相对较快
- key无需遵守NSCopying协议
（2） _YYLinkedMapNode
@interface _YYLinkedMapNode : NSObject {
@package
__unsafe_unretained _YYLinkedMapNode *_prev; //前向前一个节点的指针
__unsafe_unretained _YYLinkedMapNode *_next; //指向下一个节点的指针
id _key; //缓存数据key
id _value; //缓存数据value
NSUInteger _cost; //节点占用大小
NSTimeInterval _time; //节点操作时间戳
}
_YYLinkedMapNode封装了缓存数据的信息
（3）添加新节点
// 将一个node对象插到队列最前面
- (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;
}
}
（4） 移动节点
// 将一个node放到队列最前面
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
if (_head == node) return;//如果当前节点是表头
if (_tail == node) {//如果当前节点是尾节点
_tail = node->_prev;//将node的前驱结点指向尾节点
_tail->_next = nil;//将尾节点的后继节点置空
} else {
node->_next->_prev = node->_prev;//将node指向的下一个节点的前驱节点,指向node的前驱节点
node->_prev->_next = node->_next;//将node指向的上一个节点的后继节点,指向node的后继节点,从链表中剥离出node
}
node->_next = _head;//将node的后继节点指向当前头节点
node->_prev = nil;//将node的前驱节点置空
_head->_prev = node;//此时的头节点的前驱指向node
_head = node;//将此时的node置为头节点
}
（5）删除节点
//移除掉指定node，前提是node为链表中的一个节点
- (void)removeNode:(_YYLinkedMapNode *)node {
CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
_totalCost -= node->_cost;//调整总开销
_totalCount--;//调整总缓存数
if (node->_next) node->_next->_prev = node->_prev;//如果node 存在后继节点,则将node的后继节点的前驱指向node的前驱结点
if (node->_prev) node->_prev->_next = node->_next;//如果node 存在前驱节点,则将node的前驱节点的后继指向node的后继节点
if (_head == node) _head = node->_next;//如果node是头节点,则将node的后继节点置为头节点
if (_tail == node) _tail = node->_prev;//如果node是尾节点, 则将node的前驱结点置为尾节点
}
（6）删除尾结点
//将最后一个node移除
- (_YYLinkedMapNode *)removeTailNode {
if (!_tail) return nil;
_YYLinkedMapNode *tail = _tail;
CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
_totalCost -= _tail->_cost;
_totalCount--;
if (_head == _tail) {
_head = _tail = nil;
} else {
_tail = _tail->_prev;
_tail->_next = nil;
}
return tail;
}
（7）清除链表
- (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);
}
}
}
2.2 链表的使用
2.2.1 锁
（1）为什么要用锁
多线程很容易引起资源的抢夺，所以开放时都需要用到锁来保证线程安全
iOS锁性能
在YYCache中前期使用的是OSSpinLock，但由于iOS系统的更新迭代，系统维护了 5 个不同的线程优先级/QoS: background，utility，default，user-initiated，user-interactive。高优先级线程始终会在低优先级线程前执行，一个线程不会受到比它更低优先级线程的干扰。这种线程调度算法会产生潜在的优先级反转问题，从而破坏了 spin lock。(具体查看不再安全的 OSSpinLock），所以现在采用的是pthread_mutex。
（2）pthread_mutex
pthread_mutex是互斥锁，当涉及多线程执行代码的情况下，通过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。
2.2.2 使用
（1）初始化
- (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;
_shouldRemoveAllObjectsOnMemoryWarning = YES;
_shouldRemoveAllObjectsWhenEnteringBackground = YES;
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];
[self _trimRecursively];
return self;
}
- (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]; //循环调用本方法
});
}
- (void)_trimInBackground {
dispatch_async(_queue, ^{
[self _trimToCost:self->_costLimit];
[self _trimToCount:self->_countLimit];
[self _trimToAge:self->_ageLimit];
});
}
初始化中，创建了lru对象，设置了基本参数，添加了内存警告和进入后台通知，_trimRecursively是缓存空间边界检测
（2）边界检测
- (void)_trimToCost:(NSUInteger)costLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (costLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCost <= costLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
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;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- (void)_trimToCount:(NSUInteger)countLimit {
BOOL finish = NO;
pthread_mutex_lock(&_lock);
if (countLimit == 0) {
[_lru removeAll];
finish = YES;
} else if (_lru->_totalCount <= countLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
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;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- (void)_trimToAge:(NSTimeInterval)ageLimit {
BOOL finish = NO;
NSTimeInterval now = CACurrentMediaTime();
pthread_mutex_lock(&_lock);
if (ageLimit <= 0) {
[_lru removeAll];
finish = YES;
} else if (!_lru->_tail || (now - _lru->_tail->_time) <= ageLimit) {
finish = YES;
}
pthread_mutex_unlock(&_lock);
if (finish) return;
NSMutableArray *holder = [NSMutableArray new];
while (!finish) {
if (pthread_mutex_trylock(&_lock) == 0) {
if (_lru->_tail && (now - _lru->_tail->_time) > ageLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (node) [holder addObject:node];
} else {
finish = YES;
}
pthread_mutex_unlock(&_lock);
} else {
usleep(10 * 1000); //10 ms
}
}
if (holder.count) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
}
}
- _trimToCost 方法判断了链表中所有节点占用大小之和totalCost是否大于costLimit，如果超过，则从链表末尾开始删除节点，直到totalCost小于等于costLimit为止
- _trimToCount 方法判断链表中的所有节点个数之和是否大于countLimit，如果超过，则从链表末尾开始删除节点，直到个数之和小于等于countLimit为止
- _trimToAge 方法遍历链表中的节点，删除那些和now时刻的时间间隔大于ageLimit的节点
- 这里作者还使用了pthread_mutex_trylock，这个函数是非阻塞锁，如果没有获取到锁就会立刻返回不会阻塞当前线程,获取锁成功会返回0,否则返回其他值来说明锁的状态.但是pthread_mutex_lock如果没有获取到锁会一直等待从而发生阻塞.
（3）读写数据
- (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;
}
- (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];
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //hold 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); //解锁
}
每次YYMemoryCache在进行读写的时候都会添加互斥锁，更新对应的linkedMapNode对象的时间戳属性,并且把该对象放到队列的最前面,从而调整了缓存中对象的顺序。
（4）异步线程释放
static inline dispatch_queue_t YYMemoryCacheGetReleaseQueue() {
return dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW, 0);
}
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[holder count]; // release in queue
});
其实认真看可以发现源码中很多地方都有诸如这样的异步线程，这其实是个非常巧妙的做法（具体可以查看iOS 保持界面流畅的技巧）
Note: 对象的销毁虽然消耗资源不多，但累积起来也是不容忽视的。通常当容器类持有大量对象时，其销毁时的资源消耗就非常明显。同样的，如果对象可以放到后台线程去释放，那就挪到后台线程去。这里有个小 Tip：把对象捕获到 block 中，然后扔到后台队列去随便发送个消息以避免编译器警告，就可以让对象在后台线程销毁了。
YYMemoryCacheGetReleaseQueue 是一个低优先级DISPATCH_QUEUE_PRIORITY_LOW的全局队列，这实际上是为了让销毁线程不占用主要的CPU使用时间，在相对空闲时进行销毁，提升性能。
网友评论