YYCache是大神ibireme开源的一个高性能 iOS 缓存框架，是属于鼎鼎大名的YYKit组件之一。代码风格简洁清晰，作为本人开始通读优秀开源代码颇为合适。

项目架构和组件成员划分

架构图

借用JK大神的图：

组件成员职能

YYCache: 整个框架的最外层接口，调用了YYMemoryCache和YYDiskCache的方法。
YYMemoryCache: 负责容量较小，速度较快的内存缓存组件，线程安全。
_YYLinkedMap: 实现内存缓存的双链表类。使用者通常不会直接使用到。
_YYLinkedMapNode: 双链表节点类。使用者通常不会直接使用到。
YYDiskCache: 负责容量较大的磁盘缓存组件，线程安全。类似于NSURLCache的磁盘缓存。
YYKVStorage: 基于sqlite和文件系统实现储存的底层实现类。使用者通常不会直接使用到。
YYKVStorageItem: 服务于YYKVStorage，用来储存键值对和元数据。使用者通常不会直接使用到。

代码解析

YYCache

关键实现代码：

//根据参数key返回是否有缓存
- (BOOL)containsObjectForKey:(NSString *)key {
    return [_memoryCache containsObjectForKey:key] || [_diskCache containsObjectForKey:key];
}

//根据参数key返回缓存的value
- (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;
}

//设置指定key以缓存value
- (void)setObject:(id<NSCoding>)object forKey:(NSString *)key {
    //先存入内存缓存，在写入磁盘缓存
    [_memoryCache setObject:object forKey:key];
    [_diskCache setObject:object forKey:key];
}

//根据key清除指定缓存
- (void)removeObjectForKey:(NSString *)key {
    //先清除内存缓存，在清除磁盘缓存
    [_memoryCache removeObjectForKey:key];
    [_diskCache removeObjectForKey:key];
}

//清空缓存
- (void)removeAllObjects {
    [_memoryCache removeAllObjects];
    [_diskCache removeAllObjects];
}

以上源码可以看出，YYCache所有缓存写入、查询和清除机制都是先内存缓存，在磁盘缓存，以加快读取速度。

YYMemoryCache

API和功能都和NSCache相似，但YYMemoryCache和NSCache有几个不同的地方：

1. 利用LRU(least-recently-used)机制清除缓存,而NSCache的机制是不确定性的；
2. YYMemoryCache可以按照cost,count和age三个维度清除缓存，而后者的清除限制不是很精确；
3. 可以配置当收到内存警告或者App进入后台的时候，可以自动清除缓存。

LRU缓存机制是指，每当有新的缓存加入，就会把它放在一个表的表头，旧的缓存旧会慢慢靠后。经常访问的缓存会慢慢累积在前面，而不经常访问的会沉淀到后面。当清除缓存时，优先清除靠后的缓存，这样就可以确保缓存是经常访问的，从而提升读取速度。

YYMemoryCache种使用了双链表实现LRU算法，_YYLinkedMap就是这个双向链表类，_YYLinkedMapNode是链表内的节点类。

_YYLinkedMapNode

_YYLinkedMapNode可以被看做是对某个缓存的封装：它包含了该节点上一个和下一个节点的指针，以及缓存的key和对应的值（对象），还有该缓存的开销和访问时间。

@interface _YYLinkedMapNode : NSObject {
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
    __unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
    id _key; //缓存key
    id _value; //key对应的value
    NSUInteger _cost; //缓存开销
    NSTimeInterval _time; //访问时间
}
@end

@implementation _YYLinkedMapNode
@end

_YYLinkedMap

@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;
}

@end

二者关系图：

_YYLinkedMap几个方法的实现
在链表头部插入某节点

- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
    //设置该node的值
    CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
    _totalCost += node->_cost; //增加总开销
    _totalCount++; //总数加1
    if (_head) { //如果存在头部节点
        node->_next = _head; //将这个节点的_next指向头部节点
        _head->_prev = node; //头部节点的_prev指向这个节点
        _head = node; //头部节点指向这个节点
    } else { //链表为空
        _head = _tail = node;
    }
}

将链表内部的某个节点移到链表头部

- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
    if (_head == node) return; //头部节点就是这个节点，返回

    //把这个节点拿出来，前后的节点对接好
    if (_tail == node) { //如果是尾部节点
        _tail = node->_prev;  //尾部节点指向节点的上一个
        _tail->_next = nil;  //然后_next置空
    } else {
        node->_next->_prev = node->_prev; //前面的接到后面
        node->_prev->_next = node->_next; //后面的接到前面
    }
    //将这个节点放在头部
    node->_next = _head;
    node->_prev = nil;
    _head->_prev = node;
    _head = node;
}

移除链表中的某个节点：

