YYCache简介

YYCache的结构

YYCache由YYMemoryCache(高速内存缓存)和YYDiskCache(低速磁盘缓存)两部分组成;

通常一个缓存是由内存缓存和磁盘缓存组成，内存缓存提供容量小但高速的存取功能，磁盘缓存提供大容量但低速的持久化存储

Note: 其实源码中作者用了一些技巧性的宏，例如NS_ASSUME_NONNULL_BEGIN与NS_ASSUME_NONNULL_END来通过编译器层检测入参是否为空并给予警告

简化版YYCache的代码

从代码中我们可以看到 YYCache 中持有 YYMemoryCache 与 YYDiskCache，并且对外提供了一些接口。这些接口基本都是基于 Key 和 Value 设计的，类似于 iOS 原生的字典类接口（增删改查）。

---

YYMemoryCache的解读

YYMemoryCache 是一个高速的内存缓存，用于存储键值对。它与 NSDictionary 相反，Key 被保留并且不复制。API 和性能类似于 NSCache，所有方法都是线程安全的。

YYMemoryCache 对象与 NSCache 的不同之处在于：

YYMemoryCache 使用 LRU(least-recently-used) 算法来驱逐对象；NSCache 的驱逐方式是非确定性的。

YYMemoryCache 提供 age、cost、count 三种方式控制缓存；NSCache 的控制方式是不精确的。

YYMemoryCache 可以配置为在收到内存警告或者 App 进入后台时自动逐出对象。

Note: YYMemoryCache 中的Access Methods消耗时长通常是稳定的(O(1))。

贴出几个我在读代码的时候不太弄清属性和方法

@property(readonly) NSUInteger totalCount;// 缓存对象总数

@property(readonly) NSUInteger totalCost;// 缓存对象总开销

@property NSTimeInterval autoTrimInterval; // 缓存自动清理时间间隔，默认 5s

@property BOOL releaseOnMainThread; // 是否在主线程释放对象，默认 NO，有些对象（例如 UIView/CALayer）应该在主线程释放

@property BOOL releaseAsynchronously; // 是否异步释放对象，默认 YES

YYMemoryCache 线程安全的做法

使用pthread_mutex线程锁来确保 YYMemoryCache 的线程安全。

