“Hi，这是小5自学算力大集群相关知识的第13篇笔记。这一期我们将Facebook的技术方案看看缓存机制是如何实现系统整体性能的提升。”
摘要
这是真实的企业在尝试建立非常高容量的基础设施时所遇到的情况。它是对许多系统在追求极高性能(通过复制等方式实现)与确保一致性之间所面临的基本矛盾的一种诠释。在此过程中，诸如复制等技术实际上成为了一致性的“敌人”。
这里先稍微介绍一下Facebook的环境，它们使用的是PHP技术。PHP技术的一个特点是当用户量不断增大时，首先出现问题的是 PHP 脚本将占用过多的 CPU 时间。此时可以通过增加更多的前端服务器来获得所需的 CPU 处理能力，即多台前端服务器+单个SQL数据库后端服务器的架构。然而随着用户的继续增加，数据库服务器也将会越来越力不从心。
此时就需要使用分布式方案，即部署多台后端数据库服务器，并通过分片的方式将数据存储在不同后端服务器上。它们能够并行执行，并具备大规模的并行读写数据能力。也就是多前端服务器+多后端服务器的架构。但这种方式也还是存在局限性。比如：一种情况是，有时某些特定的热门键，这些键被频繁使用、无论怎样分割都无法真正解决问题，因为每个键只存在于单个服务器上，而其可能出现过载；分片带来的另一个问题是，为了实现分片而增加大量的MySQL 数据库服务器，实际上是一种成本高昂的方式。
那有什么方式可以解决上面所涉及到的问题呢？
- Memcache 技术
Memcache 架构是基于上述多前端服务器+分布式后端数据库服务器架构为基础的，差异点是在两者之间增加多台Memcache服务器从而构成。
当前端需要读取某些数据时，它首先会向其中一台 Memcache 服务器发出询问:“看，你有我需要的数据吗?”。即其向其中一个 Memcache服务器发送一个带有特定键的 GET 请求。Memcache 服务器的的内存中有一张大型哈希表。它会与哈希表中的键进行核对，并发送回数据表示:“哦，是的，这就是该键对应的缓存值。” 即命中了 Memcache 服务器。若在 Web 服务器中未命中，前端则需再次从相关数据库服务器请求数据。即绕过Memcache 服务器，直接请求数据库服务器。数据库服务器将表示：“哦，这是您需要的数据。”为了为下一个需要它的前端缓存它，前端将发送一个带有从数据库获取的数据的 put 请求到那个 Memcache 服务器。
Memcache 通过缓存技术在相同的硬件上每秒能处理更多的读取请求，远胜于单纯使用数据库。由于其在给定硬件条件下，读取速度至少比数据库快10倍，甚至可能更快，因此合理分配一部分硬件资源用于Memcache，同时兼顾数据库服务器确实能带来显著效益。不过仍需将写入操作发送至数据库，因为我们希望写入和更新能够持久存储于数据库磁盘上，即便发生崩溃或其他情况，数据依然存在。
这里就引出了一个疑问：为何 Memcache 服务器不代替前端执行“put’操作，并在向客户端响应之前缓存响应结果呢?
原因在于，Memcache 犹如一款完全独立的软件，它对数据库一无所知，实际上也并非必须与数据库配合使用。而更深层次的原因在于，前端通常并不是真正地在 Memcache 中一对一地存储数据库记录。前端会向数据库发出一些请求，并对结果进行一定处理，可能是将其转换为 HTML 的几步操作。或者是将数据库中多个查询、多行数据的结果汇总起来。此外，还会将部分处理过的信息缓存在 Memcache 中以节省下一个读者重复相同处理的时间。因此，Memcache实际上并不理解前端希望看到的缓存内容与如何从数据库中提取这些数据之间的关系。
这其实可以理解为旁路缓存 (look-aside cache) 与直通缓存 (look-through cache) 之间的区别。旁路缓存策略是:前端会查看缓存，看数据是否已存在。若不存在，它就会自行安排在缺失情况下获取数据。Memcache 是一种旁路缓存，完全不关心是否存在数据库，数据库中有什么内容以及 Memcache 中的内容与数据库中项之间的关系。
任何使用 Memcache 技术的网站都会面临一个问题:若不采取措施，缓存中存储的数据将与数据库中的数据不同步。因此，必须有一个策略来确保在数据库中修改某些内容时，同时对 Memcache 采取相应措施，以处理 Memcache 可能存储的过时数据，这些数据并未反映最新的更新。
同时，使用memcache意味着，你最终将拥有一个系统，它能承受的负载远超数据库所能处理的，甚至高达几个数量级。因此，一旦出现问题，例如你的某个 Memcache 服务器发生故障，导致前端现在不得不直接与数据库通信，因为它们无法使用 Memcache 存储数据，那么数据库的负载将会急剧增加。
- Facebook 方案大致介绍
Facebook 拥有多个数据中心，他们称之为“区域”。主要区域位于西海岸，即加利福尼亚州，而次要区域则在东海岸。每个节点都配备了一组运行 MySQL 的数据库服务器，数据在这些 MySQL 数据库服务器上进行了分片，同时拥有一系列的 Memcache 服务器，这些服务器实际上被组织成了独立的集群。此外还包含了一系列前端服务器。
从性能角度来看，东海岸的用户可以与附近的数据中心通信，西海岸的用户同样也能与附近的数据中心进行通信，这样可以减小网络延时。西海岸的数据中心作为主要节点，而东海岸的数据中心则作为次要节点。它们都拥有完整的数据。这意味着，所有的写入操作都必须发送到主数据库中心的相关数据库中（即东海岸）。他们利用了 MySQL 的一项特性，即一种异步目志复制机制使得主区域中的每个数据库都能将每项更新发送给次区域的对应数据库，从而即使存在几秒钟的延迟这些数据库服务器也能保持内容一致。而读取操作则是本地的，因此，这些前端在需要查找某些数据时通常会与该数据中心的 Memcache 进行通信。如果在 Memcache 中未命中，它们会与同一数据中心的数据库进行通信，并从中读取数据。
- 关于旁路缓存(look-aside caching)策略
首先，若读取的数据可能已被缓存，前端代码执行的第一步便是使用所需数据的键值调用 get 库函数，并生成一个仅针对相关 Memcache 服务器的 RPC 请求。这个库例程在客户端对键进行哈希处理，以选择 Memcache 服务器，并向该服务器发送 RPC请求。Memcache 将始终回应：“是的，这是您的数据”或者它可能会回复 nil ，表示我没有那部分数据。若为 nil，则前端将发出所需的 SQL 查询以从数据库获取数据，随后再发起一次 RPC 调用至相应的 Memcache 服务器以便将获取的数据存入该 Memcache 服务器中。以上是读取操作的常规流程。
而关于写入操作，我们将把新数据由前端发送到数据库。一旦数据库更新了新数据，写库例程便会向 Memcache 发送一个RPC 请求，告知其:“注意，你需要删除这个键。” 而这意味着什么，即下一个试图从 Memcached 中读取该键值的前端将会收到 nil 的返回，因为它已不再缓存中，随后将从数据库中获取更新后的值，并将其存入Memcached 。
实际上，在 Facebook 的方案背景下，之所以需要这种删除操作，是为了确保前端能够看到它们自身的权限。在他们的方案中，每当任何前端向数据库写入内容时，Memcache、MySQL 服务器以及数据库服务器都会发送删除操作。但由于这一过程可能耗时较长，前端也会删除该键，以确保前端不会看到刚更新数据后的陈旧值。
- 关于为”雷鸣般的奔腾”问题
在下面这个场景中，假设我们有一部分数据存在许多 Memcache 服务器上，而其中某台 Memcache 服务器存储了某些数据。有一大群前端通常在读取某一个非常热门的数据，因此不断地发送获取该数据的请求。这台 Memcache 服务器在缓存中拥有这些数据，并回应了它们。
此时，假设某个前端程序介入并对这个非常流行的数据进行了修改。它将向数据库发送带有新数据的写入操作，随后，它将向 Memcache 服务器发送删除指令。现在，我们已经删除了这个极受欢迎的 Memcache 数据缓存。然而，所有之前这些前端都还在不断地发送获取那些数据的请求。它们现在都将同时向数据库发送读取请求。因此，数据库将重复执行相同的工作，以响应最新的该键写入副本，直到前端最终将新键安装到 Memcache 中，随后人们再次开始访问。
我们真正希望的是，如果在 Memcache 中发生了删除操作且未命中，那么第一个未命中的前端能够获取数据并进行安装，其他前端则耐心等待新数据被缓存。
Facebook使用了一种称为租约的手段（这与我们通常所说的租约不同）。仍是请求一个热门的数据。第一个请求缺失数据的客户端前端，当 Memcached 返回错误提示 “哦，不，我的缓存中没有该数据”时，它会设置一个租约，即一种大型的、唯一的数字。它会选取一个租约编号，将其安装在表格中，并将这个租约 token 发送回前端。
然后，其他前端请求同一键值时，它们将简单地被要求等待，并由 Memcached 决定等待时长。因为 Memeached 已经为那个键颁发了租约，所以会告知这些请求等待。获得租约的服务器随后从数据库请求数据当收到响应后，它便会发送针对新数据的 Put 请求，包括所获取的键和值，以及租约以证明它是有权写入数据的一方。
Memcached 将查找租约并确认，然后将执行安装操作。渐渐地，那些被告知等待的其他前端将会重新发起它们的读取请求，而现在数据将会在那里。但如果前端在某个尴尬的时刻崩溃，未能从数据库请求数据，或未能在 Memcached 中安装数据，那么最终 Memcached 会因超时而删除该租赁。下一个询问的前端将会获得新的租赁，我们期望它将联系数据库并安装新数据。
如果一台Memcache服务器发生故障，而我们未采取任何特措施，那么数据库将直接暴露于原本由该 Memcache 服务器处理的读请求之中。这意味着数据库服务器将面临每秒百万次的读取压力。虽然会有自动化的程序替换发生故障的 Memcache 服务器，但这需要耗费一定的时间。
可以通过所谓”沟槽”的临时方案来解决这一问题：存在一组数量较少的备用 Memcache 服务器，它们的存在仅限于在真正的 Memcache 服务器失效时发挥作用，平时则处于空闲状态。当前端接收到错误信息，当无法与Memcache 服务器通信时，它会将相同的请求转发至其中一个备用服务器。如果沟槽服务器拥有该值，则可以直接进行响应；否则，前端服务器将与数据库服务器联系以读取该值。并将其安装到所请求的备份 Memcache 服务器中。
- 关于解决一致性问题
一致性问题在于数据存在许多副本，对于任意给定的数据片段，在主数据库中均有一份副本。而在每个本地集群中，都有一个该键的副本，位于每个本地集群中的其中一个 Memcached 内。当有写入请求时，这些操作必须在所有副本上执行，而且，写入操作可能来自多个源头。
因此，正是并发性、多副本以及权利的多源性，由于存在多个前端，这不仅为陈旧数据的出现创造了机会，还可能导致陈旧数据在系统中长时间滞留。
一个例子是：
一个客户端 C1 需要读取一个键，但 Memcache 表示它没有该数据。所以， C1 将从数据库中读取数据。假设返回了某个值，值为1。同时，客户端C2希望更新此数据。于是它发送写入键值”2”并将其发送至数据库。根据写入的规则，首先是需要从数据库、从 Memcached 中删除它。此时值1已被删除。
然而，客户端 C1 可能反应较慢，最终才向 Memcached 发送一组RPC请求。但它读取的是版本值1，即从数据库中获取现已过时陈旧的数据版本，然而它仍会将这一数据设置进 Memcached 缓存中。并且由于写入规则，很可能会将值2删除。
为了解决上述的问题，仍旧需要使用上文提到的“租约”机制。当 Memcached 返回一个错误指示，表明数据不在缓存中时，它将会授予租约。 Memcached 服务器将会记住这个租约与该键之间的关联。新规则规定，当 Memcache 服务器接收到来自其他客户端或数据库服务器的删除请求时，不仅会删除该项，还会使此租约失效。一旦这些删除请求中的任何一个到达， Memcache 服务器就会从其有效租约表中删除此租约。
因此，由于租约已经存在，如果这些删除操作中的某一个在集合之前到达，这个租约就会被判定为无效，而 Memcache 服务器将会忽略这个集合的设置。这意味着该键将一直缺失于 Memcache 中。下一个尝试读取该键的客户端将遭遇缓存未命中此时会从数据库读取最新数据，并将其存入 Memcache 。而第二次访问时，第二个读者的租约应当是有效的。
如果这些删除操作延迟，发生在集合之后。那么 Memcache 服务器就不会从其租约表中删除该租约。而是会将设置键为过期值，当这些删除操作到达时，陈旧数据将从缓存中被清除。
因此，过时数据会在缓存中停留稍久一些，但不会遇到过时数据无限期滞留在缓存中且永不删除的情况。
- 关于提升性能
其根本方式在于并行化，即并行执行。对于存储系统而言，一种策略是分区，即分片。如将数据分割成10部分，分布在10台服务器 上，这些服务器能够独立运行；另一种利用额外硬件提升性能的方式是通过复制。
Facebook实际上采用了分区与复制相结合的方式。
对于分区而言，一是内存效率高。只需存储每个数据项的单一副本。分区方式的缺点在于，只要键大致上同等流行，它的效果就相当不错。但如果存在几个热点键，一旦这些热点键被分配到不同的服务器上，分区的帮助就不大了。因为无论怎样分区，那个热点键仍然只位于一台服务器上。分区带来的另一个问题是，如果前端需要使用大量数据、多种不同的键，那么最终每个前端可能都需要与多个分区进行通信。至少在使用像TCP这样保持状态的协议时，随着 N 平方级通信的增加，会带来显著的开销。
在复制的情况下，将会在每个服务器上存储每一条数据。如果是少数几个键非常热门，可以为这些热门键制作副本，并且可以并行地服务同一键的每个副本。每个前端可能仅与一个 Memcache 服务器通信，所以通信次数更少，并非 N 的平方级。但不利之处在于，由于每个服务器上都有数据副本，使用复制技术相比分区技术，能够缓存的唯一数据项要少得多。所能存储的总数据量会减少；另一个可能的原因是。在两个站点之间进行完全复制，以便在主站点出现故障时能够将整个操作切换到辅助站点。
为什么 Facebook 决定将区域划分开来，并在每个区域建立独立完整的数据中心，以存储所有数据？
每个区域都拥有完整的一套数据库服务器。每个数据库及其对应的数据服务器存储着相同的数据。假设用户登看的内容大致相同，这意味着不同区域的 Memcache 服务器也在存储着基本相同的数据，即在不同区域进行数据复制。也意味着在数据库服务器和 Memcache 服务器中都进行了数据复制。前端为了响应用户请求而创建单个网页时，往往需要从缓存或数据库中获取数十甚至数百个不同的数据项。因此，前端从 Memcache 中获取这些数百个数据项的速度、延迟和延迟时间变得至关重要。确保前端仅与本地内存缓存服务器和本地数据库通信，并仅以中读取数据，这样才能迅速完成网页所需的数百次查询。
但这会使写入操作成本更高。因为现在如果次级区域的前端需要写入数据，它必须将数据通过互联网传输至整个网络。如果读取操作远比写入操作频繁得多，那这将是一种良好的权衡策略。
此外， Facebook 还在每个区域内使用了集群的概念。集群拥有一批前端和一批 Memcache 服务器，它们几乎是完全独立的。因此集群1的前端会将所有读请求发送到本地 Memcache 服务器，并在未命中时，需要转向一组数据库服务器。
为什么要使用集群的方式？
若不采用此方案，当需扩展容量时，将不得不向同一集群中添加越来越多的 Memcache 服务器和前端。但 Memcache 服务器中的数据大部分内容可能仅被少数用户使用，虽然也存在一些大量用户需要查阅的信息。通过采用复制和分片技术，获得了多个热门键的副本从而在不同集群间实现了对这些键的并行服务。
另一个原因是，集群内的所有数据都会分散在各个 Memcache 服务器上进行分区，任何一个前端通常最终都需要从几乎每一台 Memcache 服务器获取数据。这意味着在前端与 Memcache 服务器之间存在着一种 N 平方的通信模式。为了避免过大的开销，使用的方法是确保没有任何一个集群变得过大。如果前端需要从众多 Memcached 服务器获取数据实际上，它会将请求几乎同时发送出去。这意味着前端将几乎同时从所有 Memcache 服务器获取查询响应。如果不小心处理，将会导致数据包丢失。
最后一个原因是，在这背后存在着一个庞大的数据中心网络。构建既快速（如每秒传输大量比特）又能与众多不同计算机通信的网络，实属不易。通过将数据中心划分为这些集群，并让大部分通信仅在每个集群内部进行，这意味着他们需要一个规模较小、适中速度的网络来支持这个集群，以及一个规模适中、速度合理的网络来支持另一个集群。但他们无需构建一个能够处理所有计算机之间巨大集群间流量的单一网络。
除了每个集群内部的 Memcache 服务器池。还存在一个区域级的 Memcached 服务器池，该池由同一区域内的所有集群共享。在这个区域性池中。他们对前端软件进行了修改。使得前端软件知晓：”啊哈，这个键，该键对应的数据实际上并不常用”。与其将这个不太热门的键存储在我自己集群的 Memcached 服务器上，我打算将其存储在区域池中相应 Memcache 服务器上。
启动集群时可能会遇到一种暂时的性能问题，例如在部署新的集群时，此时可能会有成百上千规模的服务器进行部署，而这个集群并没有缓存任何的数据。这将导致所有通过此集群的请求都指向数据库服务器，从而造成数据库服务器面对的大量的突发性请求。
可以采用“冷启动”的概念。即通过某个标志在某处标记一个新集群处于“冷启动”状态。在这种情况下，当新集群的前端遇到缺失时，它实际上首先会查询其本地的内存缓存。如果回答是：“没有，我没有这些数据”。那么前端将向另一个集群中对应的内存缓存请求数据，该集群为已存有数据的预热集群。只有当本地缓存和预热缓存均未包含所需数据时，前端和新集群才会从数据库服务器中获取数据。这可能需要几个小时的时间，直到 Memcache 服务器和新集群开始拥有所有热点数据。随后便可以关闭这一冷特性，仅依赖本地集群的 Memcache 独立运行。
最后，对于许多大型操作而言，缓存对于在高负载下生存至关重要。缓存的目的并不仅仅是降低延迟，更重要的是为了隐藏相对缓慢的存储服务器所承受的巨大负载。另一个要点是，在大型系统中需要考虑分区与复制之间的权衡。
以上内容来自对 MIT 《分布式系统 6.824》的学习笔记，在此特别声明。