最近加班比较累，完全不想写作了。。

刚看到 一篇有趣的文章 ，是 redis 的作者 antirez 对 redis 的 LRU 算法的回顾。LRU 算法是 Least Recently Used 的意思，将最近最少使用的资源丢掉。Redis 经常被用作 cache，如果能够将不常用的 key 移除，尽量保留常用的，那内存的利用率就相当高了。当然，LRU 也有弱点，考虑下面一种情况：

~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|

假设有 4 个 key，A 以 5 秒 1 次的频率被访问，B 访问频率是 2 秒 1 次，C 和 D 的访问频率都是 10 秒 1 次。因为 B 有最高的访问频率，所以 B 的空闲访问时间是最小的。它的上次访问时间也是第二最近的。但是 D 是一个特例，它的访问频率是 10 秒 1 次，但是它的访问时间是最近的。

当然，长期来看，这个算法还是不错的。通常访问频率高的 key 都有相对比较小的空闲时间。LRU 算法会换掉最近最少使用的 key，即空闲时间最长的。这个算法实现起来非常简单，我们秩序要跟踪一个 key 上次访问的时间即可，甚至有时候都不用，只要维持一个链表，有访问的就移动到表头，需要换掉元素的时候，就移除链表尾部的。

Redis 最早并不支持 LRU 替换。通过修改 Redis 对象结构，作者挤出了 24bit 空间来做这个事情。因为指针太大，也没有空间来用链表实现。24bit 用来存时间戳的低位已经足够了，可以支撑 194 天了，key 的数据刷新频繁，够用了。

如何选择最大空闲时间的 key 来换出也是一个问题，Redis 的 key 存放在一个平坦的哈希表里，添加一个额外的数据结构来完成代价太大。既然 LRU 是理想换页的一个渐近算法，我们何不尝试下 LRU 的渐近算法呢？

Redis 的原始实现非常简单：当需要换出一个 Key 的时候，选任意 3 个 key，，换出其中空闲时间最长的。相当于对整个 key 空间进行随机采样，并换出较好的选择。后来这个算法演变成 N 个随机 key，算法优化后，默认变成采样 5 个 key，速度没有损失。虽然实现是如此简单，但工作起来非常好。如果你仔细思考，你会发现你不可能用这个算法作出最佳决定，但是你也不大可能作出非常坏的决定。如果数据集里有一堆经常访问的 key，5 选 1 不大可能都挑中热的 key。