Scaling Memcache at Facebook 学习笔记-上篇

过年的时候挑挑拣拣地读了《风格感觉:21 世纪协作指南》,特别喜欢连贯之弧那一章。就想着用这个方法提升阅读效率和层次,就有了这篇笔记。找到连贯之弧的感觉确实很棒。

Overview

应用场景的特点:

  1. 读远多于写
  2. 读操作从多种不同种类的数据源获取数据

Use memcache as a demand-filled look-aside cache

memcached 指 memcached 源码或一个运行中的 memcached 进程。memcached 支持的操作集很简单:set, get, delete。
memcache 指基于 memcached 构建的分布式系统。

Query Cache

我们依赖 memcache 减轻对数据库的读负担。将 memcache 用作按需填充的(demand-filled),后备/援(look-aside)缓存。

当 web server 需要数据时,它先从缓存中获取。如果这个 key 还未被缓存,就从后端服务或数据库中获取数据,并放入缓存。对于写请求,web server 将 sql 发送给数据库,然后发送 delete 请求给 memcache,以让该 key 失效(invalidation)。

【注】
数据库更新完成后,在缓存上执行的是 delete,而不是 update。为什么?
因为 delete 是幂等的(idempotent)。幂等意味着对缓存的重复或并发 delete 动作是安全的,不会因此将过期数据放入缓存,还不知道何时该项才会被更新。若是 update,多个请求并发时,很难预测最后放入缓存的数据是哪个版本。

为什么不将 query cache 封装进持久化层,而是分离出独立的 caching 层呢?
因为这样可以根据工作负载的变化来独立调整每一层。

Generic Cache

我们也将 memcache 用作一个更通用的 kv 存储。例如,工程师用它存储从复杂精妙的机器学习算法得到的预计算结果,使得这个结果可以被各种各样的应用使用。

memcache 包含这几个关键服务:configuration, aggregation, rooting service。

在三个不同部署规模上需要关注的问题:

  1. 当只部署了一个服务器集群时,我们的主要关注点在降低读很重的工作负荷和张开的很大的扇出(wide fan-out)
  2. 当需要扩展至多个 frontend 集群时,关注点在解决集群间的数据复制
  3. 当把集群散布在全世界时,关注提供一致的用户体验

Memcache Overall Architecture

我们将部署在一起的集群组织为一个 Region,并指定一个 Region 为 master。master 提供一个数据流,以使其他 non-master region 上的数据保持最新。

当演进系统的时,我们优先考虑的两个设计目标:

  1. Any change must impact a userfacing or operational issue. Optimizations that have limited scope are rarely considered.

    【注】字面意思看懂了,但没太理解这个设计目标的意义。

  2. 将读到临时过期数据的概率作为一个可调节的参数那样对待,类似响应性(responsesiveness)。我们愿意暴露轻微过期的数据以换取使后端存储服务与过度的工作负载隔绝。PS:这个思路很值得借鉴。

In a Cluster: Latency and Load

当一个集群内的服务器规模扩展至数千台时,面临的主要挑战就是降低获取缓存数据的延迟或者由于缓存未命中而施加的负载。(【注】对应上文中提及的第一个部署规模)

Reducing Latency

问题背景:

  1. 单个用户 web 请求常常会产生数百个 memcache get 请求。
  2. 通过一致性 hash 算法,将缓存项(items)分布至所有 memcached server。

结果是,在很短的时间内所有 web server 会与每一个 memcached server 通信。这种 all-to-all 的通信模式会导致 incast congestion,或者单个 memcached server 变成所有 web servers 的瓶颈。

那什么是 incast congestion 呢?
通俗地说,就是当一个上游服务器并行地发送一个同步请求给下游很多服务器,且这些请求的响应几乎同时送到上游服务器时(网络带宽充足且延迟低),在上游服务器的接收端口会发生拥塞。

如何解决呢?

数据复制(Data Replication)常常可以缓解 single-server 瓶颈,但在常见 case 中会导致显著的内存低效(内存浪费,未高效使用)问题。

我们主要聚焦于 memcache client 来降低延迟。client 部署在 web server 上,提供一系列功能,包括 serialization, compression, request routing, error handling 和 request batching。client 维护着所有可用 memcached servers 的地图,并通过一个辅助的配置系统来更新该地图。

Parallel requests and batching

