这是我在SOSP上写的最后几篇论文之一——我正在尝试一些新的东西，并在这里发布我计划阅读的论文队列。这些论文评论可以每周发送到你的收件箱，也可以订阅Atom订阅源。一如既往，请随时在Twitter上发表反馈或建议！
本周的论文是Shard Manager：一个用于地理分布应用程序的通用Shard管理框架。这项研究描述了Facebook为大规模运行分片应用程序开发的框架。
在Shard Manager的上下文中进行应用程序分片。将请求子集分配给应用程序实例，允许任务进行专门化——为请求子集专门化的一组任务称为碎片。
当任务获取状态或其他元数据时，这种方法特别有用。例如，语音识别应用程序可以加载机器学习模型来处理语言。将不同语言的请求分配给不同的切分意味着应用程序的任务不需要下载每个模型（这会占用大量时间和带宽）。
Shard Manager论文不仅讨论了大规模运行分片系统的技术方面，还包括Facebook内部的使用和采用数据。该报关于Facebook内部哪些功能对用户至关重要的信息可能有助于未来的工作优先化@rakyll有一篇关于潜在实现的伟大文章。
Shard Manager论文有五个主要贡献：分析Facebook上的分片使用情况、分片系统的设计和实现、定义分片约束的特定领域语言、将分片放入Facebook数据中心的约束解算器、分析Facebook上的分片使用情况，并对生产中的系统进行了评估。
本文指出了实现Shard Manager的三个主要动机：提高可用性、支持地理分布应用程序和改进负载平衡。
为了提高可用性，Shard Manager旨在顺利处理计划中的数据中心维护Facebook最近在其群集管理器Twine上发表了一篇论文——如果容器在处理用户请求时停止，这些请求将失败，影响应用程序的可用性。对于绝大多数容器，Facebook的基础设施提前知道容器正在关闭。Shard Manager的目标是通过与容器基础设施协调来顺利处理这些关闭事件，确保待关闭的容器停止接收请求，并确保发送到关闭容器的请求被转发到另一个活动实例。
Shard Manager的第二个主要动力是支持地理分布的应用程序（一种独立部署和扩展应用程序碎片的方法）。在Shard Manager之前，服务主要通过区域部署进行配置——为了在Facebook规模上运行，应用程序需要在称为区域的数据中心组中运行，每个区域的配置类似。对于分片应用程序，这意味着保留足够的资源来服务于每个区域的每个分片，即使不需要这些分片——这种限制导致了数据中心资源的浪费。此外，在数据中心或区域维护的情况下，区域部署非常笨拙，因为其他区域可能没有多余的容量来存储每个碎片的额外副本。
改进的负载平衡是Shard Manager的第三个主要动机。地理分布应用程序可以独立灵活地添加和移动碎片，简化了转移负载的过程——系统不需要复制每个碎片，而是可以添加或移动特定的碎片。同时，决定何时以及如何放置碎片是碎片管理器需要解决的一个困难的优化问题。
切分框架的一个关键部分是将请求分配给切分。Shard Manager使用客户端提供的密钥（称为应用密钥）来执行此映射——继续语言服务器示例，对英语的请求发送到X Shard，而对德语和普通话的请求可能发送到Y和Z Shard。
本文还讨论了另一种称为UUID密钥的方法，该方法基于客户端提供的密钥散列将请求映射到碎片。
与UUID密钥相比，使用应用程序密钥有其利弊，UUID密钥主要基于数据局部性——在shard manager的上下文中，数据局部性意味着相似的数据（可能来自世界上相关的用户或地区）被放置在相同或附近的碎片上。本文认为，应用程序密钥提供数据位置，而UUID密钥不提供数据位置。
数据局部性将支持在执行查询时顺序扫描多个碎片等功能。同时，数据局部性可能会增加热点的可能性，在热点中，相似数据的读取都会进入同一个碎片。以前的切分框架方法，如Slicer，请参阅此处关于Slicer的文章，提到添加了对类似应用程序键的方法的支持，以保留数据的局部性，但提到“由于现有存储系统的行为，许多谷歌应用程序已经围绕单键操作而不是扫描构建。”
Shard Manager体系结构有三个主要组件：应用程序客户端/服务器，使用控制平面控制平面，因为它是执行管理和元数据存储操作的层，以及集群管理器。
应用服务器是实际的二进制文件，用于操作碎片并接收来自客户端的请求。每台服务器都有一个库，允许它管理碎片状态（如报告服务器运行状况），注册/取消注册碎片接收请求，并连接到碎片管理事件。当碎片执行管理操作时，它会将状态写入Zookeeper。如果碎片管理器考虑采用Delos，这将是一个有趣的消息。Delos是一个存储控制平面数据的系统，在之前的论文综述中讨论过，持久数据存储。
要调用应用程序服务器，应用程序客户端使用库（称为服务路由器）。客户端的服务路由器根据应用程序密钥（定义从请求到碎片的映射）路由请求，并根据库在服务发现中使用的状态选择可用碎片。有关更多背景信息，请参阅本文中的服务发现。系统随着碎片的添加、删除和缩放，服务路由器会定期在后台轮询以接收更新。
Orchestrator：从应用服务器接收运行状况和负载信息的中间组件。它与控制平面的其他成员（如调度和缩放碎片的组件）共享此数据，并将其传播到服务发现系统，以便应用程序客户端拥有系统的更新视图。
TaskController：与群集管理器通信以请求更多资源（在扩展碎片时）或接收系统事件，如挂起的维护（任务控制器使用它来优雅地关闭碎片）。TaskController会将此信息传播到Orchestrator，以便它能够优雅地完成关闭应用程序服务器和碎片的工作。
基础结构堆栈的下方是群集管理器。有关群集管理器的更多信息，请参阅夹绳纸，它与上面的TaskController通信，以确保计划中的事件（如“即将到来的硬件维护事件、内核更新和容器启动/停止/移动”）得到妥善处理，从而提高应用程序可用性。
本文讨论了Shard Manager功能如何在扩展系统的同时提高应用程序可用性和支持地理分布应用程序。
Shard Manager实现了两种主要技术本文还提到了跨容错域（如多个区域和数据中心）的碎片分布，以提高可用性，但我将碎片分布的讨论推迟到布局和负载平衡。提高应用程序可用性：与群集管理器协调容器关闭，并迁移碎片流量。
协调容器关闭对于提高可用性至关重要，因为它可以确保请求不会发送到可能在响应时关闭的容器。Shard Manager还必须确保计划的维护事件不会一次离线占用太多容量（这会使应用程序处于无法响应所有传入请求的状态）。为了防止这两种情况，Shard Manager的TaskController与群集管理器进行通信，从服务发现中删除即将停用的碎片，并在其他人准备脱机时启动新的碎片。如果无法在维护之前转移碎片，任务控制器可以警告集群管理器，建议的操作将使应用程序处于不安全状态。
Shard Manager还通过实现优雅的切换过程来支持迁移Shard流量。这个过程将正在进行的请求从旧的碎片转发到新的碎片，确保尽可能少的碎片掉到地板上。该系统的流量迁移还旨在切换来自应用程序客户端的任何新请求，这些客户端可能会继续向旧的碎片发送请求——服务发现系统最终是一致的。请参阅亚马逊的沃纳·沃格尔（Werner Vogels）关于最终一致性的这篇博文，因此，客户端可能会暂时使用过时的路由状态。
地理分布应用程序允许将碎片独立部署到Facebook全球的基础设施中。虽然这项技术提供了一些好处，比如独立缩放单个碎片，但它也带来了自身的挑战——选择如何放置碎片以及何时移动碎片是一个困难的优化问题。为了解决与布局和负载平衡相关的优化问题，Shard Manager使用了一个约束解算器，该解算器可配置专用语言来表达约束。
Shard Manager最初使用基于启发式的实现来做出负载平衡决策，这既复杂又难以扩展。因此，系统迁移到约束求解器。本文提到了许多优化技术，包括混合整数规划（MIP）、遗传算法和模拟退火。我远不是这类研究的专家，所以这可能是未来论文评论的潜在主题。
解算器的输入是约束和目标——示例约束是系统稳定性或服务器容量，而示例目标是跨区域的负载平衡（以提高资源利用率）或跨多个数据中心分发副本（以在特定数据中心出现问题时提高可用性）。
应用程序使用特定于域的语言配置其位置和负载平衡VMWare对以编程方式配置群集管理器进行了一些非常有趣且相关的研究，使用声明式编程构建可扩展且灵活的群集管理器。这转化为约束解算器可以使用的形式。尽管Facebook有一个针对数据中心问题的高效约束求解器，该论文还是链接到了SOSP在RAS上的另一篇Facebook论文：持续优化的区域范围数据中心资源分配，Shard Manager进行了进一步的优化该论文提到了局部搜索，它“已经从一个简单的启发式思想发展成为一个在组合优化中吸引越来越多关注的成熟研究领域。”以适应其高请求率。
分区：每个应用程序被划分为多个分区，“每个分区通常由数千台服务器和数十万个碎片副本组成。”
mini Shard manager（mini SM），本质上是单个Shard manager控制平面的副本（在上一节中提到）。每个迷你SM处理服务器和碎片的子集。
在这种情况下，横向扩展“横向扩展”意味着添加更多的迷你碎片管理器以覆盖更多的机器，由于试图让单个Shard Manager覆盖多台机器会很困难，Shard Manager的版本还添加了几个新组件，包括充当与外部系统（如群集管理器和工具）通信的平衡器的前端，应用程序管理器通过多个迷你SMs处理应用程序分区的协调，以及应用程序管理器与之通信以将应用程序分区分配给迷你SMs的分区注册表。
Shard Manager旨在为Facebook内尽可能多的分片应用程序提供支持，并提供数据点，这些数据点对推动采用至关重要。本文论证了与项目动机一致的两个方面的功能的重要性：提高可用性和地理分布部署。
许多迁移到Shard Manager的应用程序都利用了它的可用性功能，尤其是在处理计划事件方面——“70%的SM应用程序选择在容器重启之前优雅地排空碎片。”
论文还指出，地理分布应用程序的采用率也很高——使用Shard Manager的分片应用程序中有67%使用地理分布部署。
本文使用三个标准评估Shard Manager：系统是否在规模上成功，是否能够实现提高应用程序可用性和支持地理分布应用程序的原始目标，以及Shard Manager是否能够充分解决负载平衡的优化问题。
为了评估规模，Shard Manager显示了应用程序、碎片和迷你短信的数量，表明该体系结构能够根据需要进行扩展：
SM总共管理数百个应用程序的近1亿个碎片，这些碎片托管在100多万台服务器上，这些应用程序每秒处理数十亿个请求。SM每月优雅地处理数以百万计的机器和网络维护事件。
为了评估可用性，Shard Manager显示，与不使用优雅迁移策略的应用程序相比，使用优雅迁移的应用程序显示的失败请求峰值更少。本文还展示了碎片升级如何不会导致客户端错误率的增加。
为了评估负载平衡，本文展示了在不断变化的环境和请求速率下迁移碎片以减少网络延迟和负载平衡。
最后，本文展示了改进的约束求解器如何以比基线解算器快得多的速度求解约束——事实上，原始基线解算器无法完成。
Shard Manager论文详细介绍了一个令人印象深刻的大规模生产系统，同时分享了数据点，这些数据点对sharding框架的未来实现者很有用。我特别喜欢这篇论文在优先考虑开发时如何讨论采用和内部用例——我在许多Facebook研究论文中看到过这个主题，包括Delos（我之前在这里讨论过）和RocksDB。我也期待着对开源切分框架感兴趣的人将来的工作，比如@rakyll概述的那个！