facebook memcache 论文阅读笔记

这篇paper主要价值就是设计一个无敌的分布式kv

本文目录层级如下:

  • 背景:读多写少的系统
  • 基本的读写操作
    • write-invalidate和幂等支持
  • 整体架构
  • 数据类型
  • 优化目标
  • cluster内的优化
    • 延迟优化
      • 整体低延迟方案
        • 请求优化:并行与合并
        • 连接优化:不可靠UDP的读操作、TCP复用链接
      • 突发网络拥塞方案
        • 应用层滑动窗口
    • 负载优化
      • 目标:减少单次load负载和load频率
      • 整体负载减压方案
        • lease机制避免过期写入和阻挡瞬时高压
        • pool机制针对cache miss成本优化空间利用率
      • 故障处理方案
        • gutter机制:用一致性换取可用性
        • 对比rehash
  • region内的优化(WIP)

注:对你没看错,是memcache而不是memcached,memcache指facebook设计的缓存层服务,而它只是底层选用了memcached实现

注2:虽然facebook已经换了名字,但是文章仍然采用facebook的称谓

注3:paper全称是Scaling Memcache at Facebook,文章最下方有链接

读多写少的系统

通常互联网服务大多为读多写少的场合,facebook作为当年全球最大的社交网络也不例外

facebook给出的数据是,读请求相比写高出2个数量级

具体地,每秒读请求为billions($10^{10}$)级别,系统存储量级为$10^{12}$个条目

facebook在这里的意思是:memcache足以承担以上量级的服务

读写操作

读操作:

  • 查cache
  • 如未命中,查DB
  • 如走了第二步,接着set kv


写操作:

  • 更新DB
  • 删除对应cache

写操作使用删除而非更新cache来满足幂等性

写操作之幂等支持

什么场合下需要幂等性?

可能是在有任何异常情况下

  • 返回一个含糊不清的响应状态
  • 很长一段时间没有响应

则允许直接重试,不必担心副作用

这个和超时机制搭配起来很不错

非幂等应该也是可以的,但需要应用层进一步做校验,token之类的,可能不好处理

整体架构

如图所示,一个region对应一个数据中心

单个region内有多个cluster的replica


在部署规模上,单cluster是对应了$10^3$量级的memcached server

数据使用一致性哈希分布于各个memcached中


一个用户与单个web server通信请求服务,单请求需要引起多个memcached通信

见后面“数据类型”和“延迟优化”章节

数据类型

这种应用场合下的数据类型是宽fan-out的

既放射状的读模式

用户表面上读一条数据(item),其实过程中涉及到读上百个数据

优化目标

优化需要是能影响到用户的,而不考虑过于局部的优化

允许读稍微陈旧(不一致)的数据,只要能提高系统整体负载能力

把读到陈旧数据的概率作为一个调参参考(?)

cluster内的优化

cluster内的优化目标为:

  • 减少cache hit时的延迟
  • 减少cache miss时增加的系统负载

延迟优化

前面的“整体架构”中提到web server与memcache服务的通信方式

很显然会造成all-to-all communications


而多对多会造成两个问题:

  • incast congestion
    • 这个有点含糊,大概意思应该是数据短时间突发会造成网络拥塞
    • 我觉得跟拥塞窗口的保守状态有关
  • 单server的热点瓶颈问题


通过实现replica可以解决单点问题,还顺便做到容错

不过这需要花费内存利用率上的成本


facebook的做法主要通过客户端的手段来减少延迟

(顺便一提)这个客户端的功能包括:

  • 序列化
  • 压缩
  • 请求路由
  • 错误处理
  • 请求合并


客户端的优化手段包括:

  • 请求优化
  • 通信连接优化


请求本身的优化主要是parallel并行化以及batching合并

简而言之就是要减少网络上的round trips次数

要实现这一目的可以把数据间的依赖调整为一个DAG图,由于并不存在环,因此可以并行发出请求

同时在必要时合并多个请求,经验值给出可以合并24个key


通信连接优化分为两个层面:

  • client-server通信
  • 传输层连接


在通信层面上

memcached server间互不通信

facebook希望把所有复杂实现下放到无状态的客户端

client通过一个mcrouter的代理与server通信

既web server连接client(proxy)即可,proxy接口仍然保持和memcached server一致

这样避免了单个web server直连多个memcached server


在传输层上

连接尝试尽可能通过使用UDP来减少overhead,比如读请求

UDP虽然不可靠,但是实验给出的数据是:即使处于服务高峰,也仅有0.25%的读请求被抛弃

注:这里并不是基于UDP重造可靠传输轮子,论文中最多只提到UDP上会用序列号标记顺序

如果不可靠请求被抛弃或者存在乱序行为,则是作为client端的错误,这样可以简化处理

比方说,get失败了,则认为是应该走cache miss流程(但是事实上并不引起插入行为,只是复用error handle流程简化代码)

出于可靠性的考虑,set和delete操作仍使用TCP,因为TCP机制上保证了失败重试的机制,而不用基于UDP手写错误处理

在数据上,UDP的引入使得请求整体延迟降低20%

不过,即使使用TCP仍有优化的必要,因为TCP连接本身需要占用更多的内存资源(比如缓冲区),这里略过了


上述是一些整体上的延迟降低方案

对于突发的网络拥塞问题,memcache实现应用层面上的流量控制

