前文再续，书接上一回 。上次讲到 redis 的 LRU 算法，文章实在精妙，最近可能有机会用到其中的技巧，顺便将下半部翻译出来，实现的时候参考下。

搏击俱乐部的第一法则：用裸眼观测你的算法

Redis2.8 的 LRU 实现已经上线了，在不同的负载环境下经过测试，用户没有抱怨 Redis 的清理机制。为了继续改进，我希望能观察到算法的性能，同时不会浪费大量 CPU，不增加 1 比特空间占用。

我设计了一个测试用例。导入指定数量的 key，然后顺序访问他们，好让他们的最近访问时间顺序递减。再添加 50% 的 key，那么之前的 key 有 50% 就会被淘汰掉。理想情况下，被淘汰的应该是前 50% 的。如下图：

绿色的是新添加的 key，灰色的是第一次添加的 key，白色表示被移除的。

LRU v2：不要丢掉重要信息

当采用了 N-key 取样时，默认会建立 16 个 key 的池，将里面的 key 按空闲时间排序。新 key 只会在池不满或者空闲时间大于池里最小的，才能进池。

这个实现极大的提升了性能，实现又简单，没有大 bug。只要一点点性能监控和一些 memmove() 就完成了。

同时，新的 redis-cli 模式（-lru-test）支持测试 LRU 精度，可以更接近真实的负载来看新算法的工况，尝试不同算法的时候，至少可以发现明显的速度退化。

最近最少访问（LFU）

我最近又部分重构了 Redis cache 的换页算法。这些工作源于一个 issue：当你在 Redis 3.2 有多个数据库的时候，算法总是做局部选择。比如 DB 0 的所有 key 都用的很频繁，DB 1 的所有 key 都用的很少。Redis 会从每个 DB 里丢弃一个 key。理性的选择应该是先丢弃 DB 1 的 key，丢完以后再丢 DB 0 的

Redis 用作 cache 的时候，通常不会跟不同 DB 混合用，但我还是开始着手改进，最后将 db 的 id 包括在池里，然后所有 DB 都共用一个池，这个实现比原始先快 20%

这次改进激起了我对 Redis 这块子系统的好奇心。我花了好些天进行优化，如果我用一个大点的池子，会好点吗？如果选择 key 的时候考虑了流逝的时间，效果会不会更好？

最后，我终于明白到，LRU 算法会受到取样数量限制，只要数量足够，效果就很好，很难再改进。正如上图所示，每次取样 10 个键，已经和理论上的 LRU 几乎一样准确了。

因为原始算法难以改进，我开始想其他办法。回顾前文，其实我们真正想要的，是保留未来最有可能访问的 key，即是最常访问的 key，而不是最新访问的 key。这就是 LFU 算法。理论上 LFU 的实现很简单，只要给每个 key 挂一个计数器，我们就可以知道给定的 key 是不是比另一个 key 访问更多了。

当然，LFU 的实现上有几个通用的难点：

  1. LFU 里没法使用链表法转移到头部的技巧了。因为完美 LFU 需要 key 严格按访问量排序。当访问量一致时，排序算法可能劣化为 O（N），即使计数器只变了一点点

  2. LFU 没法简单的只在访问时对计数器加一。因为访问模式会随着时间发生变化，所以一个高分的 key 需要随着时间流逝而分数递减。

在 Redis 里第一个问题不是问题，我们可以沿用 LRU 的随机取样方法。第二个问题仍然存在，我们需要一个方法来递减分数，或者随着时间流逝将计数器折半。

24bit 空间实现的 LFU

在 Redis 里，我们可以用的就是 LRU 的 24bit 空间，需要一些奇技淫巧来实现。

在 24bit 空间里，需要塞下：

  1. 某种类型的访问计数器

  2. 足够的信息来决定何时折半计数器

我的解决方案如下：

           16 bits      8 bits
      +----------------+--------+
      + Last decr time | LOG_C  |
      +----------------+--------+

8bit 用来计数，16bit 用来记录上次递减的时间

你可能会认为，8bit 计数器很快就会溢出了吧？这就是技巧所在：我用的是对数计数器。具体代码如下：

  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;
  }

计数器的值越大，真正加一的概率越小。上述代码算出一个概率 p，介乎 0 到 1 之间，计数器越大，p 越小。然后生成 0-1 之间的随机数 r，只有 r<p 的时候，计数器才会加一。

现在我们来看看计数器折半的问题。转成分钟为单位的 unix 时间，低 16 位会存在上面保留的 16 位空间内。当 Redis 进行随机取样，扫描 key 空间的时候，所有遇到的 key 都会被检查是否应该递减。如果上次递减实在 N 分钟之前（N 是可配置的），并且计数器的值是高分值，那计数器就会被折半。如果计数器是低分值，则只会递减。（希望我们可以更好的分辨少访问量的 key，因为我们的计数器精度比较低）

还有一个问题，新的 key 需要一个生存的机会。Redis 里新 key 会从 5 分开始。上面的递减算法已经考虑到这个分数，如果 key 分数低于 5 分，更容易被丢弃（一般是长时间没访问的非活跃 key）。