從 Notion 分片 Postgres 中吸取的教訓(Notion 工程團隊)

• 2022 年 5 月 7 日
• 筆記

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

今年(2021)早些時候，我們對 Notion 進行了五分鐘的定期維護。 雖然我們的聲明指向「提高穩定性和性能」，但在幕後是數月專註、緊迫的團隊合作的結果：將 Notion 的 PostgreSQL 整體分片成一個水平分區的資料庫艦隊。

分片命名法被認為起源於 MMORPG Ultima Online，當時遊戲開發者需要一個宇宙解釋來解釋存在多個運行平行世界副本的遊戲伺服器。 具體來說，每一個碎片都是從一個破碎的水晶中出現的，邪惡的巫師蒙丹曾試圖通過它奪取世界的控制權。

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

雖然轉換成功讓大家歡欣鼓舞，但我們仍然保持沉默，以防遷移後出現任何問題。 令我們高興的是，用戶很快開始注意到改進。完全是 「show don’t tell」。

讓我告訴你我們如何分片的故事以及我們在此過程中學到的東西。

決定何時分片

分片是我們不斷努力提高應用程式性能的一個重要里程碑。 在過去的幾年裡，看到越來越多的人將 Notion 應用到他們生活的方方面面，這令人欣慰和謙卑。不出所料，所有新的公司 wiki、項目跟蹤器和圖鑑都意味著數十億新的blocks、files 和 spaces。到 2020 年年中，很明顯，產品的使用將超過我們值得信賴的 Postgres 單體的能力，後者在五年和四個數量級的增長中盡職盡責地為我們服務。隨叫隨到的工程師經常被資料庫 CPU 峰值喚醒，簡單的僅目錄遷移變得不安全和不確定。

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

在分片方面，快速發展的初創公司必須進行微妙的權衡。 在此期間，大量部落格文章過早地闡述了分片的危險：增加的維護負擔、應用程式級程式碼中新發現的約束以及架構路徑依賴性。¹當然，在我們的規模上，分片是不可避免的。問題只是什麼時候。

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

對我們來說，當 Postgres VACUUM 進程開始持續停止時，拐點就到了，阻止了資料庫從死元組中回收磁碟空間。雖然可以增加磁碟容量，但更令人擔憂的是 transaction ID (TXID) wraparound，這是一種 Postgres 將停止處理所有寫入以避免破壞現有數據的安全機制。意識到 TXID wraparound 會對產品構成生存威脅，我們的基礎架構團隊加倍努力並開始工作。

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

設計分片方案

如果您以前從未對資料庫進行過分片，那麼這裡的想法是：不要使用越來越多的實例垂直擴展資料庫，而是通過跨多個資料庫分區數據來水平擴展。現在，您可以輕鬆啟動其他主機以適應增長。 不幸的是，現在您的數據位於多個位置，因此您需要設計一個在分散式環境中最大限度地提高性能和一致性的系統。

為什麼不保持垂直縮放？ 正如我們發現的那樣，使用 RDS「調整實例大小」按鈕玩 Cookie Clicker 並不是一個可行的長期策略——即使你有預算。 查詢性能和維護過程通常在表達到最大硬體綁定大小之前就開始下降； 我們停止的 Postgres auto-vacuum 就是這種軟限制的一個例子。

應用級分片

我們決定實現我們自己的分區方案並從應用程式邏輯路由查詢，這種方法稱為應用程式級分片。 在我們最初的研究中，我們還考慮了打包的分片/集群解決方案，例如用於 Postgres 的 Citus 或用於 MySQL 的 Vitess。雖然這些解決方案因其簡單性而吸引人，並提供開箱即用的跨分片工具，但實際的集群邏輯是不透明的，我們希望控制數據的分布。²

• //www.citusdata.com/
• //vitess.io/

應用程式級分片要求我們做出以下設計決策：

• 我們應該分片哪些數據？ 使我們的數據集與眾不同的部分原因在於，block 表反映了用戶創建內容的樹，這些內容的大小、深度和分支因子可能會有很大差異。 例如，單個大型企業客戶產生的負載比許多普通個人工作空間的總和還要多。 我們只想對必要的表進行分片，同時保留相關數據的局部性。
• 我們應該如何對數據進行分區？ 良好的分區鍵可確保元組在分片中均勻分布。 分區鍵的選擇還取決於應用程式結構，因為分散式連接很昂貴，並且事務性保證通常僅限於單個主機。
• 我們應該創建多少個分片？應該如何組織這些分片？ 這種考慮包括每個表的邏輯分片數量，以及邏輯分片和物理主機之間的具體映射。

決策 1：對所有與塊有傳遞關係的數據進行分片

由於 Notion 的數據模型圍繞塊的概念展開，每個塊在我們的資料庫中佔據一行，因此 block(塊) 表是分片的最高優先順序。 但是，塊可能會引用其他表，例如space（工作區）或 discussion（page-level 和 inline discussion 執行緒）。 反過來，discussion 可能會引用 comment 表中的行，等等。

