今年(2021)早些時候，我們對 Notion 進行了五分鐘的定期維護。雖然我們的聲明指向“提高穩(wěn)定性和性能”，但在幕后是數(shù)月專注、緊迫的團隊合作的結(jié)果：將 Notion 的 PostgreSQL 整體分片成一個水平分區(qū)的數(shù)據(jù)庫艦隊。

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

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

https://uo.com/

雖然轉(zhuǎn)換成功讓大家歡欣鼓舞，但我們?nèi)匀槐３殖聊?，以防遷移后出現(xiàn)任何問題。令我們高興的是，用戶很快開始注意到改進。完全是 “show don't tell”。

讓我告訴你我們?nèi)绾畏制墓适乱约拔覀冊诖诉^程中學(xué)到的東西。

決定何時分片

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

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

在分片方面，快速發(fā)展的初創(chuàng)公司必須進行微妙的權(quán)衡。在此期間，大量博客文章過早地闡述了分片的危險：增加的維護負擔、應(yīng)用程序級代碼中新發(fā)現(xiàn)的約束以及架構(gòu)路徑依賴性。1當然，在我們的規(guī)模上，分片是不可避免的。問題只是什么時候。

• 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 進程開始持續(xù)停止時，拐點就到了，阻止了數(shù)據(jù)庫從死元組中回收磁盤空間。雖然可以增加磁盤容量，但更令人擔憂的是 transaction ID (TXID) wraparound，這是一種 Postgres 將停止處理所有寫入以避免破壞現(xiàn)有數(shù)據(jù)的安全機制。意識到 TXID wraparound 會對產(chǎn)品構(gòu)成生存威脅，我們的基礎(chǔ)架構(gòu)團隊加倍努力并開始工作。

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

設(shè)計分片方案

如果您以前從未對數(shù)據(jù)庫進行過分片，那么這里的想法是：不要使用越來越多的實例垂直擴展數(shù)據(jù)庫，而是通過跨多個數(shù)據(jù)庫分區(qū)數(shù)據(jù)來水平擴展?，F(xiàn)在，您可以輕松啟動其他主機以適應(yīng)增長。不幸的是，現(xiàn)在您的數(shù)據(jù)位于多個位置，因此您需要設(shè)計一個在分布式環(huán)境中最大限度地提高性能和一致性的系統(tǒng)。

為什么不保持垂直縮放?正如我們發(fā)現(xiàn)的那樣，使用 RDS“調(diào)整實例大小”按鈕玩 Cookie Clicker 并不是一個可行的長期策略——即使你有預(yù)算。查詢性能和維護過程通常在表達到最大硬件綁定大小之前就開始下降;我們停止的 Postgres auto-vacuum 就是這種軟限制的一個例子。

應(yīng)用級分片

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

https://www.citusdata.com/

https://vitess.io/

應(yīng)用程序級分片要求我們做出以下設(shè)計決策：

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

決策 1：對所有與塊有傳遞關(guān)系的數(shù)據(jù)進行分片

由于 Notion 的數(shù)據(jù)模型圍繞塊的概念展開，每個塊在我們的數(shù)據(jù)庫中占據(jù)一行，因此 block(塊) 表是分片的最高優(yōu)先級。但是，塊可能會引用其他表，例如space(工作區(qū))或 discussion(page-level 和 inline discussion 線程)。反過來，discussion 可能會引用 comment 表中的行，等等。

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

我們決定通過某種外鍵關(guān)系對所有可從 block 表訪問的表進行分片。并非所有這些表都需要分片，但是如果一條記錄存儲在主數(shù)據(jù)庫中，而其相關(guān)塊存儲在不同的物理分片上，我們可能會在寫入不同的數(shù)據(jù)存儲時引入不一致。