根据要获取的数据之间的依赖关系,构建 directed acyclic graph (DAG),借助它最大化可并发获取的缓存项的数量,最小化网络请求数。

Reducing overhead of client-server communication

memcached servers 彼此之间不通信。保持 clients 无状态(stateless)。client 可以嵌入应用中使用,也可以作为独立的 proxy(命名为 mcrouter) 运行。

对于 get 请求,使用 UDP。web server 中的线程跟 memcached server 直接通信,不经过 mcrouter。UDP 实现负责检测被抛弃或乱序接收的数据包,在 client 中将它们作为 error 对待。它不提供任何机制以尝试恢复。client 将 get errors 作为 cache miss 对待,但 web server 在从后端查询数据后不会将其放入缓存中,避免给此时很可能已过载的网络或服务器增加额外的负担。为了可靠性,对于 set 和 delete 请求,使用 TCP。

client 将请求发送给运行在当前 web server 上的 mcrouter,由它将请求路由给 memcached server,并返回响应。

web servers 凭借高度并行化和过度订阅(over-description)实现高吞吐。如果每个 web 线程与 memcache server 之间都有一个 TCP 连接,那么成本会昂贵得令人望而却步。在 mcrouter 中对连接进行合并/汇合(connection coalescing)可减少维持高吞吐量所需的网络、CPU、内存资源。

Incast congestion

当 memcache client 请求大量的 key 时,如果这些响应全部同时达到,他们可能冲垮机架(rack)和集群交换机(cluster switches)。因此,client 使用滑动窗口机制来控制待处理的请求数。与 TCP 的拥塞控制不同的是,这个窗口应用于所有 memcache 请求,不管请求是由哪个服务器处理的;而 TCP 窗口仅应用于单个流,也就是每个流都有一个拥塞控制窗口。

Reducing Load

【注】 这里降低谁的 load 呢?当缓存读写请求并发量很大时,会发生较多 cache miss,此时如何有效降低后端服务或数据的负载。

Leases

引入 leases 机制解决两个问题:

  1. stale set operations
    并发的缓存写操作乱序,导致最后放入缓存的值非最新值。
  2. thundering herds (惊群效应)
    当一个具体的 key 正经受大量的读写操作时,随着写操作反复使刚放入缓存的值失效,许多读操作从代价高昂的途径(后端服务或数据库获取数据)获取数据。

Leases 机制是如何解决这两个问题的呢?

对于问题一,当 client 遇到 cache miss 时,memcached 实例会给它发放一个 64 位的令牌(token),该令牌与所请求的 key 绑定。client 从后端获取对应的数据后,请求 set 时要提供令牌。借助此令牌,memcached 能够校验并决定是否应该存储数据,对并发写操作进行裁决。如果收到使当前缓存项失效的请求,那么 memcached 就使对应的租约令牌(lease token)也失效。对于一个 key,控制其租约令牌的发放速度,就能控制并发的写操作数。我们配置 memcached server 每个 key 每 10 秒只发放一个令牌,每个 10 秒内就只有一个写操作可以执行。对于 10 秒内没拿到令牌的读请求,server 会返回一个专门的通知结果,告诉 client 等待一小会儿。拿到令牌的 client 成功讲最新数据写入缓存后,当等待中的 clients 重试请求时,缓存就会命中。

问题一的解决思路,基本上也解决了问题二。如果 10 秒内只有一个写操作可以执行,就不会发生在很短的时间内反复使缓存项失效的状况,同时没拿到令牌的读请求等待一小会儿后,重试请求就命中缓存,不会走代价高昂的途径。memcached server 还可以根据自身负载自动调节令牌的发放速度。

借助租约,在某些用例中,我们可以最小化应用的等待时间。对于使用稍微有点过时的数据是可接受的情形,当 key 被失效(即删除)时,将其转移到一个短时间持有最新被删除的缓存项。对于随后的读请求,服务器可能返回令牌或者已被标记为过期的数据。

Memcache Pools

将 memcache 用作通用缓存层需要各种各样的工作负载能共享基础设施,纵使它们有着不同的访问模式,内存占用和服务质量(QoS)要求。不同应用的工作负载放到一起可能产生负面干扰,导致缓存命中率降低。

为了适应这些不同,我们将一个集群中的 memcached servers 划分成独立的 pools。例如,提供一个名叫 wildcard 的 pool 作为默认 pool。为那些频繁访问但缓存未命中时代价不高的 key 准备一个 pool;为那些访问低频但缓存未命中时代价高昂的 key 再准备一个 pool。

