提到缓存，我们肯定都不陌生，由于大部分系统的数据都存在局部性，即有些数据是经常被使用到的，我们可以将其先缓存起来，这样，一方面能提高系统的吞吐量；另一方面也能降低数据库等第三方系统的请求压力。
缓存置换，是指当缓存满了之后，这时候再有新的数据需要缓存时，需要淘汰掉缓存中的一个条目，给新数据腾出位置。如果一个缓存置换方案设计的不合理，导致我们经常在缓存中找不到想要的数据，这时候，需要频繁进行缓存置换，缓存的作用很小，甚至是负作用，本来只需要请求一次外部系统，现在还额外增加对缓存系统的读写。
当需要从缓存中淘汰数据时，我们希望能淘汰那些将来不可能再被使用的数据，保留那些将来还会频繁访问的数据，但问题是缓存并不能预言未来。一个解决方法就是通过 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，否则可能在置换时，找不到要淘汰的缓存数据。
