回顾《Scaling Memcache at Facebook》论文

Posted on by luozhiyun

facebook 现在业务特点奠定了 Memcache 设计的原则：首先读要比写要多，这很明显，因为FB中浏览人数肯定大于发表的；其次在FB中查询的数据源会来源不同系统，如 MySQL、HDFS等，这种异构性要求一种灵活的缓存策略，能够存储来自不同来源的数据。

image-20250420175751676

如上图所示，memcache 读数据的时候先尝试从 memcache 中读数据，若读取失败则从DB中获取数据填充到 memcache 中；写数据时，先更新数据库，然后将 memcache 中相应的数据删除。

这里其实涉及到缓存一致性的问题，更新缓存的策略其实可以演变出4种策略：

更新数据库后更新缓存、更新数据库前更新缓存、更新数据库后删除缓存、更新数据库前删除缓存。
大体上，采取先更新数据库再删除缓存的策略是没有问题的，但是真实场景下，还是会有一个情况存在不一致的可能性，这个场景是读线程发现缓存不存在，于是读写并发时，读线程回写进去老值。并发情况如下：

时间 线程A（写请求） 线程B（读请求–缓存不存在场景） 潜在问题
T1 查询缓存，缓存缺失，查询数据库得到当前值100
T2 更新主库 X = 99（原值 X = 100）
T3 删除缓存
T4 将100写入缓存 此时缓存的值被显式更新为100，但是实际上数据库的值已经是99了

这里其实 FB 引入了 leases 解决这个问题，后面再说。

如何降低延迟

在FB中，用户的一个简单页面浏览可能会产生上百个 memcache 请求，并且 memcache 是分布式部署的，并通过一致性哈希算法进行路由，所以web服务器通常需要与多台 memcache 服务器通信才能完成用户请求，这种 all-to-all 的请求方式会造成两个问题：

  1. Incast Congestion：当许多 Web 服务器（发送方）同时向 同一个 memcache 服务器（接收方）发送请求时，会瞬间产生大量的网络流量涌向该 memcache 服务器或其连接的网络交换机端口。这会超出交换机缓冲区或 memcache 服务器网卡的处理能力，导致数据包丢失、重传和延迟急剧增加；
  2. Single Server Bottleneck：某个 memcache 服务器因为持有特别热门的数据（"hot spot"），或者自身处理能力稍弱，或者暂时出现性能波动，那么它也可能成为瓶颈；

FB 主要在每个 Web 服务器上的 memcache 客户端 来解决延迟问题。解决之道主要有两个：

  • Parallel requests and batching（并行请求和批量处理）：这主要是优化 RTT 次数，将可以一起取的数据通过一次 RTT 一并取出，减少时延；
  • Client-server communication（客户端-服务器通信）：这个优化主要将控制逻辑集中到 memcache client。memcache client 分成两部分：sdk 与 proxy，proxy 也叫做 mcrouter，它用来桥接 web server 与 memcached server。

Client 的请求还进一步优化，将查询请求优化为 UDP 请求，写请求为 TCP 请求。因为 FB 的业务中是读多写少的，且读数据对错误的容忍度高，所以查询的时候通过使用 UDP 可以让 client 直接与memcached服务器通信，无需经过 mcrouter 中转，从而可以降低大量的开销。

在 FB 的实践中，会丢弃掉由于 UDP 数据乱序或者延迟产生的错误数据，运行中大约有 0.25% 的请求被丢弃的，其中 80% 都是由于延迟或丢包导致的，剩余是由于顺序错乱所致。

处理写请求时，为了稳定性所以使用 TCP 来进行处理，但是 TCP 是有连接的，为了减少 client 与 memcache的连接，加了一层中间层 mcrouter ，client 只需要与 mcrouter 建立连接，然后由 mcrouter 与 memcache 集群建立连接，这也叫做 connection coalescing （合并连接），通过这种方式可以降低网络、CPU、内存的开销。

我们通过 FB 的统计数据可知，使用 UDP 大概节省了 20% 左右的延迟。

image-20250426173646439

