Scaling Memcache at Facebook
Memcache是一个有名的且简单的纯内存缓存方案。论文主要讲了Facebook基于Memcache来构建一个分布式kv存储来为它的社交网站服务，处理几十亿的QPS，存储了上万亿的数据项
Introduction
本文主要讲述了Facebook如何改进memcached的开源版本，这是一个全内存哈希表的开源实现，能够以较低的开销提供了对存储的访问。Facebook的目标之一是展现部署在不同规模系统的实现，同时需要保持性能、效率、容错能力和一致性。
Overview
论文提到的设计面临的场景是：读多写少，需要能从多个数据源读取数据。
MemCached提供了一组简单的操作（set、get和delete），这使它能够成为大规模分布式系统重要的基础组件。开源版本是一个单机内存哈希表，本文基于这个开源版本构建了一个可以处理每秒数十亿请求的分布式的KV储存系统。下文将用“memcached”来指代它的源码或者它运行的二进制实例，用“memcache”来指代由每个实例构成的分布式系统。
Query cache：依赖memcache来减轻读取数据库的负担。如上图所示，读取的时候先读memcache，不命中再读数据库，查询成功后会更新memcache。写请求则是写到数据库，接着发删除请求到memcache。
Generic cache：论文还讲了如何使memcache成为一个更加通用的kv系统，如保存机器学习算法的中间结果。
在系统的迭代中，论文考虑了两个重要的设计：
- 只有对用户或者运维产生影响的问题，才值得优化；
- 系统可能会暴露轻微陈旧的数据以便后台免受高负载的影响；
In a Cluster : Latency and Load
这一章主要聚焦于拉取缓存数据时的延迟和缓存不命中时带来的负载
Reducing Latency
为了减轻数据库的负载，需要准备由数百台memcache机器组成的缓存集群，但多个web服务器对多台memcache服务器的关系，可能会在短时间内导致incast congestion。数据副本可以缓解这种情况，但又会带来内存浪费。
因此论文中提到的减少延迟的方法主要集中在memcache客户端。
Parallel requests and batching：为了尽可能减少网络请求，该系统通过做拓扑图分析来表示数据间的依赖，整合将多个独立请求，并尽可能进行并发操作。
Client-server communication：memcached服务器之间并不会直接通信，而是相关控制逻辑集成到client上，memcache的client分为两个部分：sdk和一个叫mcrouter的的proxy，mcrouter在web服务器和memcached服务器之间，提供与memcached相同的接口。
考虑到对数据错误容忍度高，memcached client的get请求使用UDP与memcached服务器通信，减少了创建和维护连接带来的开销。一旦出现丢包或者乱序包，client会将其作为异常处理，即视作cache miss，get请求会被重传到数据库，论文中提到系统在高峰期也只有0.25%的请求会被丢弃。为了可靠性，对于set和delete，则是通过可靠的TCP通信。
Incast congestion：对于Incast congestion问题，memcached的client实现了类似TCP的拥塞控制逻辑，根据网络情况控制滑动窗口。
Reducing Load
为了减轻负载，论文提到了三种技术；
Leases
文中引入了租约机制来解决下面两个问题：stale sets和thundering herds，前者是保证了并发更新下的最终一致性，后者则是缓解惊群效应。
对于stale sets，是因为发生cache miss的时候，并发读取数据库后需要重新写入到memcache，这样就可能出现过期的数据在数据被删除之后才写入，导致数据库和memcache内的数据不一致。通过引入租约，每次出现cache miss的时候都会返回一个与key绑定的lease id，当数据被删除后，之前发出的lease id会失效，写入数据时，sdk需要带上上次收到的lease id，根据该id是否失效来仲裁写入与否。
对于惊群效应，当数据出现热点的时候，可能会出现大量的cache miss，导致数据库负载增大。memcache通过控制每个key的lease发送速率，比如每个key在10秒内只发送一个lease id，在这期间有对这个key的请求时，会让客户端等待重试，这时数据可能已经被获得lease的给填上，这时就会重试成功。
过期值：对于某些能接受过期数据的应用，memcache会将已经删除的数据短暂地保存到另一个数据结构中，此时web server可以决定是等待新的数据还是读取过期数据，从而减轻负载。
Memcache Pools
将memcache作为通用缓存意味着所有不同的workloads会共享这一设施，Facebook统计过更新频率高的key很可能会将更新频率低的key给逐出来。
考虑到这一点，Facebook将集群的memcache服务器分割成独立的池，一个默认pool，一个访问频率高但cache miss成本低的small poll，一个访问频率低但cache miss成本高的large pool。
Replication With in Pools
对于某些pool，可以通过数据冗余的方式来提高请求的并发能力。
###Handling Failures
论文对于故障处理主要提到了两个维度的故障：网络故障和集群自身服务器宕机。
对于少数几个server宕机或者网络故障，Facebook主要依赖一个自动恢复机制，如果大规模的停机，Facebook会将用户请求直接转移到另一个数据中心。为了避免在自动恢复的那几分钟里对数据库或者后台服务带来的雪崩，memcached的client会将请求转移到Gutter机器上接管故障服务器的能力。
一般来说，每次失败的请求都会导致转移到Gutter的存取，从而减轻数据库的负载。
In a Region: Replication
随着流量的增大，需要对Memcached做横向扩展，并且能够解决key的热点问题和网络incast congestion，论文在replication和sharding之间做了取舍，选择了将memcached servers切分成多个集群，这一个memcached集群、前端访问集群还有共享存储集群统称为region。
Regional Invalidations
考虑到由于存在多个memcached server集群，需要确保数据的一致性，避免同一条数据的不同版本出现在不同集群上。论文的做法是，监控MySQL，一旦出现数据被删除或者更新，且事务提交，那么对应key就会被一个mcsqueal守护进程记录（读取MySQL的commit log），然后批量地将删除明亮发送给对应的Memcached实例。
Regional Pools
考虑对部分数据的QPS很低，Facebook的做法是不把所有数据在一个region内存储多份冗余，而是在单个region内划分出一个pool来存储那些访问率低的数据。
Cold Cluster Warmup
由于现有集群需要进行定期维护，在新集群上线时，缓存命中率会很低。Facebook构建了一个Cold Cluster Warmup的系统，在新集群发生cache miss时从热集群中加载数据，而不是去读持久化存储。
Across Regions: Consistency
Facebook在全球都有数据中心，因此每个数据中心都会有若干个region来服务用户。基于MySQL的复制机制，Facebook将一个region设为master，其他的都是只读region，web servers请求的时候只会访问本地的DB或者memcache。至于写入，所有的请求只是发给master处理，然后mysql再将其同步到从region。这样就可能带来一致性的问题，即从region的memcache一直保留着过期数据。
对于这种场景，该系统保持一致性的方法是：
如果在master region写，前端集群收到更新，请求转发到数据库，同时删除本集群的memcache记录。数据库的进程同步修改到其他集群，其他region删除过期的记录；
在非master region写数据d：
- 本地的memcache会设置remote marker，rd；
- 将d写到master region的db；
- 将d从memcache中删除；
- 等待master DB同步带有rd信息的数据到非master DB；
- 该非master DB通过解析数据，然后删除掉rd；
在这个过程中，非master region有对该数据d进行读取，并发生cache miss时，如果发现了数据带有rd，则直接跨region访问master DB，否则直接读取本地DB。
总结
论文主要是基于memcache技术来满足Facebook的业务需求，有很多取舍在优化线上系统性能时都非常值得参考。