本文翻译自 Using Redis as an LRU Cache

Redis 作为缓存使用时,很容易在增加新数据时剔除旧数据。这也是 memcached 的默认行为。

LRU 只是其中的一种剔除方法。使用 Redis 作为 LRU 时,必须用到 maxmemory 参数来限制可用内存的大小。

最大可用内存

maxmemory 选项可以在 redis.conf 中配置,也可以使用 CONFIG SET 命令在运行时设置。如果要设置 100M 的限制,可以在 redis.conf 加上一行:

maxmemory 100mb

值为 0 意味着没有内存限制,在 64 位系统下默认为 0,32 位有个隐形的限制,即 3GB。

到达 maxmemory 的限制时,有一些策略可供选择,可以是返回错误、或者逐出某些键值。

剔除策略

策略通过 maxmemory-policy 参数来配置,可选项包括:

  • noeviction:如果内存达到最大限制,且客户端尝试执行一些增加内存的命令时,返回错误。
  • allkeys-lru:逐出最近最少使用(LRU)的键值。
  • volatile-lru:根据 LRU 的原则,逐出带有过期时间的键值。
  • allkeys-random:随机逐出键值。
  • volatile-random:随即逐出带有过期时间的键值。
  • volatile-ttl:这个选项也仅逐出带有过期时间的键值,会根据生存时间来排序,优先逐出 TTL 短的

在没有键值满足条件的情况下,volatile-lruvolatile-randomvolatile-ttlnoeviction 行为一样。

剔除的策略同样可以在运行时更改,所以你可以使用 INFO 命令监控 hit 和 miss 的情况再来做出决定。

一般的经验有:

  • 对于幂律分布(power-law distribution)地请求,使用 allkeys-lru。部分的键值比其他键值更频繁地被访问。
  • 对于循环访问的情况,达科采用 allkeys-random。每个元素都有相同的几率被访问到。
  • 如果使用 TTL 来标记键值的生存时间,就可以用 volatile-ttl
  • volatile-lruvolatile-random 适用于有部分键值需要永久保存的情况。当然,最好还是用两个 Redis 实例来分而治之。

Note:设置 key 的过期时间会占用内存,所以使用 allkeys-lru 对内存会更加友好。

剔除的过程

剔除键值的过程如下:

  1. 客户端运行了一个命令,试图增加数据。
  2. Redis 检查内存使用情况,发现超过了 maxmemory 限制。它根据逐出策略来剔除某些键值。
  3. Redis 执行新的命令。

Redis 会不断越过限制,然后通过逐出键值,再返回限制之下。如果某个命令会大量使用内存,在其后一段时间内,内存会明显超过限制。

近似 LRU 算法

Redis 没有实现严格的 LRU 算法,这就是说它不能剔除最适合的键值。但 Redis 对部分键值进行采样,并剔除样本中的最久未被访问的键值。

Redis 3.0 引入了候选池,极大地提升了性能,同时也更贴近真正的 LRU 算法。

Redis 的 LRU 算法允许设置每次剔除时的采样数量,通过配置项 maxmemory-samples 就可以调整 LRU 算法的精度。

max-memory-samples 5

Redis 没有实现严格 LRU 是为了节省内存。对于使用 Redis LRU 的应用来说,近似算法和严格 LRU 是一样的,从下图就能看出来:

生成上述图表的步骤:

  1. 使用给定数量的键值填充 Redis。
  2. 依次遍历所有键值对,因此第一个键值就是 LRU 要驱逐的。
  3. 再增加 50% 的键值对,迫使前一半的键值被踢除。

图中 3 种颜色点,形成了三个条带:

  1. 浅灰色带是被逐出的键。
  2. 灰色带是未被逐出的键。
  3. 绿色带是新添加的键。

理论上,前半部分的键将会因为过期而被逐出内存。Redis LRU 在概率上做到了这一点。

从图上也能看出,Redis 3.0 相比 2.8 有了不小的进步。采样空间为 10 的时候,性能已经接近 Reidis 3.0 的理论值。

需要注意的是,LRU 只是一种模型,用于预测未来访问给定键值的可能性。如果你的访问满足幂律分布,那么大多数的请求在 LRU 近似算法能够很好地处理。在幂律分布的情况下,真实 LRU 和 Redis LRU 的差异非常之小。

更多

关于 LRU 的算法,有一道经典的 LeetCode,常见的解法是哈希表+双向链表。美团的这篇 LruCache在美团DSP系统中的应用演进 干货也不少。