象群算法：从 Notion 分片 Postgres 的经验教训

今年早些时候，我们对 Notion 进行了 5 分钟的定期停机维护。尽管我们的公告只说了「提升稳定性与性能」，但这背后隐藏的却是数以月计的专注与紧迫的团队协作：将 Notion 的 PostgreSQL 整体分片成一个水平分区的数据库群。

分片这个术语被认为起源 于大型多人在线角色扮演游戏 (MMORPG) 网络创世纪 (Ultima Online) ， 当时游戏开发者需要一个情节来解释多个游戏服务器运行了多个并行的世界副本，其中特别提到了，每个分片都是从一个破碎的水晶球中产生的，而邪恶巫师蒙丹 (Mondain) 之前试图通过这个水晶球来夺取对世界的控制权。

虽然改动大获成功，但是为了防止迁移后出什么幺蛾子，我们并没有大肆宣扬。令人高兴的是，用户还是很快就开始注意到了这项改进：

今年上半年，我们对 Notion 进行了五分钟的定期维护。 虽然我们的公告是指向 “提高稳定性和性能” ，但在幕后是数月的专注、团队紧密配合的成果：将 Notion 的 PostgreSQL 整体分片成一个水平分区的数据库队列。

碎片命名法是 thought to originate 来自 MMORPG Ultima Online, 当游戏开发者需要在宇宙中解释存在多个运行在平行世界副本的游戏服务器时。具体来说，每一个碎片都是从一个破碎的水晶中出现的，邪恶的巫师蒙丹曾试图通过它夺取世界的控制权。

虽然转换成功让大家欢欣鼓舞，但我们并没有大肆宣扬，以防迁移后出现其他问题。值得高兴的是，用户很快就会注意到这些，并且改进。

最近感觉速度十分惊人 @notionhq 这一次的 “不露声色 “非常成功。

但是，一个维护窗口并不能说明全部问题。我们的团队花了几个月的时间来设计这次迁移，以使 Notion 在未来数年内更快、更可靠。

接下来讲述我们是如何分片的以及一路上我们学到了什么。

决定何时分片#

分片是我们不断努力提高应用程序性能的一个重要里程碑。在过去几年中，看到越来越多的人将 Notion 应用到生活的方方面面，我们感到既欣慰又惭愧。这毫不奇怪，所有新的公司维基、项目跟踪器和 Pokédexes 都意味着需要存储数十亿个新的区块、文件和空间。到 2020 的年中，产品的使用量显然会超过我们值得信赖的 Postgres 单体的能力，它已经尽职尽责地为我们服务了五年，并实现了四个数量级的增长。值班工程师经常被数据库 CPU 的峰值惊醒，简单的仅目录迁移 变得不安全、不确定。

提及分片，快速发展的初创企业必须进行微妙的权衡。在上世纪八十年代，大量博客文章阐述 分片 的危害 分片：增加维护负担、应用级代码中新发现的限制以及架构路径依赖。^1 当然，在我们的规模上，分片是不可避免的。问题只是什么时候去分片。

对我们来说，当 Postgres 的 “VACUUM “进程开始持续停滞，阻止数据库从死元组中回收磁盘空间时，拐点就出现了。虽然磁盘容量可以增加，但更令人担忧的是 事务 ID (TXID) wraparound 的前景，在这种安全机制下，Postgres 会停止处理所有写入，以避免破坏现有数据。我们的基础架构团队意识到 TXID wraparound 会对产品的生存构成威胁，于是加倍努力，开始工作。

设计分片方案#

如果你以前从未使用过分片数据库，那么你可以这样理解：与其通过逐步增加实例来纵向扩展数据库，不如通过在多个数据库之间分割数据来横向扩展。现在，您可以轻松启动更多主机来适应增长。不幸地是，现在您的数据分散在多个地方，因此您需要设计一个能在分布式环境中最大限度提高性能和一致性的系统。