当然,还可以根据其他维度划分 pool。例如缓存项的 churn 性质。如果将 low-churn keys 和 high churn keys 放到一起,会发现在不怎么被访问的 high-churn keys 被淘汰之前,仍被频繁访问的 low-churn keys 就被淘汰了。为它们准备不同的 pool 可以避免这种负面干扰,还能根据缓存未命中的代价来调整 high-churn pools 的大小。

【注】
churn 意思是啥?
猜测 churn 意指拿不同的 key 分组相比较时,冷热 key 的变化(数量、频繁)不同。有些分组,热 key (数量、key 列表)比较稳定;但有些分组,热 key (数量、key 列表)频繁变化。

如何度量一个 key family 的 churn?

Replication within a pool

考虑这样一个场景,一个 memcached server 存有 100 个缓存项,能支持 500K RPS。每个请求获取 100 个 key。在开销方便,一次获取 100 个 key 跟 1 个差异很小。现在系统要支持 1M RPS,你选择切分 key 空间,还是把这 100 项复制到一台新的 server?

我们更赞成复制。因为即使把 50% 的 keys 切分到新 server,这两个 server 都还要能支持 1M RPS,负载并没有被分担。而复制后,每个 server 只需分担 50%。不过为了维护数据一致性,采用复制时需要将失效操作(invalidations)传递给所有副本。

Handling Failures

memcache misses 会给后端服务施加过度的负责,这可能引发级联失败(cascading failures)。有两种规模的失败:

  1. 少量缓存服务器不可访问
  2. 影响了集群内极高比例的服务器的大面积服务断供

对于规模一,我们依赖一个自动修复系统。该系统并非即时的,可能要花费好几分钟才能修复好。这段时间足以引发前面提及的级联失败。为此,我们引入一个机制,更进一步将后端服务与失败隔离开。我们准备一个 gutter pool,专用来接过那些失败服务器的职责。Gutter pool 大小占一个集群的 1%。

【注】这小节并未讲述自动修复系统,而是阐述对其进行补充的 gutter pool 机制。

如果 client 未收到 get 请求的响应,它就假定目标服务器已经失败,并将请求再次发送给 Gutter。如果第二个请求仍未得到响应,client 就先请求后端服务,再把数据放入 Gutter。Gutter 中的项会快速过期,以消除发送失效请求的必要。Gutter 以提供轻微过期数据为代价,换取对后端服务负载的限制。

In a Region: Replication

随着需求的增长,购买更多的 web servers、memcached servers 扩展一个集群很有诱惑力。然后,简单地扩展集群并不能消除所有问题。随着添加更多的 web servers 来处理不断增长的用户流量,已经很热的缓存项将会变得更热。随着 memcached servers 数量的增加,Incast Congestion 将会加剧。因此,我们将 web 和 memcached servers 拆分成多个frontend clusters。这些 frontend clusters,连同一个它们共享的包含数据库的 storage cluster,共同构成一个 region。region 架构也考虑了更小的失败域(failure domain,失败的影响范围)和容易驾驭的网络配置,以数据复制换取更加分离的失败域(more independent failure domain),易驾驭的网络配置,和 Incast Congestion 的降低。

【注】

  1. 根据什么维度将大集群拆分成多个 frontend clusters?

  2. 将一个大集群拆分成多个 regions,只有一个 master region 吗?
    从后文得知,只有一个 master,其他全是 replica

  3. 请求在多个 region 间如何分配,或者如何决定将请求路由给哪个 region?
    从后文推测,分配策略应该是根据用户所在地域就近服务。

  4. frontend clusters 和 storage cluster 构成 region,那位于 frontend 和 storage 之间的 service cluster 被排除在外?
    我理解,这里的 region 不包含 service cluster,因为是从缓存的生命周期管理角度来组织 region 的,而非按处理请求的系统架构分层来组织。

Regional Invalidations

一个 region 中,storage cluster 保存着数据的权威副本。用户的读请求会将数据复制到 frontend clusters。为了保持 frontend clusters 与权威版本一致,storage cluster 负责使缓存数据失效。作为一个优化,修改数据的 web server 发送失效请求给自己所在 frontend cluster 中的 memcached servers,以为单个用户请求提供 read-after-write 语义,并减少过期数据在本地缓存中的存在时间。