实现上就是滑动窗口那一套,只是相比TCP不同在于来自同一个web server的请求会放入到同一个窗口(而不是维护单连接的窗口):当超出窗口范围时,主动拒绝响应,避免级联压垮server

不过具体的实现算法并没有给出,毕竟这是玄学(

负载优化

我们不仅需要依靠replica和sharding来分担负载成本

还需要减少load次数从根本上解决负载问题

除了次数以外,即使数量很少的cache miss也可能引起高负载

lease

memcache引入lease来解决两个问题:

  • 过期写入(stale sets)
  • 瞬时高压(thundering herds)


过期写入涉及到正确性,因为分布式下的请求是异步乱序的,可能一个key被更新后还会收到一个更加旧的写入请求

瞬时写入是指特定的一个key突然有大量的写和读请求,写请求会使得cache失效,每下一次写(使得上一次的写等同于失效)后的读都可能打穿DB,均摊下来每次读请求都非常重量级


lease的具体数据结构为64bit的token,每个lease绑定某一个key

lease的生成时机为发生cache miss时,由memcached server发出


lease可以用于判断当前的写请求(请求时携带lease)对于memcached是否已经过期

如果已经过期,则直接拒绝已减少请求次数,并且保证了正确性


对于瞬时高压问题,memcached server通过控制lease的发放频率来缓解

原理是只有拥有lease的请求才有资格访问DB并写回到cache

facebook给出的经验值是每10秒发放一次lease

在这种情况下,10s内的下一次请求会陷入等待状态

注:也可以选择重试,因为当前处理等待是因为此前含有lease的请求尚未写回到cache中,短期少量的重试可以很快得到已写回的cache中的数据

facebook实验表明这种策略使得DB请求从17K/s降低到1.3K/s


补充关于请求等待的进一步优化

前面说到的等待10秒,是在不期望读到陈旧数据的前提下

只要你接受轻微不一致数据,你可以选择直接返回(旧数据)而不必等待(最新的数据),因此并不会有性能问题

这里隐含的意思是key-value数据结构并不是一个pair of key and value,而是一个大小至少为2的按时间顺序排序的list,删除操作只不过是把数据标记为过期,添加操作是往头部插入数据


因此,对于一个请求失败的错误处理策略可以选择若干组合:

  • 等待
  • 重试
  • 直接拿取旧值

pool

facebook注意到不同的系统有不同的workload,并且memcache是作为通用cache层,全部对接同一套memcache可能不合适

注:这种不同workload来自不同的数据访问形式、内存占用、QoS要求


为了满足不同个性的web server需求,memcache中把一个cluster的memecached server划分为不同的pool


这一部分懒得翻了,并不大感兴趣,往局部性原理靠就好了

简单地说就是把一下cache miss成本比较小的放到small pool中,而成本高的则把相应的pool搞大一点

这些pool因为共享同一块内存(起码单机内是这样),因地制宜的pool大小可以相比通用memcache更好地控制workload

另外还提到pool内进一步replica,暂时没悟出大师怎么把1张100块变成4张50RMB的道理

failures

影响负载还有一个因素是故障处理

如果memcache挂了,那就得提放访问DB引起的高峰workload(当然你也可以选择不可用而不是高可用,直接拒绝服务),还有进一步可能引发级联故障


存在2种不同类型的故障:

  • 小范围内的主机无法访问,可能是个别的网络/服务器问题
  • 大范围的服务挂了


如果整个cluster都大范围下线,需要必须立刻把web请求转发到其它replica cluster,以最快速度移除当前cluster内对memcache的所有的load


对于cluster内小范围的不可用,使用gutter机制来处理

gutter指代的是cluster内预留的小部分平常并不主动使用的主机

小范围不可用需要自动修复,而修复是需要一段时间的

在这一段时间内的高可用(原来应该访问到不可用服务器的请求服务)由gutter服务器(gutter pool)承担

如果gutter pool也无法提供服务才进一步直接访问DB

facebook给出的经验值为gutter占比cluster的1%

比较特殊的是gutter中的key过期速度会相比普通memcached更快,并且限制上层的load速率,尽可能使用相对过期的数据,以避免进一步加剧故障,把可用服务限制到一定水平

更新:key过期应该换一种说法,是处于故障状态时key容易快速过期,gutter的权衡做法是写入操作并不会invalidate cache,因此数据层面的表现为更倾向于使用过期数据(进一步放宽一致性以提高可用性)


facebook顺便在这里对比了用剩余机器直接rehash的做法,分析认为小范围不可用有可能是部分hot key或者访问不均衡(non-uniform key access frequency)造成的,rehash对这种做法并无帮助(hot的还是hot,non-uniform的还是non-uniform),而是倾向于用gutter削掉这部分异常流量,并且不把问题扩散到cluster内外的其它服务器,同时gutter是转移了请求直接冲入DB的风险

在facebook的实践中,这种做法消灭了高达99%的可见故障

可以说是用非常小数目的机器做了非常出色的故障处理策略

region内的优化

前面我们(不是我,是facebook)用了非常多的手段来优化了各个cluster内部的性能

但这还没完,现在聊更加庞大的region

region是多个cluster的replica集合(见“整体架构”章节的图)

------有空再写吧,写一天了!

References

Scaling Memcache at Facebook - Meta Research

发表评论

邮箱地址不会被公开。 必填项已用*标注