为什么不继续垂直扩展呢？我们发现，使用 RDS 的 “调整实例大小 “按钮玩 Cookie Clicker 并不是一个可行的长期策略，即使你有足够的预算。查询性能和维护进程往往在表达到硬件限制的最大大小之前就开始下降；我们的 Postgres 自动真空停滞就是这种软限制的一个例子。

应用级分片#

我们决定实施自己的分区方案，并从应用逻辑中路由查询，这种方法被称为 应用级分片 。在最初的研究中，我们也考虑过打包的分片 / 集群解决方案，如用于 Postgres 的 Citus 或用于 MySQL 的 Vitess。虽然这些解决方案简单易用，而且开箱即可提供跨分片工具，但实际的集群逻辑并不透明，我们希望能控制数据的分布 [^2]。

应用级分片要求我们做出以下设计决策：

• 我们应该分片什么数据？ 我们的数据集之所以与众不同，部分原因在于 “块 “表反映了用户创建内容树，而这些内容树的大小、深度和分支因子可能千差万别。例如，一个大型企业客户产生的负载比许多普通个人工作空间产生的负载总和还要多。我们希望只对必要的表进行分片，同时保留相关数据的本地性。

• 我们应该如何对数据进行分区？ 好的分区密钥能确保图元在各分片之间均匀分布。分区键的选择还取决于应用结构，因为分布式连接的成本很高，而且事务性保证通常仅限于单个主机。

• 我们应该创建多少分片？这些分区应该如何组织？ 这种考虑既包括每个表的逻辑分区数量，也包括逻辑分区和物理主机之间的具体映射。

决策一：对所有传递相关的数据进行分片#

由于 Notion 的 数据模型 围绕块的概念展开，每个块在我们的数据库中占据一行，因此 “块 “表是分片的最高优先级。不过，区块可能会引用其他表，如 space（工作空间）或 discussion （页面级和内联讨论线程）。反过来，” 讨论 “可能会引用 “评论 “表中的行，以此类推。

我们决定将所有可以通过某种外键关系从 块 表 到达的表进行分片。并非所有这些表都需要分片，但如果一条记录存储在主数据库中，而其相关块存储在不同的物理分片上，那么在向不同数据存储写入数据时，我们可能会引入不一致性。

例如，在一个数据库中存储一个数据块，在另一个数据库中存储相关注释。如果删除该数据块，则应更新注释，但由于事务性保证仅适用于每个数据存储，因此数据块删除可能成功，而注释更新可能失败。

决策二：按工作区 ID 来划分分区数据#

一旦决定了要对哪些表进行分片，我们就必须对它们进行划分。选择一个好的分区方案在很大程度上取决于数据的分布和连接性；由于 Notion 是一款基于团队的产品，我们的下一个决定是 按工作区 ID 对数据进行分区 。[^3]

每个工作区在创建时都会分配一个 UUID，因此我们可以将 UUID 空间划分为统一的桶。由于分片表中的每一行要么是一个数据块，要么与一个数据块相关，而 每个数据块恰好属于一个工作区 ，因此我们使用工作区 ID 作为_分区键_。由于用户通常一次只查询一个工作区内的数据，因此我们避免了大部分跨分区连接。

决策二：容量规划#

postgres 分片： “你愿意让 1 个用户处理 100 万个请求，还是让 100 万个用户每人处理一个请求？

在确定了分区方案后，我们的目标是设计一种分片设置，既能处理现有数据，又能以较低的成本扩展，以满足我们对两年使用量的预测。以下是我们的一些限制条件：

• 实例类型： 磁盘 I/O 吞吐量（以 IOPS 为单位）受 AWS 实例类型和磁盘容量的限制。我们需要至少 60K 的总 IOPS 来满足现有需求，并有能力在需要时进一步扩展。

• 物理分片和逻辑分片的数量： 为了保持 Postgres 的正常运行并维护 RDS 复制保证，我们将每个表的上限设定为 500 GB，每个物理数据库的上限设定为 10 TB。我们需要选择一定数量的逻辑分片和一定数量的物理数据库，以便将分片平均分配给各个数据库。