- (void)removeNode:(_YYLinkedMapNode *)node {
    //除去该node的键对应的值
    CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
    _totalCost -= node->_cost; //减少开销
    _totalCount--; //总数减一
    //1. 将该node的头指针指向的节点赋给其尾指针指向的节点的头指针
    if (node->_next) node->_next->_prev = node->_prev;
    //2. 将该node的尾指针指向的节点赋给其头指针指向的节点的尾指针
    if (node->_prev) node->_prev->_next = node->_next;
    //3. 如果该node就是链表的头结点，则将该node的尾部指针指向的节点赋给链表的头节点（第二变成了第一）
    if (_head == node) _head = node->_next;
    //4. 如果该node就是链表的尾节点，则将该node的头部指针指向的节点赋给链表的尾节点（倒数第二变成了倒数第一）
    if (_tail == node) _tail = node->_prev;
}

了解完底层的算法后，在了解一下YYMemoryCache的几个主要API实现

写入某个缓存对象，并存入缓存开销：

- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
    if (!key) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }
    pthread_mutex_lock(&_lock);
    _YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
    NSTimeInterval now = CACurrentMediaTime();
    if (node) { //如果已经存，则更新node的value,cost,time,并放到头部
        _lru->_totalCost -= node->_cost;
        _lru->_totalCost += cost;
        node->_cost = cost;
        node->_time = now;
        node->_value = object;
        [_lru bringNodeToHead:node];
    } else { //如果不存在，则新建一个node，设置cost,time,key,value，并插入到头部
        node = [_YYLinkedMapNode new];
        node->_cost = cost;
        node->_time = now;
        node->_key = key;
        node->_value = object;
        [_lru insertNodeAtHead:node];
    }
    if (_lru->_totalCost > _costLimit) {
        dispatch_async(_queue, ^{
            [self trimToCost:_costLimit];
        });
    }
    //如果超过totalCount,则从尾部删除缓存
    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);
}

缓存清除方法

// =========== 缓存清理接口 =========== 
//清理缓存到指定个数
- (void)trimToCount:(NSUInteger)count;

//清理缓存到指定开销
- (void)trimToCost:(NSUInteger)cost;

//清理缓存时间小于指定时间的缓存
- (void)trimToAge:(NSTimeInterval)age;

自动清除缓存方法

//递归清理，相隔时间为_autoTrimInterval 默认5.0，在初始化之后立即执行
- (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];
    });
}
//清理所有不符合限制的缓存，顺序为：cost，count，age
- (void)_trimInBackground {
    dispatch_async(_queue, ^{
        [self _trimToCost:self->_costLimit];
        [self _trimToCount:self->_countLimit];
        [self _trimToAge:self->_ageLimit];
    });
}

YYDiskCache

YYDiskCache 是一个线程安全，通过用sqlite和文件系统备份数据的缓存模块。有一下功能特点：

1. 使用LRU算法清除缓存；
2. 可以通过开销，数量和时间三个维度控制缓存；
3. 可以配置当没有磁盘空间时自动清理缓存；
4. 能自动决定使用哪种方法缓存每一个数据以达到更高的效率。

首先看缓存的方式有三种：

typedef NS_ENUM(NSUInteger, YYKVStorageType) {

    /// 以文件的形式储存数据
    YYKVStorageTypeFile = 0,

    /// 以sqlite元数据的形式储存
    YYKVStorageTypeSQLite = 1,

    /// 混合上面两种
    YYKVStorageTypeMixed = 2,
};

作者建议如果储存大量的小数据（例如通讯录），用YYKVStorageTypeSQLite的方式会有更好的表现。如果储存大文件（例如图片缓存），用YYKVStorageTypeFile会更好。

初始化方法：

- (instancetype)initWithPath:(NSString *)path {
    return [self initWithPath:path inlineThreshold:1024 * 20]; // 20KB
}

- (instancetype)initWithPath:(NSString *)path
             inlineThreshold:(NSUInteger)threshold {
    self = [super init];
    if (!self) return nil;

    YYDiskCache *globalCache = _YYDiskCacheGetGlobal(path);
    if (globalCache) return globalCache;

    YYKVStorageType type;
    if (threshold == 0) {
        type = YYKVStorageTypeFile;
    } else if (threshold == NSUIntegerMax) {
        type = YYKVStorageTypeSQLite;
    } else {
        type = YYKVStorageTypeMixed;
    }

    YYKVStorage *kv = [[YYKVStorage alloc] initWithPath:path type:type];
    if (!kv) return nil;

    _kv = kv;
    _path = path;
    _lock = dispatch_semaphore_create(1);
    _queue = dispatch_queue_create("com.ibireme.cache.disk", DISPATCH_QUEUE_CONCURRENT);
    _inlineThreshold = threshold;
    _countLimit = NSUIntegerMax;
    _costLimit = NSUIntegerMax;
    _ageLimit = DBL_MAX;
    _freeDiskSpaceLimit = 0;
    _autoTrimInterval = 60;

    [self _trimRecursively];
    _YYDiskCacheSetGlobal(self);

    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(_appWillBeTerminated) name:UIApplicationWillTerminateNotification object:nil];
    return self;
}