为了解决Incast Congestion问题，FB 在 client 中使用了滑动窗口机制来做流量限制，滑动窗口的大小和 TCP 的拥塞机制做的有点类似，滑动窗口的大小会在请求成功的时候缓慢增大窗口，在请求没有回应的时候缩小窗口。

image-20250426180000094

当窗口较小时，应用必须串行分发更多批次的memcache请求，从而延长了网络请求的处理时长。而窗口过大时，同时发起的memcache请求会引发网络拥塞，在这两种极端情况之间存在着最佳平衡点，既可避免不必要的延迟，又能最大限度减少网络拥塞。

降低负载

租期 Leases

FB 使用 Leases 主要为了解决两个问题：

  • 陈旧写入（Stale Set）
  • 惊群效应（Thundering Herd）

Stale Sets（陈旧写入）

当多个客户端同时更新同一键值时，若网络延迟或系统调度导致写入操作乱序到达，后提交的更新可能覆盖先前已生效的更新，后续读取可能将旧数据重新写入缓存，形成持久性污染。

虑以下操作序列：

  1. 客户端B发送DELETE K指令清除缓存
  2. 客户端A由于网络延迟，稍后发送SET K=V1
  3. 客户端C在此时读取K，将获得已过时的V1值

这种时序错乱会导致缓存系统与持久化存储之间的数据不一致，进而引发业务逻辑错误。

惊群效应（Thundering Herd）

惊群效应（Thundering Herd）特指当某个热点缓存项失效时，大量并发请求同时穿透缓存层，直接冲击后端数据库的现象。这种场景类似于自然界的"踩踏事件"，在毫秒级时间窗口内形成请求洪峰。

假设某热门内容（如病毒式传播的视频元数据）缓存过期：

  1. 缓存服务器标记键K为失效状态
  2. 在接下来的100ms内，10,000个客户端同时请求K
  3. 所有请求均未命中缓存，触发数据库查询
  4. 数据库瞬间承受超过日常峰值10倍的查询压力

这种突发负载可能导致数据库响应延迟激增，严重时引发级联故障。

综上，基于这几个问题，FB 使用 Leases 机制，通过 令牌仲裁 与 速率限制 同时解决上述两大问题：

Stale Sets 的解决路径：

  1. 令牌绑定：每个缓存未命中事件生成唯一租约令牌，客户端需携带令牌进行写入；
  2. 无效化仲裁：若键值在租约有效期内被删除（如数据库更新），后续携带该令牌的写入将被拒绝；
  3. 单调性保证：通过令牌版本号确保写入操作的时序一致性，消除乱序覆盖；

Thundering Herds 的抑制策略

  1. 令牌发放速率限制：每键每 10 秒 仅发放一个有效租约，强制后续请求等待或重试；
  2. 渐进式回填：首个获得租约的客户端负责从数据库加载数据并回填缓存，其他客户端在短暂等待后可直接读取缓存；

伪代码如下：

// 伪代码示例：租约校验逻辑
void handle_get_request(key) {
    if (cache_miss(key)) {
        if (lease_rate_limit_exceeded(key)) {
            return WAIT_RESPONSE;
        }
        lease_token = generate_lease(key);
        return lease_token;
    }
}

void handle_set_request(key, value, lease_token) {
    if (validate_lease(key, lease_token)) {
        cache_set(key, value);
    }
}

进一步的，FB 还设置了 Stale values 机制，可以让业务来自行选择是否使用略微过期的数据来降低请求等待的时间。当一个 key 被删除时，这个 key 的值被短暂的存储到一个过期数据的地方，但是这个时候memcache里面还没被写入新的值，这个时候如果业务不想等待，那么可以直接取走老的数据，从而加速响应时间。

Memcache Pools 缓存池

memcache因为是一个基础应用，但是需要应对不同应用，那么不同业务的工作负载可能会对 memcache 缓存命中产生负面干扰，导致命中率下降。所以为了应对不同的业务，FB 在 memcache 中按照业务的特点来划分了不同的缓存进行隔离。

FB 将缓存集群划分为：

  1. Wildcard Pool：存储常规数据，采用标准淘汰策略
  2. Small Pool：存放高频访问但缺失代价低的元数据
  3. Large Pool：存储低频访问但重建成本高的批量数据

