前言
缓存在iOS开发中很常用，大到网络请求的缓存，小到各种属性的缓存。比如用户发送朋友圈时，写了很多内容，因为某些操作导致APP crash，之前编辑的内容都不在了，造成非常不好的体验。之所以阅读YYCache，一是作者的编码风格非常值得学习，文档读起来和苹果官方风格一样；二是，想用这样的方式学习作者的编程思想，不断提升自己的能力。
知识储备
双向链表
-
双向链表(双链表)是链表的一种。和单链表一样，双链表也是由节点组成，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表
image - 表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；末尾节点的后继节点是表头。
OSSPinkLock(自旋锁)
- 锁的作用不过多解释，主要目的还是防止多线程时的资源抢夺
- 下面是OSSpinLock使用方式，编译会报警告，已经废弃了，OSSpinLock大家也已经不再用它了，因为它在某一些场景下已经不安全了
- 参考文章：不再安全的 OSSpinLock
OSSpinLock lock = OS_SPINLOCK_INIT;
OSSpinLockLock(&lock);
...
OSSpinLockUnlock(&lock);
pthread_mutex(互斥锁)
- 由于作者已经提出OSSpinLock不再安全，所以代码里用pthread_mutex进行了替换。
- pthread 表示 POSIX thread，定义了一组跨平台的线程相关的 API，pthread_mutex 表示互斥锁。互斥锁的实现原理与信号量非常相似，不是使用忙等，而是阻塞线程并睡眠，需要进行上下文切换。
pthread_mutexattr_t attr;
pthread_mutexattr_init(&attr);
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL); // 定义锁的属性
pthread_mutex_t mutex;
pthread_mutex_init(&mutex, &attr) // 创建锁
pthread_mutex_lock(&mutex); // 申请锁
// 临界区
pthread_mutex_unlock(&mutex); // 释放锁
- 更多参考：深入理解 iOS 开发中的锁
static inline
- 内联函数有些类似于宏。内联函数的代码会被直接嵌入在它被调用的地方，调用几次就嵌入几次，没有使用call指令。这样省去了函数调用时的一些额外开销，比如保存和恢复函数返回地址等，可以加快速度。不过调用次数多的话，会使可执行文件变大，这样会降低速度。相比起宏来说，内核开发者一般更喜欢使用内联函数。因为内联函数没有长度限制，格式限制。编译器还可以检查函数调用方式，以防止其被误用。
- static inline的内联函数，一般情况下不会产生函数本身的代码，而是全部被嵌入在被调用的地方。如果不加static，则表示该函数有可能会被其他编译单元所调用，所以一定会产生函数本身的代码。所以加了static，一般可令可执行文件变小。内核里一般见不到只用inline的情况，而都是使用static inline
__unsafe_unretained
- __unsafe_unretained和__weak一样，表示的是对象的一种弱引用关系，唯一的区别是
- __weak修饰的对象被释放后，指向对象的指针会置空，也就是指向nil,不会产生野指针；
- __unsafe_unretained修饰的对象被释放后，指针不会置空，而是变成一个野指针，那么此时如果访问这个对象的话，程序就会Crash，抛出BAD_ACCESS的异常。
- __weak对性能会有一定的消耗，使用__weak,需要检查对象是否被释放，在追踪是否被释放的时候当然需要追踪一些信息，那么此时__unsafe_unretained比__weak快，而且一个对象有大量的__weak引用对象的时候，当对象被废弃，那么此时就要遍历weak表，把表里所有的指针置空，消耗cpu资源
NSHashTable
- NSHashTable 是 NSSet 的通用版本,和 NSSet/NSMutableSet不同的是,NSHashTable具有以下特性:
- NSHashTable是可变的,没有不可变的对应类
- NSHashTable可以持有成员的弱引用
- NSHashTable可以在加入成员时进行copy操作
- NSHashTable可以存储任意的指针,通过指针来进行相等性和散列检查
- 基本用法
NSHashTable *hashTable = [NSHashTable hashTableWithOptions:NSPointerFunctionsCopyIn];
[hashTable addObject:@"hello"];
[hashTable addObject:@10];
[hashTable addObject:@"world"];
[hashTable removeObject:@"world"];
NSLog(@"Members: %@", [hashTable allObjects]);
NSMapTable
- NSMapTable是NSDictionary的通用版本,NSMapTable具有下面特性:
- NSMapTable是可变的,没有不可变的类
- NSMapTable可以持有键和值的弱引用,当键或值当中的一个被释放时,整个这一项就会被移除掉
- NSMapTable可以在加入成员时进行copy操作
- NSMapTable可以存储任意的指针,通过指针来进行相等性和散列检查
- 基本用法
NSMapTable *mapTable = [NSMapTable mapTableWithKeyOptions:NSMapTableStrongMemory valueOptions:NSMapTableWeakMemory];
[mapTable setObject:delegate forKey:@"foo"];
NSLog(@"Keys: %@", [[mapTable keyEnumerator] allObjects]);
NSPointerArray
- NSPointerArray是NSArray的通用版本,NSPointerArray具有下面特性:
- 和传统Array一样,用于有序的插入或移除
- 与传统Array不同的是,可以存储NULL,并且NULL还参与 count的计算
- 与传统Array不同的是, count可以set,如果直接set count,那么会使用NULL占位
- 可以使用weak来修饰成员
- 成员可以是所有指针类型
- 遵循 NSFastEnumeration,可以通过 for...in来进行遍历
总结
- 如果想让加入集合中的对象弱引用，除了使用上诉的三种集合外，还可以将集合中的对象使用NSValue进行包裹
- NSValue的方法valueWithNonretainedObject
YYCache总体结构
image
- 通过上图可以很清楚的发现，YYCache主要分为YYDiskCache（磁盘缓存）和YYMemoryCache（内存缓存）
- 内存缓存：提供容量小但高速的存取功能
- 磁盘缓存：提供容量大但低速的持久化存储
YYMemoryCache
- 存储的单元是_YYLinkedMapNode,除了key和value外,还存储了它的前后Node的地址_prev,_next.整个实现基于_YYLinkedMap；
- 它是一个双向链表,除了存储了字典_dic外,还存储了头结点和尾节点.
- 它实现的功能很简单,就是:有新数据了插入链表头部,访问过的数据结点移到头部,内存紧张时把尾部的结点移除.
- 就这样实现了淘汰算法(LRU).因为内存访问速度很快,锁占用的时间少,pthread_mutex
链表节点的结构图
"区块链"
// 有新数据了插入链表头部
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
NSTimeInterval now = CACurrentMediaTime();
if (node) {
_lru->_totalCost -= node->_cost;
_lru->_totalCost += cost;
node->_cost = cost;
node->_time = now;
node->_value = object;
[_lru bringNodeToHead:node];
} else {
node = [_YYLinkedMapNode new];
node->_cost = cost;
node->_time = now;
node->_key = key;
node->_value = object;
[_lru insertNodeAtHead:node];
}
// 访问过的数据，移到头部
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);
// 内存紧张时把尾部的结点移除
if (_lru->_totalCost > costLimit) {
_YYLinkedMapNode *node = [_lru removeTailNode];
if (node) [holder addObject:node];
}
// 通过设置autoTrimInterval属性去完成每隔一定时间
// 去检查countLimit，costLimit是否达到了最大限制，
// 并做相应的操作。
- (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];
//当前的时间和链表最后的节点时间的差值是否大于设定的_ageLimit值，移除大于该值得节点
[self _trimToAge:self->_ageLimit];
});
}
YYDiskCache
- 采用的是文件和sqlite数据库相互配合的方式
- 有一个参数inlineThreshold,默认20KB,小于它存数据库,大于它存文件.能获得效率的提高.
- key:path,value:cache存储在NSMapTable里.根据path获得cache,进行一系列的set,get,remove操作更底层的是YYKVStorage
- 它能直接对sqlite和文件系统进行读写.每次内存超过限制时,select key, filename, size from manifest order by last_access_time desc limit ?1
- 会根据时间排序来删除最近不常用的数据.硬盘访问的时间比较长,如果用OSSpinLockLock锁会造成CPU消耗过大,所以用的dispatch_semaphore_wait来做.
/**
If the object's data size (in bytes) is larger than this value, then object will
be stored as a file, otherwise the object will be stored in sqlite.
0 means all objects will be stored as separated files, NSUIntegerMax means all
objects will be stored in sqlite.
The default value is 20480 (20KB).
*/
YYKVStorageType type;
if (threshold == 0) {
type = YYKVStorageTypeFile;
} else if (threshold == NSUIntegerMax) {
type = YYKVStorageTypeSQLite;
} else {
type = YYKVStorageTypeMixed;
}
- 每当一个 YYDiskCache 被初始化时，其实会先到 NSMapTable 中获取对应 path 的 YYDiskCache 实例，如果获取不到才会去真正的初始化一个 YYDiskCache 实例，并且将其引用在 NSMapTable 中，这样做也会提升不少性能。
- YYDiskCache类的操作其实就是去操作持有的YYKVStorage对象
- (instancetype)initWithPath:(NSString *)path
inlineThreshold:(NSUInteger)threshold {
// 判断是否可以成功初始化，省略
...
// 先从 NSMapTable 单例中根据 path 获取 YYDiskCache 实例，如果获取到就直接返回该实例
YYDiskCache *globalCache = _YYDiskCacheGetGlobal(path);
if (globalCache) return globalCache;
// 没有获取到则初始化一个 YYDiskCache 实例
// 要想初始化一个 YYDiskCache 首先要初始化一个 YYKVStorage
YYKVStorage *kv = [[YYKVStorage alloc] initWithPath:path type:type];
if (!kv) return nil;
// 根据刚才得到的 kv 和 path 入参初始化一个 YYDiskCache 实例，代码太长省略
...
// 开启递归清理，会根据 _autoTrimInterval 对 YYDiskCache trim
[self _trimRecursively];
// 向 NSMapTable 单例注册新生成的 YYDiskCache 实例
_YYDiskCacheSetGlobal(self);
// App 生命周期通知相关代码，省略
...
return self;
}
- (void)setObject:(id<NSCoding>)object forKey:(NSString *)key {
if (!key) return;
if (!object) {
[self removeObjectForKey:key];
return;
}
//runtime 取extended_data_key的value
NSData *extendedData = [YYDiskCache getExtendedDataFromObject:object];
NSData *value = nil;
if (_customArchiveBlock) {
//block返回
value = _customArchiveBlock(object);
} else {
@try {
//序列化
value = [NSKeyedArchiver archivedDataWithRootObject:object];
}
@catch (NSException *exception) {
// nothing to do...
}
}
if (!value) return;
NSString *filename = nil;
if (_kv.type != YYKVStorageTypeSQLite) {
//长度判断这个储存方式，value.length当大于_inlineThreshold则文件储存
if (value.length > _inlineThreshold) {
//将key 进行md5加密
filename = [self _filenameForKey:key];
}
}
Lock();
[_kv saveItemWithKey:key value:value filename:filename extendedData:extendedData];
Unlock();
}
YYDiskCache使用dispatch_semaphore作为锁的原因
- dispatch_semaphore 是信号量，但当信号总量设为 1 时也可以当作锁来。
- 在没有等待情况出现时，它的性能比 pthread_mutex 还要高，但一旦有等待情况出现时，性能就会下降许多。
- 相对于 OSSpinLock 来说，它的优势在于等待时不会消耗 CPU 资源。对磁盘缓存来说，它比较合适。
最后
YYCache内部的设计思想非常精妙，对于性能上的优化也是一点一点积累出来的，比如作者对于锁的选择，异步释放缓存对象，使用 NSMapTable 单例管理的 YYDiskCache，甚至使用 CoreFoundation 来换取微乎其微的性能提升，这一切都是通过细节的追求积少成多换来的。
