Facebook 的构造文件系统：Exascale 的效率

今天的论文是 Facebook 的 Tectonic Filesystem: Efficiency from Exascale from FaST '21。这篇论文涵盖了 Facebook 的 Tectonic 文件系统、它的实现以及他们做出的各种设计决策。我将总结这篇论文，并深入探讨其中的一些亮点。虽然文件系统论文和系统有着丰富的历史，但阅读这篇 Tectonic 论文还是很不错的，因为许多经常被引用的论文已经有点长了。谷歌文件系统 (2003) 论文已有近 20 年的历史，但在野外被引用的次数超过了 Bill Murray。 1 还有一些更现代的论文，主要来自 Microsoft，如 Windows Azure Storage (2011) 和 Azure Data Lake Store (2017)，但很高兴看到来自不同公司的一些东西。 Tectonic 使用胖客户端架构，支持直接从磁盘到客户端的数据流，并使用分片元数据服务为文件系统提供服务。 Tectonic 将元数据层分成三个部分：(1) 名称层，(2) 文件层，和 (3) 块层。每个层负责一部分元数据，并且所有层都作为无状态微服务实现在 ZippyDB 之上，ZippyDB 是一个水平可扩展的键值存储。由于元数据层是完全独立的，每个层都可以独立缩放以处理其负载。 Name 层提供目录树抽象，将目录映射到它们包含的文件和目录。文件层从文件映射到它们的组成块。块是对连续字节串的抽象，隐藏了它们的存储或编码方式。文件只是块的有序列表。在 Tectonic 中，块使用复制编码，其中 \(N\) 个相同的块每个存储块的完整副本，或者使用 Reed-Solomon 编码，其中块被编码为 \(X\) 数据块和 \(Y\ ) 代码/奇偶校验块。块层包含从块到其编码及其组块集的映射。 Tectonic 的最后一部分是 Chunk Store，它是它自己的分布式数据存储，其中节点存储原始字节块和一些最小元数据，以从块 id 映射到存储在本地、修改过的 XFS 文件系统上的字节。 Name 层、File 层和 Block 层的模式在论文中的这张表中：

Name 层维护从目录到子目录和其中包含的文件的映射，并由目录的 dir_id 分片。 File 层从文件映射到其逻辑块列表，并由 file_id 分片。 Block 层从块映射到存储它的块/磁盘列表，并由 blk_id 分片。块层还维护从每个磁盘到存储在其上的块列表的映射。这种反向映射对于维护很有用，例如，当磁盘丢失时，这种映射允许后台维护任务准确枚举哪些块需要向上复制或以其他方式重建。 ZippyDB 将键组合成分片，并保证具有相同分片 id 的所有键值对都放置在同一个分片中。这意味着由 dir_id 分片的 Tectonic 的 Name 层可以从单个分片快速提供一个目录中所有子目录和文件的强一致性列表，而它的 File 层，由 file_id 分片，可以为所有的列表做同样的事情。文件块。但是，不能保证子目录与父目录位于同一分片上，并且 ZippyDB 不提供任何跨分片事务，因此不支持大多数递归文件系统操作。 Tectonic 的 ZippyDB 模式还将列表存储为（键，值）对的完全“扩展”组合。也就是说，对于包含子目录 bar 和 quux 的目录 foo，Tectonic 存储两个单独的键 (foo, bar) 和 (foo, quux)，并使用前缀键扫描 foo, 处理目录 foo 的列表请求。这种扩展的列表格式用于降低向已经拥有数百万个文件的大型目录添加或删除单个条目的成本，因为 Tectonic 不必反序列化、编辑、序列化和写回一百万个条目列表。 Tectonic 具有单写入器、仅追加语义——这意味着 Tectonic 禁止多个并发写入器写入一个文件，并且文件只能追加到。为确保单写入器语义，每当客户端打开文件时，它都会获得一个写入令牌，该令牌与文件一起存储在元数据层中。每当客户端希望写入文件时，它必须包含写入令牌，并且只有最新的写入令牌才被允许改变文件元数据并写入其块。当控制路径通过元数据层和 ZippyDB 时，数据路径直接从客户端到块存储节点。这减少了整个系统所需的网络带宽，以及在网络上移动字节所需的计算。 Tectonic 的胖客户端对其读取和写入具有非常细粒度的控制，因为它直接进入块存储节点来读取和写入单个块。这允许客户端针对不同的工作负载进行调整，例如，是否优化写入的持久性或延迟。与可能在整个文件系统中强制执行单个配置的其他系统相反，Tectonic 客户端还可以针对每个文件甚至每个块调整这些参数。 Tectonic 使用常见的仲裁提交或仲裁写入技术来优化客户端执行全块写入 - 只需要客户端持久地写入块的所有块副本中的大多数以提交块。举例来说，对于具有 3 个副本的 \(R(3.2)\) 复制文件 2 Tectonic 只需要客户端在考虑提交的块之前完成对其中 2 个副本块的写入——这有助于尾延迟 3。如果最后的第三个副本块写入失败，Tectonic 的后台维护服务将通过修复第 3 个块副本来修复块。

