浅谈 Redis 中的 LRU/LFU

算法思想

LRU 算法基于的思想是：最近频繁被访问到的 key，未来很可能会被再次访问到。这一思想基于访问模式通常不会发生突变以及程序的局部性原理，因此 LRU 在实际工程中往往很有效。LRU 算法通过记录 key 最近一次被访问的时间来近似实现“最近频繁被访问到”的原则，认为更高频度被访问到的 keys，其被访问到的时间间隔也大概率会更小。

算法存在的问题

LRU 只看一个 key 最近一次被访问到的时间，这可能导致在某些特定访问模式下，LRU 无法准确淘汰最不常用的 key。例如，在一种访问模式下，某个 key 在很长时间内没有被访问，但在最近被访问了一次，那么按照 LRU 的原则，这个 key 将被认为是最近被访问过的，因此不会被淘汰，即使它的访问频度实际上很低。但从长久范围来看，LRU 还是可以近似“最近频繁被访问到”的原则。

实现思路

LRU 的核心是将 keys 按照“最近一次被访问”的时间排序，因此关键就是高效的排序及排序管理。一种常见的实现方式是使用链表，将每个 key 作为一个节点，每次访问一个 key 时，就将其节点移动到链表的最前端。这样，链表的最尾端就是最近一次被访问时间最久远的 key，也就是最应该被淘汰的 key。

Redis 中的 LRU 实现

Redis 中的 LRU 实现面临一个挑战：Redis Object 数据结构只有 24 个 bit 可以用来存储额外信息，无法直接添加链表等字段。因此，Redis 采用了一种近似算法：每次随机采样 N 个 key，挑选出其中最近一次访问时间最久远的 key 进入候选池，需要淘汰的时候从候选池中选一个即可。作者提出，N 取 5 可以达到算法性能和速度的最佳平衡。

LRU 优化

为了进一步提高 LRU 算法的准确性，Redis 采用了一个小的改进：用一个池子维护合适的候选 key，池子里的 key 按“最近一次被访问到”的时间排序。每一轮对 N 个 key 进行采样时，只有当这 N 个 key 中最差的 key 的访问时间比池子里最近一次被访问时间最近的 key 更久远时，才可以进入这个池子。这样，就充分利用了“key 被访问到的时间”这一信息。

算法思想

LFU 算法基于的思想是：淘汰访问频度最低的 key。LFU 算法认为，计算机科学中的很多指标服从“偏态分布”，即访问集中在小部分对象上。因此，通过记录 key 的访问频度，并按照频度排序，可以更有效地淘汰最不常用的 key。

实现思路

LFU 算法的实现面临两个挑战：一是算法复杂度的问题，二是访问频度计数的更新机制。

对于算法复杂度的问题，LFU 可以采用和 LRU 一样的随机采样方法，避免了对所有 key 进行排序的高复杂度操作。

对于访问频度计数的更新机制，LFU 需要设计一个“减少”的机制，以反映访问模式的变化。Redis 采用了一种“对数计数”和“退火算法”相结合的方法。

• 频度的“对数计数”：Redis 对 24 个 bit 进行了功能划分，其中 8 bit 用来记录访问频度，16 bit 用来记录 key 上一次做“减少（decrement）”操作的时间戳。为了避免计数器快速溢出，Redis 采用了一种基于概率的计数增加方法。当计数器越大时，其增加的概率越低，从而实现了“对数计数”的效果。

• 频度的退火算法：如果 key 的“last decrement time”超过一定时间阈值（可配置），则频度计数直接折半；否则，频度计数减一。这种退火算法有助于更好地区分很少被访问到的 key，因为计数的分辨率很低（只有 8 个 bit）。

一点工程优化

对于新加入的 key 来说，其频度此时很低（0），对于 LFU 来说，这种 key 是非常好的淘汰对象。但显然这是不太合理的。因此，Redis 采用了一种优化方法：key 新加入时频度计数为一个非零值（如 5），保证新加入的 key 能在最近的几次淘汰中能存活下来。

• LRU 算法基于“时间局部性”原理，通过记录 key 最近一次被访问的时间来近似实现“最近频繁被访问到”的原则。Redis 中的 LRU 实现采用随机采样和候选池的方法，以平衡算法性能和准确性。
• LFU 算法基于“偏态分布”原理，通过记录 key 的访问频度来淘汰最不常用的 key。Redis 中的 LFU 实现采用“对数计数”和“退火算法”相结合的方法，以反映访问模式的变化并避免计数器快速溢出。同时，通过优化新加入 key 的频度计数，确保新加入的 key 能在最近的几次淘汰中能存活下来。