源码

YYCache 源码剖析：一览亮点

投稿者投稿者 源码 2018-06-11
2.37K

写在前面

YYCache 作为当下 iOS 圈最流行的缓存框架，有着优越的性能和绝佳的设计。笔者花了些时间对其“解剖”了一番，发现了很多有意思的东西，所以写下本文分享一下。

考虑到篇幅，笔者对于源码的解析不会过多的涉及 API 使用和一些基础知识，更多的是剖析作者 ibireme 的设计思维和重要技术实现细节。

YYCache 主要分为两部分：内存缓存和磁盘缓存（对应 YYMemoryCache 和 YYDiskCache）。在日常开发业务使用中，多是直接操作 YYCache 类，该类是对内存缓存功能和磁盘缓存功能的一个简单封装。

一、内存缓存：YYMemoryCache

总览 API ，会发现一些见名知意的方法：

- (nullable id)objectForKey:(id)key;
- (void)setObject:(nullable id)object forKey:(id)key;
- (void)trimToCount:(NSUInteger)count;
- (void)trimToCost:(NSUInteger)cost;
- (void)trimToAge:(NSTimeInterval)age;
......

可以看出，该类主要包含读写功能和修剪功能（修剪是为了控制内存缓存的大小等）。当然，还有其他一些自定义方法，比如释放操作的线程选择、内存警告和进入后台时是否清除内存缓存等。

好了，对该类的基本功能有了了解之后，就可以直接切实现源码了（这一步是个阅读源码的小 tip）。

（1）LRU 缓存淘汰算法

既然有修剪缓存的功能，必然涉及到一个缓存淘汰算法，YYMemoryCache 和 YYDiskCache 都是实现的 LRU  (least-recently-used) ，即最近最少使用淘汰算法。

在 YYMemoryCache.m 文件中，有如下的代码：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

熟悉链表的朋友应该一眼就看出来猫腻，作者是使用的一个双向链表来实现 LRU 的。

链表的结点 (_YYLinkedMapNode)：

  1. 同时使用前驱和后继指针（即_prev 和 _next）是为了保证链表双向查找的效率。

  2. 这里使用 __unsafe_unretained 而不使用 __weak 笔者有些疑惑，虽然两者都不会持有指针所指向的对象，但是在指向对象释放时，前者并不会置空指针，形成野指针。不过经过笔者后面的阅读，发现作者避免了野指针的出现（哈哈，很强势）。

  3. _key 和 _value 就是框架使用者想要存储的键值对，可以看出作者的设计是一个键值对对应一个结点（_YYLinkedMapNode）。

  4. _cost 和 _time 表示该结点的内存大小和最后访问的时间。

链表的头 (_YYLinkedMap) ：

  1. 头结点有头尾指针（_head和_tail），保证双端查询的效率。

  2. _totalCost 和 _totalCount 记录最大内存占用限制和数量限制。

  3. _releaseOnMainThread 和 _releaseAsynchronously 分别表示在主线程释放和在异步非主线程释放，它们的实现后文会讲到。

  4. 很多人可能有疑问，对于上面结点 (_YYLinkedMapNode) 的设计，前驱和后继指针均未引用结点，那这个结点不会释放么？其实答案就在头里面的 _dic 变量，所有结点都会在 _dic 中以 key-value 的形式存在，由这个 hash 来持有所有的结点。此处使用一个 hash 的目的很明显，是为了在常数级的时间复杂度下高速查找。

既然是 LRU 算法，怎么能只有数据结构，往下面看 _YYLinkedMap 类实现了如下算法（嗯，挺常规的结点操作，代码质量挺高的，就不说明实现了）：

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
- (void)removeNode:(_YYLinkedMapNode *)node;
- (_YYLinkedMapNode *)removeTailNode;
- (void)removeAll;

现在 LRU 的数据结构和操作算法实现都有了，就可以看具体的业务了。

（2）修剪内存的逻辑

