MIT 6.824 Lecture 16课堂及论文笔记

前言

入职应用运维一个月，发现早上、中午都能有半小时左右的空闲时间。目前还没忙碌起来，之前说的找下一门课还没想好，那就不如把6.824剩下的课程看完吧，lab 4就还是先不做了，实在太费时间🤣

在这倒数第五堂课里，robert教授主要介绍facebook的一份关于如何在不同规模的系统使用缓存的论文。

Facebook如何使用Memcached

Facebook超大规模社交网络的特性要求它能够：

1. 近乎实时的通信能力（指的是Messenger?）
2. 随时随地从不同来源聚集信息
3. 高效读写热点内容
4. 支持几百万的用户qps

为了支撑这个量级的系统，Facebook大量使用Memcached缓存来规避数据库的读写瓶颈，具体来说，他们把Memcached作为Demand-filled look-aside cache来使用：

1. 对于读请求，服务器收到数据请求时优先查找缓存，假如没有的话，则从数据库中查询并放入缓存中
2. 对于写请求，服务器更新数据库，然后删除缓存（为什么不直接更新缓存呢，论文中简洁地说明了，删除是幂等的，而Robert教授在课堂中也给出了具体的例子，假如更新的话，会在节省内部通信的情况下引入一致性问题）

论文以Facebook系统规模的增长为线索，介绍从single cluster → multi-cluster → multi-cluster around the world三个阶段的发展中，伴随架构改变而来的各种问题，以及Facebook团队是如何处理它们的，下图则是发展至论文发表为止Facebook的整体架构：

可以发现：

• 总共有两个Region，每个Region中有很多个Front-End Cluster
• 每个Front-End Cluster中有多个服务器以及缓存
• 一个Region一套Storage Cluster，其中一个为master，接收所有的写请求，并通过复制同步给follower cluster

Phase 1：Scale within Single Cluster

在一个集群中扩大服务器数量的规模时，facebook要解决的主要问题是延迟以及负载。

由于大量使用memcache缓存，而且缓存服务使用一致性哈希来分散数据，每个用户请求可能会带来大量的缓存查询，比如说，每次加载一个热门页面会带来521个不同的缓存条目查询。为了降低缓存查询的延迟，facebook在论文中谈到了许多个优化点，包括网络优化以及memcache客户端的定制等，其中比较有趣的一个是Parallel requests and batching——facebook把请求所需的数据按照依赖关系构建出它们的DAG依赖图，然后按照这个图最大限度地进行并行查询来提高效率。

当缓存中没有查到数据时，服务器自然需要到数据库中进行查找，在这个阶段的第二个重点便是降低cache miss所引起的数据库负载。

Facebook引入lease机制来缓解缓存失效带来的负载问题（也就是热点缓存失效带来的thundering herd，缓存雪崩现象），同时也解决了缓存潜在的stale set问题（也就是缓存存放了过期数据）。简单来说，memcached中的每一个kv对会绑定一个64比特的lease值，memcache通过在cache miss的情况下发出这个lease和校验请求中的lease来对并发请求进行管理：

• 在对缓存kv进行set操作时，memcached每10秒发出一次lease，拿到lease的客户端就会在cache miss之后到数据库拿数据，而其他访问同样kv的客户端则因为没有lease，不能去数据库拿数据，而是定期重试缓存查询。如此，在热点缓存失效的情况下，只有最先拿到lease的那个客户端会访问数据库，而其他则会不断轮询缓存，如此便避免了数据库面临突发的高负载。

• lease机制同时也解决了由于分布式请求乱序引起的过期缓存的问题。一个简单的例子是读写请求的并发场景：

  1 2 3 4 5 6 7

  client1: reads k from cache -> miss client1: reads k from db -> get v1 --- client2: set k = v2 in db client2: delete k in cache --- client1: set k = v1 in cache

  lease机制避免了这个问题：在一个kv被更新，而引起缓存被删除的时候，memcache会同时把这个kv所绑定的lease给失效，而set缓存请求比较附带有效的lease才能被接受。在上面的场景中，client1因为cache miss拿到了lease，去数据库里面查新的数值，此时client2更新db，删除缓存并使这个lease失效，然后client1拿回旧值以及已失效的lease去缓存中进行请求，memcache由于lease失效而拒绝这次请求。如此，lease的失效便避免了缓存中的stale set现象。