例如，考慮一個存儲在一個數(shù)據(jù)庫中的塊，在另一個數(shù)據(jù)庫中具有相關(guān)的評論。如果塊被刪除，評論應(yīng)該被更新 — 但是，由于事務(wù)性保證只適用于每個數(shù)據(jù)存儲，所以塊刪除可能成功，而評論更新可能失敗。

決策 2：按 Workspace ID 劃分塊數(shù)據(jù)

一旦我們決定分片哪些表，我們就必須將它們分開。選擇一個好的分區(qū)方案很大程度上取決于數(shù)據(jù)的分布和連通性;由于 Notion 是基于團隊的產(chǎn)品，我們的下一個決定是按 workspace ID 對數(shù)據(jù)進行分區(qū)。3

每個工作空間在創(chuàng)建時都分配了一個 UUID，因此我們可以將 UUID 空間劃分為統(tǒng)一的存儲桶。因為分片表中的每一行要么是一個塊，要么與一個塊相關(guān)，并且每個塊都屬于一個工作區(qū)，所以我們使用 workspace ID 作為分區(qū)鍵(partition key)。由于用戶通常一次在單個工作空間內(nèi)查詢數(shù)據(jù)，因此我們避免了大多數(shù)跨分片連接。

決策 3：容量規(guī)劃

決定了分區(qū)方案后，我們的目標是設(shè)計一個分片設(shè)置，以處理我們現(xiàn)有的數(shù)據(jù)和規(guī)模，以輕松滿足我們兩年的使用預(yù)測。以下是我們的一些限制條件：

• 實例類型： 以 IOPS 量化的磁盤 I/O 吞吐量受 AWS 實例類型和磁盤容量的限制。我們需要至少 60K 的總 IOPS 來滿足現(xiàn)有需求，并在需要時具有進一步擴展的能力。

https://docs.aws.amazon.com/AmazonRDS/latest/UserGuide/CHAP_Storage.html

• 物理和邏輯分片的數(shù)量： 為了保持 Postgres 正常運行并保留 RDS 復(fù)制保證，我們將每個表的上限設(shè)置為 500 GB，每個物理數(shù)據(jù)庫設(shè)置為 10 TB。我們需要選擇多個邏輯分片和多個物理數(shù)據(jù)庫，以便分片可以在數(shù)據(jù)庫之間均勻劃分。
• 實例數(shù)： 更多實例意味著更高的維護成本，但是系統(tǒng)更健壯。
• 成本： 我們希望我們的賬單隨著我們的數(shù)據(jù)庫設(shè)置線性擴展，并且我們希望能夠靈活地分別擴展計算和磁盤空間。

在計算了數(shù)字之后，我們確定了一個由 480 個邏輯分片(logical shards)組成的架構(gòu)，這些分片均勻分布在 32 個物理數(shù)據(jù)庫中。層次結(jié)構(gòu)如下所示：

• 物理數(shù)據(jù)庫(共 32 個)

block 表(每個邏輯分片 1 個，總共 480 個)

collection 表(每個邏輯分片 1 個，總共 480 個)

space 表(每個邏輯分片 1 個，總共 480 個)

等所有分片表

邏輯分片，表示為 Postgres 模式(每個數(shù)據(jù)庫 15 個，總共 480 個)

您可能想知道，“為什么要 480 個分片?我認為所有計算機科學(xué)都是以 2 的冪次方完成的，這不是我認識的驅(qū)動器大小!”

有很多因素導(dǎo)致選擇 480：

• 2
• 3
• 4
• 5
• 6
• 8
• 10, 12, 15, 16, 20, 24, 30, 32, 40, 48, 60, 80, 96, 120, 160, 240

關(guān)鍵是，480 可以被很多數(shù)字整除——這提供了添加或刪除物理主機的靈活性，同時保持統(tǒng)一的分片分布。例如，將來我們可以從 32 臺擴展到 40 臺再到 48 臺主機，每次都進行增量跳躍。相比之下，假設(shè)我們有 512 個邏輯分片。512 的因數(shù)都是 2 的冪，這意味著如果我們想保持分片均勻，我們會從 32 臺主機跳到 64 臺主機。任何 2 的冪都需要我們將物理主機的數(shù)量增加一倍以進行升級。選擇具有很多因素的值!