正如一开始贴的 API ，该类有三种修剪内存的依据：根据缓存的内存块数量、根据占用内存大小、根据是否是最近使用。它们的实现逻辑几乎一下，这里就其中一个为例子（代码有删减）：

- (void)_trimToAge:(NSTimeInterval)ageLimit {
    ......
    
    NSMutableArray *holder = [NSMutableArray new];
//1 迭代部分
    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
        }
    }
//2 释放部分
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

这里有两个重要技术点，很有意思，当时看得笔者都激动了。

迭代部分：

  1. 通过一个 while 循环不断释放尾结点 removeTailNode，直到满足参数 ageLimit 对时间的要求，而链表的排序规则是：最近使用的内存块会排到头结点后面，也就保证了删除的内存永远是最不常使用的（后面会看到如何实现排序的）。

  2. 不妨思考这样一个问题：为何要使用pthread_mutex_trylock() 方法尝试获取锁，而获取失败过后做了一个线程睡眠操作 usleep ？
    历史情况：在老版本的代码中，作者是使用的 OSSpinLock 自旋锁来保证线程安全，而后来由于 OSSpinLock 的 bug 问题（不再线程安全），作者将其替换成了 pthread_mutex_t 互斥锁。
    笔者的理解： pthread_mutex_t 是互斥锁，它有一个特性：当多个线程出现数据竞争时，除了"竞争成功"的那个线程外，其他线程都会进入被动挂起状态，而当"竞争成功"的那个线程解锁时，会主动去将其他线程激活，这个过程包含了上下文的切换，cpu抢占，信号发送等开销，很明显，互斥锁的起始开销有些大，效率低于自旋锁。
    所以作者使用了 pthread_mutex_trylock () 尝试解锁，若解锁失败该方法会立即返回，让当前线程不会进入被动的挂起状态（也可以说阻塞），在下一次循环时又继续尝试获取锁。这个过程很有意思，感觉是手动实现了一个自旋锁。而自旋锁有个需要注意的问题是：死循环等待的时间越长，对 cpu 的消耗越大。所以作者做了一个很短的睡眠 usleep(10 * 1000);，有效的减小了循环的调用次数，至于这个睡眠时间的长度为什么是 10ms， 作者应该做了测试。

  3. 基于第2点的分析，可能有人会疑问为什么作者要在主线程做内存修剪的操作？如果创建一个串行的队列，然后在该队列中执行这些逻辑不是可以不使用锁就能保证线程安全了么？嗯，这里估计也是因为线程切换的资源开销大于当前业务逻辑平均的资源开销吧。

释放部分：

这里作者使用了一个容器将要释放的结点装起来，然后在某个队列（默认是非主队列）里面调用了一下该容器的方法。虽然看代码可能不理解，但是作者写了一句注释// release in queue：某个对象的方法最后在某个线程调用，这个对象就会在当前线程释放。很明显，这里是作者将结点的释放放其他线程，从而减轻主线程的资源开销。

这一段代码非常精致，不得不佩服作者的技术能力，对内存、线程安全、性能的掌握可以说是炉火纯青

（3）检查内存是否超限的定时任务

有这样一段代码：

- (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];
    });
}

可以看到，作者是使用一个递归来实现定时任务的，这里可以自定义检测的时间间隔。

（4）进入后台和内存警告的处理

在该类初始化时，作者写了内存警告和进入后台两个监听：

[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidReceiveMemoryWarningNotification) name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
[[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appDidEnterBackgroundNotification) name:UIApplicationDidEnterBackgroundNotification object:nil];

然后可以由使用者定义在触发响应时是否需要清除内存（简化了一下代码）：

- (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];
}

使用者还可以通过闭包实时监听。

（5）读数据

- (id)objectForKey:(id)key {
    if (!key) return nil;
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    if (node) {
        node->_time = CACurrentMediaTime();
        [_lru bringNodeToHead:node];
    }
    pthread_mutex_unlock(&_lock);
    return node ? node->_value : nil;
}

