使用碎片管理器扩展服务

多年来，随着我们在规模和功能上的扩张，Facebook已经从一个基本的Web服务器架构演变成一个拥有数千项服务在幕后运行的复杂架构。扩展Facebook产品所需的广泛后端服务绝非易事。我们发现，我们的许多团队都在构建自己的具有重叠功能的自定义分片解决方案。为了解决这个问题，我们将Shard Manager构建为一个通用平台，可促进可靠的分片应用程序的高效开发和操作。

使用分片来扩展服务的概念并不新鲜。然而，据我们所知，我们是业内唯一在我们的规模上获得广泛采用的通用分片平台。分片管理器管理托管在生产中数百个应用程序的数十万台服务器上的数千万个分片。

在最基本的形式中，人们熟悉分片作为扩展服务以支持高吞吐量的一种方式。下图说明了典型Web堆栈的扩展。Web层通常是无状态的，并且很容易向外扩展。由于任何服务器都可以处理任何请求，因此可以使用广泛的流量路由策略，如轮询或随机。

另一方面，由于数据库部分的状态，扩展数据库部分不是一件容易的事。我们需要应用一种方案来确定地跨服务器分布数据。像HASH(DATA_KEY)%NUM_SERVERS这样的简单散列方案可以传播数据，但在大规模添加服务器时会出现数据乱序的问题。一致散列通过仅将现有服务器中的一小部分数据重新分配到新服务器来解决此问题。然而，该方案要求应用程序具有细粒度的密钥，以使统计负载平衡有效。一致散列支持基于约束的分配(例如，应将欧盟用户的数据存储在欧洲数据中心以降低延迟)的能力也因其性质而受到限制。因此，只有某些类别的应用程序(如分布式缓存)才采用此方案。

另一种方案是显式地将数据分区到分配给服务器的碎片中。数十亿用户的数据跨多个数据库实例存储，每个实例都可以看作一个碎片。为了提高容错能力，每个数据库碎片可以有多个副本(也称为副本)，根据一致性要求，每个副本可以扮演不同的角色(例如，主副本或辅助副本)。

服务器的碎片分配是通过合并各种约束(如位置首选项)的能力显式计算的，而散列解决方案不支持这些约束。我们发现，分片方法比散列方法更灵活，适合更广泛的分布式应用的需要。

采用这种分片方法的应用程序通常需要一定的分片管理能力才能在规模上可靠运行。最基本的是故障转移能力。在硬件或软件发生故障的情况下，系统可以将客户端流量从故障服务器转移出去，甚至可能需要在健康的服务器上重建受影响的副本。在大型数据中心，服务器总是有计划内停机时间来执行硬件或软件维护。碎片管理系统需要确保每个碎片都有足够的健康副本，方法是主动将副本从服务器移出，以便在认为有必要时将其删除。

此外，可能不均匀且不断变化的分片负载需要负载均衡，这意味着必须动态调整每个服务器托管的分片集，以实现统一的资源利用率，提高整体资源效率和服务可靠性。最后，客户端流量的波动需要分片缩放，系统在每个分片的基础上动态调整复制因子，以确保每个副本的平均负载保持最佳。

我们发现，Facebook的不同服务团队已经在构建自己的定制解决方案，其完备性程度各不相同。常见的情况是，服务能够处理故障转移，但负载平衡形式非常有限。这导致了次优的可靠性和较高的操作开销。这就是我们将碎片管理器设计为通用碎片管理平台的原因。

多年来，在Shard Manager上搭建或迁移了上百个分片应用，在历史上高速增长的上几十万台服务器上，总计有上千万个分片副本，如下图所示。

这些应用程序帮助各种面向用户的产品顺利运行，包括Facebook应用程序、Messenger、WhatsApp和Instagram。

除了绝对数量的应用程序外，它们的使用情形在复杂性和规模上都有很大差异，从具有数十台服务器的简单柜台服务到具有数万台服务器的基于Paxos的复杂全局存储服务。下图显示了广泛的代表性应用程序，其大小由字体大小表示。

