Facebook 扩展 Memcache

来自 Facebook 2013 年论文 Memcache at Facebook。

1 介绍

社交网络基础设施面临的巨大挑战：

1. 接近即时通讯
2. 从多处来源即时聚合内容
3. 能够访问和更新非常流行的共享内容
4. 每秒处理数百万个用户请求

Facebook 改进了开源的 memcached 并构建了一个分布式键值存储，每秒处理超过十亿个请求并存储上万亿条数据。memcached 以很低的开销为共享的存储池提供了低延迟的访问，这是构建数据密集型功能的基础。

• 性能
• 效率
• 容错
• 一致性

到了一定规模以上要求中的某些会变得难以实现：小集群的数据一致性比大集群更易于实现；随着节点数量的增加，网络也会成为瓶颈。

2 概述

以下特性极大地影响了设计：

1. 相比创造内容，用户消费的更多。主要的工作负载是获取数据，缓存有着巨大的优势。
2. 阅读操作从各种数据源获取数据，例如 MySQL 和 HDFS 还有后端服务。这种异构性需要一种足够灵活的缓存策略能够存储来自四面八方的数据。

memcached 提供了简洁的操作集合（set、get 和 delete）。开源版本提供了一个单机的内存哈希表。

查询缓存：减轻数据库的读取负载。

• 读请求：web 服务器先通过 key 从 memcache 查询，如果查不到就去数据库或其他后端服务获取数据并将键值对缓存。
• 写请求：web 服务器应用 SQL 表达式并向 memcache 发送 delete 请求使过期数据失效。

选择 memcache 来解决 MySQL 数据库过多的读取流量是因为权衡工程资源和时间。另外将缓存层和持久层分离使得能够根据工作负载变化单独调整每一层。

通用缓存：利用 memcache 作为更通用的键值存储。

3 集群内：延迟和负载

挑战来自集群中的服务器数量扩展到数千台。在这个规模，大部分精力都用在降低获取缓存数据的延迟或由于缓存未命中带来的负载。

3.1 降低延迟

memcache 应答的延迟是一条用户请求的应答时间的关键因素；单条用户请求经常导致成百上千次 memcache get 请求。Facebook 的一个集群中有上百台 memcached 服务器来降低数据库的负载。所有的 web 服务器在在短时间内与每台 memcached 服务器通信。这种 all-to-all 的通讯模式会引发拥塞或使得单台服务器成为瓶颈。数据副本虽然减轻了单点瓶颈但导致内存效率相当低。

主要通过优化 memcache 客户端来降低延迟，客户端提供了一系列功能：

• 序列化

• 压缩

• 请求路由

• 错误处理

• 批量请求

• 并行和批量请求：最小化网络来回的必要

• CS 通信：将系统的复杂性嵌入无状态的客户端而不是 memcached 服务器中。客户端逻辑被划分为两部分：

  • 嵌入应用程序中或作为独立代理的 lib 名为 mcrouter

  • UDP：

    客户端使用 UDP 承载 get 请求来降低延迟和负载，因为无需建立和维护连接。在峰值负载下，memcache 客户端观察到 0.25% 的 get 请求会被丢弃，其中 80% 是因为超时或丢包，其余的是因为乱序。客户端将 get 错误当做未命中，但 web 服务器不会将查询到的数据插入 memcached，这是为了避免给本就不富裕的网络或服务器雪上加霜。

  • TCP：

    set 和 delete 请求操作基于 TCP。TCP 本身就有重试机制，而 UDP 需要自行实现。

    已打开的 TCP 连接的高内存需求使得 web 服务器每个线程都和 memcached 建立连接的成本高的令人望而却步。通过 mcrouter 合并连接通过降低高吞吐量时网络、CPU 和内存资源提高了网络效率

    

    UDP 和 通过 mcrouter 的 TCP 的 get 请求延迟

