YYCache 源码学习 —— YYMemoryCache

YYCache是一个高性能的缓存工具，本着阅读优秀的人的代码就相当于与优秀的人交流的本意，我拜读了 YYCache 的开源代码。这篇文章是自己阅读源码时的记录。

• 介绍
• 代码拆解
  • YYMemoryCache
• 其它知识点
  • 异步释放对象
  • 底层类的使用

成员介绍

项目结构

• YYCache
  • YYMemoryCache
    • _YYLinkedMap
    • _YYLinkedMapNode
  • YYDiskCache
    • YYKVStorage
    • YYKVStorageItem

成员职责

类名	职责
YYCache	对 YYMemoryCache 和 YYDiskCache 的操作进行了封装
YYMemoryCache	线程安全的内存缓存，支持手动和自动清除缓存及对象释放控制
_YYLinkedMap	双向链表，供 YYMemoryCache 使用来支持 LRU (least-recently-used) 淘汰算法
_YYLinkedMapNode	_YYLinkedMap 的结点
YYDiskCache	磁盘缓存
YYKVStorage	YYDiskCache 的底层实现类，用于管理磁盘缓存
YYKVStorageItem	内置在 YYKVStorage 中，是 YYKVStorage 内部用于封装某个缓存的类

代码拆解

YYCache

YYCache 提供了最外层的缓存操作方法，而这些方法都是对 YYMemoryCache 及 YYDiskCache 操作的封装。

在 YYCache 中对缓存内容进行的操作都是先调用 YYMemoryCache 再调用 YYDiskCache，例如：

// 是否包含
- (BOOL)containsObjectForKey:(NSString *)key {
    return [_memoryCache containsObjectForKey:key] || [_diskCache containsObjectForKey:key];
}

// 根据 key 查找
- (id<NSCoding>)objectForKey:(NSString *)key {
    id<NSCoding> object = [_memoryCache objectForKey:key];
    if (!object) {
        object = [_diskCache objectForKey:key];
        if (object) {
            [_memoryCache setObject:object forKey:key];
        }
    }
    return object;
}

// 根据 key 设置缓存
- (void)setObject:(id<NSCoding>)object forKey:(NSString *)key {
    [_memoryCache setObject:object forKey:key];
    [_diskCache setObject:object forKey:key];
}

// 根据 key 删除某个缓存
- (void)removeObjectForKey:(NSString *)key {
    [_memoryCache removeObjectForKey:key];
    [_diskCache removeObjectForKey:key];
}

// 删除所有缓存
- (void)removeAllObjects {
    [_memoryCache removeAllObjects];
    [_diskCache removeAllObjects];
}

YYMemoryCache

LRU 淘汰算法

YYMemoryCache 使用了 _YYLinkedMap 及 _ YYLInkedMapNode 实现了 LRU 淘汰算法。

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

在 YYMemoryCache 中使用了双向链表结构来处理缓存：

1. 写入一个新的缓存时，将缓存接头插入到链表头部。
2. 访问一个已有的缓存时，将被访问的缓存结点移动到链表头部。
3. 清理缓存时，从链表的尾部开始逐个清理。

知道了 YYMemoryCache 是怎么处理缓存之后，我们来看看这个双向链表的具体实现吧。

_YYLinkedMap

/**
 定义的双向链表，是非线程安全的
 
 不推荐直接使用
 */
@interface _YYLinkedMap : NSObject {
    @package
    CFMutableDictionaryRef _dic; // do not set object directly
    NSUInteger _totalCost;
    NSUInteger _totalCount;
    _YYLinkedMapNode *_head; // MRU, do not change it directly
    _YYLinkedMapNode *_tail; // LRU, do not change it directly
    BOOL _releaseOnMainThread;
    BOOL _releaseAsynchronously;
}

// 在链表头部插入一个新的结点
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;

// 将某个结点移动到链表头部
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;

/// Remove a inner node and update the total cost.
/// Node should already inside the dic.
- (void)removeNode:(_YYLinkedMapNode *)node;

/// Remove tail node if exist.
- (_YYLinkedMapNode *)removeTailNode;

/// Remove all node in background queue.
- (void)removeAll;

@end

_YYLinkedMapNode

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // 前节点
    __unsafe_unretained _YYLinkedMapNode *_next; // 后节点
    id _key; // 缓存的 key
    id _value; // 缓存数据
    NSUInteger _cost; // 占用大小
    NSTimeInterval _time; // 最后一次使用时间
}
@end

关于双向链表的操作这里就不展开了，如果对链表的操作不熟悉的，可以去前面的文章数据结构学习：线性表(链式存储)中回顾一下。

缓存控制

YYCache 通过三个维度进行缓存的控制：缓存开销，缓存数量，缓存时间。我们可以手动根据这三个维度去清理缓存，YYCache 自身也有自动清理缓存的策略，并且 YYCache 还监听了 UIApplicationDidReceiveMemoryWarningNotification 及 UIApplicationDidEnterBackgroundNotification 两个系统通知，在内存报警和进入后台时根据用户的配置选择是否清空所有缓存。

自动清理

在 YYCache 初始化时，就开启了缓存的自动清理功能以及监听了进入后台和内存报警的通知：

- (instancetype)init {
    self = super.init;
    
    .....
    
    [[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];
    });
}

这里的自动清理是一个递归调用，按照 cost，count，age 的顺序清理掉不符合要求的数据。

通知监听的实现：

- (void)_appDidReceiveMemoryWarningNotification {
    if (self.didReceiveMemoryWarningBlock) {
        self.didReceiveMemoryWarningBlock(self);
    }
    if (self.shouldRemoveAllObjectsOnMemoryWarning) {
        [self removeAllObjects];
    }
}

- (void)_appDidEnterBackgroundNotification {
    if (self.didEnterBackgroundBlock) {
        self.didEnterBackgroundBlock(self);
    }
    if (self.shouldRemoveAllObjectsWhenEnteringBackground) {
        [self removeAllObjects];
    }
}

YYCache 提供了两个属性：

// 是否在收到内存警告时删除全部缓存。默认为 YES
@property BOOL shouldRemoveAllObjectsOnMemoryWarning;

// 是否在进入后台时删除全部缓存。默认为 YES
@property BOOL shouldRemoveAllObjectsWhenEnteringBackground;

手动清理

其实上面的自动清理中调用的修剪缓存的方法，全部都提供了外部调用的接口：

- (void)trimToCount:(NSUInteger)count;

- (void)trimToCost:(NSUInteger)cost;

- (void)trimToAge:(NSTimeInterval)age;

手动清理的时候，我们可以根据自己的需求对缓存进行控制。

学到的什么

异步释放对象

- (void)removeObjectForKey:(id)key {
    
    if (!key) return;
    
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        [_lru removeNode:node];
        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);
}

node 在执行这个方法后出了作用域，reference 减一，但是 block 里面调用 node，使node 被这个 queue Hold 住，reference 加一, 那么，执行完这个 block 之后，reference count 减一，就达到了再对应线程里面释放目的。

底层类的使用

在实现双向链表时，完全可以使用 NSDictionary，但是源码中使用了更加底层的 CFDictionary 来提高缓存的性能。

多线程的使用

在源码中可以看到大量使用了多线程来将缓存的自动清理和释放放到子线程中执行，对性能的提升有很大的帮助。

总结

看了这么优秀的源码，我们可以看到作者设计接口的一些思路，看到作者为性能提升做的一些努力。功能的东西大概就是这些，每个人都能说上几句，但是设计思路以及为提升性能做的一些细节更是我们需要学习的东西。