Cache 基础知识

本文主要讲述一些 Cache 的基础知识，简单介绍一下 YYCache的实现。

“存贮数据（使用频繁的数据）的临时地方，因为取原始数据的代价太大了,
避免每次都要重复地向服务器请求相同的数据,既浪费用户流量,也影响APP响应速度.

1. 缓存术语

• 命中：当客户发起一个请求，我们的应用接受这个请求，并且如果是在第一次检查缓存的时候，需要去数据库读取产品信息。如果在缓存中，一个条目通过一个标记被找到了，这个条目就会被使用、我们就叫它缓存命中。

• Cache Miss：但是这里需要注意两点：

  1. 如果还有缓存的空间，那么，没有命中的对象会被存储到缓存中来。
  2. 如果缓存慢了，而又没有命中缓存，那么就会按照某一种策略，把缓存中的旧对象踢出，而把新的对象加入缓存池。而这些策略统称为替代策略（缓存算法），这些策略会决定到底应该提出哪些对象。

• 存储成本：当没有命中时，我们会从数据库取出数据，然后放入缓存。而把这个数据放入缓存所需要的时间和空间，就是存储成本。

• 索引成本：和存储成本相仿。

• 失效：当存在缓存中的数据需要更新时，就意味着缓存中的这个数据失效了。

• 替代策略：当缓存没有命中时，并且缓存容量已经满了，就需要在缓存中踢出一个老的条目，加入一条新的条目，而到底应该踢出什么条目，就由替代策略决定。

• 最优替代策略：最优的替代策略就是想把缓存中最没用的条目给踢出去，但是未来是不能够被预知的，所以这种策略是不可能实现的。但是有很多策略，都是朝着这个目前去努力。

2. 缓存算法

介绍一些替代策略，根据实际情况选择，没有优劣之分

• Least Frequently Used（LFU）：
  核心思想是 “如果数据过去被访问多次，那么将来被访问的频率也更高”。
  计算每个缓存对象被使用的频率 ,把最不常用的缓存对象踢走。
  LFU队列
  1. 新加入数据插入到队列尾部（因为引用计数为1）；
  2. 队列中的数据被访问后，引用计数增加，队列重新排序；
  3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除。

• Least Recently User（LRU）：
  算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。
  有两种方法可以实现我，array 或者是 linked list。把最新被访问的缓存对象，放到缓存池的顶部,把最近最少使用的缓存对象给踢走。所以，经常被读取的缓存对象就会一直呆在缓存池中。
  

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

LRU2 和 2Q 是对LRU的优化,有需要可以自己了解

• First in First out（FIFO）：

先进先出，正好符合队列的特性，数据结构上使用队列Queue来实现。

1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；
2. 淘汰FIFO队列头部的数据；

• Adaptive Replacement Cache（ARC）：

ARC介于 LRU 和 LFU 之间，为了提高效果，由2个 LRU 组成，第一个，也就是 L1，包含的条目是最近只被使用过一次的，而第二个 LRU，也就是 L2，包含的是最近被使用过两次的条目。因此， L1 放的是新的对象，而 L2 放的是常用的对象。

ARC被认为是性能最好的缓存算法之一，能够自调，并且是低负载的。ARC也保存着历史对象，这样可以记住那些被移除的对象,也可以看到被移除的对象是否可以留下，取而代之的是踢走别的对象。ARC记忆力很差，但是很快，适用性也强。

3. 缓存的实现

手机缓存一般有两种方式,内存缓存和硬盘缓存。
客户端每次请求数据,首先检测内存缓存是否有数据,若没有则检测硬盘,还是没有才请求服务器.请求数据成功后,把数据存入内存和硬盘中。

现在的缓存库很多,官方自带的NSCache
比较常见的开源缓存库SDWebImage、FastImageCache 、YYCache
比较常见的闭源缓存库NSURLCache、Facebook的FBDiskCache

---

4. YYCache 简介

YYCache架构图
YYMemoryCache
实现了LRU,采用两种数据结构实现 双向链表,哈希表。
存储单元是_YYLinkedMapNode,除了key和value外,还存储了它的前后Node的地址_prev,_next,当前缓存内存开销_cost, 缓存时间_time

整个实现基于_YYLinkedMap,它是一个双向链表, CFMutableDictionaryRef字典保存所有节点_YYLinkedMapNode。
有新数据了插入链表头部,访问过的数据结点移到头部,内存紧张时把尾部的结点移除.就这样实现了LRU淘汰算法。

因为内存访问速度很快,锁占用的时间少,所以用的速度最快的OSSpinLockLock。

_YYLinkedMap

YYDiskCache
采用的是文件和数据库相互配合的方式 。
有一个参数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来做.

以上知识简单介绍，部分参考了下 面两篇文章
YYCache作者对于各种缓存库的评测,和以上缓存库的实现思路
还有YYCache源码分析 添加了详细的注释，可很快熟悉YYCache的结构，和一些小tips。

阅读YYCache 你需要了解的一些基础知识，双链表，NSMapTable ，线程同步问题，GCD的使用等等

好了就这么多，想到再补充