因为当高低频数据共存于同一池时，会产生 缓存驱逐风暴，高频数据持续写入导致低频数据的 LRU 链提前被截断，低频数据被迫频繁回填，引发数据库查询洪峰。

Replication Within Pools 池内复制

其核心目标是通过数据冗余换取吞吐量提升，适用批量读取密集型场景，比如应用需要单次请求获取大量关联键值。

举个例子，如用户动态页需加载100+社交关系数据：

  • 分片方案：将100键分片到2节点，每节点处理50键请求总吞吐量维持1M QPS，单节点负载500K QPS；

  • 复制方案：2副本各存储完整100键总吞吐量提升至2M QPS，单节点负载500K QPS。

虽然两种方案的单节点负载相同，但复制方案通过减少网络交互次数实现了端到端延迟优化。

Gutter 机制

Gutter 被定义为临时故障接管池，当一个常规的 memcache 服务器发生故障，客户端在访问该服务器上的数据时会超时或失败。此时，客户端会将请求重定向到Gutter服务器。如果Gutter服务器中也没有这份数据（缓存未命中），客户端会从后端数据库获取数据，并将这份数据写入到Gutter服务器中。这样，Gutter服务器就临时接管了故障服务器的缓存职责，吸收了原本会直接冲击数据库的请求。

如果没有 Gutter 服务器，少量memcache 服务器的故障会导致大量请求直接打到后端数据库。Gutter通过提供一个临时的缓存层，有效地缓冲了这种冲击。并且 Gutter中的条目通常设置了较短的过期时间。当故障的Memcache服务器被修复或替换后，系统会逐渐恢复正常，Gutter中的数据也会因为过期而自动清理，避免了复杂的失效通知机制。同时，Gutter的存在使得在少量服务器故障期间，系统仍然能够保持较高的缓存命中率。

也就是说 Gutter 起到了故障转移与负载吸收、防止雪崩等作用。在实践中，该Gutter 将客户端可见的故障率降低了99%，并且每天将10%-25%的缓存失败转换为缓存命中。如果memcache 服务器完全失败，Gutter 的命中率通常在4分钟内超过35%，并且通常接近50%，有效的吸收了负载。

Regional 按区域复制

在单个集群内扩展 memcache 虽然在一定程度上有效，但在延迟、负载管理和容错方面会遇到限制 。随着 Web 服务器数量和请求量的增加，单个 memcache 集群可能会成为瓶颈。并且管理和维护如此庞大的单体集群也带来了运营挑战 。对于频繁访问（“热”）的键，简单地将数据分区到更多服务器上（分片）并不能减轻持有这些键的特定服务器上的负载 。

所以 FB 把 memcache 转向了按区域复制，通过按区域部署分散负载并提高故障隔离能力。FB 将位于同一地理区域内部署多个前端集群，每个前端集群由一组处理用户请求的 Web 服务器和 memcache 服务器组成 ，但是同一区域内的所有这些前端集群共享同一个底层存储集群。

前端缓存层与后端持久存储的分离提供了更高的灵活性，FB 能够流量情况扩展前端的 memcache 实例数量，而数据库基础设施可以根据写入量和数据存储需求独立扩展。

Regional Invalidations 区域失效机制

失效机制主要由一个名为 mcsqueal 的守护进程驱动。存储集群，特别是 MySQL 提交日志 ，是数据修改的真实来源 。mcsqueal 守护进程在每个数据库服务器上运行，并监视已提交的 SQL 语句中是否有修改数据的操作。

检测到相关的数据库修改后，mcsqueal 会提取需要失效的相应 memcache 键 。为了最大限度地减少网络开销，这些失效命令（通常是删除操作）被批量处理成更少的包 。然后，这些批处理的失效消息被发送到位于每个前端集群中的专用 mcrouter 服务器 。mcrouter 服务器解包单个删除命令，并将它们路由到其本地集群中相应的 memcache 服务器 。

image-20250510180752441

Regional Pools 区域池

如果不管数据大小和key的访问热度，而盲目进行复制数据可能导致内存效率低下，尤其是对于大型的、很少访问的 key，所以 FB 使用区域池来管理这部分数据。区域池是同一区域内所有前端集群都可以访问的共享 memcache 服务器集合 。区域池中只存储一个副本，应用程序逻辑负责确定哪些键应该驻留在区域池中。

