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

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

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

https://uo.com/

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

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

決定何時(shí)分片

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

• 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)公司必須進(jìn)行微妙的權(quán)衡。在此期間，大量博客文章過(guò)早地闡述了分片的危險(xiǎn)：增加的維護(hù)負(fù)擔(dān)、應(yīng)用程序級(jí)代碼中新發(fā)現(xiàn)的約束以及架構(gòu)路徑依賴(lài)性。1當(dāng)然，在我們的規(guī)模上，分片是不可避免的。問(wèn)題只是什么時(shí)候。

• 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

對(duì)我們來(lái)說(shuō)，當(dāng) Postgres VACUUM 進(jìn)程開(kāi)始持續(xù)停止時(shí)，拐點(diǎn)就到了，阻止了數(shù)據(jù)庫(kù)從死元組中回收磁盤(pán)空間。雖然可以增加磁盤(pán)容量，但更令人擔(dān)憂(yōu)的是 transaction ID (TXID) wraparound，這是一種 Postgres 將停止處理所有寫(xiě)入以避免破壞現(xiàn)有數(shù)據(jù)的安全機(jī)制。意識(shí)到 TXID wraparound 會(huì)對(duì)產(chǎn)品構(gòu)成生存威脅，我們的基礎(chǔ)架構(gòu)團(tuán)隊(duì)加倍努力并開(kāi)始工作。

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

設(shè)計(jì)分片方案

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

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

應(yīng)用級(jí)分片

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

https://www.citusdata.com/

https://vitess.io/

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

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

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

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

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

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

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

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

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

每個(gè)工作空間在創(chuàng)建時(shí)都分配了一個(gè) UUID，因此我們可以將 UUID 空間劃分為統(tǒng)一的存儲(chǔ)桶。因?yàn)榉制碇械拿恳恍幸词且粋€(gè)塊，要么與一個(gè)塊相關(guān)，并且每個(gè)塊都屬于一個(gè)工作區(qū)，所以我們使用 workspace ID 作為分區(qū)鍵(partition key)。由于用戶(hù)通常一次在單個(gè)工作空間內(nèi)查詢(xún)數(shù)據(jù)，因此我們避免了大多數(shù)跨分片連接。

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

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

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

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

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

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

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

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

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

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

等所有分片表

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

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

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

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

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

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

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

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

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

遷移到分片

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

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

用審計(jì)日志雙重寫(xiě)入

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

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

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

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

我們選擇了 audit log 策略而不是邏輯復(fù)制，因?yàn)楹笳咴诔跏伎煺詹襟E中難以跟上 block 表寫(xiě)入量。

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

我們還準(zhǔn)備并測(cè)試了一個(gè)反向?qū)徲?jì)日志和腳本，以防我們需要從分片切換回單體應(yīng)用。該腳本將捕獲對(duì)分片數(shù)據(jù)庫(kù)的任何傳入寫(xiě)入，并允許我們?cè)趩误w應(yīng)用程序上重放這些編輯。最后，我們不需要恢復(fù)，但這是我們應(yīng)急計(jì)劃的重要組成部分。

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

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

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

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

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

• 驗(yàn)證腳本：我們的腳本驗(yàn)證了從給定值開(kāi)始的 UUID 空間的連續(xù)范圍，將單體上的每條記錄與相應(yīng)的分片記錄進(jìn)行比較。因?yàn)槿頀呙钑?huì)非常昂貴，所以我們隨機(jī)抽樣 UUID 并驗(yàn)證它們的相鄰范圍。
• “暗”讀：在遷移讀查詢(xún)之前，我們添加了一個(gè)標(biāo)志來(lái)從新舊數(shù)據(jù)庫(kù)中獲取數(shù)據(jù)(稱(chēng)為暗讀)。我們比較了這些記錄并丟棄了分片副本，記錄了過(guò)程中的差異。引入暗讀增加了 API 延遲，但提供了無(wú)縫切換的信心。

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

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

艱難的教訓(xùn)

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

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

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

腳注

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

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

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

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