聊聊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，虞大胆的叽叽喳喳），所有文章都是原创，主要来源于平常工作中遇到的问题和学习中的少量想法。