• incast 拥塞：memcache 客户端实现流控机制限制 incast 拥塞。当客户端发送海量请求时，同时到达的应答会干崩汇聚层交换机。客户端因此使用滑动窗口机制控制请求数量，类似 TCP 的拥塞控制。

3.2 降低负载

3.2.1 租约

解决两个问题：

1. 过期：并发更新可能会导致 memcache 中的值不是最新的。

   当客户端未命中缓存时，memcached 实例给客户端一个租约（64 位的令牌）来将数据写回缓存。租约与客户端原先请求中的 key 绑定，当客户端在缓存中写入值时提供租约令牌，memcached 能够验证并确定数据是否应该被存储，从而仲裁并发写入。memcached 接收到 delete 请求，失效租约，验证就失败。

2. 惊群：一个特定的 key 经历繁重的读写活动。写操作会失效最近的值，那么读流量会被打向数据库。

   memcached 服务器调节返回令牌的频率。默认每个 key 每十秒返回一个令牌，在令牌签发十秒内请求键值，返回一个特殊的通知告诉客户端等一会再来。通常有租约的客户端在几毫秒成功写数据，因此当客户端重试，数据已经在缓存中了。

3.2.2 memcache 池

将 memcache 作为通用缓存层意味着工作负载要共享基础架构，不同的应用程序会产生负面影响，甚至降低命中率。将集群的 memcached 服务器划分至隔离的池中：例如为频繁访问但缓存未命中的 key 提供一个池；为不经常被访问到的 key 提供一个大型池，这些 key 的缓存未命中开销相当大。

3.2.3 池内多副本

对一些 memcache 池使用多副本提高效率降低延迟。

以下情况考虑多副本：

1. 应用程序并行获取多个键值对
2. 整个数据集都在一两个 memcached 服务器中
3. 请求频率远超单服务器能管理的

3.3 错误处理

无法从 memcache 中获取数据，导致后端服务负载过大，可能造成进一步的故障。必须解决的两个问题：

1. 少量服务器因为网络或服务器故障无法访问
2. 集群内大规模服务器故障

如果整个集群必须下线，那就将用户的请求转移至其他集群。

面对小规模停机，依赖自动化的救火系统。这个系统并不及时，要花个几分钟。这段时间足够引发进一步的故障，因此 Facebook 引入了 Gutter（一小组接管故障服务器的机器）来避免后端服务被冲垮。Gutter 大概占一个集群中 memcached 服务器数量的 1%。

当 memcached 客户端没收到应答时，客户端假设服务器已经坏了然后向一个特殊的 Gutter 池重发请求。

这种设计与客户端在剩余的 memcached 服务器中 rehash 的方式不同：这种方式存在热区风险（一个单独的 key 占 20% 服务器请求），将负载分流至空闲服务器限制了这种风险。该系统减少了 99% 的客户端可见故障，每天将 10%-25% 的故障转换为命中。

4 区域内：多副本

将 web 和 memcached 服务器拆分至多个前端集群，还有一个包含数据库的存储集群，定义为一个 region。这种区域架构的故障域更小而且网络配置更易于掌控。

4.1 区域内失效

region 中存储集群持有数据的权威副本。web 服务器修改数据的同时要让缓存失效。Facebook 为每个数据库部署了一个失效 daemon 叫做 mcsqueal，所以变更数据状态的 SQL 语句要带上 memcache key。这些守护进程会删除区域内所有 memcache 的过期数据。

• 降低发包频率：mcsqueal 将删除操作合并至更少的包中并发送给 mcrouter，mcrouter 拆包后将删除操作路由至正确的 memcached 服务器。

• 通过 web 服务器失效：web 服务器广播失效操作至所有前端集群更简答，但这种方式存在两个问题：

  1. 批量失效相比 mcsqueal 流水线更低效
  2. 当出现系统性失效问题时例如配置错误时很难追溯；相反将失效命令嵌入 SQL 语句，数据库会将其存进日志。

4.2 区域池

过度复制数据会导致内存效率低下，尤其是很少被访问的条目。通过让多个前端集群共享同一组 memcached 服务器来减少副本数，这个被称作区域池。