• 实例数量： 更多的实例意味着更高的维护成本，但系统更强大。

• 成本： 我们希望账单能与数据库设置成线性扩展，而且我们希望能灵活地分别扩展计算和磁盘空间。

经过计算，我们确定了一个由 480 个逻辑分片 组成的架构，这些分片均匀分布在 32 个物理数据库 。层级结构如下:

• 物理数据库（32 个）

  • 逻辑分区，表示为 Postgres 模式（每个数据库 15 个，共 480 个）

    • block 表（每个逻辑分片 1 个，共 480 个）

    • collection 表（每个逻辑分片 1 个，共 480 个）

    • space 表（每个逻辑分片 1 个，共 480 个）

    • 等所有分片表

你可能会问：为什么是 480 个碎片？ 我以为所有计算机科学都是用 2 的幂来表示的，而且这不是我认识的驱动器大小！

选择 480 有很多因素：

• 2

• 3

• 4

• 5

• 6

• 8

• 10, 12, 15, 16, 20, 24, 30, 32, 40, 48, 60, 80, 96, 120, 160, 240

关键是，480 可以被很多数字整除，这就为我们提供了增加或移除物理主机的灵活性，同时保留了统一的分片分布。例如，将来我们可以从 32 台主机扩展到 40 台主机，再扩展到 48 台主机，每次跳跃都是递增的。

相比之下，假设我们有 512 个逻辑分区。512 的系数都是 2 的幂次，这意味着如果我们想保持分片数量均衡，主机数量就要从 32 台增加到 64 台。任何 2 的幂次都会要求我们将物理主机的数量增加一倍，以扩大规模。选择系数较大的值！

我们从一个包含所有表的单一数据库发展到由 32 个物理数据库组成的舰队，每个物理数据库包含 15 个逻辑分片，每个分片包含一个分片表。我们总共有 480 个逻辑分片。

我们选择将 “schema001.block”、”schema002.block “等构建为 独立的表 ，而不是为每个数据库维护一个包含 15 个子表的 分区 “block “表。本地分区表引入了另一种路由逻辑：

1. 应用程序代码：工作区 ID → 物理数据库

2. 分区表：工作区 ID → 逻辑模式

保留单独的表使我们能够直接从应用程序路由到特定的数据库和逻辑分区。

我们希望从工作区 ID 到逻辑分片的路由选择只有一个真实来源，因此我们选择单独构建表，并在应用程序中执行所有路由选择。

迁移到分片#

建立分片方案后，就到了实施的时候了。对于任何迁移，我们的一般框架都是这样的：

1. 双重写入： 传入的写入内容会同时应用到新旧数据库。

2. 回填： 一旦开始双写，就将旧数据迁移到新数据库。

3. 验证： 确保新数据库数据的完整性。

4. 切换： 确保切换到新数据库。这可以通过增量方式完成，例如双读取，然后迁移所有读取。

使用审计日志进行双重书写#

双写阶段可确保新数据同时填充新旧数据库，即使新数据库尚未使用。双写有几种选择：

• 直接写入两个数据库： 看似简单明了，但写入过程中出现的任何问题都会很快导致数据库之间出现不一致，因此这种方法对于关键路径生产数据存储来说过于不稳定。

• 逻辑复制： 内置 Postgres 功能，使用发布 / 订阅模式向多个数据库广播命令。在源数据库和目标数据库之间修改数据的能力有限。

• 审计日志和追赶脚本： 创建一个审计日志表，跟踪所有写入正在迁移的表的内容。追赶过程会遍历审计日志，将每次更新应用到新数据库，并根据需要进行修改。

我们选择了 审计日志 策略，而不是逻辑复制，因为后者在 初始快照步骤中难以跟上 “block” 表的写入量。

