YYCache 探寻记

• 摘要：阅读YYCache源码后的一些体会

---

前言

最近一周都在纠结如何实现好一个优雅的缓存。我该用什么数据结构呢？磁盘LRU如何实现呢？今日阅读了YYCache的源码，不得不感慨前人的智慧

谨以此文为记录自己对YYCache源码的一些理解

注：限于作者水平，部分源码理解剖析得可能不够正确，还望各位指正！

正文

整体构造

整个YYCache UML图如下

​

其中，各类负责以下不同的功能

• YYCache：整个缓存的顶层类，亦是用户主要使用的对象
• YYMemoryCache：内存缓存顶层类
• _YYLinkedMap：双向链表，用于实现内存缓存以及实现内存LRU算法的
• _YYLinkedMapNode：双向队列链表，用于双向链表的实现
• YYDiskCache：磁盘缓存顶层类
• YYKVStorage：封装了底层磁盘存储类
• YYKVSStorageItem：存储的单元类，执行SQL返回的对象类

方法剖析

个人认为，理解YYCache最重要在于理解他如何存、如何取以及如何删，下面我将对这几个点进行简析

• 如何存

  当我们使用YYCache - setObject:forKey: 时，YYCache会进行内存缓存以及进行磁盘缓存。而如果我们使用YYCache - setObject:forKey:withBlock:，YYCache会帮我们把磁盘缓存操作以及传入的block放在YYCache维护的GCD并行队列中异步执行

  • 内存缓存操作步骤
    1. 判断key是否存在
       • 若不存在，则返回
       • 若存在，则执行第二步
    2. 判断object是否存在
       • 若不存在，则执行[self removeObjectForKey:key];，即将该key对应的object置空
       • 若存在，执行第三步
    3. 新建节点，赋值，根据LRU算法插入到双向链表
    4. 根据costLimit / countLimit判断是否需要执行淘汰算法
  • 磁盘缓存操作步骤
    1. 判断key是否存在
       • 若不存在，则返回
       • 若存在，则执行第二步
    2. 判断object是否存在
       • 若不存在，则执行[self removeObjectForKey:key];，即将该key对应的object置空
       • 若存在，执行第三步
    3. 对数据进行归档（使用_customArchiveBlock / NSKeyedArchiver）
    4. 判断缓存类型，执行不同的操作（注意此处可能有误）
       • 若是SQLite类型：执行SQL写入 {key: value}
       • 若是File类型：使用md5(key) / _customFileNameBlock(key)生成filename，将value写入文件名为filename的文件，并执行SQL写入{key: filename}
       • 若是Mixed类型且大于临界值：同File
       • 若是Mixed且小于临界值：执行SQL查询，判断能否根据key值找到filename
         • 若能，则删除磁盘filename文件，执行SQL写入{key: value}
         • 若不能，则执行SQL写入{key: value}

• 如何取

  当我们使用YYCache - objectForKey: 时，YYCache会进行内存缓存检索以及磁盘缓存检索。而如果我们使用YYCache - objectForKey:withBlock:，YYCache会帮我们把磁盘缓存检索操作以及传入的block放在YYCache维护的GCD并行队列中异步执行

  • 内存缓存检索步骤
    • 查找双向链表，判断是否存在对应key的object
      • 若存在，则返回，并刷新时间，将其放置队列首
      • 若不存在，进行磁盘检索
  • 磁盘缓存检索步骤
    1. 执行SQL查询语句，根据key获得对应的value(type = YYKVStorageItem *)
    2. 执行SQL更新语句，刷新时间，以便LRU算法实现
    3. 判断value是否含有文件名
       • 如果含有文件名，即表示其将实际数据存在文件中，我们需要从文件中读取
       • 如果不含有文件名，即表示其已为实际数据
    4. 从文件系统解档（使用_customUnarchiveBlock / NSKeyedUnarchiver）
    5. 将本数据放入内存缓存
    6. 返回数据

• 如何删

  当我们使用YYCache - removeObjectForKey: 时，YYCache会进行以下操作，分别是对内存缓存以及磁盘缓存中的值进行删除。同样的，如果我们使用YYCache - removeObjectForKey:withBlock:，YYCache会帮我们把磁盘缓存删除操作以及传入的block放在YYCache维护的GCD并行队列中异步执行

  • 内存缓存删除步骤
    1. 找到对应的节点
    2. 判断是否需要在主队列释放，若否则在GCD Low Global Low Queue中释放
  • 磁盘缓存删除步骤
    • 根据磁盘缓存的不同类型进行删除
      • 若为SQLite类型：执行SQL语句删除值
      • 若为File类型 / Mixed类型
        1. 执行SQL指令，从数据库中读出文件名
        2. 把文件从沙盒中删除
        3. 执行SQL指令，把数据库元信息删除