参数inlineThreshold的默认值是20480(20K）,即使用文件+数据库的形式储存。至于为什么是20k，是因为单条数据小于20k的时候，SQLite读取性能比文件高，超过20k，则文件速度更快。以下是作者原话：

iPhone 6 64G 下，SQLite 写入性能比直接写文件要高，但读取性能取决于数据大小：当单条数据小于 20K 时，数据越小 SQLite 读取性能越高；单条数据大于 20K 时，直接写为文件速度会更快一些。这和 SQLite 官网的描述基本一致。另外，直接从官网下载最新的 SQLite 源码编译，会比 iOS 系统自带的 sqlite3.dylib 性能要高很多。基于 SQLite 的这种表现，磁盘缓存最好是把 SQLite 和文件存储结合起来：key-value 元数据保存在 SQLite 中，而 value 数据则根据大小不同选择 SQLite 或文件存储。

另外作者提到NSURLCache 选定的数据大小的阈值是 16K。

在来看setObject方法

- (void)setObject:(id<NSCoding>)object forKey:(NSString *)key {
    if (!key) return;
    if (!object) {
        [self removeObjectForKey:key];
        return;
    }

    NSData *extendedData = [YYDiskCache getExtendedDataFromObject:object];
    NSData *value = nil;
    if (_customArchiveBlock) {
        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) {
        if (value.length > _inlineThreshold) {
            filename = [self _filenameForKey:key];
        }
    }

    Lock();
    [_kv saveItemWithKey:key value:value filename:filename extendedData:extendedData];
    Unlock();
}

就是根据数据的大小判读储存的方式，最后实现YYKVStorage的方法（saveItemWithKey:value:filename:extendedData:）。

YYKVStorage

YYKVStorage实例负责保存和管理所有磁盘缓存。和YYMemoryCache里面的_YYLinkedMap将缓存封装成节点类_YYLinkedMapNode类似，YYKVStorage也将某个单独的磁盘缓存封装成了一个类，这个类就是YYKVStorageItem，它保存了某个缓存所对应的一些信息(key, value, 文件名，大小等等)：

@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

既然在这里将缓存封装成了YYKVStorageItem实例，那么作为缓存的管理者，YYKVStorage就必然有操作YYKVStorageItem的接口了,关键是写入缓存的接口：

- (BOOL)saveItem:(YYKVStorageItem *)item {
    return [self saveItemWithKey:item.key value:item.value filename:item.filename extendedData:item.extendedData];
}

- (BOOL)saveItemWithKey:(NSString *)key value:(NSData *)value {
    return [self saveItemWithKey:key value:value filename:nil extendedData:nil];
}

- (BOOL)saveItemWithKey:(NSString *)key value:(NSData *)value filename:(NSString *)filename extendedData:(NSData *)extendedData {
    if (key.length == 0 || value.length == 0) return NO;
    if (_type == YYKVStorageTypeFile && filename.length == 0) {
        return NO;
    }

    if (filename.length) {
        if (![self _fileWriteWithName:filename data:value]) {
            return NO;
        }
        if (![self _dbSaveWithKey:key value:value fileName:filename extendedData:extendedData]) {
            [self _fileDeleteWithName:filename];
            return NO;
        }
        return YES;
    } else {
        if (_type != YYKVStorageTypeSQLite) {
            NSString *filename = [self _dbGetFilenameWithKey:key];
            if (filename) {
                [self _fileDeleteWithName:filename];
            }
        }
        return [self _dbSaveWithKey:key value:value fileName:nil extendedData:extendedData];
    }
}

1. 判断key和value是否符合要求；
2. 判断是文件储存的时候文件名是否为空，否则返回No；
3. 根据文件名字符串是否为空;
4. 不是空的话，将数据写入文件，再将除value以外的所有信息(key,filename,value的长度，访问和修改时间和extededData)存在SQLite中;
   5.如果为空的话，首先判断是不是SQLite形式，是的话，将所有信息存到SQLite，否则删除写入的缓存文件。

关于第三点操作，源码如下：

- (BOOL)_dbSaveWithKey:(NSString *)key value:(NSData *)value fileName:(NSString *)fileName extendedData:(NSData *)extendedData {
    NSString *sql = @"insert or replace into manifest (key, filename, size, inline_data, modification_time, last_access_time, extended_data) values (?1, ?2, ?3, ?4, ?5, ?6, ?7);";
    sqlite3_stmt *stmt = [self _dbPrepareStmt:sql];
    if (!stmt) return NO;

    int timestamp = (int)time(NULL);
    sqlite3_bind_text(stmt, 1, key.UTF8String, -1, NULL);
    sqlite3_bind_text(stmt, 2, fileName.UTF8String, -1, NULL);
    sqlite3_bind_int(stmt, 3, (int)value.length);
    if (fileName.length == 0) {
    //如果文件名长度==0，则将value存入数据库
        sqlite3_bind_blob(stmt, 4, value.bytes, (int)value.length, 0);
    } else {
    //如果文件名长度不为0，则不将value存入数据库
        sqlite3_bind_blob(stmt, 4, NULL, 0, 0);
    }
    sqlite3_bind_int(stmt, 5, timestamp);
    sqlite3_bind_int(stmt, 6, timestamp);
    sqlite3_bind_blob(stmt, 7, extendedData.bytes, (int)extendedData.length, 0);

    int result = sqlite3_step(stmt);
    if (result != SQLITE_DONE) {
        if (_errorLogsEnabled) NSLog(@"%s line:%d sqlite insert error (%d): %s", __FUNCTION__, __LINE__, result, sqlite3_errmsg(_db));
        return NO;
    }
    return YES;
}

框架作者用数据库的一条记录来保存关于某个缓存的所有信息。 而且数据库的第四个字段是保存缓存对应的data的，从上面的代码可以看出当filename为空和不为空的时候的处理的差别。

接下里是获取缓存的操作：

- (YYKVStorageItem *)getItemForKey:(NSString *)key {
    if (key.length == 0) return nil;
    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;
            }
        }
    }
    return item;
}

