转载请联系作者获取授权，并标明文章作者，谢谢!
iOS开发中经常会遇到数据本地化或者是图片缓存到本地，本文将会解读一个比较优秀的数据缓存开源库——YYCache（作者：ibireme），从源码上分析YYCache中优秀的缓存数据结构和LRU缓存淘汰算法。
目录
YYCache的源码结构
YYCache
YYDiskCache
YYKVStorage
YYMemoryCache
YYCache的存储数据结构（核心）
Memory
链表节点模型
存储流程分析
Disk
数据库模型对象
存储流程分析
LRU缓存淘汰算法实现
Memory-LRU
Disk-LRU
总结
YYCache的源码结构
YYCache
代码对外的接口，提供大部分的对外接口，使用者拿该类中的接口就可以使用，内部实现基本上是调用后面几个类中的接口。
初始化方法：
- (instancetype)initWithName:(NSString *)name;
- (instancetype)initWithPath:(NSString *)path;
object set and get:
//是否包含以这个key存储的对象，同步接口阻塞线程
- (BOOL)containsObjectForKey:(NSString *)key;
//是否包含以这个key存储的对象，异步回调接口不阻塞线程
- (void)containsObjectForKey:(NSString *)key withBlock:(nullable void(^)(NSString *key, BOOL contains))block;
//下面这些方法见名知意
- (nullable id<NSCoding>)objectForKey:(NSString *)key;
- (void)objectForKey:(NSString *)key withBlock:(nullable void(^)(NSString *key, id<NSCoding> object))block;
- (void)setObject:(nullable id<NSCoding>)object forKey:(NSString *)key;
- (void)setObject:(nullable id<NSCoding>)object forKey:(NSString *)key withBlock:(nullable void(^)(void))block;
- (void)removeObjectForKey:(NSString *)key;
*key))block;
//带有删除进度的删除接口
- (void)removeAllObjectsWithProgressBlock:(nullable void(^)(int removedCount, int totalCount))progress
endBlock:(nullable void(^)(BOOL error))end;
通过name初始化的对象会默认将缓存路径设置为Document目录下Cache路径下名字为name的文件夹。第二个方法见名知意直接以path作为缓存路径。
YYDiskCache
源码中负责磁盘缓存的类，细化为磁盘文件缓存和磁盘数据库缓存。里面大多也是提供相应接口，方法实现大多是调用YYKVStorage中的接口。
初始化方法：
- (nullable instancetype)initWithPath:(NSString *)path;
属性：
//磁盘存储方式阀值。根据作者（ibireme）的测试，当存储的数据大于某个阀值时直接存储到文件会比存储到数据库效率高，该属性默认阀值是20480(20kb)，手动设置后则会根据这个阀值决定数据存储位置
@property (readonly) NSUInteger inlineThreshold;
//自定义数据编解码方式，当对数据进行编解码时会先调用该block如果不为空则使用自定义的编解码方式，默认使用NSKeyedArchiver编解码
@property (nullable, copy) NSData *(^customArchiveBlock)(id object);
@property (nullable, copy) id (^customUnarchiveBlock)(NSData *data);
//自定义key的存储名字，不设置默认为将key进行一次md5加密
@property (nullable, copy) NSString *(^customFileNameBlock)(NSString *key);
//下面LRU淘汰条件，最大存储空间，最大存储数量，最长存储时间，磁盘最小剩余空间
@property NSUInteger costLimit;
@property NSUInteger countLimit;
@property NSTimeInterval ageLimit;
//定时检查这些限制的定时器执行时间
@property NSTimeInterval autoTrimInterval;
@property NSUInteger freeDiskSpaceLimit;
后面的数据get和set方法用法基本和YYCache类中一致，额外添加了数据附加数据：
+ (void)setExtendedData:(nullable NSData *)extendedData toObject:(id)object;
+ (nullable NSData *)getExtendedDataFromObject:(id)object;
YYKVStorage
YYDiskCache类中的接口实现，内部实现了磁盘文件存储和磁盘数据库存储。
里面的内部类：
//数据库模型对象
@interface YYKVStorageItem : NSObject
//数据存储方式
//文件：YYKVStorageTypeFile
//数据库：YYKVStorageTypeSQLite
//自适应：YYKVStorageTypeMixed
@property (nonatomic, readonly) YYKVStorageType type;
下面就是一些根据key的get和set方法。这里不做过多解释，后面会直接分析内部实现。
YYMemoryCache
YYCache的内存存储对象，主要实现了内存存储数据。里面的LRU淘汰条件和YYDiskCache一致，和YYDiskCache区别在于多了一个最小剩余空间的限制。由于是内存缓存所以需要监听内存是否过大导致占用过多CPU资源。object的set和get方法和YYDiskCache中使用方法一致。
//当内存警告时是否删除所有内存中的缓存数据
@property BOOL shouldRemoveAllObjectsOnMemoryWarning;
//当App进入后台时是否删除所有内存中的缓存数据
@property BOOL shouldRemoveAllObjectsWhenEnteringBackground;
//内存警告时的回调
@property (nullable, copy) void(^didReceiveMemoryWarningBlock)(YYMemoryCache *cache);
//进入后台时的回调
@property (nullable, copy) void(^didEnterBackgroundBlock)(YYMemoryCache *cache);
//是否在主线程释放对象
@property BOOL releaseOnMainThread;
YYCache的存储数据结构（核心）
下面我们按照Memory - File - Storage的顺序来分析源码中的数据结构和实现代码。LRU算法将在后面解读。
Memory
内存存储中主要以双向链表+CFDictionary的方式来存储，利用链表的有序性来存储数据的存储顺序，LRU算法也是通过限制条件从链表的尾部开始删除。利用字典的key-value读取数据快的特性用来快速读写数据。
链表节点模型：
@interface _YYLinkedMapNode : NSObject {
@package
//前置指针
__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
//后置指针
__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
//存储key
id _key;
//存储数据
id _value;
//数据大小
NSUInteger _cost;
//数据最后一次读取时间
NSTimeInterval _time;
}
下面是双向链表类，里面实现了数据的get和set
@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;
}
//下面的方法见名知意，这里不做过多翻译
/// Insert a node at head and update the total cost.
/// Node and node.key should not be nil.
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
/// Bring a inner node to header.
/// Node should already inside the dic.
- (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;
YYMemoryCache,初始化一个双向链表，一个线程安全锁和一个异步队列
pthread_mutex_t _lock;
_YYLinkedMap *_lru;
dispatch_queue_t _queue;
存储流程分析
首先调用的对外接口YYCache -
- (void)setObject:(nullable id<NSCoding>)object forKey:(NSString *)key
此时YYChahe类会现在内存中查找如果有则返回，如果没有再去磁盘中找，如果找到了则返回并将数据存储到内存中，毕竟内存的存取速度要快几倍于磁盘的存取速度。代码如下：
- (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;
}
内存中存数据的方法：YYMemoryCache -
- (void)setObject:(id)object forKey:(id)key
该方法中首先在字典中get一下，如果有则将数据替换，并将数据的_time属性换成当前时间，对应的链表节点也将移到链表头部，代表该数据是最近被读取过的。
如果没有则创建新的链表节点存储到头部。
下面是将链表节点移动到头部的方法，添加新节点到头部的方法：
[_lru bringNodeToHead: node]
[_lru insertNodeAtHead:node]
每次存完数据会通过LRU淘汰条件判断一下是否需要淘汰数据：
if (_lru->_totalCost > _costLimit)
if (_lru->_totalCount > _countLimit)
之后会根据_releaseAsynchronously属性和_releaseOnMainThread属性来决定淘汰掉的节点数据在哪个线程释放：
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
});
}
内存中取数据的方法：
YYMemoryCache -
- (id)objectForKey:(id)key
该方法会从数据字典中找到对应的value，并将链表中该节点的时间换成最新且移动到链表头部。
Disk
磁盘缓存分为两部分：文件缓存和数据库缓存。根据前面提到的阀值属性：inlineThreshold来判定数据应该存储到哪里。
首先YYDiskCache变量创建于YYCache的构造方法里，如果YYCache变量被释放则会导致YYDiskCache变量也被释放则无法执行后续的数据存取操作，所以源码中采用一个static的内存来将YYDiskCache变量存储起来：
static NSMapTable *_globalInstances;
static dispatch_semaphore_t _globalInstancesLock;
_globalInstancesLock是保证线程安全的信号量。
初始化方法和_globalInstances的创建不再解释直接看源码很容易理解，YYDiskCache中只有三个变量：
//负责操作数据的类，里面实现了全部的数据读写方法和LRU淘汰算法
YYKVStorage *_kv;
//线程安全的信号量
dispatch_semaphore_t _lock;
//异步线程队列
dispatch_queue_t _queue;
数据库模型对象：
@interface YYKVStorageItem : NSObject
@property (nonatomic, strong) NSString *key; ///< key
@property (nonatomic, strong) NSData *value; ///< value
@property (nullable, nonatomic, strong) NSString *filename; ///< filename (nil if inline)
@property (nonatomic) int size; ///< value's size in bytes
@property (nonatomic) int modTime; ///< modification unix timestamp
@property (nonatomic) int accessTime; ///< last access unix timestamp
@property (nullable, nonatomic, strong) NSData *extendedData; ///< extended data (nil if no extended data)
@end
下面解读存取流程。
存储流程分析
当数据来的时候首先判断数据的大小和_inlineThreshold阀值比较如果大于该阀值则表示数据要存储到文件中此时用一个变量filename代表存储文件的名字，反之该变量为nil。YYDiskCache -
- (void)setObject:(id<NSCoding>)object forKey:(NSString *)key
if (value.length > _inlineThreshold) {
filename = [self _filenameForKey:key];
}
之后会调用YYKVStorage中的方法来存数据 -
[_kv saveItemWithKey:key value:value filename:filename extendedData:extendedData]
进入到对应方法中会发现判断failName是否为空，如果不为空说明需要存储到文件中，此时会调用_fileWriteWithName方法存储到文件。之后会还会存储到数据库中，但是只存储除了数据以外的其他部分。便于以后读取存储到文件中数据的属性（size，最后读取时间，failName等）。
取数据时会先从数据库中获取到item，因为无论是存储到文件中或者数据库中的文件，它们的基本信息（key，fileName，accessTime，size...）都存储到了数据库中,拿到了这些信息就可以拿到数据。调用方法：getItemForKey该方法会刷新数据库中的accessTime字段代表该数据最近被读取过。而后面的LRU算法也是根据该字段来淘汰数据的。
拿到item后根据fileName字段判断数据存在哪里取出来object进行解码。
取item代码：
YYKVStorageItem *item = [self _dbGetItemWithKey:key excludeInlineData:NO];
if (item) {
[self _dbUpdateAccessTimeWithKey:key];
if (item.filename) {
item.value = [self _fileReadWithName:item.filename];
if (!item.value) {
[self _dbDeleteItemWithKey:key];
item = nil;
}
}
}
解码：
if (_customUnarchiveBlock) {
object = _customUnarchiveBlock(item.value);
} else {
@try {
object = [NSKeyedUnarchiver unarchiveObjectWithData:item.value];
}
@catch (NSException *exception) {
// nothing to do...
}
}
之后判断是否有附加数据如果有则通过runtime的方法保存起来：objc_setAssociatedObject。
类中数据库采用的是iOS内置的sqlite3使用起来比较麻烦，可以将数据库部分替换成FMDB等第三方库。
LRU缓存淘汰算法实现
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
下面将分为Memory和Disk两部分解析LRU的实现：
Memory-LRU
在YYMemoryCache对象创建的时候会调用下面方法：
- (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方法就是根据空间大小，存储数量，存储时间来淘汰数据的方法。如下代码：
- (void)_trimInBackground {
dispatch_async(_queue, ^{
[self _trimToCost:self->_costLimit];
[self _trimToCount:self->_countLimit];
[self _trimToAge:self->_ageLimit];
});
}
下面我们只分析根据空间大小淘汰数据的方法，其他的类似，_trimToCost方法：
首先数据读写需要添加线程安全锁：
pthread_mutex_lock(&_lock);
pthread_mutex_unlock(&_lock);
如果传递过来的_costLimit为0则代表全部清除直接调用
[_lru removeAll]方法清空内存缓存数据。否则while循环移除链表尾节点，直到总存储大小小于_costLimit。代码如下：
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
}
}
其中removeTailNode方法就是移除链表尾节点并将数据从字典中移除。
内存中的LRU算法至此完成，总结下来就是每次读取数据时该数据都会移动到链表的头部，所以链表的尾节点就是相对最近最少使用的数据。而开头的无限递归方法_trimRecursively就是定期淘汰最近最少使用过的数据。
Disk-LRU
上面介绍了Memory中根据链表存储顺序决定了先淘汰哪个数据，而Disk中则没有有序的数据结构来存储，所以上文讲解Disk存储的时候提到了所有要存到磁盘的数据（无论是存到文件中或者数据库中）都会将基本信息存到数据库中，其中包括accessTime字段：最后读写该数据的时间，所以我们可以根据该字段判断哪个数据是最近最少使用过的数据。使用到的sql语句这里不做过多解释。
YYDiskCache类中和YYMemoryCache类中使用LRU的用法基本一致都是在构造方法中异步开启一个无限循环执行的方法-_trimRecursively,该方法会每隔一段时间进行数据检查淘汰：
- (void)_trimInBackground {
__weak typeof(self) _self = self;
dispatch_async(_queue, ^{
__strong typeof(_self) self = _self;
if (!self) return;
Lock();
[self _trimToCost:self.costLimit];
[self _trimToCount:self.countLimit];
[self _trimToAge:self.ageLimit];
[self _trimToFreeDiskSpace:self.freeDiskSpaceLimit];
Unlock();
});
}
下面只讲解一下_trimToCost:方法的实现，其他的条件检查类似。
首先根据方法：[self _dbGetTotalItemSize]获取到当前所存储的数据总大小: total，该方法直接将数据库中所有的size字段累加即可，因为无论存储到哪里的数据，size属性都会保存在数据库中。将total和maxSize进行比较。
然后写一个do-while循环，循环的跳出条件就是当total < maxSize。
根据方法：- (NSMutableArray *)_dbGetItemSizeInfoOrderByTimeAscWithLimit:(int)count取出数据库中accessTime字段最小的count条数据，sql语句如下：
NSString *sql = @"select key, filename, size from manifest order by last_access_time asc limit ?1;";
该方法返回一个YYKVStorageItem对象数组，根据YYKVStorageItem的fileName属性可以直到数据存储的位置，如果fileName不为nil则存储到文件中调用：- (BOOL)_fileDeleteWithName:(NSString *)filename方法从文件中删除，在调用- (BOOL)_dbDeleteItemWithKey:(NSString *)key方法从数据库中删除，如果只存储到数据库中则直接调用后者方法即可。一次根据存储大小条件的数据淘汰完成。
至此LRU算法解读完毕，我们可以发现想要实现完善的LRU良好的数据结构和内存管理是必须的，良好的数据结构可以提升数据读写效率，良好的内存管理可以最大化节省CPU和磁盘资源并防止出错。
总结
首先由衷的感谢和敬佩作者：ibireme，给大家分享这么优秀的源码，用过YYKit的开发者应该对ibireme不陌生，他优秀的编程思想和代码设计理念值得我们学习。
本文讲解了ibireme的开源代码YYCache，笔者从中主要学习到数据的存储结构和里面对于线程队列的处理，以及LRU淘汰算法。如果想做iOS数据缓存YYCache是一个不错的选择。关于YYCache的用法大家可以参考这篇文章：YYCache的使用
作者：Olivia_Zqy