• 特殊

  这里我还要特别的提一下两个很重要的操作，分别是定期删除以及缓存重置操作

  • 定期删除

    在我们初始化YYCache的时候，我们初始化的调用过程是这样的：

    1. 所有YYCache的初始化方法最终都会调用YYCache - initWithPath:这一指定构造器
    2. 接着会分别调用YYDiskCache - initWithPath:inlineThreshold:以及YYMemoryCache - init
    3. 两个方法都会分别调用[self _trimRecursively];，这个方法便是我想要提及的定期删除方法

    我们来大概看一下_trimRecursively的伪代码

    - (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 - Weak Dance
            __strong typeof(_self) self = _self;
            if (!self) return;
          	// 在维护的GCD队列中执行不同的淘汰标准算法
          	// YYMemoryCache维护的是GCD串行队列，YYDiskCache维护的是GCD并行队列
            [self _trimInBackground];
          	// 重新将函数入栈
            [self _trimRecursively];
        });
    }

    在这个实现中，我们可以看到YYCache很巧妙的使用GCD + 尾递归实现了定期淘汰算法

  • 缓存重置

    关于缓存重置，大家可能认为没什么好说的，无非是把内存释放了，把磁盘文件删除了。在那YYCache是怎样释放的呢？

    首先是当我们的程序收到内存警告的时候，YYMemoryCache会判断我们自己有没有didReceiveMemoryWarningBlock能够执行，执行完后则对shouldRemoveAllObjectsOnMemoryWarning这一属性值进行判断（默认为YES），当其为真的时候，执行[self removeAllObjects];，也就是上面所说的，简单的内存释放了。

    当我们的程序进入后台的时候，也是同理，判断是否存在didEnterBackgroundBlock能够执行，执行完后则对shouldRemoveAllObjectsWhenEnteringBackground这一属性值进行判断（默认为YES），当其为真时，执行[self removeAllObjects];

    那究竟有什么好说的呢？我想说的是我们手动调用YYCache - removeAllObjects的时候，对于硬盘缓存的处理过程

    同样的，我们先大概看一下YYKVStorage - removeAllItems代码

    - (BOOL)removeAllItems {
        if (![self _dbClose]) return NO;
        [self _reset];
        if (![self _dbOpen]) return NO;
        if (![self _dbInitialize]) return NO;
        return YES;
    }

    这样看，似乎也没有什么大不了嘛，无非是断开与数据库的连接，清除文件，再重新建与数据库的连接，然后再执行初始化方法。下面再让我们来看一下YYKVStorage - _reset这一代码

    - (void)_reset {
        [[NSFileManager defaultManager] removeItemAtPath:[_path stringByAppendingPathComponent:kDBFileName] error:nil];
        [[NSFileManager defaultManager] removeItemAtPath:[_path stringByAppendingPathComponent:kDBShmFileName] error:nil];
        [[NSFileManager defaultManager] removeItemAtPath:[_path stringByAppendingPathComponent:kDBWalFileName] error:nil];
        [self _fileMoveAllToTrash];
        [self _fileEmptyTrashInBackground];
    }

    我们在这里除了看到了把记录了元信息的数据库文件删除这一操作的代码，还看到了什么？回收站！对的，魔法就在于此，我们再看一下YYDiskCache - _fileMoveAllToTrash这一代码

    // _dataPath  = ~/Library/Cache/data
    // _trashPath = ~/Library/Cache/trash
    
    - (BOOL)_fileMoveAllToTrash {
        CFUUIDRef uuidRef = CFUUIDCreate(NULL);
        CFStringRef uuid = CFUUIDCreateString(NULL, uuidRef);
        CFRelease(uuidRef);
        NSString *tmpPath = [_trashPath stringByAppendingPathComponent:(__bridge NSString *)(uuid)];
        BOOL suc = [[NSFileManager defaultManager] moveItemAtPath:_dataPath toPath:tmpPath error:nil];
        if (suc) {
            suc = [[NSFileManager defaultManager] createDirectoryAtPath:_dataPath withIntermediateDirectories:YES attributes:nil error:NULL];
        }
        CFRelease(uuid);
        return suc;
    }

    YYCache首先会将我们的磁盘缓存文件，移动到其所维护的回收站目录当中，然后再在后台线程对其删除。避免了删除过程影响我们新建立磁盘缓存。个人认为，设计思想实在十分巧妙。

    YYCache还做了什么