我們從包含每張表的單個數(shù)據(jù)庫發(fā)展為由 32 個物理數(shù)據(jù)庫組成的艦隊，每個數(shù)據(jù)庫包含 15 個邏輯分片，每個分片包含每個分片表中的一個。我們總共有 480 個邏輯分片。

我們選擇將 schema001.block、schema002.block 等構(gòu)建為單獨的表，而不是為每個數(shù)據(jù)庫維護一個具有 15 個子表的分區(qū) block 表。原生分區(qū)表引入了另一條路由邏輯：

• 應(yīng)用代碼：workspace ID → 物理數(shù)據(jù)庫。
• 分區(qū)表：workspace ID → 邏輯 schema。

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

保留單獨的表允許我們直接從應(yīng)用程序路由到特定的數(shù)據(jù)庫和邏輯分片。

我們想要從 workspace ID 路由到邏輯分片的單一事實來源，因此我們選擇單獨構(gòu)建表并在應(yīng)用程序中執(zhí)行所有路由。

遷移到分片

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

• 雙寫(Double-write)：傳入的寫入同時應(yīng)用于舊數(shù)據(jù)庫和新數(shù)據(jù)庫。
• 回填(Backfill)：雙寫開始后，將舊數(shù)據(jù)遷移到新數(shù)據(jù)庫。
• 驗證(Verification)：確保新數(shù)據(jù)庫中數(shù)據(jù)的完整性。
• 切換(Switch-over)：實際切換到新數(shù)據(jù)庫。這可以逐步完成，例如：雙讀，然后遷移所有的讀。

用審計日志雙重寫入

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

• 直接寫入兩個數(shù)據(jù)庫：看似簡單，但任何一種寫入的任何問題都可能很快導(dǎo)致數(shù)據(jù)庫之間的不一致，從而使這種方法對于關(guān)鍵路徑生產(chǎn)數(shù)據(jù)存儲來說過于不穩(wěn)定。
• 邏輯復(fù)制：內(nèi)置的 Postgres 功能，使用發(fā)布/訂閱模型將命令廣播到多個數(shù)據(jù)庫。在源數(shù)據(jù)庫和目標數(shù)據(jù)庫之間修改數(shù)據(jù)的能力有限。

https://www.postgresql.org/docs/10/logical-replication.html

• 審核日志和追趕腳本：創(chuàng)建審核日志表以跟蹤對遷移中的表的所有寫入。一個追趕過程遍歷審計日志并將每次更新應(yīng)用到新數(shù)據(jù)庫，并根據(jù)需要進行任何修改。

我們選擇了 audit log 策略而不是邏輯復(fù)制，因為后者在初始快照步驟中難以跟上 block 表寫入量。

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

我們還準備并測試了一個反向?qū)徲嬋罩竞湍_本，以防我們需要從分片切換回單體應(yīng)用。該腳本將捕獲對分片數(shù)據(jù)庫的任何傳入寫入，并允許我們在單體應(yīng)用程序上重放這些編輯。最后，我們不需要恢復(fù)，但這是我們應(yīng)急計劃的重要組成部分。

回填舊數(shù)據(jù)

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

任何值得稱道的回填都應(yīng)該在寫入舊數(shù)據(jù)之前比較記錄版本，跳過具有最近更新的記錄。通過以任何順序運行追趕腳本和回填，新數(shù)據(jù)庫最終將聚合以復(fù)制整體。

驗證數(shù)據(jù)完整性

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

