Facebook的可扩展的memcache
原文链接： https://medium.com/@shagun/scaling-memcache-at-facebook-1ba77d71c082
本周，我在阅读了Scaling Memcache at Facebook.
。 该论文记录了Facebook如何在Memcache（当时是简单的内存中缓存）之上创建高性能，分布式键值存储的故事，并对其进行了扩展以支持全球最大的社交网络。
在Facebook的背景下，用户消费的内容比他们创建的要多得多。因此，工作量需要大量读取，并且缓存有助于减少工作量。 Facebook使用Memcache群集，其中每个Memcache实例都是一个满足需求的后备缓存。这意味着，如果客户端从Memcache请求数据而数据不可用，则客户端将从数据库中获取数据，并填充高速缓存以进行进一步的请求。 Memcache不是加载缓存，它不必担心从数据库检索数据的逻辑，并且可以轻松地与多个数据库集成。如果有写请求，则客户端会向数据库发出更新命令，并将删除命令发送给Memcache。删除是幂等的，胜过更新。尽管概述看起来很简单，但实际实现中还有更多细节。 Facebook考虑优化了3个部署规模-
一个集群的服务器，不同集群之间的数据复制，以及遍布全球的集群的数据复制。
单个服务器集群
它们的特点是读强度很高，工作量大，而很多扇出。
知识卡片：扇入：是指直接调用该模块的上级模块的个数。扇入大表示模块的复用程序高。
扇出：是指该模块直接调用的下级模块的个数。扇出大表示模块的复杂度高，需要控制和协调过多的下级模块；但扇出过小（例如总是1）也不好。扇出过 大一般是因为缺乏中间层次，应该适当增加中间层次的模块。扇出太小时可以把下级模块进一步分解成若干个子功能模块，或者合并到它的上级模块中去。
大约44％的请求与20多个Memcache服务器连接。 对于流行的页面，此数字跨越100多个不同的服务器。
点评： 一个请求需要涉及的服务器很多。
原因之一是每个请求返回的数据量非常小。 在get请求的情况下，UDP执行得比TCP好，虽然没有执行插入，但get错误被视为缓存未命中。
这种设计选择似乎是可行的，因为只有0.25％的请求由于延迟/丢失或乱序数据包而失败。 尽管响应大小很小，但变化很大，均值= 954字节，中位数= 135字节。 尽管已合并连接以提高效率，但更新和删除操作仍在TCP上执行（出于可靠性考虑）。
点评： 这边的理解是GET他们选取了UDP来做，更新和扇出选用TCP。
在集群中，数据通过一致的哈希分布在数百台服务器上。 很高的请求率加上较大的扇出导致Memcache服务器与客户端之间的所有通信，甚至单个服务器也可能成为许多请求的瓶颈。
客户端构造一个DAG来表示数据之间的依赖关系，以便同时触发更多独立请求。 Facebook还提供了一个称为mcrouter的独立代理，该代理充当Memcache服务器的接口，并将请求/回复路由到其他服务器/从其他服务器路由。 伴随着这些，提供了滑动窗口的流量控制以限制请求堵塞。
点评： 首先数据是散落在一致性HASH环上的，一个请求有很大的扇出意味着要去访问多个MEMCACHE服务器，构造DAG来判断哪些请求可以并行发送。独立代理解决定位到哪个MEMCACHE服务器上的问题。滑动窗口是为了防止请求拥塞网络。以上是单个集群服务器上做的优化。
租约
租约用于处理过期数据集合（当Web服务器在缓存中写入陈旧值时）和惊群效应（当KEY经历大量读写操作时）。 当客户端遇到缓存未命中时，Memcache会为其提供租约（绑定到请求的密钥的64位令牌）。 当客户端设置租约时，此租约由Memcache验证。 如果Memcache收到密钥删除请求，则该租约无效，并且无法设置该值。 为了减少惊群效应，Memcache每个密钥每10秒仅返回一次令牌。 如果在发出令牌后的10秒钟内发出读取请求，则会在短时间后通知客户端重试，通过该时间，可以在缓存中设置更新的值。 在返回陈旧数据的问题不大的情况下，客户端不必等待，并且可以返回陈旧数据（最多10秒）。
知识卡片：租约和令牌（token）
点评：当客户端要写一个值的时候，为了防止其他客户端不同时写，SERVER会给他一个特权写的时间。允许他在这个时间范围内更新。如果到期了还在写，服务器会通过TOKEN判定出这个租约已经过期，会拒绝写请求。这样就避免了过期数据的写入。详细例子可以看上述知识卡片。因为只有一个拿到租约的客户端可以更新，避免了大量写。大量读的请求如果可以容忍陈旧数据则直接从MEMCACHE里返回，如果不能容忍则让客户端短时间后重试。
内存缓存池
由于不同的工作负载可能具有不同的访问模式和要求，因此Memcache群集被划分为多个池。 默认池称为通配符，然后对于不能驻留在通配符池中的密钥有单独的池。 可以为缓存未命中代价不高的键设置一个小池。 当请求率很高并且数据可以轻松放入几台计算机中时，将在池中复制数据。 在Facebook的背景下，尽管复制具有保持一致性的额外开销，但复制似乎比分片更好。
万一少数Memcache服务器发生故障，一小部分称为gutters的计算机将接管工作。 如果发生的故障更为普遍，则将请求转移到备用群集。
点评：容灾分为池内容灾和集群容灾。缓存未命中的可以建小一点的POOL。 请求率高数据量不大可以在池内复制数据。
regions
多个前端群集（Web和Memcache群集）以及存储群集（数据库）定义了一个region。 存储群集具有在前端群集之间复制的数据副本。 为了处理数据修改，在每个数据库上部署了称为mcsqueal的失效守护程序，该守护程序解析查询，提取和组合delete语句并将其广播到该region中的所有前端集群。 批处理的删除操作将发送到每个前端群集中的mcrouter实例，然后再将各个删除操作解压缩并将其路由到相关的Memcache服务器。 作为一种优化，修改其数据的Web服务器还将无效发送到其自己的群集，以确保单个用户请求的写后读语义。
点评：上述描述了一个REGION中怎么使得数据库和CACHE数据一致的问题。会有一个守护程序去组合语句并广播到REGION里CACHE集群上。一般是发给集群的代理路由，再将各个删除操作路由给相关的CACHE服务器。
这样做的效率是低的，作为优化，可以不用等待守护程序去触发，而是自己群集的无效问题自己解决。确保用户后序的读和写可以快速响应。（因为如果上一次写没更新，后序的读写应被阻塞）
冷集群热身
当新群集上线时，填充它会花费一些时间，并且最初的缓存命中率非常低。因此，采用了一种称为“冷群集预热”的技术，其中使用来自暖群集而不是数据库群集的数据填充新的冷群集。这样，冷群集将在数小时内达到最大容量。但是需要考虑竞争条件。一个示例可能是：冷集群中的客户端进行更新，并且在此更新到达热集群之前，冷集群又对同一密钥进行了另一个请求，因此冷缓存中的项将无限期地不一致。为避免这种情况，一旦执行删除操作，Memcache将拒绝添加操作2秒钟（称为释抑时间）。因此，如果在冷集群中更新值，并且在2秒内发出后续请求，则添加操作将被拒绝，指示数据已更新。选择2秒，因为大多数更新似乎都在此时间内传播。
点评： 冷集群先去问热集群要数据没有再去数据库拿。如果冷集群收到一个删除指令，这个指令还没同步给热集群，又有1个读取指令，发现缓存MISS了，然后去问热集群要到旧的数据添加进了冷集群的缓存。这样冷热集群的缓存发生了不一致，需要一个holdoff时间。
跨区(region)一致性
包含存储群集和几个前端群集的群集部署在不同的区域中。只有一个区域包含主数据库，其余区域充当副本。这增加了同步的挑战。
来自主区域的写入仅在主区域内发送无效指令。将无效指令发送到外部可能会导致竞争状况，即在复制数据之前，删除操作已达到目标。 Facebook使用mcsequal守护程序有助于避免这种情况，但要花费一段时间来提供过时的数据。
点评：
a. 主区某个前端集群收到更新，将更新发给数据库，同时删掉本集群的缓存记录
b. 数据库里的守护进程发现更新提交，发给其他前端集群，用于删除缓存记录。
c. 数据库从主区传播到从区，从区删除过期的缓存记录。
这种情况比较简单，原因是更新发生在主区，从区的缓存过期数据只能来自于过期的数据库的拷贝版，这种从区的过期Memcache无能为力，只能依赖于数据库的一致性模型。
来自非主区域的写入的处理方式有所不同。假设用户以较大的复制滞后时间从非主区域更新其数据。仅在复制流已赶上之后才允许从副本数据库重新填充缓存。远程标记机制用于最小化读取陈旧数据的可能性。标记的存在指示副本中的数据已过期，并且查询被重定向到主区域。当网络服务器更新密钥k时，它会在该区域中设置一个远程标记rk，对具有密钥k的主数据库执行写操作，并删除本地集群中的k。下次尝试读取k时，它将遇到高速缓存未命中，将检查rk是否存在，并将其查询重定向到主群集。如果未设置rk，则查询将转到本地群集本身。在这里引入了延迟，以确保读取最新的数据。
点评1：在从区更新时，对应的键加一个标记。这个标记只能主区更新完毕，传播回从区后才能去掉。在标记存在的期间，键的全部缓存未命中，请求直接转发给主区的集群。用这种牺牲延迟的方式保证最终一致性。
点评2： 上述有2个概念，一个主集群，一个是主数据库。所以我们会有4种不同的数据库。主集群主数据库，主集群从数据库，从集群主数据库，从集群从数据库。当从集群更新密钥K，会在这个集群上打上RK比较。 随后去从集群主数据库更新K，然后删除从集群缓存K。 下次从集群读的时候发现这个RK，虽然缓存未命中，不应该去从集群主数据库拿，而是应该把请求转给主集群。
单服务器改进
Facebook还为单实例运行的Memcache服务器引入了许多改进。这包括扩展Memcache以支持哈希表的自动扩展，而无需将查找时间漂移到O（n），使用全局锁使服务器成为多线程服务器，并为每个线程提供自己的UDP端口以减少争用。
Memcache使用Adaptive Slab Allocator，它将内存组织为slab类(预先分配的大小统一的内存块)。项目存储在可能适合数据的最小slab class中。slab大小从64字节开始，最高可达1 Mb。每个slab class维护一个可用块的空闲列表，并在空闲列表为空的情况下请求以1MB为单位的更多内存。如果无法分配更多的可用内存，则以最近最少使用（LR）的方式逐出。分配器会定期重新平衡平板分配，以跟上工作量。内存在较少使用的slab上释放，并分配给使用更频繁的slab。
大多数项目从内存中被懒惰地逐出，尽管有些一旦过期就被逐出。短期项目将根据项目的到期时间放入链接列表的循环缓冲区（以距离到期还有多少秒为索引），称为临时项目缓存。每隔一秒，缓冲器顶部的存储桶中的所有物品都会被逐出，头部前进一个。通过向一组频繁使用的键添加一个较短的过期时间(这些键的项的使用寿命很短)，这个键族使用的Memcache池的比例从6%降低到0.3%，而不会影响命中率。
作者的收获
Memcache的设计决策不仅取决于直觉，还取决于数据。在做出诸如使用UDP进行读取操作以及为释抑时间之类的参数选择值之类的决定之前，Facebook似乎已经尝试了许多配置。这就是应该的方式-数据驱动的决策。在开发Memcache的整个过程中，Facebook专注于会影响大量用户和用例的优化，而不是针对每个可能的用例进行优化。
Facebook将缓存层与持久层分离开来，这使得单独塑造这两层变得更加容易。通过让应用程序本身维护缓存插入逻辑，Facebook可以更容易地用不同的数据存储插入Memcache。通过将读取过期数据的概率建模为参数，它们允许持久性存储上的延迟和命中率在一定程度上可配置，从而扩展了Memcache的范围。 Facebook将单个页面加载请求分解为多个请求，从而为每个组件提供不同类型的陈旧数据容限。例如，服务于个人资料图片的服务器可以比服务于消息的服务器更长地缓存内容。这有助于降低响应等待时间并减少数据层的负载。
Facebook的Memcache是旨在解决一个相当普遍的问题（可扩展的分布式键值存储）的众多解决方案之一。亚马逊的Dynamo解决方案非常适合小数据量的写密集型工作负载，而Facebook解决了读密集型工作负载的良好解决方案。名单中的其他竞争者包括Cassandra，Voldemort，Redis，Twitter的Memcache等。数量众多的可能的，众所周知的解决方案表明问题有很多方面，其中一些尚不为人所知，我们仍然没有一个可以用于所有用例的解决方案。
我的思考与启发
- 这样大规模的分布式缓存部署，我们要考虑单个集群内，不同集群间，不同REGION间的数据复制问题。
- 单个集群内的优化手段有通过将GET 改造成UDP，如果发生丢包则当做一次缓存MISS。原因是UDP的通讯成本显著低于TCP，因为UDP不需要提前建立连接，也没有诸如拥塞控制，重连等机制。在比较良好的通讯情况下，UDP的通讯失败率（通讯失败指丢包或者乱序包）也相对较低。
- 对请求进行拓扑分析，尽量的并行化请求以及BATCHING请求都是优化手段。
- 为了避免系统内的请求数，写了自己的滑动窗口来控制请求发送量。
- 2~4 是考虑如何降低延迟，另一方面我们需要减少负荷。我们可以通过租约的方式来让缓存击穿问题得以缓解。没有拿到租约的请求会被稍后重试。
- 对CACHE MISS代价高的建一个大池，代价小的建一个小池
- 通过远程标记机制来解决数据跨区一致性的问题。
- 单服务器的改进有支持动态扩展的HASH表，支持多线程，自己维护的内存分配策略和缓存过期策略。也包括条目LAZY 被逐出，和到期被逐出2种手段。在不减少缓存命中率的情况下使得内存利用率更好。