除了这种常见的优化之外，Tectonic 还使用了一种称为 Reservation Requests 的巧妙技术来优化全块写入，这类似于 The Tail At Scale 中讨论的对冲请求。为了激发预留请求，我们将首先绕道而行，看看对冲请求、它们的优点和缺点，以及为什么预留请求可能更适合 Tectonic 的用例。对冲请求是一种延迟优化，您可以将请求发送到可能的多台服务器，并接受来自最快服务器的第一个响应，而不是为一项工作发送单个请求。不只是重复大量工作的关键是，不是立即将请求发送到多个服务器，而是等待一点，其中“一点”意味着您期望正常请求需要多长时间。如果回复仍未到达，那么您“对冲”您的赌注，即该服务器将在合理的时间范围内响应并将相同的请求发送到另一个副本。对冲请求有助于改善长尾延迟，因为您可以避免客户端在取得任何进展之前必须等待可能不健康的节点响应其请求的情况。然而，对冲请求的一个问题是，它们可能会导致接收服务器完成的工作量激增，以及额外请求和响应所需的额外带宽——这是存储系统所关心的像构造。此外，Tectonic 客户端不能真的只是选择另一个随机存储节点来写入他们的数据，他们必须与元数据层协调，以便元数据准确反映哪些节点存储哪些块。相反，Tectonic 使用保留请求，这些请求很小，类似于 ping 请求，客户端发送到多个块存储节点来决定将其数据实际写入哪些节点。 Tectonic 选择最先响应的块存储节点作为进行实际写入的节点，假设可以快速响应的节点当前没有过载。预留请求不携带任何用于实际写入的数据，因此它们使用的带宽非常少，并且处理成本非常低。例如，如果客户端正在写入 \(R(3.2)\) 复制文件，则客户端将首先向 5 个块存储节点发送预留请求。客户端选择最先响应的 3 个存储节点来实际发送 3 个写入请求。通过这种方式，数据仍然只广播到 3 个节点，但是首先通过预留请求进行的快速健康检查减少了客户端等待不健康或卡住的节点的可能性，从而减少了尾部延迟。预留请求不使用任何额外的带宽或处理，但与对冲请求相比确实有缺点。由于全块写入必须首先执行这些预留请求，因此它们会为每个写入增加一点延迟。这就是为什么预留请求仅用于全块写入，在这种情况下，写入的数据量足够大，这种延迟开销是可以接受的更好的尾部延迟的折衷。我假设预留请求在实践中运行良好，但我感兴趣的是预留请求提供的健康检查和负载平衡信号必须是多近的，以避免最糟糕的尾部延迟。我可以想象一个使用较少检查频率的系统可能仍然能够提供预订请求的大部分好处，同时还减少了完成的工作量。