@implementationYYMemoryCache{

pthread_mutex_t _lock;// 线程锁，旨在保证 YYMemoryCache 线程安全

_YYLinkedMap *_lru;// _YYLinkedMap，YYMemoryCache 通过它间接操作缓存对象

dispatch_queue_t_queue;// 串行队列，用于 YYMemoryCache 的 trim 操作}

注:在最初 YYMemoryCache 这里使用的锁是OSSpinLock自旋锁（详见YYCache 设计思路备注-关于锁），后面有人在 Github 向作者提issue反馈OSSpinLock不安全，经过作者的确认（详见不再安全的 OSSpinLock）最后选择用pthread_mutex替代OSSpinLock。

性能测试结果

上面是 ibireme 在确认OSSpinLock不再安全之后为了寻找替代方案做的简单性能测试，对比了一下几种能够替代OSSpinLock锁的性能。在不再安全的 OSSpinLock文末的评论中，我找到了作者使用pthread_mutex的原因。

ibireme: 苹果员工说 libobjc 里spinlock是用了一些私有方法 (mach_thread_switch)，贡献出了高线程的优先来避免优先级反转的问题，但是我翻了下 libdispatch 的源码倒是没发现相关逻辑，也可能是我忽略了什么。在我的一些测试中，OSSpinLock和dispatch_semaphore都不会产生特别明显的死锁，所以我也无法确定用dispatch_semaphore代替OSSpinLock是否正确。能够肯定的是，用pthread_mutex是安全的。

_YYLinkedMapNode与_YYLinkedMap

通过内部的_YYLinkedMapNode与_YYLinkedMap来间接的操作缓存对象。

_YYLinkedMapNode是_YYLinkedMap 中的一个节点。通常情况下我们不应该使用这个类

_YYLinkedMapNode属性:

__unsafe_unretained _YYLinkedMapNode *_prev; // __unsafe_unretained 是为了性能优化，节点被 _YYLinkedMap 的 _dic 强引用

NSUInteger_cost;// 记录开销，对应 YYMemoryCache 提供的 cost 控制NSTimeInterval_time;// 记录时间，对应 YYMemoryCache 提供的 age 控制

_YYLinkedMap是YYMemoryCache 内的一个链表。_YYLinkedMap 不是一个线程安全的类，而且它也不对参数做校验。通常情况下我们不应该使用这个类。

_YYLinkedMapNode与_YYLinkedMap是双向链表节点和双向链表。

_YYLinkedMapNode作为双向链表节点，除了基本的_prev、_next，还有键值缓存基本的_key与_value，我们可以把_YYLinkedMapNode理解为 YYMemoryCache 中的一个缓存对象

_YYLinkedMap作为由_YYLinkedMapNode节点组成的双向链表，使用CFMutableDictionaryRef _dic字典存储_YYLinkedMapNode。这样在确保_YYLinkedMapNode被强引用的同时，能够利用字典的 Hash 快速定位用户要访问的缓存对象，这样既符合了键值缓存的概念又省去了自己实现的麻烦

总得来说 YYMemoryCache 是通过使用_YYLinkedMap双向链表来操作_YYLinkedMapNode缓存对象节点的

---

LRU(least-recently-used) 算法的实现

缓存替换策略

首先 LRU 是缓存替换策略（Cache replacement policies）的一种，还有很多缓存替换策略诸如：

First In First Out (FIFO)

Last In First Out (LIFO)

Time aware Least Recently Used (TLRU)

Most Recently Used (MRU)

Pseudo-LRU (PLRU)

Random Replacement (RR)

Segmented LRU (SLRU)

Least-Frequently Used (LFU)

Least Frequent Recently Used (LFRU)

LFU with Dynamic Aging (LFUDA)

Low Inter-reference Recency Set (LIRS)

Adaptive Replacement Cache (ARC)

Clock with Adaptive Replacement (CAR)

Multi Queue (MQ) caching algorithm|Multi Queue (MQ)

Pannier: Container-based caching algorithm for compound objects

缓存替换策略是为了提高缓存命中率

缓存命中 = 用户要访问的缓存对象在高速缓存中,我们直接在高速缓存中通过Hash将其找到并返回给用户

缓存命中率 = 用户要访问的缓存对象在高速缓存中被我们访问到的概率。

缓存丢失 = 由于高速缓存数量有限（占据内存等原因），所以用户要访问的缓存对象很有可能被我们从有限的高速缓存中淘汰掉了，我们可能会将其存储于低速的磁盘缓存中（如果磁盘缓存还有资源的话），那么就要从磁盘缓存中获取该缓存对象以返回给用户，这种情况我理解为（高速）缓存未命中，即缓存丢失（并不是真的被我们丢掉了，但肯定是被我们从高速缓存淘汰掉了）。

LRU

LRU(least-recently-used) 翻译过来是“最近使用”，顾名思义这种缓存替换策略是基于用户最近访问过的缓存对象而建立。 LRU 缓存替换策略的核心思想在于：LRU 认为用户最新使用（访问）过的缓存对象为高频缓存对象，即用户很可能还会再次使用（访问）该缓存对象；而反之，用户很久之前使用（访问）过的缓存对象（期间一直没有再次访问）为低频缓存对象，即用户很可能不会再去使用（访问）该缓存对象，通常在资源不足时会先去释放低频缓存对象。

_YYLinkedMapNode与_YYLinkedMap实现 LRU

YYCache 作者通过_YYLinkedMapNode与_YYLinkedMap双向链表实现 LRU 缓存替换策略的思路:

双向链表中有头结点和尾节点：

头结点 = 链表中用户最近一次使用（访问）的缓存对象节点，MRU。(more-recently-used)

尾节点 = 链表中用户已经很久没有再次使用（访问）的缓存对象节点，LRU。(least-recently-used)

如何让头结点和尾节点指向我们想指向的缓存对象节点？我们结合代码来看：

1>在用户使用（访问）时更新缓存节点信息，并将其移动至双向链表头结点。

代码注释

2>在用户设置缓存对象时，判断入参 key 对应的缓存对象节点是否存在？存在则更新缓存对象节点并将节点移动至链表头结点；不存在则根据入参生成新的缓存对象节点并插入链表表头。

代码截图

3>在资源不足时，从双线链表的尾节点（LRU）开始清理缓存，释放资源。

代码截图

上面3>涉及到的异步释放技巧的解释:

这个技巧 ibireme 在他的另一篇文章iOS 保持界面流畅的技巧中有提及：

Note: 对象的销毁虽然消耗资源不多，但累积起来也是不容忽视的。通常当容器类持有大量对象时，其销毁时的资源消耗就非常明显。同样的，如果对象可以放到后台线程去释放，那就挪到后台线程去。这里有个小 Tip：把对象捕获到 block 中，然后扔到后台队列去随便发送个消息以避免编译器警告，就可以让对象在后台线程销毁了。

// 静态内联 dispatch_queue_tstaticinlinedispatch_queue_tYYMemoryCacheGetReleaseQueue() {returndispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_LOW,0);}

在源码中可以看到 YYMemoryCacheGetReleaseQueue 是一个低优先级DISPATCH_QUEUE_PRIORITY_LOW队列，猜测这样设计的原因是可以让 iOS 在系统相对空闲时再来异步释放缓存对象。

---

YYDiskCache 细节剖析

YYDiskCache 是一个线程安全的磁盘缓存，用于存储由 SQLite 和文件系统支持的键值对（类似于 NSURLCache 的磁盘缓存）。

YYDiskCache 具有以下功能：

它使用 LRU(least-recently-used) 来删除对象。

支持按 cost，count 和 age 进行控制。

它可以被配置为当没有可用的磁盘空间时自动驱逐缓存对象。

它可以自动抉择每个缓存对象的存储类型（sqlite/file）以便提供更好的性能表现。

YYDiskCache 是基于 sqlite 和 file 来做的磁盘缓存，我们的缓存对象可以自由的选择存储类型，下面简单对比一下：

sqlite: 对于小数据（例如 NSNumber）的存取效率明显高于 file。

file: 对于较大数据（例如高质量图片）的存取效率优于 sqlite。

所以 YYDiskCache 使用两者配合，灵活的存储以提高性能。

NSMapTable

NSMapTable 是类似于字典的集合，但具有更广泛的可用内存语义。NSMapTable 是 iOS6 之后引入的类，它基于 NSDictionary 建模，但是具有以下差异：

键/值可以选择 “weakly” 持有，以便于在回收其中一个对象时删除对应条目。

它可以包含任意指针（其内容不被约束为对象）。

您可以将 NSMapTable 实例配置为对任意指针进行操作，而不仅仅是对象。

Note: 配置映射表时，请注意，只有 NSMapTableOptions 中列出的选项才能保证其余的 API 能够正常工作，包括复制，归档和快速枚举。 虽然其他 NSPointerFunctions 选项用于某些配置，例如持有任意指针，但并不是所有选项的组合都有效。使用某些组合，NSMapTableOptions 可能无法正常工作，甚至可能无法正确初始化。

更多信息详见NSMapTable 官方文档。

YYDiskCache 使用 dispatch_semaphore 保障 NSMapTable 线程安全

在YYCache 设计思路中找到了作者使用 dispatch_semaphore 作为 YYDiskCache 锁的原因：

dispatch_semaphore 是信号量，但当信号总量设为 1 时也可以当作锁来。在没有等待情况出现时，它的性能比 pthread_mutex 还要高，但一旦有等待情况出现时，性能就会下降许多。相对于 OSSpinLock 来说，它的优势在于等待时不会消耗 CPU 资源。对磁盘缓存来说，它比较合适。

与 YYMemoryCache 相对应的，YYDiskCache 也不会直接操作缓存对象（sqlite/file），而是通过 YYKVStorage 来间接的操作缓存对象。

YYKVStorage 性能优化细节

上文说到 YYKVStorage 可以基于 SQLite 和文件系统做磁盘存储，这里再提一些我阅读源码发现到的有趣细节：

@implementationYYKVStorage{

...CFMutableDictionaryRef_dbStmtCache;// 焦点集中在这里...

}

可以看到CFMutableDictionaryRef _dbStmtCache;是 YYKVStorage 中的私有成员，它是一个可变字典充当着 sqlite3_stmt 缓存的角色。

- (sqlite3_stmt *)_dbPrepareStmt:(NSString*)sql 该方法可以省去一些重复生成 sqlite3_stmt 的开销。

sqlite3_stmt: 该对象的实例表示已经编译成二进制形式并准备执行的单个 SQL 语句

更多关于 SQLite 的信息请点击SQLite 官方文档查阅。

---

优秀的缓存应该具备哪些特质

内存缓存和磁盘缓存

线程安全

缓存控制

缓存替换策略

缓存命中率

性能

YYCache 源码中是如何体现这些特质的。

1>内存缓存和磁盘缓存

YYCache 是由内存缓存 YYMemoryCache 与磁盘缓存 YYDiskCache 相互配合组成的，内存缓存提供容量小但高速的存取功能，磁盘缓存提供大容量但低速的持久化存储。这样的设计支持用户在缓存不同对象时都能够有很好的体验。

在 YYCache 中使用接口访问缓存对象时，会先去尝试从内存缓存 YYMemoryCache 中访问，如果访问不到（没有使用该 key 缓存过对象或者该对象已经从容量有限的 YYMemoryCache 中淘汰掉）才会去从 YYDiskCache 访问，如果访问到（表示之前确实使用该 key 缓存过对象，该对象已经从容量有限的 YYMemoryCache 中淘汰掉成立）会先在 YYMemoryCache 中更新一次该缓存对象的访问信息之后才返回给接口。

2>线程安全

如果说 YYCache 这个类是一个纯逻辑层的缓存类（指 YYCache 的接口实现全部是调用其他类完成），那么 YYMemoryCache 与 YYDiskCache 还是做了一些事情的（并没有 YYCache 当甩手掌柜那么轻松），其中最显而易见的就是 YYMemoryCache 与 YYDiskCache 为 YYCache 保证了线程安全。

YYMemoryCache 使用了pthread_mutex线程锁来确保线程安全，而 YYDiskCache 则选择了更适合它的dispatch_semaphore，上文已经给出了作者选择这些锁的原因。

3>缓存控制

YYCache 提供了三种控制维度，分别是：cost、count、age。这已经满足了绝大多数开发者的需求，我们在自己设计缓存时也可以根据自己的使用环境提供合适的控制方式。

4>缓存替换策略

在上文解析 YYCache 源码的时候，介绍了缓存替换策略的概念并且列举了很多经典的策略。YYCache 使用了双向链表（_YYLinkedMapNode与_YYLinkedMap）实现了 LRU(least-recently-used) 策略，旨在提高 YYCache 的缓存命中率。

5>缓存命中率

这一概念是在上文解析_YYLinkedMapNode与_YYLinkedMap小节介绍的，我们在自己设计缓存时不一定非要使用 LRU 策略，可以根据我们的实际使用环境选择最适合我们自己的缓存替换策略。

6>性能

其实性能这个东西是隐而不见的，又是到处可见的（笑）。它从我们最开始设计一个缓存架构时就被带入，一直到我们具体的实现细节中慢慢成形，最后成为了我们设计出来的缓存优秀与否的决定性因素。

上文中剖析了太多 YYCache 中对于性能提升的实现细节：

异步释放缓存对象

锁的选择

使用 NSMapTable 单例管理的 YYDiskCache

YYKVStorage 中的_dbStmtCache

甚至使用 CoreFoundation 来换取微乎其微的性能提升

读完YYCache源码看到这个还不错,就摘下来了