• //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 來滿足現有需求，並在需要時具有進一步擴展的能力。
  • //docs.aws.amazon.com/AmazonRDS/latest/UserGuide/CHAP_Storage.html
• 物理和邏輯分片的數量： 為了保持 Postgres 正常運行並保留 RDS 複製保證，我們將每個表的上限設置為 500 GB，每個物理資料庫設置為 10 TB。 我們需要選擇多個邏輯分片和多個物理資料庫，以便分片可以在資料庫之間均勻劃分。
• 實例數： 更多實例意味著更高的維護成本，但是系統更健壯。
• 成本： 我們希望我們的賬單隨著我們的資料庫設置線性擴展，並且我們希望能夠靈活地分別擴展計算和磁碟空間。

在計算了數字之後，我們確定了一個由 480 個邏輯分片(logical shards)組成的架構，這些分片均勻分布在 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. 應用程式碼：workspace ID → 物理資料庫。
2. 分區表：workspace ID → 邏輯 schema。

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

保留單獨的表允許我們直接從應用程式路由到特定的資料庫和邏輯分片。

我們想要從 workspace ID 路由到邏輯分片的單一事實來源，因此我們選擇單獨構建表並在應用程式中執行所有路由。

遷移到分片

一旦我們建立了分片方案，就該實施它了。 對於任何遷移，我們的一般框架都是這樣的：

1. 雙寫(Double-write)：傳入的寫入同時應用於舊資料庫和新資料庫。
2. 回填(Backfill)：雙寫開始後，將舊數據遷移到新資料庫。
3. 驗證(Verification)：確保新資料庫中數據的完整性。
4. 切換(Switch-over)：實際切換到新資料庫。這可以逐步完成，例如：雙讀，然後遷移所有的讀。

用審計日誌雙重寫入

雙寫階段確保新數據同時填充新舊資料庫，即使新資料庫尚未使用。雙寫有幾種選擇：

• 直接寫入兩個資料庫：看似簡單，但任何一種寫入的任何問題都可能很快導致資料庫之間的不一致，從而使這種方法對於關鍵路徑生產數據存儲來說過於不穩定。
• 邏輯複製：內置的 Postgres 功能，使用發布/訂閱模型將命令廣播到多個資料庫。在源資料庫和目標資料庫之間修改數據的能力有限。
  • //www.postgresql.org/docs/10/logical-replication.html
• 審核日誌和追趕腳本：創建審核日誌表以跟蹤對遷移中的表的所有寫入。 一個追趕過程遍歷審計日誌並將每次更新應用到新資料庫，並根據需要進行任何修改。

我們選擇了 audit log 策略而不是邏輯複製，因為後者在初始快照步驟中難以跟上 block 表寫入量。

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

我們還準備並測試了一個反向審計日誌和腳本，以防我們需要從分片切換回單體應用。 該腳本將捕獲對分片資料庫的任何傳入寫入，並允許我們在單體應用程式上重放這些編輯。 最後，我們不需要恢復，但這是我們應急計劃的重要組成部分。

回填舊數據

一旦傳入的寫入成功傳播到新資料庫，我們就會啟動回填過程以遷移所有現有數據。使用我們預置的 m5.24xlarge 實例上的所有 96 CPUs(!)，我們的最終腳本大約需要三天時間來回填生產環境。

任何值得稱道的回填都應該在寫入舊數據之前比較記錄版本，跳過具有最近更新的記錄。 通過以任何順序運行追趕腳本和回填，新資料庫最終將聚合以複製整體。

驗證數據完整性

遷移僅與底層數據的完整性一樣好，因此在分片與單體應用保持同步後，我們開始驗證正確性的過程。

• 驗證腳本：我們的腳本驗證了從給定值開始的 UUID 空間的連續範圍，將單體上的每條記錄與相應的分片記錄進行比較。因為全表掃描會非常昂貴，所以我們隨機抽樣 UUID 並驗證它們的相鄰範圍。
• 「暗」讀：在遷移讀查詢之前，我們添加了一個標誌來從新舊資料庫中獲取數據（稱為暗讀）。 我們比較了這些記錄並丟棄了分片副本，記錄了過程中的差異。引入暗讀增加了 API 延遲，但提供了無縫切換的信心。
  • //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，以獲得更大的磁碟吞吐量（由於備份和複製的維護成本而被拒絕）。
  • //aws.amazon.com/ec2/instance-types/i3en/
• [3] 除了基於鍵的分區（基於某些屬性劃分數據）之外，還有其他方法：按服務進行垂直分區，以及使用中間查找表路由所有讀寫的基於目錄的分區。
  • //www.startuplessonslearned.com/2009/01/sharding-for-startups.html?m=1#comment-form

更多

• Citus 簡介，將 Postgres 轉換為分散式資料庫
• 分散式 PostgreSQL – Citus 架構及概念
• 擴展我們的分析處理服務(Smartly.io)：使用 Citus 對 PostgreSQL 資料庫進行分片
• 分散式 PostgreSQL 集群(Citus)官方示例 – 多租戶應用程式實戰
• 分散式 PostgreSQL 集群(Citus)官方安裝指南