【注】这里的“本地缓存”指的是 web server 所在集群中的 memcached cache 还是指 web server 进程内的内存缓存?
推测指的是 memcached cache。

修改权威副本的 SQL 会被修缮(amended),以包含一旦事务提交就需要被失效的 memcache keys。在每个数据库上,都部署有一个名叫 mcsqueal 的守护进程,它负责检查提交的 SQL,提取任何删除操作,将它们广播给该 region 的每一个 frontend cluster 的 memcache。

Reducing packet rates

mcsqueal 先将删除操作分批,以减少数据包数量,再将数据包发送给 frontend cluster 中一组专用的 mcrouter 实例。这些 mcrouters 负责解包,并将失效(invalidation)请求路由给位于相同 frontend cluster 中的 memcached servers。

mcsqueal 是可以直接跟 frontend cluster 中的 memcached servers 通信的,但是没有选择这样做,为什么呢?

因为这样做,从后端集群(即存储集群)发送给 frontend cluster 的数据包速率会高得无法承受。

Why not broadcast invalidations via web servers

通过 web servers 将失效请求广播给所有的 frontend clusters 听起来很简单,但这种方式有两个问题:
首先,在 batching invalidations 方面,web server 没有 mcqueal 管道高效。
其次,当系统性的 invalidation 问题出现时,这种方式基本没有提供应对手段。例如,因为配置错误导致删除操作被错误路由。在过去,这常常需要滚动重启整个 memcache 系统,一个我们想要避免的,漫长且制造混乱的过程。

相比之下,将 invalidations 嵌入 SQL 中,SQL 由数据库提交并保存至可靠的日志中,这就允许 mcqueal 简单重放可能会被丢失或错误路由的 invalidations。

Regional Pools

看到这儿时,我的脑袋有点晕,因为概念有点多,得停下来捋捋。

刚开始,所有东西都放在一个集群中:web servers + mcrouters + memcached servers + gutter pool。根据不同的访问模式、内存占用和服务质量要求将 memcached servers 划分成独立的分组就得到 memcache pools。gutter pool 中也是 memcached servers。

然后,随着集群不断膨胀,开始按照如下策略拆分:

  • 起初的那个大集群中的 web servers 和 memcached servers 被拆分成多个 frontend clusters。

frontend cluster = web servers + mcrouters + memcached servers

  • 整个大集群被拆分成多个 regions,一个 master,多个 slaves。

region = some frontend clusters + storage cluster shared by them

现在 regional pool 要粉墨登场了。

如果请求随机路由给所有可用的 frontend clusters,那么所有集群上的缓存数据大致相同。这允许我们下线一个集群以进行维护,而不会降低命中率。但是过度复制数据导致内存使用低效,特别是对于那些很大,很少访问的项。(【注】一些项可能只需少量副本就能提供所需的吞吐量)。让多个 frontend clusters 共享同一组 memcached servers 就可以减少副本数。我们称这组 servers 为 regional pool

对一些数据来说,放弃多副本,在 region 中只保留一个副本,会有更好的成本效益(cost efficient)。在一个 region 内扩展 memcache 的主要挑战之一就是决定一个 key 需要被复制到所有 frontend clusters,还是在 region 中只存一个副本。当 regional pool 中的 servers 失败时,gutter 也会被使用。

【注】

  1. 在 region 内,请求被随机路由给所有集群。在集群内,采用什么算法将请求路由给所有 memcached servers?
    这里有一个矛盾的地方。如果在 region 内,请求被随机路由给所有集群,那么所有集群上的数据大致相同,就无需复制。为什么还要考虑是否需要复制?这部分作者逻辑很混乱。

  2. 全局只有一个 master region,还是多个?如果有多个,在这些 regions 间如何分配请求?对一个缓存项的多次请求,会被分配给不同的 region 吗?

Cold Cluster Warmup

当已有集群失败,或对其进行日常维护时,我们会上线一个新的集群。此时缓存命中率会很糟糕,这会减弱对后端服务的保护能力。Cold Cluster Warmup 系统解决了这个问题。cold cluster 中的 clients 从 warm cluster 中获取数据,而非持久存储。

但需注意避免由竞争条件(race conditions)导致的不一致性。例如,在 cold cluster 中,一个 client 执行一个数据库更新操作(操作完成后会发送 invalidation 请求),紧接着来自另一个 client 的请求从 warm cluster 中获取了过期数据,在 warm cluster 收到 invalidation 请求之前。这个项在 cold cluster 将无限期地处于不一致状态。