我们还准备并测试了一个 反向审计日志 和脚本，以备需要从分片切换回单体时使用。该脚本将捕获任何写入碎片数据库的内容，并允许我们在单体上重放这些编辑内容。最终，我们并不需要还原，但这是我们应急预案中的重要一环。

回填旧数据#

当传入的写入内容成功移植到新数据库后，我们启动了回填流程以迁移所有现有数据。在我们配置的 m5.24xlarge 实例上有全部 96 个 CPU（！），我们的最终脚本花了大约三天时间来回填生产环境。

任何有价值的回填都应该在写入旧数据之前 比较记录版本 ，跳过最近更新的记录。通过以任意顺序运行追赶脚本和回填，新数据库最终会趋于一致，复制单体。

验证数据完整性#

迁移的好坏取决于底层数据的完整性，因此在分片与单体更新后，我们开始了 验证正确性 的过程。

• 验证脚本： 我们的脚本从给定值开始验证 UUID 空间的连续范围，将单体上的每条记录与相应的分片记录进行比较。由于全表扫描的成本过高，我们随机抽取 UUID 并验证其相邻范围。

• 黑暗读取： 在迁移读取查询之前，我们添加了一个从新旧数据库中获取数据的标记（称为 黑暗读取）。我们对这些记录进行比较，并丢弃分片副本，在此过程中记录差异。暗读的引入增加了 API 的延迟，但为无缝切换提供了信心。

为谨慎起见，迁移和验证逻辑由不同的人。否则，有人在两个阶段犯同样错误的可能性就会增大，从而削弱了验证的前提。

汲取的困难教训#

虽然分片项目的大部分工作都体现了 Notion 工程团队的最佳工作状态，但事后我们仍会重新考虑许多决定。下面是几个例子：

• 更早切片 作为一个小团队，我们非常清楚过早优化所带来的得失。不过，我们一直等到现有数据库压力过大，这意味着我们必须非常节俭地进行迁移，以免增加更多负载。这种限制使我们无法使用 逻辑复制来进行双重写入。工作区 ID（我们的分区密钥）尚未在旧数据库中填充， 回填这一列会加重我们单体的负载 。相反，我们在向分片写入数据时，会即时回填每一行，这就需要一个自定义的补全脚本。

• 争取实现零停机迁移 双倍写入吞吐量是我们最终切换的主要瓶颈：一旦服务器宕机，我们就需要让追赶脚本完成向分片的写入传播。如果我们再花一周时间优化脚本，使其在切换过程中花费 0 秒的时间来抓取分片，那么就有可能在负载均衡器层面进行热插拔，而不会出现停机。

• 引入组合主键而不是单独的分区键 现在，分片表中的行使用一个复合键：”id”，旧数据库中的主键；”space_id”，当前安排中的分区键。由于我们无论如何都要进行全表扫描，因此我们可以将这两个键合并为一个新列，这样就无需在整个应用程序中传递 space_id。

尽管存在这些问题，但分片技术还是取得了巨大成功。对于 Notion 用户来说，几分钟的停机时间让产品的运行速度明显加快。在公司内部，我们展示了团队的协调合作和果断执行力，实现了时间紧迫的目标。

如果紧迫的时间并不妨碍您对长期技术影响进行严谨的思考，我们很乐意与您交流– 加入我们！

---

附注

[^2]: 除了打包解决方案外，我们还考虑了一些替代方案：改用 DynamoDB 等其他数据库系统（对于我们的使用案例来说风险太大），以及在裸机 NVMe 重实例 上运行 Postgres 以获得更大的磁盘吞吐量（由于备份和复制的维护成本而被拒绝）。

[^3]: 除了基于键的分区（根据某些属性划分数据），还有 其他 方法： 按服务进行垂直分区，以及使用中间查找表对所有读写进行路由的基于目录的分区。

设计一个分片方案#

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接
我们的翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

---

原文地址：https://www.notion.so/blog/sharding-post...

译文地址：https://learnku.com/mysql/t/71959