Tectonic 还通过仲裁追加来优化小于块大小的追加，类似于完整块写入。优化有助于减少尾部延迟，但对于部分块追加而不是完整块写入，仲裁提交要正确实现有点棘手。如果您正在编写一个完整的块，那么您不必担心并发写入器争相写入同一个块，但是对于较小的写入，这可能是一个问题。为了说明可能发生的可能错误，请考虑一个 \(R(3.2)\) 文件，该文件的块大小为 8MB，多个客户端附加到单个块。客户端A追加512字节，成功提交追加到第一个和第二个块，但写入第三个块副本失败。然后客户端 B 控制文件并附加另外 512 个字节，但第二个块副本失败，第一个和第三个成功。最后，客户端 C 控制了文件并附加了另外 512 个字节，但是第一个块写入失败，而第二个和第三个成功。剩下的第一个块副本长度为 1024 字节（第一和第二次追加），第二个副本长度为 1024 字节（第一和第三次追加），第三个副本长度为 1024 字节（第二和第三次追加）。读者会看到文件元数据报告的块长度为 1536 字节，但实际数据块都不是那个长度！并且没有一个块包含相同的数据！并且不清楚在完成这些写入时读者可能会阅读什么！或者，如果所有的块都以相同的数据结束！或者，如果这篇博文中的其余句子将以感叹号结尾！ 4 Tectonic 处理这些潜在问题的方式是强制执行两条规则：(1) 只允许创建块的客户端附加到它，以及 (2) 客户端向元数据层提交新的块长度和校验和之前确认仲裁附加到应用程序。虽然论文没有明确说明这一点，但我认为单个客户端会将其追加序列化到给定的块存储节点——也就是说，如果它执行第一次追加和第二次追加，它将等待第一次追加到在将第二个 append 写入存储节点之前成功。通过客户端完成这种序列化，并强制只有一个客户端可以写入块，我们上面的竞争不会发生，因为客户端将在写入第二个追加之前等待第一个追加发生在块存储节点上。这可以确保多个作者不会互相踩踏。在每个仲裁追加之后提交块长度和校验和，但在向应用程序确认之前向读者保证他们可以读取的内容。这意味着应用程序应该具有写后读一致性，因为 Tectonic 向应用程序确认的任何数据都已持久提交到两个块存储节点，并将新长度提交到元数据层。一般来说，这意味着如果 Tectonic 报告的块长度为 \(B\) 字节，那么至少 \(B\) 字节已经被提交到两个块存储节点，并且任何客户端都可以读取到 \(B\)字节，并保证它们是正确的。许多工作负载是“一次写入，很少读取”，这意味着数据应该进行 Reed-Solomon 编码而不是复制以减少存储开销。但是，数据通常以交互方式写入，并且写入延迟对客户端很重要，因此使用复制编码来减少尾部延迟 5 是有意义的。利用复制写入改进的延迟，同时还具有提高了 Reed-Solomon 编码的字节效率。

通过让客户端以复制编码写入块，Tectonic 可以吃蛋糕，也可以吃它，但是一旦块已满并密封，客户端将在后台将块重新编码为 Reed-Solomon。通过我们讨论的所有优化，应用程序通过这种方式获得了复制写入的改进延迟，但 Reed-Solomon 存储的空间效率。从论文中不清楚如果客户端应用程序崩溃会发生什么，但我假设有一个后台服务可以将完全写入的块重新编码为 Reed-Solomon。 Tectonic 使用副本集复制来最大程度地减少在遇到协调磁盘故障时数据丢失的可能性。 Copyset 复制真的很聪明，但我们将不得不稍微备份一下，以讨论在尝试将数据放置到磁盘上时存在的困难问题和权衡。在选择将数据写入哪些磁盘时，在磁盘可能出现故障的情况下，需要在数据丢失的可能性与每个数据丢失事件丢失的数据量之间进行权衡。例如，如果对于所有 \(R(3.2)\) 复制文件，您将每个块副本写入随机选择的磁盘，则任何 3 个磁盘故障将导致某些复制文件的数据丢失事件的可能性越来越大。这是因为对于每个块，我们随机选择一组 3 个磁盘来存储其块，并且随着我们向系统添加更多块，最终每组 3 个磁盘将存储某个块的所有块副本。这意味着对于随机磁盘选择，当我们由于数据中心故障而丢失磁盘时，发生数据丢失事件的概率最高。然而，每个数据丢失事件丢失的数据量非常低，因为一个块的块副本恰好位于一组失败的磁盘上的可能性很小，因为它们是随机选择的。一种思考方式是，如果 3 个磁盘发生故障，则丢失块的预期值较低，但至少丢失一个块的概率很高。但是，您可以想象另一种方法，将所有节点分成 3 个节点的集合，称为副本集。当我们想将一个块的块分配给存储节点时，我们首先为该块选择一个副本集，然后将块副本分配给该副本集的 3 个节点。在具有 9 个节点的数据中心中，节点 \([1,2,3]\) 可能是一个副本集，\([4,5,6]\) 将是另一个副本集，而 \([7,8,9]\ ) 将是最后一个。在该方案中，只有3个三节点故障会导致数据丢失，即只有一个副本集的所有节点丢失才会导致一个块的数据丢失。这是一个非常低概率的事件，因为在可能的 \({9 \choose 3} = 84\) 个三节点集合中只有 3 个集合会导致数据丢失。相比之下，随机节点复制最终会使所有 84 个三节点集成为某个块的副本集，因此副本集复制比随机复制提高了 28 倍，以降低数据丢失的概率。但请记住，对于副本集复制，每个数据丢失事件丢失的数据量会非常高——分配给副本集的所有块都将丢失。虽然丢失所有数据可能不是正确的权衡，但我们可能会在每个事件丢失更多数据的情况下进行权衡，以减少任何数据丢失事件的可能性。这是因为任何数量的数据丢失都会导致大量固定的数据恢复工作开销，作为运营商，我们真的希望尽可能避免它。这是我们寻找更好的方式将块分配到磁盘的动机。

