Redis 常被用作缓存，在这种场景下会设定一个固定的最大可用内存。当有新数据写入时，就需要通过移除旧数据来腾出空间。Redis 作为缓存的效率，取决于它在决定淘汰哪些数据时的判断是否明智：把很快就会用到的数据删掉是糟糕的策略，而把不太可能再次被访问的数据删掉则是好的策略。

换句话说，每个缓存都有一个命中/未命中率，定性地讲，就是缓存能够响应的读请求所占的百分比。在大多数负载下，对缓存中键的访问并非在整个数据集中均匀分布。通常，一小部分键占据了绝大部分访问量。此外，访问模式往往会随着时间而变化，也就是说，随着时间推移，某些曾经被频繁访问的键可能不再常被访问，反之，曾经不受欢迎的键也可能变成最热门的键。

所以，一般来说，缓存应该尽量保留未来最有可能被访问的那些键。从淘汰策略（即为新数据腾出空间所采用的策略）的角度来看，这恰好反过来：应该从数据集中移除未来被访问概率最低的那个键。只有一个问题：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 算法会淘汰最近最少使用的键，也就是空闲时间最长的那个键。它的实现很简单，因为我们只需要记录每个键最后一次被访问的时间，有时甚至连这都不需要：我们可以把所有可能被淘汰的对象用一个链表串起来。当某个对象被访问时，就把它移到链表头部；需要淘汰时，就从链表尾部开始淘汰。就这么简单！大功告成。

Redis 中的 LRU：起源

起初 Redis 并不支持 LRU 淘汰。后来由于内存效率成为一大关注点，才加入了这一功能。通过对 Redis 对象结构稍作修改，我设法挤出了 24 位的空间。已经没有空间用链表把对象串起来了（指针太占地方！），而且实现必须足够高效，不能因为挑选要淘汰的键就让服务器性能大幅下降。

对象中的这 24 位足以存储当前 Unix 时间（以秒为单位）的低位部分。在 Redis 源码中，这种表示方式被称为“LRU 时钟”，需要 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()，再做一些性能分析，我不记得这块出过什么重大 bug。

与此同时，还新增了一种用于测试 LRU 精确度的 redis-cli 模式（参见 —lru-test 选项），这样我就有另一种方式可以在幂律访问模式下检验 LRU 代码的性能。这个工具通过另一项测试验证了新算法在更接近真实世界的负载下表现更好。它还使用了流水线并会显示每秒访问次数，因此也可以用来对不同实现进行基准测试，至少能发现明显的性能回退。

最不经常使用

我现在写这篇博文，是因为几天前我对 Redis 缓存淘汰代码进行了部分重构和多项改进。

一切都源于一个未解决的问题：在 Redis 3.2 中，如果你使用了多个数据库，算法会在每个库内做局部选择。例如，如果 0 号库中的所有键空闲时间都很短，而 1 号库中的所有键空闲时间都很长，Redis 却会从每个库各淘汰一个键。更合理的做法当然是先从 1 号库开始淘汰，之后再去淘汰其他库的键。

这通常不是什么大问题，因为把 Redis 用作缓存时，很少会用到多个数据库，不过这正是我再次着手修改淘汰代码的契机。最终，我修改了池的结构，让它包含数据库 ID，并对所有数据库使用同一个池，而不是每个库各用一个池。起初这样做反而更慢，但经过性能分析和调优，最终比原有实现快了约 20%。

不过到那时，我对 Redis 这一子系统的好奇心又被激发了，想要进一步改进它。我花了几天时间尝试优化 LRU 的实现：比如用更大的池？或者在挑选最佳键时把时间流逝考虑进去？

过了一段时间，在完善了工具之后，我意识到 LRU 算法主要受限于在数据库中采样的数据量，除此之外它本身已经非常好，很难再改进。这其实从展示不同算法的那张图就能看出：每轮采样 10 个键时，算法的准确度就已经几乎接近理论上的 LRU 了。

既然原有算法难以再改进，我便开始尝试新的算法。如果我们回顾一下博文开头提到的，LRU 其实是一种取巧的办法。我们真正想要保留的是未来最有可能被访问的键，也就是*被最频繁访问*的那些键，而不仅仅是最近被访问过的键。

淘汰访问次数最少的键的算法被称为 LFU，即最不经常使用（Least Frequently Used），它试图淘汰的就是具备这一特征的键，以便为新键腾出空间。

理论上，LFU 就像给每个键关联一个计数器一样简单。每次访问时计数器加一，这样我们就能知道某个键比另一个键被访问得更频繁。

当然，至少还有几个问题，并非 Redis 独有，而是 LFU 实现普遍会遇到的：

1. 对于 LFU，你无法像 LRU 那样使用“移到头部”的链表技巧来简单地获得按淘汰顺序排好序的元素，因为在“理想的 LFU”中，键必须按访问次数排序。把被访问的键移到正确的位置可能会很棘手，因为可能有大量键具有相同的分数，所以即使键的频率计数器只是发生了微小变化，最坏情况下操作也可能是 O(N) 的。而且正如我们将在第 2 点中看到的，访问计数器并不总是只发生微小变化，有时也会出现大幅度的突变。
2. LFU 也不能真的像每次访问就简单地把访问计数器加一那样简单。正如我们所说，访问模式会随时间变化，所以如果一个高分键长时间无人访问，它的分数就应该随着时间而降低。我们的算法必须能够随时间自适应。

在 Redis 中，第一个问题其实不是问题：我们可以直接沿用 LRU 的技巧——带候选池的随机采样。第二个问题则依然存在。所以通常的 LFU 实现都会有某种机制，不时地递减或减半访问计数器。

在 24 位空间中实现 LFU

LFU 本身在实现上就有其特殊之处，而在 Redis 中，我们能用来建模 LFU 的只有那 24 位的 LRU 字段。要在每个对象仅用 24 位来实现 LFU，就有点棘手了。

我们需要在 24 位内做到：

1. 某种访问频率计数器。
2. 足以判断何时该将计数器减半的信息。

我的解决方案是将这 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，计数器越大，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 中新的淘汰代码还带来了其他好消息：

1. 策略现在是“跨库”的。过去如本文开头所述，Redis 会做局部选择。现在这个问题对所有策略都已修复，而不仅仅是 LRU。
2. volatile-ttl 淘汰策略，即根据设置了过期时间的键的剩余生存时间来淘汰的策略，现在也像其他策略一样使用候选池了。
3. 通过在键池中复用 SDS 对象，性能得到了提升。

这篇文章写得比我预期的要长得多，但希望它能就新功能以及对已有功能的改进提供一些见解。Redis 与其说是一个解决特定问题的“解决方案”，不如说是一个通用工具。如何以正确的方式运用它，取决于明智的开发者。许多人将 Redis 用作缓存方案，因此这一领域的改进总会不时被探索。

Hacker News 评论：https://news.ycombinator.com/item?id=12185534