从 Notion 分片 Postgres 中吸取的教训(Notion 工程团队)

https://www.notion.so/blog/sharding-postgres-at-notion

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

https://www.raphkoster.com/2009/01/08/database-sharding-came-from-uo/
https://uo.com/

虽然转换成功让大家欢欣鼓舞，但我们仍然保持沉默，以防迁移后出现任何问题。令我们高兴的是，用户很快开始注意到改进。完全是 “show don't tell”。

让我告诉你我们如何分片的故事以及我们在此过程中学到的东西。

决定何时分片

分片是我们不断努力提高应用程序性能的一个重要里程碑。在过去的几年里，看到越来越多的人将 Notion 应用到他们生活的方方面面，这令人欣慰和谦卑。不出所料，所有新的公司 wiki、项目跟踪器和图鉴都意味着数十亿新的blocks、files 和 spaces。到 2020 年年中，很明显，产品的使用将超过我们值得信赖的 Postgres 单体的能力，后者在五年和四个数量级的增长中尽职尽责地为我们服务。随叫随到的工程师经常被数据库 CPU 峰值唤醒，简单的仅目录迁移变得不安全和不确定。

https://www.notion.so/blog/data-model-behind-notion
https://medium.com/paypal-tech/postgresql-at-scale-database-schema-changes-without-downtime-20d3749ed680

在分片方面，快速发展的初创公司必须进行微妙的权衡。在此期间，大量博客文章过早地阐述了分片的危险：增加的维护负担、应用程序级代码中新发现的约束以及架构路径依赖性。¹当然，在我们的规模上，分片是不可避免的。问题只是什么时候。

https://www.percona.com/blog/2009/08/06/why-you-dont-want-to-shard/
http://www.37signals.com/svn/posts/1509-mr-moore-gets-to-punt-on-sharding#
https://www.drdobbs.com/errant-architectures/184414966
https://www.infoworld.com/article/2073449/think-twice-before-sharding.html

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

https://blog.sentry.io/2015/07/23/transaction-id-wraparound-in-postgres

设计分片方案

如果您以前从未对数据库进行过分片，那么这里的想法是：不要使用越来越多的实例垂直扩展数据库，而是通过跨多个数据库分区数据来水平扩展。现在，您可以轻松启动其他主机以适应增长。不幸的是，现在您的数据位于多个位置，因此您需要设计一个在分布式环境中最大限度地提高性能和一致性的系统。

为什么不保持垂直缩放？正如我们发现的那样，使用 RDS“调整实例大小”按钮玩 Cookie Clicker 并不是一个可行的长期策略——即使你有预算。查询性能和维护过程通常在表达到最大硬件绑定大小之前就开始下降；我们停止的 Postgres auto-vacuum 就是这种软限制的一个例子。

应用级分片

我们决定实现我们自己的分区方案并从应用程序逻辑路由查询，这种方法称为应用程序级分片。在我们最初的研究中，我们还考虑了打包的分片/集群解决方案，例如用于 Postgres 的 Citus 或用于 MySQL 的 Vitess。虽然这些解决方案因其简单性而吸引人，并提供开箱即用的跨分片工具，但实际的集群逻辑是不透明的，我们希望控制数据的分布。²

https://www.citusdata.com/
https://vitess.io/

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

我们应该分片哪些数据？使我们的数据集与众不同的部分原因在于，block 表反映了用户创建内容的树，这些内容的大小、深度和分支因子可能会有很大差异。例如，单个大型企业客户产生的负载比许多普通个人工作空间的总和还要多。我们只想对必要的表进行分片，同时保留相关数据的局部性。
我们应该如何对数据进行分区？良好的分区键可确保元组在分片中均匀分布。分区键的选择还取决于应用程序结构，因为分布式连接很昂贵，并且事务性保证通常仅限于单个主机。
我们应该创建多少个分片？应该如何组织这些分片？这种考虑包括每个表的逻辑分片数量，以及逻辑分片和物理主机之间的具体映射。

决策 1：对所有与块有传递关系的数据进行分片

