本文来源于公众号： 跬步匠心

原文链接：http://mp.weixin.qq.com/s... 作者：跬步匠心

提到缓存，我们肯定都不陌生，由于大部分系统的数据都存在局部性，即有些数据是经常被使用到的，我们可以将其先缓存起来，这样，一方面能提高系统的吞吐量；另一方面也能降低数据库等第三方系统的请求压力。

缓存置换，是指当缓存满了之后，这时候再有新的数据需要缓存时，需要淘汰掉缓存中的一个条目，给新数据腾出位置。如果一个缓存置换方案设计的不合理，导致我们经常在缓存中找不到想要的数据，这时候，需要频繁进行缓存置换，缓存的作用很小，甚至是负作用，本来只需要请求一次外部系统，现在还额外增加对缓存系统的读写。

当需要从缓存中淘汰数据时，我们希望能淘汰那些将来不可能再被使用的数据，保留那些将来还会频繁访问的数据，但问题是缓存并不能预言未来。一个解决方法就是通过 LRU 进行预测：最近被频繁访问的数据将来被访问的可能性也越大。

常规的 LRU 算法实现

常见的 LRU 使用哈希链表实现，哈希链表是双向链表和哈希表的结合体。

查询时，利用哈希表，可以在 O (1) 的复杂度下快速找到某个 key 是否在缓存 (链表) 并读取出值；每次访问后，会将缓存条目移动到链表头。这样，最近一直没有访问的数据就会处于链表尾部，发生缓存置换时，删除链表尾部的数据，并将新数据写入链表头部。

为什么使用双向链表，使用单向链表有什么问题吗？使用双向链表是为了在移动缓存数据到表头的复杂度为 O (1)。移动缓存数据在链表中的位置等价于先把节点删除，再把节点移动到表头位置，删除时，我们需要同时知道节点的前驱节点和后驱节点分别是哪个，才能将他们相连。单向链表需要对链表进行遍历才能获取前驱节点，显然不能满足要求。

redis 近似 LRU 实现

上面的 LRU 实现用到了一个双向链表来记录数据的最近访问情况，每个链表节点需要维护一个前驱指针和一个后驱指针，当缓存量较大时，两个指针额外占用的内存也是不可忽视的。所以，在缓存数据库 redis 中，为了节省内存的占用，实现了一种基于采样的近似 LRU 置换算法。

缓存数据依然通过一个哈希表管理，通过 key 可以快速找到对应的数据。每个缓存数据除了 key-value 之外，额外多保存一个最后访问的时间戳 last_read_time。发生缓存置换时，随机选出 N 个缓存数据，淘汰掉其中最久未被访问的数据。

这种方案，虽然可能每次过滤的不是整个缓存中最久未被访问的数据，但计算简单，执行效率也是 O (1) 级别的。而且，这个方案能进一步优化，我们每次淘汰时，可能上一次采样淘汰后剩下的 N-1 个数据中，比下一次采样得到的 N 个数据的最后一次访问时间都早，这种情况第一次采样剩下的那几个老数据并不会被淘汰掉。

新数据：最后一次访问时间距离现在较近，last_read_time 值较大
老数据：最后一次访问时间距离现在较远，last_read_time 值较小

为了不辜负之前采样的 “努力”，使算法能尽量淘汰掉更老的数据，我们可以额外维护一个大小为 M 的大顶堆，堆中数据按照 last_read_time 的值排序，这样，堆中最新的数据将会处于堆顶。每次采样后，我们将采样得到的数据依次与堆顶数据比较，如果 last_read_time 比堆顶元素小（即采样的数据更老），我们就把堆顶元素删除，并将采样的数据插入堆中；如果比堆顶元素大（即采样的数据比较新），则不做处理。全部采样数据比较完成后，我们再淘汰掉堆中最老的一条数据，这样，我们就能结合” 历史 “采样的数据，淘汰掉更老的数据。

bit 级别模拟 LRU

在上面两种实现中，我们对哈希表都是一笔带过，但有些场景下，缓存很贵，操作缓存的成本也很高，需要我们对缓存进行更底层的设计，更加合理的利用缓存空间。比如 cpu 上的缓存，缓存很小，可能就只有几百几千个缓存行，但因离 CPU 很近，造价很高，对缓存性能的要求也更高。

我们先将这类缓存的数据结构抽象成一个特定长度的数组，对这个数组进行缓存设计。

为了能满足快速查询到某个缓存数据，我们依旧可以参考哈希表的思路，设计一个哈希函数，根据 key 快速定位到数据在数组中的位置。当然，问题也是很明显的，一个数据通过哈希计算后，数组位置是确定的，所以缓存置换时替换的缓存数据也是确定的，无法选择淘汰掉更老的数据。

这个问题在于数据在数组中位置是唯一确定的，如果允许一个数据映射到数组的多个位置，就可以在这多个位置的缓存数据中淘汰掉其中比较老的数据了。

这里我们给出一种方案，在经过哈希计算出一个位置 a 后，可以在 a 开始的往后 N 个位置中查找数据。这 N 个位置的数据组成一个选择组。例如缓存总容量 100，选择组大小设置为 8。要查找 key="lru" 在缓存中的值，经过哈希后得出在位置 11，那么，可以在位置【11、12、13、14、15、16、17、18】中依次查找，直至找到 key 的缓存数据。

当有新数据需要缓存时，先通过哈希计算出选择组的 N 个数据，然后在这 N 个数据中选择老数据替换成新加的数据。那么，这个时候该如何选择呢？

比较容易可以想到的是，可以参考 redis 的实现，每个缓存数据记录下最后访问的时间戳，置换时，在选择组中淘汰掉最老的数据即可。但是，这对于” 寸土寸金 “的 CPU 缓存来说，额外存储一个时间戳，对缓存空间的消耗还是有点太 “奢侈” 了。

1bit 模拟 LRU

这里介绍一种更” 节约 “的模拟 LRU 置换方案，每个缓存条目拿出 1 个 LRU 位 (bit) 来记录缓存的访问情况。0 代表要被淘汰，当缓存被访问时，将这个 bit 设置为 1，置换时查找 0 的缓存数据替换出去。当选择组的缓存条目全为 1 时，将选择组中的缓存条 LRU 位全部重置为 0。

bit 搜索树模拟 LRU

最后再介绍一种更巧妙的模拟 LRU 方法。用几个 bit 来为每个选择组构造一个满二叉树，如下图。

树中的每个节点都是一个 bit，节点为 0 时表示指向左子节点，1 时表示指向右子节点，初始状态都为 0，即都指向左边。

读取缓存时，将改变指向读取的缓存的节点的箭头指向，比如，读取 A 时，会将指向 A 的箭头会被翻转，结果如下图。

当然，如果读取 d 时，整个树的各节点指向不需要改变。

发生缓存置换时，会从根节点开始寻找，顺着箭头方向找到需要淘汰替换的缓存条目。在寻找过程中，会将路径上的节点箭头全部反转，0 变成 1，1 变成 0。比如，要写入新缓存 “K”，结果如下。

总结来说，也就是树的叶子节点指向的缓存条目，都是较早被访问的，应该先被淘汰掉。

思考下，构造 bit-tree 模拟 LRU 对选择组中缓存数量有要求吗？
其实是应该满足 2^n 的，因为搜索树是一颗满二叉树，叶子节点的数量是 2^n, 每个叶子节点负责两个缓存数据，所以，缓存数?>据的数量应该是也 2^n，否则可能在置换时，找不到要淘汰的缓存数据。