逻辑很简单，关键的一步是 node->_time = CACurrentMediaTime(); 和 [_lru bringNodeToHead:node]; 即更新这块内存的时间，然后将该结点移动到最前面，实现了基于时间的优先级排序。

（6）写数据

代码有删减，解析写在代码中：
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    ......
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    NSTimeInterval now = CACurrentMediaTime();
    if (node) {
//1 若缓存中有：修改node的变量，将该结点移动到头部
        ......
        [_lru bringNodeToHead:node];
    } else {
//2 若缓存中没有，创建一个内存，将该结点插入到头部
        node = [_YYLinkedMapNode new];
        ......
        [_lru insertNodeAtHead:node];
    }
//3 判断是否需要修剪内存占用，若需要：异步修剪，保证写入的性能
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
//4 判断是否需要修剪内存块数量，若需要：默认在非主队列释放无用内存，保证写入的性能
    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);
}

二、磁盘缓存：YYDiskCache

在暴露给用户的 API 中，磁盘缓存的功能和内存缓存很像，同样有读写数据和修剪数据等功能。

YYDiskCache 的磁盘缓存处理性能非常优越，作者测试了数据库和文件存储的读写效率：iPhone 6 64G 下，SQLite 写入性能比直接写文件要高，但读取性能取决于数据大小：当单条数据小于 20K 时，数据越小 SQLite 读取性能越高；单条数据大于 20K 时，直接写为文件速度会更快一些。（更详细的说明看文末链接）

所以作者对磁盘缓存的处理方式为 SQLite 结合文件存储的方式。

磁盘缓存的核心类是 YYKVStorage，注意该类是非线程安全的，它主要封装了 SQLite 数据库的操作和文件存储操作。

后文的剖析大部分的代码都是在 YYKVStorage 文件中。

（1）磁盘缓存的文件结构

首先，需要了解一下作者设计的在磁盘中的文件结构（在YYKVStorage.m中作者的注释）：

/*
 File:
 /path/
      /manifest.sqlite
      /manifest.sqlite-shm
      /manifest.sqlite-wal
      /data/
           /e10adc3949ba59abbe56e057f20f883e
           /e10adc3949ba59abbe56e057f20f883e
      /trash/
            /unused_file_or_folder
 
 SQL:
 create table if not exists manifest (
    key                 text,
    filename            text,
    size                integer,
    inline_data         blob,
    modification_time   integer,
    last_access_time    integer,
    extended_data       blob,
    primary key(key)
 ); 
 create index if not exists last_access_time_idx on manifest(last_access_time);
 */

path 是一个初始化时使用的变量，不同的 path 对应不同的数据库。在 path 下面有 sqlite 数据库相关的三个文件，以及两个目录（/data 和 /trash），这两个目录就是文件存储方便直接读取的地方，也就是为了实现上文说的在高于某个临界值时直接读取文件比从数据库读取快的理论。

在数据库中，建了一个表，表的结构如上代码所示：

  1. key 唯一标识

  2. size 当前内存块的大小。

  3. inline_data 使用者存储内容（value）的二进制数据。

  4. last_access_time 最后访问时间，便于磁盘缓存实现 LRU 算法的数据结构排序。

  5. filename 文件名，它指向直接存文件情况下的文件名，具体交互请往下看~

如何实现 SQLite 结合文件存储

这一个重点问题，就像之前说的，在某个临界值时，直接读取文件的效率要高于从数据库读取，第一反应可能是写文件和写数据库分离，也就是上面的结构中，manifest.sqlite 数据库文件和 /data 文件夹内容无关联，让 /data 去存储高于临界值的数据，让 sqlite 去存储低于临界值的数据。

然而这样会带来两个问题：

  1. /data 目录下的缓存数据无法高速查找（可能只有遍历）

  2. 无法统一管理磁盘缓存

为了完美处理该问题，作者将它们结合了起来，所有关于用户存储数据的相关信息都会放在数据库中（即刚才说的那个table中），而待存储数据的二进制文件，却根据情况分别处理：要么存在数据库表的 inline_data 下，要么直接存储在 /data 文件夹下。