• 驗證腳本：我們的腳本驗證了從給定值開始的 UUID 空間的連續(xù)范圍，將單體上的每條記錄與相應(yīng)的分片記錄進行比較。因為全表掃描會非常昂貴，所以我們隨機抽樣 UUID 并驗證它們的相鄰范圍。
• “暗”讀：在遷移讀查詢之前，我們添加了一個標志來從新舊數(shù)據(jù)庫中獲取數(shù)據(jù)(稱為暗讀)。我們比較了這些記錄并丟棄了分片副本，記錄了過程中的差異。引入暗讀增加了 API 延遲，但提供了無縫切換的信心。

https://slack.engineering/re-architecting-slacks-workspace-preferences-how-to-move-to-an-eav-model-to-support-scalability/

作為預(yù)防措施，遷移和驗證邏輯是由不同的人實現(xiàn)的。否則，在兩個階段都犯同樣錯誤的可能性更大，削弱了驗證的前提。

艱難的教訓(xùn)

雖然分片項目的大部分內(nèi)容都讓 Notion 的工程團隊處于最佳狀態(tài)，但我們事后會重新考慮許多決定。這里有一些例子：

• 分片過早。作為一個小團隊，我們敏銳地意識到與過早優(yōu)化相關(guān)的權(quán)衡。但是，我們一直等到現(xiàn)有數(shù)據(jù)庫嚴重緊張，這意味著我們必須非常節(jié)儉地進行遷移，以免增加更多負載。這種限制使我們無法使用邏輯復(fù)制進行雙重寫入。workspace ID(我們的分區(qū)鍵)尚未填充到舊數(shù)據(jù)庫中，回填此列會加劇我們單體應(yīng)用的負載。相反，我們在寫入分片時即時回填每一行，需要一個自定義的追趕腳本。
• 旨在實現(xiàn)零停機遷移。雙寫吞吐量是我們最終切換的主要瓶頸：一旦我們關(guān)閉服務(wù)器，我們需要讓追趕腳本完成將寫入傳播到分片。如果我們再花一周時間優(yōu)化腳本，以便在切換期間花不到 30 秒的時間趕上分片，則可能可以在負載均衡器級別進行熱交換而無需停機。
• 引入組合主鍵而不是單獨的分區(qū)鍵。今天，分表中的行使用復(fù)合鍵:id，舊數(shù)據(jù)庫中的主鍵;和 space_id，當前排列中的分區(qū)鍵。由于無論如何我們都必須進行全表掃描，我們可以將兩個鍵合并到一個新列中，從而無需在整個應(yīng)用程序中傳遞 space_ids。

盡管有這些假設(shè)，分片還是取得了巨大的成功。對于 Notion 用戶來說，幾分鐘的停機時間使產(chǎn)品明顯更快。在內(nèi)部，我們在時間敏感的目標下展示了協(xié)調(diào)的團隊合作和果斷的執(zhí)行力。

腳注

• [1] 除了引入不必要的復(fù)雜性之外，過早分片的一個被低估的危險是它可以在產(chǎn)品模型在業(yè)務(wù)方面得到明確定義之前對其進行約束。例如，如果一個團隊按用戶分片并隨后轉(zhuǎn)向以團隊為中心的產(chǎn)品策略，那么架構(gòu)阻抗不匹配可能會導(dǎo)致嚴重的技術(shù)難題，甚至?xí)拗颇承┕δ堋?/li>
• [2] 除了打包的解決方案外，我們還考慮了一些替代方案：切換到另一個數(shù)據(jù)庫系統(tǒng)，如 DynamoDB(對于我們的用例來說風險太大)，并在裸機 NVMe 重型實例上運行 Postgres，以獲得更大的磁盤吞吐量(由于備份和復(fù)制的維護成本而被拒絕)。

https://aws.amazon.com/ec2/instance-types/i3en/

• [3] 除了基于鍵的分區(qū)(基于某些屬性劃分數(shù)據(jù))之外，還有其他方法：按服務(wù)進行垂直分區(qū)，以及使用中間查找表路由所有讀寫的基于目錄的分區(qū)。

https://www.startuplessonslearned.com/2009/01/sharding-for-startups.html?m=1#comment-form