前言
这篇paper的主要价值就是设计一个无敌的分布式KV
注1：对你没看错，是memcache而不是memcached——memcache指facebook设计的分布式缓存层服务，而它只是底层选用了memcached实现（理论上，换成别的完全ok）
注2：虽然facebook已经换了名字，但是文章仍然采用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优化以及region优化
cluster内的优化
优化预期
cluster内的优化目标为：
- 减少cache hit时的延迟
- 减少cache miss时增加的系统负载
延迟优化
前面的“整体架构”中提到web server与memcache服务的通信方式，这很显然会造成all-to-all communications
而all-to-all会造成两个问题：
- incast congestion
- 这个有点含糊，大概意思应该是数据短时间突发会造成网络拥塞
- 我觉得跟拥塞窗口的保守状态有关
- 单server的热点瓶颈问题
通过实现replica可以解决单点问题，还顺便做到容错，不过这需要花费内存利用率上的成本
facebook的做法主要通过客户端的手段来减少延迟，手段分为：
- 请求优化
- 通信连接优化
（顺便一提）这个客户端的功能包括：
- 序列化
- 压缩
- 请求路由
- 错误处理
- 请求合并
请求优化
请求优化简而言之就是要减少网络上的round trips次数
优化手段主要是：
- parallel（并行化）
- batching（合并）
要实现这一目的可以把数据间的依赖调整为一个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内预留的小部分平常并不主动使用的主机。实践中，facebook把这“小部分”规划为1%
小范围不可用需要自动修复，而修复是需要一段时间的（数据给出是分钟级别的停顿）。在这一段时间内的高可用（原来应该访问到不可用服务器的请求服务）将由gutter服务器（gutter pool）承担，直到gutter pool也无法提供服务才进一步直接访问DB
比较特殊的是gutter中的key过期速度会相比普通memcached更快，并且限制上层的load速率，尽可能使用相对过期的数据，以避免进一步加剧故障，把可用服务限制到一定水平
更新：“key过期”应该换一种说法，是处于故障状态时key容易快速过期（外部workload导致）。gutter对这种现象的权衡做法是写入操作时并不invalidate cache，因此数据层面的表现为更倾向于使用过期数据（进一步放宽一致性以提高可用性）
gutter对比rehash
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
replica
region是多个cluster的replica集合（见“整体架构”章节的图）：
- 包含多个frontend cluster（既web + memcache）
- 包含一个storage cluster（既DB）
这里的“多”个cluster就是replica副本（图片堆叠部分）
注：frontend是相对于backend的存储层而言
注：facebook在原文中较前的章节提到，用户是按照IP地址来选取replica访问
为什么需要replica
如果不考虑replica，对于横向扩展，一种可行方式就是买更多的机器，把一个cluster做得更大
但是，这种横向扩展是容易到达瓶颈的：
- 用户量增大，单点hot key会变得更热
- all-to-all交互，导致incast congestion随cluster增大而更加严重
因此，需要另一种思维去解决，既replica——通过副本的形式做成多cluster
region级别的失效
daemon
很显然，在这种架构设计下，storage cluster具有权威的数据版本，用户的请求会使得数据按需从DB传递给（诸多）frontend cluster
既然产生了数据的副本，那么需要考虑如何让副本失效，以保证frontend和权威数据的一致性
facebook的设计也是由storage cluster负责副本的失效。在storage cluster层，facebook为每一个DB实例部署了daemon进程（McSqueal），每个daemon会监听SQL语句（commit log），如果一个事务有删除行为，则把删除操作广播到frontend cluster
局部优化
除此以外，有一个利用局部性的优化：改动了数据的web server也会顺手让自己cluster中的cache失效。这样就满足了read-after-write特性，不仅提高了单用户的体验，还减少了本地cache的过期时间间隔
进一步减小包速率
虽然daemon可以直接和每一个memcached server通信，但是这样做的话，从storage cluster到frontend cluster的通信会很频繁
注意一个memcache cluster有很多很多的memcached server！
于是有了进一步的优化：
- daemon合并删除操作，使得网络包数减少
- daemon只和每一个frontend cluster中的一个（或者一部分）memcached server，这些server运行着mcrouter实例（既前面提到的代理客户端），由mcrouter来广播到本地cluster
region级别的pool
其实我们应该考虑是不是所有的cluster都需要做replica处理，如果能针对性优化，那将有助于提高整个region的内存利用率
比方说，对于一些使用率并不频繁的key保留一份就足够了，这些特殊的cluster被定义为regional pool
（后略）
跨越region！
多地数据中心
对于大厂来说，region当然是有多个的
如字面意思，region按地理区域划分，这样做有很多好处：
- 安全第一，避免自然灾害造成对数据的破坏
- 用户体验足够好，网络延迟得到物理性质的改善
- 为公司节约经济成本，多区域可以考虑电费更低廉的地方
一致性
facebook设计的多region是master-slave形式：
- 只有一个master region是可以对storage cluster进行写入操作的
- 其它的region是只读的，既本质上是对master的replica
- 它们的master-slave同步是依赖于MySQL的副本机制
这样做的好处是，任意web server都可以低时延访问本地memcached和DB
而facebook写了很长一段话说我们最终一致性是OK的，这里不细说了。。。
master的写操作
位于master region的写操作很好理解：
- frontend收到写操作，下发到storage，同时删除本地cache
- storage中的daemon解析SQL，发给该region内的其它frontend，让他们广播
- 同时daemon也从master广播到non-master region
第二步就是“region级别的失效”章节描述的内容
non-master的写操作
前面提到non-master region都是只读的，non-master实际的写操作会转发到master region
但这会造成潜在的竞争。如图所示，其竞争的关键点是master到non-master尚未更新完，non-master的frontend又收到了读请求，于是读到了stale data且cached
那么如何解决？facebook引入了一个remote marker机制。简单地说就是写操作前先往cache（对应的key）打上该标记，那么在cache miss时（但是知道有这个marker）会直接往master region的数据库获取数据
全篇完
原文仍有大量的数据可供参考，还有一些单机优化的讨论，感兴趣的可以去翻翻看