多方面的因素促成了这一广泛的采用。首先，与Shard Manager集成意味着只需实现一个由add_shard和drop_shard原语组成的小而简单的接口。其次，每个应用程序都可以通过基于意图的规范来声明其可靠性和效率要求。第三，通用约束优化解算器的使用使Shard Manager能够提供多种负载平衡功能，并轻松添加对新平衡策略的支持。

最后但并非最不重要的一点是，通过完全集成到整个基础设施生态系统(包括容量和容器管理)，Shard Manager不仅支持高效的开发，而且支持安全运行的分片应用程序，因此提供了类似平台无法提供的端到端解决方案。与Apache Helix等类似平台相比，Shard Manager支持更复杂的用例，包括基于Paxos的存储系统用例。

我们抽象出Shard Manager上的应用程序的共性，并将其分类为三种类型：仅主要应用程序、仅次要应用程序和主要-次要应用程序。

仅主副本：每个碎片都有单个副本，称为主副本。这些类型的应用程序通常将状态存储在外部系统中，如数据库和数据仓库。一种常见的范例是，每个分片代表一个工作器，该工作器获取指定的数据、处理它们、可选地服务于客户端请求，并通过可选的优化(如批处理)写回结果。流处理是一个处理来自输入流的数据并将结果写入输出流的真实示例。Shard Manager提供最多一个主要保证，以帮助防止由于重复数据处理而导致的数据不一致，就像传统的基于ZooKeeper锁的方法一样。

仅限次要副本：每个碎片都有多个角色相同的副本，称为次要副本。来自多个副本的冗余提供了更好的容错性。此外，可以根据工作负载调整复制因子：热分片可以有更多副本来分散负载。通常，这些类型的应用程序是只读的，没有很强的一致性要求。它们从外部存储系统获取数据，有选择地处理数据，在本地缓存结果，并根据本地数据提供查询服务。一个真实的例子是机器学习推理系统，它从远程存储下载训练好的模型并服务于推理请求。

主要-次要：每个分片都有两个角色的多个副本-主要和次要。这些类型的应用程序通常是对数据一致性和持久性有严格要求的存储系统，其中主复制副本接受写入请求并推动所有复制副本之间的复制，而辅助复制副本提供冗余，并且可以选择性地提供读取服务以减少主复制副本上的负载。ZippyDB就是一个例子，它是一个带有基于Paxos的复制的全局键值存储。

我们发现，以上三种类型可以模拟Facebook上最分片的应用程序，截至2020年8月的分发百分比如下所示。67%的应用程序是主要的-仅由于体系结构的简单性和与传统ZooKeeper的基于锁的解决方案的概念相似。但是，就服务器数量而言，仅主应用程序仅占17%，这意味着仅主应用程序平均比其他两种类型的应用程序小。

在应用程序所有者决定如何将他们的工作负载/数据分成碎片以及哪种应用程序类型适合他们的需求之后，在Shard Manager上构建分片应用程序有三个简单、标准化的步骤，与使用情形无关。

应用程序链接Shard Manager库，并使用插入的业务逻辑实现Shard状态转换接口。

应用程序所有者提供基于意图的规范来配置约束。分片管理器提供四组主要的开箱即用功能：容错、负载平衡、分片伸缩和操作安全。

碎片状态转换接口我们的碎片状态转换接口由如下所示的一组小型但坚实的命令性原语组成，通过这些原语可以插入特定于应用程序的逻辑：

Add_shard调用指示服务器加载传入的分片ID标识的分片，返回值表示转换的状态，比如分片加载是进行中还是出错。相反，Drop_shard调用指示服务器删除碎片并停止为客户端请求提供服务。

此接口使应用程序可以完全自由地将碎片映射到其特定于域的数据。对于存储服务，add_shard调用通常触发来自对等副本的数据传输；对于机器学习推理平台，add_shard调用触发将模型从远程存储加载到本地主机。