由于 Notion 的数据模型围绕块的概念展开，每个块在我们的数据库中占据一行，因此 block(块) 表是分片的最高优先级。但是，块可能会引用其他表，例如space（工作区）或 discussion（page-level 和 inline discussion 线程）。反过来，discussion 可能会引用 comment 表中的行，等等。

https://www.notion.so/blog/data-model-behind-notion

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

例如，考虑一个存储在一个数据库中的块，在另一个数据库中具有相关的评论。如果块被删除，评论应该被更新 — 但是，由于事务性保证只适用于每个数据存储，所以块删除可能成功，而评论更新可能失败。

决策 2：按 Workspace ID 划分块数据

一旦我们决定分片哪些表，我们就必须将它们分开。选择一个好的分区方案很大程度上取决于数据的分布和连通性；由于 Notion 是基于团队的产品，我们的下一个决定是按 workspace ID 对数据进行分区。³

每个工作空间在创建时都分配了一个 UUID，因此我们可以将 UUID 空间划分为统一的存储桶。因为分片表中的每一行要么是一个块，要么与一个块相关，并且每个块都属于一个工作区，所以我们使用 workspace ID 作为分区键(partition key)。由于用户通常一次在单个工作空间内查询数据，因此我们避免了大多数跨分片连接。

决策 3：容量规划

决定了分区方案后，我们的目标是设计一个分片设置，以处理我们现有的数据和规模，以轻松满足我们两年的使用预测。以下是我们的一些限制条件：

实例类型：以 IOPS 量化的磁盘 I/O 吞吐量受 AWS 实例类型和磁盘容量的限制。我们需要至少 60K 的总 IOPS 来满足现有需求，并在需要时具有进一步扩展的能力。
- https://docs.aws.amazon.com/AmazonRDS/latest/UserGuide/CHAP_Storage.html
物理和逻辑分片的数量：为了保持 Postgres 正常运行并保留 RDS 复制保证，我们将每个表的上限设置为 500 GB，每个物理数据库设置为 10 TB。我们需要选择多个逻辑分片和多个物理数据库，以便分片可以在数据库之间均匀划分。
实例数：更多实例意味着更高的维护成本，但是系统更健壮。
成本：我们希望我们的账单随着我们的数据库设置线性扩展，并且我们希望能够灵活地分别扩展计算和磁盘空间。

在计算了数字之后，我们确定了一个由 480 个逻辑分片(logical shards)组成的架构，这些分片均匀分布在 32 个物理数据库中。层次结构如下所示：

物理数据库（共 32 个）
- block 表（每个逻辑分片 1 个，总共 480 个）
- collection 表（每个逻辑分片 1 个，总共 480 个）
- space 表（每个逻辑分片 1 个，总共 480 个）
- 等所有分片表
- 逻辑分片，表示为 Postgres 模式（每个数据库 15 个，总共 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 表。原生分区表引入了另一条路由逻辑：

应用代码：workspace ID → 物理数据库。
分区表：workspace ID → 逻辑 schema。

https://www.postgresql.org/docs/10/ddl-partitioning.html

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

我们想要从 workspace ID 路由到逻辑分片的单一事实来源，因此我们选择单独构建表并在应用程序中执行所有路由。

迁移到分片

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

双写(Double-write)：传入的写入同时应用于旧数据库和新数据库。
回填(Backfill)：双写开始后，将旧数据迁移到新数据库。
验证(Verification)：确保新数据库中数据的完整性。
切换(Switch-over)：实际切换到新数据库。这可以逐步完成，例如：双读，然后迁移所有的读。

用审计日志双重写入

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

直接写入两个数据库：看似简单，但任何一种写入的任何问题都可能很快导致数据库之间的不一致，从而使这种方法对于关键路径生产数据存储来说过于不稳定。
逻辑复制：内置的 Postgres 功能，使用发布/订阅模型将命令广播到多个数据库。在源数据库和目标数据库之间修改数据的能力有限。
- https://www.postgresql.org/docs/10/logical-replication.html
审核日志和追赶脚本：创建审核日志表以跟踪对迁移中的表的所有写入。一个追赶过程遍历审计日志并将每次更新应用到新数据库，并根据需要进行任何修改。

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

https://www.postgresql.org/docs/10/logical-replication-architecture.html#LOGICAL-REPLICATION-SNAPSHOT

