memcached 最初部署时，通常与后端 Web 服务器共置，使用备用 RAM 和 CPU 周期。重要的是它保持 CPU 使用量低，同时保持速度快；否则，它会影响它试图改进的应用程序的性能。

随着时间的推移，部署方式发生了变化。通常有更少的专用节点，但有更多的 RAM，但备用 CPU。最重要的是，Web 请求可以一次获取数十到数百个对象，请求延迟对整体影响更大。

这篇文章重点介绍了减少浪费缓存空间的过期项目数量、通用 LRU 改进以及延迟一致性的努力。

原始实现

在 1.4.x 及更早版本中，memcached 中的 LRU 是一个标准的双向链表：有一个头和一个尾。新项目插入到头部，驱逐从尾部弹出。如果访问了某个项目，它将从其位置取消链接，然后重新链接到头部（在此称为“碰撞”），回到 LRU 的顶部。

没有后台线程来积极维护数据。如果项目过期，它将保留在内存中，直到再次被访问。当查找过期项目时，内存将被释放，并向客户端返回 MISS。

过期项目被删除的唯一时间

• 当被有意删除时
• 当通过 SET 覆盖时
• 当过期后通过 GET、ADD 等重新访问时。
• 当需要驱逐时，它会查看尾部周围的几个项目，以查找要回收的过期项目，而不是驱逐实际的尾部。

早期进行了一个重要的优化，导致项目每 60 秒只碰撞一次。因此，频繁访问的项目避免了过多的互斥锁和变异。

即使热门项目并不总是“碰撞”在 LRU 中，一次获取数百个项目也可能导致至少其中几个项目碰撞（或者如果用户从零食休息回来，则可能导致所有项目碰撞）。这会导致互斥锁争用、延迟不均匀以及服务器上的 CPU 使用量过高。

LRU 锁定严重限制了多线程可扩展性。使用原始 LRU，扩展到 8 个工作线程以上很困难。一旦优化完成，非常读重的负载几乎可以线性扩展到 48 个核心。

我们采用了一种极简主义的方法来寻找新的算法。代码改动必须相对较小，向后兼容，并且易于测试和验证。最终用户也拥有各种未知的负载模式，需要更通用的方法。

分段 LRU

第一个改进：我们构建了一个受 2Q、分段 LRU 设计影响的修改版 LRU，以及 OpenBSD 文件系统缓冲区缓存的命名。

LRU 被分成四个子 LRU。每个子 LRU 都有自己的互斥锁。它们都由一个名为“LRU 维护者”的单一后台线程控制，详见下文。

每个项目都有两个位标志指示活动级别。

• FETCHED：如果项目曾经被请求过，则设置。
• ACTIVE：如果项目第二次被访问，则设置。当项目被提升或移动时，将被移除。

HOT 充当一个试用队列，因为项目很可能表现出强烈的时序局部性或非常短的 TTL（生存时间）。因此，项目在 HOT 中永远不会被提升：一旦项目到达队列尾部，如果项目处于活动状态（3），它将被移动到 WARM，否则将被移动到 COLD（5）。

WARM 充当扫描工作负载的缓冲区，例如读取旧帖子的网络爬虫。从未被击中两次的项目无法进入 WARM。WARM 项目有更大的机会活出它们的 TTL，同时还能减少锁争用。如果尾部项目处于活动状态，我们将把它提升回头部（4）。否则，我们将非活动项目移动到 COLD（7）。

COLD 包含最不活跃的项目。非活动项目将从 HOT（5）和 WARM（7）流向 COLD。当内存已满时，项目将从 COLD 的尾部被驱逐。如果项目变为活动状态，它将被排队异步移动到 WARM（6）。在突发或大量访问 COLD 的情况下，提升队列可能会溢出，项目将保持非活动状态。在过载情况下，从 COLD 的提升将变得概率性，而不是阻塞工作线程。

TEMP 充当具有非常短 TTL（2）（通常为秒）的新项目的队列。TEMP 中的项目永远不会被提升，也不会流向其他 LRU，从而节省了 CPU 和锁争用。它目前默认情况下未启用。

HOT 和 WARM LRU 的大小主要受内存使用百分比的限制，而 COLD 和 TEMP 是无限的。HOT 和 WARM 还有一个相对于 COLD 的尾部年龄限制。这可以防止非常空闲的项目无谓地持续存在于活动队列中。

LRU 维护者线程

所有这些都由 LRU 维护者后台线程联系在一起。它有一个简单的任务

• 遍历每个子 LRU 并查看尾部项目。
• 确保每个子 LRU 都遵守其限制，在必要时移动项目。
• 回收过期的尾部项目。
• 处理来自 COLD LRU 的任何异步碰撞。

这有一个需要注意的地方，即对特定 Slab 类持续过载的 SET 可能会耗尽可驱逐的 COLD 项目。如果发生这种情况，SET 将进入“直接回收”模式，工作线程将在将项目从 HOT 和 WARM 中推出时阻塞。

摘要

除了内存效率外，分段 LRU 对性能有几个主要影响。

1. 直接获取项目时不会发生碰撞。您可以一次获取 500 个键，而无需等待 LRU 锁。
2. 项目是异步碰撞的。SET 或获取流量的短时间突发会导致 HOT 或 WARM 中出现暂时性不平衡。
3. 额外的互斥锁有助于扩展写入操作。
4. 每个项目的元数据大小没有增加。