区域池提供了一种通过维护较少访问数据的单个区域副本，从而减少整体缓存层内存占用量的方法。

Cold Cluster Warmup 冷集群预热策略

当一个新的前端集群上线时，其 memcache 服务器最初是空的，导致缓存未命中率很高 。这种后端数据库请求的突然增加可能导致性能下降和潜在的过载。为了缓解这个问题，FB 采用了一种称为冷集群预热的机制 。

在预热过程中，它会将请求转发到同一区域中一个已经运行并具有良好缓存命中率的集群 。然后暖集群将数据提供给冷集群中的客户端，并且冷集群也会用此数据填充其自身的缓存。这使得新集群能够逐步构建其缓存，其中包含频繁访问的项目，而不会直接压垮数据库 。

Across Regions: Consistency 跨区域一致性

FB 通常会指定一个区域作为数据库的主区域用于写，而其他区域则包含只读的副本 。数据不一致的主要原因是主数据库和位于不同区域的副本数据库之间存在复制延迟 。

来自主区域的写入：mcsqueal 运行在主数据库上，负责提取与数据修改相对应的删除语句。然后，mcsqueal 将这些失效通知广播到主区域内所有前端集群的 memcache 部署。

来自非主区域的写入：FB 为了避免数据不一致的情况，引入了“远程标记”（remote marker）机制 。

当 Web 服务器想要更新键 k 的数据时，会执行以下步骤 ：

  • 在区域池（该区域内多个前端集群共享的 Memcache 池）中设置一个远程标记 rk。
  • 将写入请求发送到主区域，并在请求中包含 k 和 rk，以便在写入复制时失效 。
  • 从非主区域的本地 Memcache 集群中删除键 k 。

随后，当非主区域再次请求键 k 时，会发生以下情况 ：

  • Web 服务器在本地 Memcache 中找不到 k（因为之前已被删除）。
  • 然后，它会检查区域池中是否存在远程标记 rk。
  • 如果 rk 存在，则表明本地副本数据库可能仍然是过时的，因此该查询将被重定向到主区域以获取最新数据
  • 如果 rk 不存在，则表明来自主区域的复制可能已经完成，可以从本地副本数据库提供读取服务。

需要注意的是，当存在远程标记时，由于请求需要发送到主区域，这种机制会在缓存未命中时引入额外的延迟 。

Single Server Improvements 单服务器改进

这里的改进主要从数据结构、锁的粒度、协议：

  • 哈希表扩展：自动扩展哈希表以避免O(n)查找时间，确保高效的数据访问；

  • 细粒度锁定：最初引入多线程使用全局锁，随后改进为细粒度锁定；

  • UDP端口分配：为每个线程分配自己的UDP端口，以减少争用并分散中断处理开销；

  • 使用UDP替代TCP：单次获取提高13%，10键多获取提高8%；

总结

可以看到整片论文其实是围绕着下面几点优化进行的：

  • 传输协议优化：UDP用于查询请求，TCP用于写的请求，这样既可以降低查询请求延迟，也可以保证数据的一致性；
  • 租约机制：租约机制防止陈旧集（stale sets）和惊群效应（Thundering Herd）保证分布式集群下的数据一致性；
  • 池化技术的合理利用：系统分为默认通配符池、小池（频繁但缓存未命中成本低）和大池（不频繁但未命中成本高），使用缓存池来剥离不同的业务场景；并对于频繁访问的数据，复制到多个服务器，减少单服务器负载，优化资源使用；
  • 处理故障：使用 Gutter 接管故障服务器，客户端在无响应时重试到排水池，防止雪崩；
  • 跨区域一致性：主区域处理所有写入，并使用 mcsqueal 同步数据库的修改操作到 memcache 前端集群避免竞争条件；
  • 优化单服务器：最后还要提升单服务器的性能，比如使用细粒度锁定减少锁占用，使用UDP替代TCP等；

Reference

https://read.engineerscodex.com/p/how-facebook-scaled-memcached

https://tech.ipalfish.com/blog/2020/04/07/fb-memcache/