Memcached 的 delete 操作(即 invalidation)支持非零的拖延时间(hold-off times)参数,在指定的拖延时间内拒绝 add 操作。默认情况下,所有发送给 cold cluster 的 deletes 的拖延时间参数为两秒钟。在 cold cluster 中,发生未命中时,client 重新请求 warm cluster 并将数据添加(add)至 cold cluster。add 失败则表明更新的数据可用了,那么这个 client 就从数据库获取值。虽然 deletes 延误时间多于两秒仍有理论上的可能性,但对于绝大多数此种情形,这不是真的。cold cluster 较快预热在运维方面的收益远大于罕见发生的不一致性问题的成本。一旦 cold cluster 的命中率稳定了,这种好处就少了,我们就关闭它。

Across Regions: Consistency

我们将多个 region 分布在广阔的地理区域中,每个 region 由一个 storage cluster 和几个 frontend clusters 组成。我们指定其中一个 region 拥有 master 数据库,其他 regions 包含只读副本。我们依赖 MYSQL 的复制机制来保持副本数据库跟 masters 一样新。当跨 regions 扩展时,维护 memcache 和持久存储中的数据一致性就变成要主要的技术挑战。这些挑战源自于一个问题:副本数据库可能会落后于 master 数据库。

面对这些挑战,我们选择尽最大努力实现最终一致性(best-effort eventual consistency),但更强调性能和可用性。

Writes from a master region

前面我们决定由存储集群中的守护程序发起 invalidations。在多 regions 架构中,这有很重要的作用。它避免一个竞争条件:invalidation 在数据被复制到副本数据库之前到达。考虑这样一个场景:master region 执行了一次更新数据库的操作,同步机制正在复制数据到 replica region;master 的存储集群将 invalidation 广播给了 replica 的 web server;replica region 正在处理一个查询该数据的请求。三个动作中,如果复制先完成,放入缓存中的数据肯定是最新的;如果删除先于复制,放入缓存中的数据就可能是过期的。master 将 invalidation 广播给 replica 的 web server,这使得在 replica 中删除操作过早发生,进而增加了把过期数据放入缓存的概率。历史上,我们在扩展到多 regions 后才实现了 mcsqueal。

【注】
该如何将删除同步到 replica region 却没说。我觉得可以这样,将 invalidations 连同数据一起同步给 replica 数据库,数据复制完成后,由 replica 数据库上的守护程序将相应的删除操作发送给 region 内的 web servers。

Writes from a non-master region

考虑这样一个场景,一个 replica region,复制落后很大。一个用户从该 region 更新数据,接着又查询该数据。如果用户的更新丢失,他会很困惑。如果允许在复制赶上之前从副本数据库回填缓存,就会填入过期数据。

我们采用 remote marker 机制来最小化读到过期数据的概率。在 replica region 中,当 web server 想要更新数据库中缓存项 k 对应的数据时,该 server

  1. 在 region 的 region pool 中添加一个 remote marker $R_k$。$R_k$ 本质上是一个缓存项。
  2. 请求 master 执行写操作。将要删除的 k 和 $R_k$ 嵌入要执行的 SQL
  3. 删除 local cluster 中的 k
    随后对 k 的请求到来时,web server 将找不到缓存数据,然后检查 $R_k$ 是否存在。若存在,将查询转给 master,否则在 local region 内处理。

如果在 region 内发生对同一条数据的并发修改,那么其中一个操作可能删除对其他正在进行中的操作来说本应存在的 remote marker。此时,用户仍会看到过期的数据。

Operational considerations

region 间的通信很昂贵,因为数据要穿越很长的地理距离。让删除操作的传播和数据库复制共享通信通道,在低带宽连接上可以提升网络效率。

Regional Invalidations 小节提到的管理删除的系统也跟着副本数据库一起部署,以将删除广播给这个 replica region 中的 memcached servers。数据库和 mcrouters 会暂存 deletes 作为缓冲,当下游组件变得不可响应时。任何组件的失败或迟滞都会增加读到过期数据的可能性。

Resources

打赏
  • © 2016-2020 Konglong
  • Powered by Hexo Theme Ayer
    • PV:
    • UV:

请我喝杯咖啡吧~

支付宝
微信