数据布局服务与局部性管理 · OSDI '18

『看看论文』是一系列分析计算机和软件工程领域论文的文章，我们在这个系列的每一篇文章中都会阅读一篇来自 OSDI、SOSP 等顶会中的论文，这里不会事无巨细地介绍所有的细节，而是会筛选论文中的关键内容，如果你对相关的论文非常感兴趣，可以直接点击链接阅读原文。

本文要介绍的是 2018 年 OSDI 期刊中的论文 —— Sharding the Shards: Managing Datastore Locality at Scale with Akkio¹，这篇论文实现的 Akkio 能够在多个数据中心之间管理数据的局部性，显著地降低用户访问数据的延迟。Facebook 在 2014 年开始在生产环境中投入使用 Akkio，它可以降低 50% 的用户访问延迟、50% 的跨数据中心数据传输以及 40% 的存储空间。

图 1 - Akkio 架构

Facebook 将 Akkio 称作数据布局服务（Data Placement Service），它可以管理分布式数据库中万亿级别的小分片，决定如何移动、何时移动分片以提高全球用户的访问性能并减少数据存储的占用²，它的核心逻辑其实是统计用户访问的相关数据，根据用户对不同数据中心的访问频率，在不同数据中心之间重新布局和迁移数据提高整体的访问局部性并降低延迟。

虽然通过访问局部性提高性能是该系统带来的优点，但是我们还是要了解该系统出现的背景和动机，系统的作者在论文中列出了研发 Akkio 数据布局服务的五个不同的原因：

• 减少资金和运维的成本（Capital and operational costs matter）— 减少数据的副本数、存储空间和跨数据中心的网络通信；
• 服务请求运动（Service request movements）— 访问数据中心的请求可能会随着时间不断变换，每个用户访问的数据也会不断变化；
• 读写比率较低（Low read-write ratios）— 大多数的数据库和业务都会有比较高的读写比例，然而 Facebook 大多数业务的读写比率低于五，因为写的频率非常高，所以完全复制的数据会导致明显地跨数据中心通信；
• 分布式缓存效率低（Ineffectiveness of distributed caches）
  • 如果缓存命中率比较低并且目标数据不在当前数据中心，那么用户请求的平均读延迟会非常高；
  • 因为要写入的数据很可能在其他数据中心，所以低读写比例会导致跨数据中心传输频繁；
  • 大多数的数据集都需要对外提供强一致性的保证，但是这会带来跨数据中心的数据拷贝；
• 分离局部性管理层（Separate locality management layer）
  • 分片的大小是数据存储谨慎挑选的，它的主要目的是管理负载均衡和错误恢复；
  • 局部性存储管理系统不能适用所有的场景，它是对特定场景进行的优化；

本文接下来会详细介绍 Akkio 的设计原理、架构以及整个系统中最重要的数据布局服务的职责，帮助各位读者快速理解如何在多数据中心中管理数据的局部性。

架构与设计

我们在这里简单介绍一下 Akkio 的设计与架构原则，首先是 Akkio 遵循的三大设计准则：

1. 引入了新的抽象 μ 分片（μ-shard），将 μ-shard 依赖到数据库底层的分片上以获取副本、一致性和负载均衡方面的支持；
2. 使用异步的方式执行大多数的操作，只有在访问数据时，查询分片位置的操作才是同步的；
3. 减少了与底层数据库存储的耦合，可以快速适配不同的数据库，提高系统的可移植性；

作为客户端应用程序和数据库之间的中间层，Akkio 会对相邻的两个模块提出需求，通过相邻模块提供的信息和功能，该系统才能发挥应有的作用：

• Akkio 需要客户端满足以下三点需求：
  1. 客户端需要主动将数据划分到不同的 μ-shard 中，同一个 μ-shard 中的数据可以提供非常好的访问局部性；
  2. 客户端也需要为它拥有的 μ-shard 指定全局唯一的键以便访问；
  3. 客户端在访问数据时，需要通过 μ-shard 的主键显式地指定数据所在的 μ-shard 分片；
• Akkio 需要底层数据库满足以下两点需求：
  1. 数据库需要保证同一个 μ-shard 中的数据不会跨越多个分片；
  2. 数据库需要为 Akkio 迁移时保证强一致性提供支持；

图 2 - Akkio 和相邻模块

当客户端和底层的数据库满足上述的这些需求时，Akkio 就能很好地完成它的工作，为应用系统提供好的局部性以提高访问的性能。

Akkio 的系统设计如下图所示，局部性管理系统需要将一部分逻辑嵌入到客户端，客户端会通过 ZippyDB 的客户端获取数据，在获取数据的过程中，我们会调用 Akkio 的客户端获取数据所在的位置并访问对应的数据库获取期望的数据，而组成 Akkio 的三个服务会协助处理整个过程：

图 3 - Akkio 系统设计

• Akkio 位置服务（Akkio Location Service、ALS）维护位置数据库，客户端会调用 getLocation 函数获取分片所在的位置，当分片在数据中心之间迁移时，位置数据库就会更新；
• 访问计数服务（Access Counter Service、ACS）维护访问计数数据库，该服务会追踪客户端的所有访问数据，这些访问数据会决定 μ-shard 的布局和迁移，所有的数据统计过程都是异步的，不会影响访问数据的核心路径；
• 数据布局服务（Data Placement Service）会决定 μ-shard 的布局位置以减少访问延迟和存储空间，该服务会初始化并管理 μ-shard 的迁移，当客户端会异步地通知 μ-shard 的布局可能不够合理时，它会根据访问计数服务中存储的数据决定重新评估是否需要进行迁移；

