聊聊memcached1.4的LRU算法

Memcached 是完全基于内存，而内存总会被用完的，如果在 set 操作的时候发现内存不足了，它会怎么办？它采用 Least Recently Used (LRU) 算法，理解 LRU 算法对于使用 memcached 非常关键。

从 memcached1.5 开始，为了进一步优化内存使用和提高性能，memcached 采取了新的 LRU 算法，我会分三篇文章说说新旧版本的 LRU 算法，今天描述 memcached1.4 以前版本的 LRU 算法的原理，相对简单一点。

在 memcached1.4 以前的版本中，如果一个 item 过期了，memcached 并不会主动回收内存空间；也没有异步的线程在后台回收。它的内存回收策略完全是 同步 的，对于一个 set 操作来说，如果 memcacheed 发现内存不够了，它会采用一种算法进行内存操作，从而为新的 item 腾出空间。

它采取的不是 FIFO 这种先进先出的内存淘汰算法，它采用的是更高级的内存淘汰算法，这就是 LRU，如果一个 item 长时间没有使用且已经过期了，会优先清空它们的内存空间，当然这个算法也不是那么智能，假设两个 item 的过期时间一样，在清理的时候，不会优先清理相对较大的 item。

甚至 不同 的 Slab-class 其 LRU 淘汰策略也是完全独立的，互不影响。

在 set 的时候，如果没有过期的 item 被淘汰，那怎么办？这个时候 memcached 只好根据 LRU 算法淘汰尚未过期的 item，这个操作也叫做 evict 。

memcached 本质上是缓存软件，如果你存储的数据不能丢失（非缓存），那需要好好进行内存容量规划，避免数据被 evict。想想看，假设 session 数据使用 memcached 存储，如果一个正常用户对应的 session 被 evict 了，那么这个用户就 logout 了，影响可大可小。

那么 memcached 内部是如何实现 LRU 算法的呢？我没有 看源代码 ，完全通过 wiki 和官方博客学习，如果描述有问题或模棱两可，还请见谅。

在 memcached 中，每个 item 对象被创建的时候，它维护一个计数器，item 对象计数器的值就是 unix 当前时间戳，当一个 item 被 FETCHED 的时候（get、set、replace），这个计数器的值就会更新为当前时间（表示被使用了）。

如果 memcached 在遇到 set 操作的时候，发现内存不够，就会淘汰计数器值最小的 item（过期的优先淘汰），本质上就是这么简单：如果某个 item 没被使用就优先淘汰。

听上去是不是很简单？我们再稍微深入一点，每个 Slab-class 的 LRU 由一个双向链表维护，如下图：

当一个新 item 被 set 的时候，它会进入链表的 head，如果发生 evict，那么在链表 tail 尾的 item 会从内存中释放。

当 get 一个 item，它会从链表中 unlink，然后重新 link 到链表的 head，这个过程叫做 bump 。

由于 bump 会有锁（mutex locks and mutations），频繁发生对性能有非常大的影响，所以 memcached 做了一个优化，在 60 秒内同一个 item 只会产生一次 bump。

活跃的 item 即使没有频繁产生 bump，但如果 get 操作非常多，也会产生很多的锁竞争，导致某些 get 延时不一致，甚至导致 cpu 负载在某个时间过高，也就是多线程的扩展性受制于 memcached 的 LRU lock。什么意思呢？对于老的 URL 实现来说，memcached 开启的工作线程建议不要超过 8 个。

为了进一步提升 LRU 的效率和减少内存的使用，后续我会描述最新的 memcached LRU 算法。

再补充一点，一个 item 什么时候会释放内存呢？通常下面几个步骤会释放：

• 主动 del 操作。

• set 覆盖操作。

• 一个过期 item 进行 get，add，replace 操作的时候。

• evict 操作发生的时候，优先回收 tail 尾部过期的 item。

观察 evict 和内存回收情况对于评估 memcached 非常实用，可以通过 stats 和 stats items 命令了解详细的情况。相关参数解释如下：

1：reclaimed：表示有多少过过期的 item 被回收了。

2：evicted：查看有多少个 item 在过期前发生了 evict

3：evicted_nonzero：查看有多少个明确设置了过期时间的 item 在过期前。相对来说明确设置过期时间的 item 被 evict，那么可能会影响业务。

4：evicted_time：上一次运行 evict 到现在的时间。

5：expired_unfetched：查看有多少 item 被 set 后，从来没访问过，然后因为过期被回收的数量。

6：evicted_unfetched：查看有多少 item 被 set 后，从来没访问过，然后被 evict 的数量。

7：evicted_active：查看有多少 item 被 set 后，最近被访问过（但没来得及达到 LRU head），然后被 evict 的数量。

memcached 相关文章：

• 简单理解memcached的内存分配

• 使用Memcached实现抽奖活动

欢迎大家关注我的公众号（ID：yudadanwx，虞大胆的叽叽喳喳），所有文章都是原创，主要来源于平时工作中遇到的问题和学习中的一些想法。