改进 Redis LRU 算法的随想
Redis 常被用作缓存，在这种场景下会指定一个固定的最大内存使用量。当新数据到来时，我们需要通过删除旧数据来腾出空间。Redis 作为缓存的效率，取决于它在淘汰哪些数据方面做出的决策有多好：删除即将被用到的数据是一种糟糕的策略，而删除不太可能再次被请求的数据则是一种好策略。
换句话说，每个缓存都有一个命中率/未命中率（hits/misses ratio），从定性角度讲，就是缓存能够响应的读查询所占的百分比。在大多数工作负载中，对缓存键的访问并不是均匀分布在数据集上的。往往一小部分键就占据了所有访问中的很大比例。此外，访问模式常常随时间变化，这意味着随着时间推移，某些曾经被频繁请求的键可能不再被经常访问；反之，一些曾经不受欢迎的键可能变成访问最频繁的键。
所以总体而言，缓存应该尽力保留那些未来最有可能被访问的键。从淘汰策略（即用来腾出空间以让新数据进入的策略）的角度来看，这可以转化为相反的说法：未来最不可能被访问的键应该从数据集中移除。只有一个问题：Redis 和其他缓存都无法预知未来。
LRU 算法
虽然缓存无法预测未来，但它们可以这样推理：很可能再次被请求的键，是最近经常被请求的键。由于访问模式通常不会突然改变，这是一种有效的策略。然而，“最近经常被请求”这个概念比乍看起来更加微妙（我们稍后会回到这一点）。于是这个概念被简化成一个叫做 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|键 A 每 5 秒被访问一次，键 B 每 2 秒一次，键 C 和 D 都是每 10 秒一次。
鉴于键 B 的访问频率很高，它的空闲时间是最短的之一，也就是说它的最后访问时间是四个键中第二近的。
类似地，A 和 C 分别为 2 秒和 6 秒的空闲时间也很好地反映了这两个键的访问频率。不过正如你所见，这个技巧并不总是有效：键 D 每 10 秒才被访问一次，但它却拥有所有键中最近的访问时间。
尽管如此，从长远来看，这个算法的效果还是足够好的。通常访问频率更高的键具有更小的空闲时间。LRU 算法淘汰的是“最久未使用”（Least Recently Used）的键，也就是空闲时间最大的那个键。它实现起来很简单，因为我们只需要跟踪给定键最后一次被访问的时间即可；有时甚至这都不需要：我们可以把所有想要淘汰的对象链接在一个链表里。当某个对象被访问时，就把它移到链表的头部。当我们要淘汰对象时，就从链表尾部开始淘汰。搞定！胜利。
Redis 中的 LRU：起源
最初 Redis 并不支持 LRU 淘汰。它是后来才加入的，当时内存效率是一个大问题。通过对 Redis Object 结构稍作修改，我腾出了 24 位的空间。没有空间把对象链接到链表中（胖指针！），而且实现必须高效，因为服务器性能不应因为选择要淘汰的键而下降太多。
对象中的 24 位足以存储当前 Unix 时间（以秒为单位）的最低有效位。这种表示法在 Redis 源代码中被称为“LRU clock”，需要 194 天才会溢出。键的元数据更新得非常频繁，所以这就足够好了。
然而还有一个更复杂的问题要解决：如何选出空闲时间最大的键以便将其淘汰？Redis 的键空间是用一个扁平哈希表来表示的。再增加一个数据结构来保存这些元数据并不可行，但由于 LRU 本身就是对我们所要达到目标的近似，那么何不干脆对 LRU 本身做近似呢？
最初的 Redis 算法就是这么简单：当需要淘汰一个键时，随机选取 3 个键，然后淘汰其中空闲时间最大的那个。基本上就是对键空间进行随机采样，淘汰碰巧表现最好的那个键。后来，“3 个随机键”变成了可配置的“N 个随机键”，算法速度也得到了改进，因此默认值提高到了采样 5 个键而不损失性能。考虑到它有多朴素，它工作得很好，实际上非常好。想一想就会发现，用这个算法你几乎从来不会做出最优决策，但也极不可能做出非常糟糕的决策。如果数据集中存在一小部分访问非常频繁的键，要从 5 个键里恰好只采到空闲时间都很短的键，是很难这么倒霉的。
然而，如果你把这个算法*跨多次执行*来看，就能发现我们丢弃了很多有价值的信息。也许在对 N 个键进行采样时，我们会遇到很多好的候选者，但我们只是淘汰其中最好的一个，然后在下一个周期又从头再来。
搏击俱乐部的第一条规则是：用肉眼观察你的算法
有一段时间我正在开发即将发布的 Redis 3.0。Redis 2.8 在多个环境中被积极用作 LRU 缓存，人们对 Redis 淘汰的精确度并没有太多抱怨，但很明显，即使不占用可观的额外 CPU 时间、也不多占哪怕一位空间，它仍然可以得到改进。
然而要改进某样东西，你必须先观察它。观察 LRU 算法有不同的方式。例如，你可以编写工具来模拟不同的工作负载，并在结束时检查命中率/未命中率。我就是这么做的，但命中率/未命中率在很大程度上取决于访问模式，所以除了这些信息之外，我还编写了一个能以可视化方式展示算法质量的实用程序。
这个程序非常简单：它先添加一定数量的键，然后按顺序访问这些键，使每个键都具有递减的空闲时间。最后再添加 50% 的新键（图中的绿色部分），这样就需要淘汰一半的旧键。
在一个完美的 LRU 实现中，新添加的键不会被淘汰任何一员，而被淘汰的是旧数据集最初的 50%。
这是该程序针对不同版本的 Redis 和不同设置生成的表示图：
http://redis.io/images/redisdoc/lru_comparison.png
看这张图时请记住，我们到目前为止讨论的实现是 Redis 2.8 的。你在 Redis 3.0 中看到的改进将在下一节解释。
LRU V2：不要丢掉重要信息
有了新的可视化工具，我可以尝试新的方法，并在几分钟内完成测试。改进 Redis 所用的原始算法最显而易见的方式，就是把那些原本会被丢弃的信息积累到一个由优秀淘汰候选者组成的“池”中。
基本上，当执行 N 个键的采样时，会用它来填充一个更大的候选池（默认只有 16 个键）。这个池中的按键空闲时间排序，所以只有当新键的空闲时间大于池中某个键，或者池中还有空位时，新键才会进入池中。
这个小改动极大地提升了算法的性能，正如你在上面链接的图片中所看到的，而且实现并不复杂。这里几个 memmove()，那里几次性能剖析（profiling），我不记得这方面有什么大的 bug。
与此同时，还添加了一个用于测试 LRU 精确度的新 redis-cli 模式（参见 —lru-test 选项），这样我就有了另一种方法，可以用幂律访问模式来检验 LRU 代码的性能。这个工具被用来通过不同的测试验证新算法在更接近真实世界的工作负载下表现得更好。它还使用了流水线（pipelining）并显示每秒访问次数，因此也可以用来对不同实现进行基准测试，至少可以检查明显的速度回退。
LFU（Least Frequently Used，最不经常使用）
我现在写这篇博客文章的原因，是因为几天前我对 Redis 缓存淘汰代码进行了部分重新实现和一些不同的改进。
一切都始于一个开放的 issue：当你使用 Redis 3.2 并且有多个数据库时，该算法会做出局部性的选择。举例来说，如果 DB 0 中的所有键空闲时间都很小，而 DB 1 中的所有键空闲时间都很大，Redis 会从每个 DB 各淘汰一个键。更合理的选择当然是从 DB 1 开始淘汰键，之后再淘汰其他键。
这通常不是什么大问题，因为 Redis 用作缓存时很少使用多个 DB，但这正是我重新着手研究淘汰代码的起点。最终我得以修改候选池使其包含数据库 ID，并对所有 DB 使用单一候选池而不是多个池。一开始它变慢了，但经过性能剖析和调优，最终它比原来的实现快了大约 20%。
然而那时我对 Redis 这个子系统的好奇心又被激发起来，我想进一步改进它。我花了几天时间尝试改进 LRU 实现：也许用一个更大的候选池？在选择最佳键时考虑流逝的时间？
过了一段时间，在完善了我的工具之后，我明白 LRU 算法受限于数据库中被采样的数据量，除此之外它已经非常出色、很难改进了。其实这一点从展示不同算法对比的那张图片中就可以明显看出：每个周期采样 10 个键时，该算法的准确度已接近理论上的 LRU。
既然原算法难以改进，我开始测试新的算法。如果我们稍微回溯到这篇博客的开头，我们说过 LRU 其实算是一种取巧。我们真正想要的是保留那些未来最有可能被访问的键，也就是*访问最频繁*的键，而不是最近被访问过的键。
淘汰访问次数最少键的算法叫做 LFU。它的意思是 Least Frequently Used（最不经常使用），也就是它试图消灭的那个特性，以便为新键腾出空间。
理论上 LFU 很简单：给每个键关联一个计数器。每次访问时计数器加一，这样我们就知道某个键比另一个键被访问得更频繁。
嗯，其实至少还有几个问题，不是 Redis 特有的，而是 LFU 实现的普遍问题：
- 使用 LFU 时，不能像 LRU 那样利用“移到头部”的链表技巧来简单地按淘汰顺序排列元素，因为在“完美 LFU”中键必须按访问次数排序。把被访问的键移动到正确的位置可能会有问题，因为可能有很多键具有相同的分数，所以最坏情况下操作可能是 O(N)，即使键的频率计数器只发生了很小的变化。另外，正如我们在第“2”点中将看到的，访问计数器并不总是只发生很小的变化，也会出现突然的大幅变化。
- LFU 不能真的简单到每次访问就把访问计数器加一。如前所述，访问模式会随时间变化，所以一个高分的键如果不再有人访问，其分数需要随时间降低。我们的算法必须能够随时间自适应。
在 Redis 中第一个问题不是问题：我们可以直接使用 LRU 的技巧：随机采样加上候选池。第二个问题依然存在。所以通常 LFU 实现都有某种方式来不时地递减或减半访问计数器。
用 24 位空间实现 LFU
LFU 本身就有其实现的特殊性，而在 Redis 中我们能使用的只有那 24 位的 LRU 字段来建模 LFU。在每个对象仅 24 位的情况下实现 LFU 要更棘手一些。
我们需要在这 24 位中做到：
- 某种形式的访问频率计数器。
- 足够的信息来决定何时将计数器减半。
我的解决方案是把 24 位拆分成两个字段：
16 bits 8 bits
+----------------+--------+
+ Last decr time | LOG_C |
+----------------+--------+16 位字段是上次递减时间，这样 Redis 就知道计数器上次被递减的时间，而 8 位字段则是实际的访问计数器。
你会想，8 位计数器很快就溢出了，对吧？好吧，诀窍在于，我没有只用一个普通计数器，而是用了对数计数器。下面就是在键被访问时递增计数器的函数：
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;
double r = (double)rand()/RAND_MAX;
double baseval = counter - LFU_INIT_VAL;
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);
if (r < p) counter++;
return counter;
}基本上，计数器的值越大，计数器真正被递增的概率就越低：上面的代码计算出一个介于 0 和 1 之间的数‘p’，它随着计数器的增大而越来越小。然后它提取一个介于 0 和 1 之间的随机数‘r’，只有当‘r < p’为真时才递增计数器。
你可以通过 redis.conf 参数配置计数器递增的激进程度，比如，在默认设置下，情况是这样的：
100 次命中后计数器的值为 10；1000 次后为 18；10 万次后为 142；100 万次命中后达到 255 的上限，不再递增。
现在来看看这个计数器是如何被递减的。这 16 位用来存储转换为分钟单位的 UNIX 时间的最低有效位。当 Redis 进行随机采样扫描键空间以寻找填充候选池的键时，遇到的所有键都会被检查是否需要递减。如果距离上次递减已经超过 N 分钟（N 可配置），那么当计数值较高时就将其减半，较低时则直接递减（希望这样能更好地区分访问次数少的键，毕竟我们的计数器分辨率非常小）。
还有一个问题：新键总归需要有机会存活下来。在原始 LFU 中，刚添加的键的访问分数为 0，因此是非常好的淘汰候选者。在 Redis 中，新键的 LFU 初始值为 5。这个初始值已被计入递增和减半算法之中。模拟表明，有了这一改动，键有时间去积累访问：分数低于 5 的键会被优先淘汰（长时间不活跃的键）。
代码与性能
上述实现可以在 Redis 的“unstable”分支中找到。我的初步测试显示，在幂律访问模式下它的表现优于 LRU，同时每个键占用的内存量相同，不过真实世界的访问模式可能有所不同：访问的时间和空间局部性可能以非常不同的方式变化，所以我非常乐意从真实世界的使用案例中了解 LFU 的表现如何，以及你可以调整的 Redis LFU 实现的两个参数如何影响不同工作负载下的性能。
此外还添加了一个 OBJECT FREQ 子命令，用于报告给定键的频率计数器，这既可以用来观察应用程序的访问模式，也可以用来调试 LFU 实现。
请注意，在运行时于 LRU 和 LFU 策略之间切换会导致最初出现近乎随机的淘汰，因为累积在 24 位计数器中的元数据与新选择的策略含义不匹配。不过随着时间的推移它会重新适应。
可能还有很多可以改进的地方。
Ben Manes（本·马内斯）向我指出了这篇有趣的论文，描述了一种叫做 TinyLRU 的算法（http://arxiv.org/pdf/1512.00727.pdf）。
这篇论文包含一个非常精妙的想法：与其记住当前对象的访问频率，不如（以概率方式）记住迄今为止见过的所有对象的访问频率，这样一来，如果根据名字我们认为某个新键可能只会得到很少的访问，我们甚至可以拒绝它，从而完全不需要淘汰——前提是淘汰一个键意味着降低命中率/未命中率。
我的感觉是，这项技术虽然对于纯粹的 GET/SET LFU 缓存非常有趣，但不适用于 Redis 作为数据结构服务器的本质：用户期望键在被创建之后至少存在几毫秒。完全拒绝键的创建在语义上似乎不符合 Redis 的定位。
不过，当一个键被覆写时，Redis 会保留其 LFU 信息，例如在执行：
SET oldkey some_new_value之后，24 位的 LFU 计数器会被复制到与旧键关联的新对象上。
Redis unstable 新的淘汰代码还包含其他好消息：
- 策略现在是“跨数据库”的了。过去 Redis 会做出本文开头所解释的那种局部性选择。现在这个问题对所有策略都已修复，而不仅仅是 LRU。
- volatile-ttl 淘汰策略——即基于设置了过期时间的键的剩余存活时间来进行淘汰的策略——现在和其他策略一样使用候选池。
- 通过在键候选池中复用 SDS 对象，性能得到了提升。
这篇文章比我预期的长了不少，但我希望它能为大家提供一些关于新东西以及对我们已有旧东西的改进的洞见。与其说 Redis 是解决特定问题的“方案”，不如说它是一个通用工具。如何正确地运用它，取决于明智的开发者自己。很多人把 Redis 用作缓存解决方案，所以我们时不时会对这一领域进行研究改进。
Hacker News 评论：https://news.ycombinator.com/item?id=12185534