我们还准备并测试了一个反向审计日志和脚本，以防我们需要从分片切换回单体应用。该脚本将捕获对分片数据库的任何传入写入，并允许我们在单体应用程序上重放这些编辑。最后，我们不需要恢复，但这是我们应急计划的重要组成部分。

回填旧数据

一旦传入的写入成功传播到新数据库，我们就会启动回填过程以迁移所有现有数据。使用我们预置的 m5.24xlarge 实例上的所有 96 CPUs(!)，我们的最终脚本大约需要三天时间来回填生产环境。

任何值得称道的回填都应该在写入旧数据之前比较记录版本，跳过具有最近更新的记录。通过以任何顺序运行追赶脚本和回填，新数据库最终将聚合以复制整体。

验证数据完整性

迁移仅与底层数据的完整性一样好，因此在分片与单体应用保持同步后，我们开始验证正确性的过程。

验证脚本：我们的脚本验证了从给定值开始的 UUID 空间的连续范围，将单体上的每条记录与相应的分片记录进行比较。因为全表扫描会非常昂贵，所以我们随机抽样 UUID 并验证它们的相邻范围。
“暗”读：在迁移读查询之前，我们添加了一个标志来从新旧数据库中获取数据（称为暗读）。我们比较了这些记录并丢弃了分片副本，记录了过程中的差异。引入暗读增加了 API 延迟，但提供了无缝切换的信心。
- https://slack.engineering/re-architecting-slacks-workspace-preferences-how-to-move-to-an-eav-model-to-support-scalability/

作为预防措施，迁移和验证逻辑是由不同的人实现的。否则，在两个阶段都犯同样错误的可能性更大，削弱了验证的前提。

艰难的教训

虽然分片项目的大部分内容都让 Notion 的工程团队处于最佳状态，但我们事后会重新考虑许多决定。这里有一些例子：

分片过早。作为一个小团队，我们敏锐地意识到与过早优化相关的权衡。但是，我们一直等到现有数据库严重紧张，这意味着我们必须非常节俭地进行迁移，以免增加更多负载。这种限制使我们无法使用逻辑复制进行双重写入。workspace ID（我们的分区键）尚未填充到旧数据库中，回填此列会加剧我们单体应用的负载。相反，我们在写入分片时即时回填每一行，需要一个自定义的追赶脚本。
旨在实现零停机迁移。双写吞吐量是我们最终切换的主要瓶颈：一旦我们关闭服务器，我们需要让追赶脚本完成将写入传播到分片。如果我们再花一周时间优化脚本，以便在切换期间花不到 30 秒的时间赶上分片，则可能可以在负载均衡器级别进行热交换而无需停机。
引入组合主键而不是单独的分区键。今天，分表中的行使用复合键:id，旧数据库中的主键；和 space_id，当前排列中的分区键。由于无论如何我们都必须进行全表扫描，我们可以将两个键合并到一个新列中，从而无需在整个应用程序中传递 space_ids。

尽管有这些假设，分片还是取得了巨大的成功。对于 Notion 用户来说，几分钟的停机时间使产品明显更快。在内部，我们在时间敏感的目标下展示了协调的团队合作和果断的执行力。

脚注

[1] 除了引入不必要的复杂性之外，过早分片的一个被低估的危险是它可以在产品模型在业务方面得到明确定义之前对其进行约束。例如，如果一个团队按用户分片并随后转向以团队为中心的产品策略，那么架构阻抗不匹配可能会导致严重的技术难题，甚至会限制某些功能。
[2] 除了打包的解决方案外，我们还考虑了一些替代方案：切换到另一个数据库系统，如 DynamoDB（对于我们的用例来说风险太大），并在裸机 NVMe 重型实例上运行 Postgres，以获得更大的磁盘吞吐量（由于备份和复制的维护成本而被拒绝）。
- https://aws.amazon.com/ec2/instance-types/i3en/
[3] 除了基于键的分区（基于某些属性划分数据）之外，还有其他方法：按服务进行垂直分区，以及使用中间查找表路由所有读写的基于目录的分区。
- https://www.startuplessonslearned.com/2009/01/sharding-for-startups.html?m=1#comment-form