如此一来，一切问题迎刃而解，下文根据源码进行验证和探究。

（2）数据库表的OC模型体现

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

0

该类的属性和数据库表的键一一对应。

（3）数据库的操作封装

对于 sqlite 的封装比较常规，作者的容错处理做得很好，下面就一些重点地方做一些讲解，对数据库操作感兴趣的朋友可以直接去看源码。

sqlite3_stmt 缓存

YYKVStorage 类有这样一个变量：CFMutableDictionaryRef _dbStmtCache;
通过 sql 生成 sqlite3_stmt 的封装方法是这样的：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

1

作者使用了一个 hash 来缓存 stmt， 每次根据 sql 生成 stmt 时，若已经存在缓存就执行一次 sqlite3_reset(stmt); 让 stmt 回到初始状态。

如此一来，提高了数据库读写的效率，是一个小 tip。

利用 sql 语句操作数据库实现 LRU

数据库操作，仍然有根据占用内存大小、最后访问时间、内存块数量进行修剪内存的方法，下面就根据最后访问时间进行修剪方法做为例子：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

2

可以看到，作者利用 sql 语句，很轻松的实现了内存的修剪。

写入时的核心逻辑

写入时，作者根据是否有 filename 判断是否需要将写入的数据二进制存入数据库（代码有删减）：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

3

若存在 filename ，虽然不会写入数据库，但是会直接写入 /data 文件夹，这个逻辑是在本类的 public 方法中做的。

（4）文件操作的封装

主要是 NSFileManager 相关方法的基本使用，比较独特的是，作者使用了一个“垃圾箱”，也就是磁盘文件存储结构中的 /trash 目录。

可以看到两个方法：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

4

上面个方法是将 /data 目录下的文件移动到 /trash 目录下，下面个方法是将 /trash 目录下的文件在异步线程清理掉。

笔者的理解：很容易想到，删除文件是一个比较耗时的操作，所以作者把它放到了一个专门的队列处理。而删除的文件用一个专门的路径 /trash 放置，避免了写入数据和删除数据之间发生冲突。试想，若删除的逻辑和写入的逻辑都是对 /data 目录进行操作，而删除逻辑比较耗时，那么就会很容易出现误删等无法预估的情况。

（5）YYDiskCache 对 YYKVStorage 的二次封装

对于 YYKVStorage 的公有方法，笔者不做解析，就是对数据库操作和写文件操作的一个结合封装，很简单一看便知。

作者不提倡直接使用非线程安全的 YYKVStorage ，所以封装了一个线程安全的 YYDiskCache 便于大家使用。

所以，YYDiskCache 中主要是做了一些操作磁盘缓存的线程安全机制，是基于信号量（dispatch_semaphore）来处理的。暴露的接口中类似 YYMemoryCache 的一系列方法，比如文件读写、定时任务检测内存、内存的自定义修剪。

剩余磁盘空间的限制

磁盘缓存中，多了一个如下修剪方法：

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

5

根据剩余的磁盘空间的限制进行修剪，作者确实想得很周到。_YYDiskSpaceFree()是作者写的一个 c 方法，用于获取剩余磁盘空间。

MD5 加密 key

@interface _YYLinkedMapNode : NSObject {    
      @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key;    
    id _value;    
    NSUInteger _cost;    
    NSTimeInterval _time;
}@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;
}

6

赞(1)
赏

本文由 投稿者 创作，文章地址：https://blog.isoyu.com/archives/yycache-yuanmapouxiyilanliangdian.html
采用知识共享署名4.0 国际许可协议进行许可。除注明转载/出处外，均为本站原创或翻译，转载前请务必署名。最后编辑时间为:6 月 11, 2018 at 03:49 下午

相关文章

热评文章

发表回复

[必填]

我是人？

提交后请等待三秒以免造成未提交成功和重复