源码阅读——YYCache

作者: Bestmer | 来源:发表于2019-01-30 10:43 被阅读16次

YYCache源码阅读一YYMemoryCache
iOS开发小贴：缓存
YYCache 源码剖析：一览亮点
源码阅读：YYCache
YYCache源码阅读
源码阅读——YYCache
单链表基本操作
ios三方库解析
iOS 一些框架源码解析
iOS缓存框架YYCache的学习

前言

缓存在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 来换取微乎其微的性能提升，这一切都是通过细节的追求积少成多换来的。

YYCache源码阅读一YYMemoryCache
YYCache源码阅读一（YYMemoryCache） YYCache：高性能 iOS 缓存框架。 YYCache...
iOS开发小贴：缓存
YYCache学习篇首先，YYCache GitHub地址 YYCache源码分析(一)YYCache源码分析(...
YYCache 源码剖析：一览亮点
YYCache 源码剖析：一览亮点 YYCache 源码剖析：一览亮点
源码阅读：YYCache
前言因项目需要加入了大量的数据缓存功能，在优化项目本地缓存组件的之前。研究阅读了一下YYCache这个国内最优秀...
YYCache源码阅读
模块 YYCache 这个类是底层YYMemoryCache和YYDiskCa...
源码阅读——YYCache
前言缓存在iOS开发中很常用，大到网络请求的缓存，小到各种属性的缓存。比如用户发送朋友圈时，写了很多内容，因为某...
单链表基本操作
早前读YYCache源码时候 ,写过一篇文章 : YYCache源码解读,对源码中使用的LRU算法无比钦佩,其中涉...
ios三方库解析
YYCache 源码解析 YTKNetwork 源码解析 MJRefresh 源码解析 VVeboTableVie...
iOS 一些框架源码解析
YYCache 源码解析 YTKNetwork源码解析 MJRefresh 源码解析 VVeboTableView...
iOS缓存框架YYCache的学习
先上源码链接https://github.com/ibireme/YYCache 简介 YYCache 是提供用用...