多副本用更多的 memcached 服务器换取更少的集群间带宽，更低的延迟和更好的容错能力。但对某些数据而言，但副本更节约成本。主要挑战之一是决策一个 key 是否需要在所有前端集群中复制。当区域池中的服务器故障时，Gutter 也会被用到。

4.3 集群启动预热

新集群刚上线时，缓存的命中率非常低，进而威胁到后端服务。预热系统通过允许“冷集群”中的客户端从“热集群”（命中率正常的缓存）中获取数据来缓解这种情况，而不是直接访问持久化存储。这个系统还利用了前面说到的跨前端集群的数据复制，“冷集群”在几小时内就可以达到满载。

必须注意避免源于竞争的不一致。比如一个冷集群中的客户端做了一次数据库更新操作，随后另一个客户端从热集群中获取到过期数据，因为热集群还没收到失效操作，两边就不一致了。memcached 支持延迟删除，在此期间将拒绝 add 操作。默认对冷集群的所有删除都做两秒钟推迟。当在冷集群中未命中缓存，客户端将重新向热集群请求并将其 add 至冷集群。add 失败表示数据更新了，客户端就从数据库获取。预热集群这个操作带来大收益远大于缓存一致性问题的开销。

5 集群间：一致性

数据中心应该异地分布：

1. web 服务器就近部署极大地降低了延迟
2. 异地能够减轻自然灾害或大规模停电带来的影响
3. 甚至可能有当地政策优惠

部署多个区域，每个区域由一个存储集群和多个前端集群组成，指定一个区域来存放主数据库，其他区域包含的都是只读的副本。主要的挑战是维护 memcache 和持久化存储中数据的一致性，都来自一个问题：副本数据库可能落后主库。

系统要在一致性和性能之间权衡。系统管理海量数据，意味着任何会导致增加网络或存储需求的细微变化都会带来可观的成本。Facebook 选择了最终一致性，因为性能和可用性同样重要。

• 来自主（master）区域的写操作：

  主区域的 web 服务器已经完成了对数据库的修改操作，并试图使过期数据失效。然而对副本区域来说失效数据可能为时过早，因为这些变更还未传播至副本数据库中。这时查询副本区域数据库有可能将旧数据回填至 memcache。强制存储集群必须通过 mcsqueal daemon 失效数据避免了这种竞态：在数据被复制完全之前就执行失效操作。

• 来自非主区域的写操作：

  在非主区域更新数据时的复制延迟相当大。用户下一个请求可能令其困惑，因为刚才的修改不见了。只有在复制流赶上进度后才允许从副本数据库中填入缓存，否则接踵而至的请求可能导致副本数据库中的过期数据被获取和缓存。

  Facebook 采用一种 remote marker 机制来最小化读到过期数据的可能性。marker 标记本地副本数据库中的数据是否有可能过期，查询是否应该被重定向至主区域。

  当 web 服务器想要更新数据，key 为 k：

  1. web 服务器在本地区域内设置一个 remote marker rk
  2. 执行主数据库写操作，在 SQL 语句中嵌入 k 和 rk 失效的指令
  3. 在本地集群中删除 k；随后获取 k 的请求必然无法找到缓存的数据，检查 rk 是否存在并选择向 master 还是本地区域查询

  在这种情况下，用额外的延迟来换取降低读到过期数据的可能性。

6 单机提升

all-to-all 通讯模式意味着单服务器会成为整个集群的瓶颈。

6.1 性能优化

从单线程 memcached 进程开始，使用了一个大小固定的哈希表。

所做的优化：

1. 允许哈希表自动扩容来避免查询时间变成 O(n)
2. 多线程
3. 为每个线程开一个单独的 UDP 端口，降低应答时的竞争