这些系统的效率因工作负载而异。如果您插入许多具有 60 秒 TTL 的项目，并与具有 86400（1D）TTL 的项目混合在一起，那么 60 秒的项目将浪费内存，直到它们被获取或降至尾部。在此期间，系统会驱逐剩余生命周期为数小时的项目。

这仍然是一个非常有效的缓存。由于它是一个 LRU，因此经常请求的具有较长 TTL 的项目很可能会停留在头部，并且可以自由地存活其 TTL。

LRU 爬虫

此实现仍然存在一些未解决的问题

缓存的大小很难确定。我的 RAM 太多还是太少？有了中间的所有浪费，很难判断。具有不一致访问模式的项目（例如；用户出去吃午饭或睡觉）可能会导致过度丢失。较大的（多千字节）已过期项目可以为数百个较小的项目腾出空间，或者允许它们存储更长时间。

解决这些问题导致了 LRU 爬虫，这是一种异步遍历缓存中项目的机制。它能够回收已过期项目，并且可以检查整个缓存或其子集。

爬虫是一个单一的后台线程，它将特殊的爬虫项目插入每个 Slab 类中每个子 LRU 的尾部。然后，它并发地从下到上，反向遍历每个爬虫项目。爬虫检查它经过的每个项目，查看它是否已过期，如果是，则回收。

它将查看类 1 中的一个项目，HOT，然后查看类 1 WARM 中的一个项目，依此类推。如果类 5 有十个项目，而类 1 有一百万个项目，它将快速完成对类 5 的扫描，然后花费很长时间完成类 1 的扫描。

在扫描每个子 LRU 时，会构建一个剩余 TTL 的直方图。然后，它使用直方图来决定以多大的力度重新扫描每个 LRU。例如，如果类 1 有一百万个 TTL 为 0 的项目，它最多每小时扫描一次类 1。如果类 5 有 100000 个项目，其中 1% 的项目将在 5 分钟内过期，它将安排在 5 分钟后重新运行。如果需要，它可以每隔几秒钟重新扫描一次。

调度功能强大：较高的 Slab 类自然拥有更少的项目，这些项目占用更多空间。它可以非常快速地扫描和重新扫描大型项目，以保持较低的死内存比率。它可以反复扫描类 50，即使扫描类 1 一次需要 10 分钟。

结合分段 LRU，LRU 爬虫可以学习到“HOT”永远不值得扫描，而“WARM”和“COLD”则会带来丰厚的成果。或者相反：如果“HOT”包含许多低 TTL 项目，爬虫可以保持其清洁，同时避免扫描相对较大的“COLD”。这有助于减少单个 Slab 类内部的扫描工作量。

如果我们试图通过从头到尾遍历哈希表来实现这一点。一个剩余 TTL 为 10 秒的 1MB 项目，直到哈希表中的每个项目都被查看一次后才会再次被看到。

摘要

这个二级进程涵盖了管理带有 TTL 的数据的 LRU 的大部分剩余效率问题。纯 LRU 无法识别空洞或过期项目，而文件系统缓冲池通常会以类似的大小（例如 8k 块）保留数据。

使用后台进程来处理死数据，同时自我关注它可以发挥最大效力的位置，可以回收几乎所有死内存。现在，更易于评估缓存实际占用了多少内存。

其他功能可以并且已经构建在 LRU 爬虫之上。

lru_crawler metadump <classid,classid|all>
example output:
key=foo exp=1539196410 la=1539196351 cas=3 fetch=no cls=1 size=64

此命令接受一个类 ID 列表或“all”，将异步打印缓存中每个项目的键和元数据信息。

Memcached 调优

LRU 代码有几个选项可以在运行实例中更改。

lru [tune|mode|temp_ttl] [option list]

• “mode” flat|segmented：您可以在运行时在分段 LRU 和传统 LRU 模式之间切换。HOT 或 WARM 中的项目将异步流入 COLD，而 COLD 将成为主要的 LRU。

• “tune”：接受“percent hot”、“percent warm”、“max hot age factor”、“max warm age factor”作为参数。这允许您动态地使用更大或更小的 HOT 或 WARM 队列来试验命中率。

lru tune 10 25 0.1 2.0

在这个例子中，HOT 被限制在内存的 10%，或者 COLD 尾部年龄的 10%。WARM 被限制在内存的 25%，或者 COLD 尾部年龄的 200%。LRU 维护程序将在必要时移动项目以匹配新的限制。

• “temp_ttl” ttl：设置为 -1 以禁用，或设置为大于 0 以在运行时启用 TEMP LRU 的使用。任何以小于指定 TTL 的 TTL 进入的对象将直接进入 TEMP，并一直保留在那里，直到过期或被删除。

所有这些都可以通过命令行启动选项进行调整，使用“-h”命令获取最新的启动选项。

源代码中的 doc/protocol.txt 包含有关实时调整的最新详细信息。它还包含与该代码相关的新的统计计数器解释，这些计数器主要出现在“stats items”输出中。

结论

这篇文章介绍了两个影响内存效率的改进，它们在 memcached 1.5.0 中默认启用。

软件社区中有很多新颖有趣的想法，我们将继续进行实验。为通用工作配置文件创建高速键值缓存需要仔细权衡取舍。这些功能的实现工作总共花费了几个星期，但生产测试导致多年来的细微变化。

我们已经证明，可以通过在后台线程中使用有限的 CPU 来大幅提高 memcached 的内存效率，同时改善延迟情况。