Phase 2: Scale within Region

随着cluster中的服务器与memcache缓存提升，热点数据只会变得更加“热”，整个集群的网络性能将逐步变差。此时，facebook把一些服务器与memcache拆出来，构成新的cluster，而若干个cluster与一个数据库集群构成了一个Region。

这样做的原因在于：

• 网络是无法无限扩容的，一个服务请求基本上可能会访问所有的缓存服务器（由于分区），把服务器与memcache划分到一个个独立的cluster能有效提高网络效率，同时分割failure zone。
• 多个memcache集群维护了多个热点数据的副本，服务器可以并行访问它们他们来提升访问效率。

在这一阶段，facebook在论文中主要讨论允许cluster间共享数据库集群，维护各自的缓存所带来的一些挑战。

Regional Invalidation

维护多套缓存集群的副本带来的一个问题是，在服务器更新数据库集群中某一个kv时，需要有人来负责使所有的缓存集群中的kv失效，facebook的特点是它能够容忍一定时间的stale data，但不能永久过期。由于一个数据库条目对应很多个缓存中的计算结果，而它们又在不同cluster之间维护副本，每次更新都会需要使很多缓存服务器失效，针对这一点，facebook团队做了这些优化：

• 发起更新请求的服务器同时负责把失效发送给自己所在集群的缓存，如此来加速本地缓存更新速度，让同一用户的后续读请求能够读到新值。
• 在修改数据的SQL语句中增添所属事务提交后需要失效的缓存key，在数据库集群中，维护专门的进程负责读取这些key，并在事务提交的时候把失效的key广播到region中的所有缓存集群中。

Cold Cluster Warmup

在集群宕机、维护或者重启时，其所拥有的缓存不在有效，那么所有服务器都必须到数据库中拿数据，这突然的负载可能会击垮数据库资源。为了解决这个问题，facebook引入了cold cluster warmup这个机制。其原理十分简单，当一个”cold cluster”，也就是缓存啥都没有的集群启动的时候，它们的服务器会在缓存没有命中的情况下，从（大概率同region的）正在运行的”warm cluster”的缓存中查找，假如找到就顺便放入自己集群的缓存中，这样在一段时间后（教授说一般几个小时），cold cluster中的缓存的命中率就会趋向其他集群，cluster就从一个冷启动的状态，变成正常运行的状态了。

Phase 3: Scale Beyond Region

当规模扩展至多Region多集群时，集群间数据复制的延迟使得数据一致性成为首要挑战。一个最典型的案例是Follower Region的写入延迟。

但处于非master区域的用户发起写入请求时，由于只有master region被允许处理写请求，系统将其路由至遥远的master区域的服务器，而假如master区域往该用户所在区域的数据复制流延迟很大，那么用户就可能十分诧异地发现自己没有读到最新的修改。

为了解决这个问题，facebook团队引入remote marker这个概念：

1. 当用户更新数据，导致缓存k失效时，系统会生成一个绑定的remote marker Rk
2. 此时系统把k以及Rk一并发到master region的数据库中进行更新，然后删除缓存
3. 当用户再次请求数据k时，假如系统中有Rk，那么请求就会被路由至master region，否则就会在local region中查找（应该当数据复制回来local region时，系统会查找里面的remote marker Rk，然后把它删掉）

后话

这篇论文以及这一堂课不涉及什么全新的分布式技术——单纯只是介绍facebook在大规模跨区域集群中使用缓存的经验与挑战。但分布式系统本身就是一个巨大的工程问题，重点在于根据自己系统的需求，在一致性与性能之间进行取舍，达到对所运行的系统而言各方面综合最优的解决方案。从这个角度来考虑，facebook这篇论文以及这堂课就显得十分有价值了，甚至其更新数据库→删除缓存的做法以及原因已然成为面试八股之一。

这篇论文还有很多facebook遇到的技术挑战以及相应措施，这里就不细说了，论文地址在这里，以后需要再细看吧。