最初的 Facebook 多线程单锁实现、细粒度锁和公版 1.4.10。细粒度锁将峰值命中从原先的 600k/s 提升至 1.8M/s；丢失也从 2.7M/s 增长到 4.5M/s。命中的开销更大因为返回值要序列化和传输；而未命中（丢失）只要返回一个静态的结果就行了。

使用 UDP 的表现比 TCP 好。

6.2 自适应 Slab 分配器

memcached 采用 slab 分配器来管理内存。分配器将内存组织为 slab class，每个都包含预先分配好的、大小统一的内存块。memcached 将条目存储在尽可能小的 slab class 中。每个 slab class 维护一张空闲表，提供可用的内存块。每当 memcached 服务器不能申请空闲内存时，就会 LRU 驱逐条目来为新纪录腾地方。

Facebook 实现了一个定期重新平衡 slab 分配以匹配当前工作负载的自适应分配器。它认为这样的 slab class 需要更多内存：它们正在驱逐条目 并且 下一个要被驱逐的条目相至少比其他 slab class 中 LRU 的条目的平均值多了 20%。如果存在这样的 slab class，存储 LRU 条目的 slab 会被释放，并转移至需要内存的 class。

6.3 临时条目缓存

memcached 支持过期时间，但是过期的条目有可能还存活在内存中。memcached 每当收到 get 请求才会执行 LRU 惰性驱逐。虽然普通场景下还算高效，但这种方案还是浪费内存。

Facebook 引入了一种混合的方案，在惰性驱逐的基础上主动驱逐过期的条目。

6.4 软件更新

memcached 服务器能够在几小时内达到峰值命中率的 90%，因此可能需要 12 小时来升级一组 memcached 服务器，因为要非常谨慎处理由此产生的数据库负载。

7 Memcache 工作负载

7.1 web 服务器端的测算

• 扇出

  

  web 服务器可能需要访问的 memcached 服务器分布
  56% 的请求要访问 20 台以内 memcached 服务器；该图也描绘了用户请求受欢迎的页面时的分布，更好地展示了 all-to-all 的通讯模式：访问几百台 memcached 服务器。

• 应答尺寸

  

  memcache 请求的累计应答尺寸
  大尺寸的条目一般是列表化的数据；小尺寸的存储单片内容。

• 延迟

  向 memcache 请求数据的延迟包括请求的路由开销、网络传输时间还有反序列化和解压缩的开销。

7.2 memcache 池统计数据

4 个 memcache 池：

• wildcard（默认池）
• app
• 经常被访问的数据的副本池
• 难得被访问的数据的区域池

每个池每 4 分钟收集统计数据：

这些数据近似于这些池的峰值负载。

副本池有着最高的 get 率；尽管条目尺寸最小，但字节数与数据包数量的比值最大。利用副本与批处理确实能实现更好地性能。

不同的特征使得 Facebook 将这些工作负载相互隔离。

7.3 失效延迟

失效的及时性是决定过期数据暴露概率的关键因素。

Facebook 采样了百万条删除并记录下了删除时间，随后在所有前端集群中查询采样的键值，如果条目仍存在就记录一个错误。

将数据分成两部分：

1. web 服务器对主区域中 memcached 的删除操作
2. 副本区域中对其他副本区域的删除操作

如数据所示，当删除的起源和目标都在主区域中，成功率要高得多。根据经验，失效失败最常见的原因是第一次尝试失败，重试就能解决问题。

9 总结

本文 Facebook 论述了如何基于 memcached 架构将 memcache 扩展至跟上不断增长的业务需求。许多权衡取舍都是为了平衡现实中的工程资源，同时持续地开发来发展生产系统。

在构建、运维和迭代系统中我们学到了：

1. 缓存和持久化存储系统分离使得我们能够单独扩展它们
2. 提升监控、调试和运营效率的功能和性能一样重要
3. 管理有状态的组件比无状态的要复杂的多，因此在无状态的客户端中保留逻辑有助于功能的迭代并最大程度上减少中断
4. 系统必须支持滚动更新，因为可能会导致功能集发生变化
5. 简单至关重要