除了影响数据丢失的概率之外，我们如何将块分配给节点也会影响我们假设的解决方案必须处理的系统的其他属性。在我们的 naive 3 copyset 设置中，如果节点 1 发生故障，我们只能从节点 2 和 3 恢复该数据，这可能会将这些节点上的负载增加 50%。对于随机磁盘选择设置，如果一个节点出现故障，我们可以从所有剩余节点恢复数据，因为数据已均匀分布在所有 84 个副本集上。因此，随机磁盘选择在提供潜在恢复工作的良好负载平衡方面具有优势。然而，如果我们打破严格的副本集设置，并允许一个节点上的数据潜在地复制到更多的其他节点，那么我们可以更快地从单个节点故障中恢复，并且不会在所有节点上施加太多负载。剩余节点。让我们将存储单个节点数据副本的节点数称为散点宽度。在上面 9 个节点和 3 个副本集的示例中，我们的分散宽度为 2，因为只有 2 个其他节点拥有任何其他节点数据的副本——节点 1 的数据也在节点 2 和节点 3 上。但是，如果我们引入了 3 \([1,4,7]\)、\([2,5,8]\) 和 \([3,6,9]\) 的更多副本集然后现在节点 1 上的数据可以在任一节点 2、3、4 或 7，因此分散宽度现在为 4——允许我们更快地从节点故障中恢复。总而言之，我们希望拥有较高的分散宽度以确保我们可以从大量节点恢复数据，但我们也希望将副本集的数量保持在较低水平以降低发生数据丢失事件的可能性。想出一个方案来做这两件事是一个不平凡的问题。 Copysets 论文为这个问题提供了一个近乎最优的解决方案，称为复制集复制，旨在创建给定散布宽度的少数副本集。换句话说，副本集复制降低了数据丢失事件的可能性，同时仍然允许节点之间的良好负载平衡。这篇论文解释了他们的算法如何是最优的，但核心思想是你创建系统中所有节点的排列，然后通过将排列组合成连续节点的运行来从排列中形成副本集。您可以通过创建更多排列来增加分散宽度，但这将创建更多副本集，因为额外的排列将具有不同的节点改组，从而导致不同和更多的副本集。但关键是副本集数量的这种增加将尽可能小，从而使数据丢失事件的概率尽可能低。当客户端需要写入块时，首先随机选择一个节点作为主节点，这将副本集集限制为每个排列一个。您可以选择一个随机排列及其副本集，或者在 Tectonic 的情况下，块层从对应于该块 ID 的排列中选择副本集，以排列数为模，以使其具有确定性。

虽然相对于副本集方案初始放置是最佳的，但磁盘仍然会出现故障或被取出进行维护，因此后台重新平衡器服务也尝试将块的块保留在其原始副本集中。 Copyset 复制和 Tectonic' ......