这篇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集合（见“整体架构”章节的图）
——有空再写吧，写一天了！