根据key获取item，然后更新访问时间，如果item的文件名不为空，获取item的value，如果value为空，删除item。

关于线程安全的方案

YYMemoryCache 使用了 pthread_mutex 线程锁（互斥锁）来确保线程安全
YYDiskCache 则选择了更适合它的 dispatch_semaphore。

pthread_mutex线程锁（互斥锁）：

在YYMemoryCache的初始化方法中得到了互斥锁，并在它的所有接口里都加入了互斥锁来保证线程安全，最后在dealloc方法销毁。

- (instancetype)init {
    self = super.init;
    //初始化锁
    pthread_mutex_init(&_lock, NULL);
    _lru = [_YYLinkedMap new];
    ...
}

- (NSUInteger)totalCount {
    //上锁
    pthread_mutex_lock(&_lock);
    NSUInteger count = _lru->_totalCount;
    //解锁
    pthread_mutex_unlock(&_lock);
    return count;
}

- (void)dealloc {
    [[NSNotificationCenter defaultCenter] removeObserver:self name:UIApplicationDidReceiveMemoryWarningNotification object:nil];
    [[NSNotificationCenter defaultCenter] removeObserver:self name:UIApplicationDidEnterBackgroundNotification object:nil];
    [_lru removeAll];
    //销毁锁
    pthread_mutex_destroy(&_lock);
}

dispatch_semaphore信号量代替锁

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

初始化的时候实例化了一个信号量：

- (instancetype)initWithPath:(NSString *)path
             inlineThreshold:(NSUInteger)threshold {
    ...
    _lock = dispatch_semaphore_create(1);
    _queue = dispatch_queue_create("com.ibireme.cache.disk", DISPATCH_QUEUE_CONCURRENT);
    ...

用宏来代替加锁解锁的代码

#define Lock() dispatch_semaphore_wait(self->_lock, DISPATCH_TIME_FOREVER)
#define Unlock() dispatch_semaphore_signal(self->_lock)

涉及到的一些技巧

异步释放对象的技巧

为了异步将某个对象释放掉，可以通过在GCD的block里面给它发个消息来实现。这个技巧在该框架中很常见，举一个删除一个内存缓存的例子：

- (void)_trimToCost:(NSUInteger)costLimit {
    ...

    NSMutableArray *holder = [NSMutableArray new];
    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
        }
    }
    if (holder.count) {
        dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
        dispatch_async(queue, ^{
            [holder count]; // release in queue
        });
    }
}

因为OC对象的释放也是会消耗性能的。作者把需要释放的对象放到子线程中是对性能的考虑。
通过数组holder持有所有待释放的node对象，然后在指定线程的block中持有，最后在queue中释放。

holder 持有了待释放的对象，这些对象应该根据配置在不同线程进行释放(release)。此处 holder 被 block 持有，然后在另外的 queue 中释放。[holder count] 只是为了让 holder 被 block 捕获，保证编译器不会优化掉这个操作，所以随便调用了一个方法。

总结YYCache的技术点

双向链表的概念以及相关操作
互斥锁，信号量的使用
实现线程安全的方案
缓存的策略