• 使用了SQLite WAL机制

  关于此，限于读者水平不做介绍，各位朋友可以移步至SQLite分析之WAL机制 by 岩之痕

• 维护多个GCD队列

  总的而言，YYCache使用了不少的GCD队列，目前我发现的有以下几个，欢迎补充~

  • YYDiskCache
    • Trim Check队列: Low Global Queue
    • Trim队列 / 磁盘读写队列: GCD并行队列
    • 清除回收站队列: GCD串行队列
      • 仅reset时使用回收站，其他均直接在主队列删除
  • YYMemoryCache
    • Trim Check队列: Low Global Queue
    • Trim队列: GCD串行队列
    • 释放队列: _releaseOnMainThread ? Main Queue : Low Global Queue

• 线程安全

  • 目前我发现在YYDiskCache中，使用的是GCD信号量实现线程安全，在YYMemoryCache中，使用的是pthread_mutex_t来实现线程安全。这两种都是继OSSpinLock之后性能较高的锁，当OSSpinLock被证实不再安全之后，Apple更偏向于使用pthread_mutex_t，而Google更偏向于使用GCD信号量，当然，这只是题外话了~关于锁的选择，可以继续看下文

Trick Learn from YYCache

以下的代码是我从YYCache中提取而来，当然这些小技巧可能有朋友早已学会，此处仅作整理，大家可以略过~

• Release Trick：在ARC中，我们没办法调用release，那怎样让对象在其他线程释放呢？使用GCD调用对象的方法即可，hodler会被block获取，随后在block结束时，在queue中释放！
• Try Lock Trick：pthread_mutex_trylock是 pthread_mutex_lock的非阻塞版本。如果pthread_mutex所引用的互斥对象当前被任何线程（包括当前线程）锁定，则将立即返回该调用。否则，该互斥锁将处于锁定状态，调用线程是其属主。当我们获取锁失败的时候，可以短暂的睡眠（usleep），过一段时间再次请求

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

// try lock trick
while (Condition) {
	if (pthread_mutex_trylock(&_lock) == 0) {
        ...
        pthread_mutex_unlock(&_lock);
	} else {
        usleep(10 * 1000); //10 ms
    }
}

Learn From Issue, Commit and Release

下面的Q & A整理自YYCache下的Issue, Commit and Release

• YYCache作者建议我们不要使用Apple的SQLite库，而是使用官方的最新版SQLite，如何做呢？

  我们只需从sqlite官网下载源码包，将解压后的两个文件sqlite.h，sqlite.c，拖入工程中即可

• 从源码我们可以看见，大部分操作都需要执行SQL语句，这样做会不会有性能问题呢？

  SQLite中存储的总数据量较少（仅存储简单的元数据（key、time、size）和少量的Value）

  写入方面，开启了SQLite的WAL模式，速度不会太慢

  查询方面，因为有索引的关系，所以查询速度较快

• YYKVStorage中为什么不直接用sqlite3_exec， 而是使用了sqlite3_prepare_v2，sqlite3_step以及sqlite3_finalize？

  主要是两个方面，一是为了防止 SQL 注入，另一方面用缓存好的 stmt 会提升性能

• 为什么内存缓存中使用pthread_mutex_t，而磁盘缓存中使用GCD信号量进行加锁呢？

  主要是历史原因，一开始作者使用OSSpinLock进行内存缓存加锁，但由于后来OSSpinLock被证实不安全，因此改用pthread_mutex_t

---

• 总结：作为iOS缓存界中的一个优雅实现，YYCache在内存缓存上使用了双向链表结构实现了LRU算法，在磁盘缓存上，则通过使用SQLite记录元信息这一方式，实现了文件系统上的LRU算法
• 本文使用的代码
  • YYModel Version 1.0.4
  • 运行环境：Xcode 8.2.1（8C1002）
• 参考资料
  • YYCache设计思路

---

• Last Edited：2017.2.26
• Author：@Seahub
• Please contact me if you want to share this Article, 3Q~