在上述原语之上，碎片管理器构建了一个高级碎片移动协议，如下所示。Shard Manager决定将一个碎片从负载较高的服务器A移动到负载较轻的服务器B，以平衡负载。首先，Shard Manager向服务器A发出DROP_SHARD调用，并等待其成功。其次，它对服务器B进行add_shard调用。该协议最多提供一个主服务器保证。

上述两个基本原语是典型应用程序要实现分片和实现可伸缩性所需实现的全部。对于复杂的应用程序，Shard Manager支持更强大的接口，下面将详细介绍。

在上述协议中，处于过渡状态的分片的客户端在分片不在任何服务器时都会出现暂时不可用的情况，这对于面向用户的应用来说是不可接受的。因此，我们开发了一个更复杂的协议，该协议支持无缝所有权移交，并将碎片停机时间降至最低。

UPDATE_Membership I构造分片的主成员来验证和执行副本成员资格更改，这对于基于Paxos的应用程序最大化数据正确性非常重要。

上述界面是我们对分片应用程序进行全面分析和体验的结果。事实证明，它们足够通用，可以支持大多数应用程序。

对于分布式系统，故障是常态，而不是例外，知道如何为故障做好准备并从故障中恢复对于实现高可用性至关重要。

复制：通过复制实现冗余是提高容错性的常用策略。分片管理器支持在每个分片的基础上配置复制因子。如果单个故障域的故障可以关闭所有冗余副本，则复制的好处微乎其微。分片管理器支持跨可配置的故障域分布分片副本，例如区域应用的数据中心大楼和全局应用的区域。

自动故障检测和分片故障转移：分片管理器可以自动检测服务器故障和网络分区。在检测到故障之后，立即构建替换副本并不总是理想的做法。碎片管理器通过配置故障检测延迟和碎片故障转移延迟，使应用程序能够在构建新副本的成本和可接受的不可用之间进行适当的权衡。此外，当网络分区发生时，应用程序可以在可用性和一致性之间进行选择。

故障转移调节：为了防止级联故障，Shard Manager支持故障转移调节，这限制了碎片故障转移的速率，并保护其余健康的服务器在重大停机情况下不会突然过载。

负载均衡是指将碎片及其工作负载持续均匀分布在应用服务器上的过程。它实现了资源的高效利用，避免了热点。

异构硬件和碎片：在Facebook，我们有多种类型和多代硬件。大多数应用程序需要在异构硬件上运行。对于工作负载/数据无法均匀分片的应用程序，分片的大小和负载可能会有所不同。分片管理器负载均衡算法考虑了每个服务器和每个分片(副本)的细粒度信息，因此同时支持异构硬件和分片。

动态负载收集：分片的负载可能会因其使用情况而随时间变化。如果应用程序可用容量与动态资源(如可用磁盘空间)相关联，则可用容量可能会有所不同。碎片管理器定期从应用程序收集每个副本的负载和每个服务器的容量，并实例化负载平衡。

多资源平衡：Shard Manager支持使用各种用户可配置的优先级同时平衡计算、内存和存储等多个资源。它确保瓶颈资源的利用率落在可接受的范围内，并尽可能平衡不太重要的资源的使用。

节流：与故障转移节流类似，负载均衡生成的碎片移动量是按照总移动量和每台服务器移动量的粒度进行节流的。

上述对空间和时间负载可变性的通用支持适合于分片应用程序的不同平衡需求。

Facebook的许多应用程序直接或间接地服务于用户的请求。因此，流量呈现出在高峰和非高峰时间之间请求率显著下降的周日模式。

弹性计算根据工作负载变化动态调整资源分配，是一种在不牺牲可靠性的前提下提高资源效率的解决方案。针对实时负载变化，分片管理器可以进行分片伸缩，即当分片的每个副本的平均负载偏离用户配置的可接受范围时，可以动态调整复制因子。碎片扩展限制可以配置为限制给定时间段内添加或删除的副本数量。