上述三种服务分别负责了不同的事情，它们的职责非常明确，其中前两者的设计与实现非常简单，无论是为客户端提供位置信息，还是统计用户的访问数据，这些都是相对比较常见的功能，这里更关注的其实是数据布局服务，我们会在下面重点介绍它。

数据布局服务

Akkio 的核心就是数据布局服务，该服务负责将 μ-shard 映射到对应的位置上并负责迁移 μ-shard 以提高局部性。该服务会对外提供两个主要的接口，分别是 createUshard 和 evaluatePlacement，其中前者负责创建新的分片，后者负责评估分片的布局。

数据布局服务会在它的数据存储系统中存储 μ-shard 的迁移信息，这些信息可以防止系统同时对一个 μ-shard 执行多次并行迁移，也能够在数据布局服务宕机时提供足够的信息用来恢复。我们在这里会介绍数据布局服务处理的三种常见任务，分别是：创建新分片、决定分片布局和分片迁移。

创建新分片

当新的 μ-shard 分片被创建时，数据布局服务需要决定当前分片的存储位置。在通常情况下，我们都会在距离请求的客户端最近的数据中心选择副本存储数据并在相邻的数据中心中选择负载较轻的作为备份。使用数据布局服务创建新的分片主要是为了避免分片的竞争条件，我们也可以直接使用简单的哈希函数来决定数据存储的数据中心，整个系统收集的数据会让分片迁移到更合适的位置。

决定分片布局

数据布局服务在迁移数据时，会在一组副本中根据访问数据选择分数最高的副本的进行迁移，除了考虑数据的访问情况，我们还需要考虑数据中心的可用资源。我们会通过以下两个步骤决定分片的布局：

1. 根据数据中心数据在过去 X 天被访问的次数计算每个数据中心的得分，越近的请求会得到越高的权重
   • 如果某个数据中心处于绝对领先的位置，我们就会将当前分片迁移到目标数据中心；
   • 如果多个数据中心拥有相同的分数，我们会进入下一个步骤；
2. 根据数据中心的可用资源确定每个数据中心的得分，例如：CPU 利用率、磁盘存储空间、IOPS 等信息
   • 如果某个数据中心处于绝对领先的位置，我们就会将当前分片迁移到目标数据中心；
   • 如果多个数据中心拥有相同的分数，我们会随机选择一个数据中心进行迁移；

如何决定时间的权重是需要不断测试和调整的，但是决定分片布局的计算过程还是相对比较简单；不过为了满足数据布局服务决定分片布局的需求，该服务需要访问数据中心的可用资源信息以及访问计数服务数据库，如何在多个数据中心收集并处理更加实时的、准确的海量数据可能是更复杂的问题。

分片迁移

当数据布局服务选择了目标的数据中心之后，它就会开始迁移对应的 μ-shard 分片，不同的底层数据库会使用不同的迁移方法，但是在迁移的过程中，我们需要保证数据的强一致性以及系统的可用性。使用 ACL 的 ZippyDB 会使用如下所示的方法迁移分片：

1. 获取 μ-shard 分片上的锁并将当前迁移加入『迁移中列表』；
2. 将源数据的访问权限设置成只读并从源数据中心读取 μ-shard 分片；
3. 向目标数据中心写入 μ-shard 分片并将其访问权限设置成只读；
4. 更新位置数据库中 μ-shard 分片映射的数据中心；
5. 删除源 μ-shard 分片并将目标 μ-shard 分片的访问权限设置成读写；
6. 释放 μ-shard 分片上的锁并将当前迁移从『迁移中列表』移除；

不是所有的数据库都支持访问权限控制，Facebook 内部使用的 Cassandra 会使用另一种迁移策略，在迁移的过程中，客户端的访问请求会同时写入到源数据和目的数据，这也是一种比较常见的热迁移策略，这里也就不展开介绍了。

总结

通过对 Akkio 系统架构的分析，我们能够发现该系统其实打通了数据的消费者和生产者之间的关系，用户对数据的访问可以决定数据的存储方法。与传统的分布式数据库不一样，因为数据库最终还是要服务用户，所以 Akkio 通过合理利用用户的访问数据，让系统中的数据布局和存储变得更加动态并贴近用户，不仅能够提高用户的体验，还能够降低成本，未来的很多系统可能都会朝着这一个方向发展，由用户的数据来决定工具和系统内部数据和信息的组织方式。

推荐阅读

• 处理器感知线程管理系统 · OSDI ‘18
• 操作系统模型与乐高积木 · OSDI ‘18

---

1. Muthukaruppan Annamalai, Kaushik Ravichandran, Harish Srinivas, Igor Zinkovsky, Luning Pan, Tony Savor, David Nagle, and Michael Stumm. 2018. Sharding the shards: managing datastore locality at scale with Akkio. In Proceedings of the 13th USENIX conference on Operating Systems Design and Implementation (OSDI'18). USENIX Association, USA, 445–460. ↩︎

2. Muthukaruppan Annamalai, Victoria Dudin. Managing data store locality at scale with Akkio. OCT 8, 2018. https://engineering.fb.com/core-data/akkio/ ↩︎

转载申请

本作品采用知识共享署名 4.0 国际许可协议进行许可，转载时请注明原文链接，图片在使用时请保留全部内容，可适当缩放并在引用处附上图片所在的文章链接。

Go 语言设计与实现

各位读者朋友，很高兴大家通过本博客学习 Go 语言，感谢一路相伴！ 《Go语言设计与实现》 的纸质版图书已经上架京东，本书目前已经四印，印数超过 10,000 册，有需要的朋友请点击 链接 或者下面的图片购买。

文章图片

你可以在 技术文章配图指南 中找到画图的方法和素材。