下图展示了一个分片的伸缩流程。最初，所有复制副本的总负载都会增加，因此每个复制副本的负载也会增加。一旦每个副本的负载超过上限阈值，碎片缩放就会生效并添加足够数量的新副本，以将每个副本的负载恢复到可接受的范围。随后，分片负载开始减少，分片伸缩会减少副本数量，以释放不需要的资源供其他热点分片或应用程序使用。

除了故障，运营事件也是常态而不是例外，并被视为一等公民，以将其对可靠性的影响降至最低。常见操作事件包括二进制更新、硬件维修和维护以及内核升级。碎片管理器与容器管理系统Twin共同设计，以实现无缝事件处理。TWine聚合事件，将它们转换为容器生命周期事件，如容器停止/重新启动/移动，并通过TaskControl接口将它们传递给Shard Manager Scheduler。

Shard Manager Scheduler评估事件的破坏性和持续时间，并进行必要的主动碎片移动，以防止事件影响可靠性。分片管理器保证每个分片必须至少有一个健康的副本，这一点是不变的。对于具有多数仲裁规则的基于Paxos的应用程序，Shard Manager支持保证的变体，以确保大多数副本是健康的。操作安全性和效率之间的权衡因应用程序而异，可以通过配置进行调整，例如同时受影响的碎片的上限。

下图显示了一个具有四个容器和三个碎片的应用程序示例。首先，请求一个短暂的维护操作，如影响Container 4的内核升级或安全补丁，并且Shard Manager允许该操作立即进行，因为所有的Shard在其余服务器上仍有足够的副本。接下来，请求容器1到3的二进制更新。观察到并发更新任意两个容器会导致碎片不可用，Shard Manager按顺序将更新应用于容器，一次一个。

我们在Facebook使用公共路由库来路由请求。路由库接受应用程序的名称和分片ID作为输入，并返回一个RPC客户端对象，通过该对象可以简单地进行RPC调用，如以下代码所示。发现碎片分配位置的魔力隐藏在create_rpc_client之后。

在本节中，我们将深入探讨如何构建碎片管理器来支持我们讨论的功能。我们将首先分享我们的基础设施的分层，特别是分片管理器的角色。

在Facebook，我们的整体基础设施是采用分层方法构建的，各层之间的关注点有明显的分离。这使我们能够独立、稳健地发展和扩展每一层。下图显示了我们的基础设施的分层情况。每一层都分配并定义相邻上层运行的范围。

主机管理：资源分配系统管理所有物理服务器，并为组织和团队分配容量。

容器管理：TWINE从资源允许系统获取容量，并以容器为单位将其分配给各个应用程序。

产品：这些是面向用户的产品，如移动应用程序，由分片的后端应用程序提供支持。

除了每一层对相邻较低层的向下功能依赖之外，整个基础设施堆栈都是通过向上传播的信号和事件共同设计和协同工作的。具体地说，对于Shard Manager层，TaskControl是我们实现协作调度的机制。

中央控制平面碎片管理器是一项纯控制平面服务，可监控应用程序状态，并协调在碎片中的服务器之间移动应用程序数据。集中式全局视图使Shard Manager能够计算全局最优的碎片分配，并通过整体协调所有计划的操作事件来确保高可用性。在此中央控制平面关闭的情况下，应用程序可以使用现有的碎片分配继续以降级模式运行。

带有状态转换接口碎片的不透明碎片对于Shard Manager是不透明的，用户可以将其映射到其应用程序中的任何实体，例如数据库实例、日志组和数据桶。我们定义了每个应用程序必须实现的碎片状态转换接口。这种清晰的描述使Shard Manager有别于特定于应用程序的数据平面，并在可以利用Shard Manager的用例方面提供了巨大的灵活性。

碎片粒度