美團面試：百億級分片，如何設計基因算法？

分庫分表背景知識

問題 1：爲什麼分庫分表？

大家都知道，當一個表（比如訂單表） 達到 500 萬條或 2GB 時，需要考慮水平分表。

爲啥？ 讀寫併發高場景，單服務器單一數據庫 CPU、內存、網絡 IO 壓力大。

所以，需要分庫，一個庫拆成多個庫。

同時，數據量大，單表存不下，需要分表，一張表拆分成多個表。

總之，分庫分表的原因是：

• 數據量大，選分表；

• 併發高，選分庫；

• 海量存儲 + 高併發，分庫 + 分表。

具體實操，請參考尼恩的硬核架構視頻

問題 2：如何做數據庫水平拆分？

分庫和分表， 主要還是 對數據的水平拆分，對數據的垂直拆分的重要程度弱太多，所以這個不做介紹。

水平分片又稱爲橫向拆分。

相對於垂直分片，它不再將數據根據業務邏輯分類，而是通過某個字段（或某幾個字段），根據某種規則將數據分散至多個庫或表中，每個分片僅包含數據的一部分。

例如：根據主鍵分片，偶數主鍵的記錄放入 0 庫（或表），奇數主鍵的記錄放入 1 庫（或表），如下圖所示。

水平分片從理論上突破了單機數據量處理的瓶頸，並且擴展相對自由，是數據分片的標準解決方案。

對數據的水平拆分 ，核心的設計是：

• 1： 用哪個字段拆分表，

• 2： 用什麼路由策略尋找目標庫表。

分片鍵的設計目標、建議

數據庫水平拆分的字段叫分片鍵。分片鍵也稱爲 Sharding key

關於分片鍵的選擇，我們需要選擇具有共性的字段是最基本的要求，也是就儘量能覆蓋絕大多數查詢場景。

同時分片鍵也應具有足夠龐大的基數以及唯一性，從而使 Shard 可靈活規劃，具備較好的擴展性。

舉個反例，如果選取布爾類型的字段爲分片鍵，那麼分片最多隻能存在兩份，這就陷入了非常尷尬的局面，基本失去了 Sharding 的意義。

如何做 Sharding key 的設計呢？

• 最常見的情況是：用表的單個字段做分片鍵，

• 複雜情況是：可以用兩個或多個字段組合成分片鍵。

Sharding key 的設計目標：

合理選擇 Sharding key，避免大多數的查詢變成重量級操作，比如：

• 跨庫查詢

• 全表路由

40 歲老架構師尼恩的建議是：

• 合理選擇 Sharding key， 盡一切可能減少 全表路由、跨庫查詢，

• 從而使得大部分查詢在 單庫實現結果閉環，從而減少 多庫之間大的數據合併和二次排序， 從而提升分庫分表的吞吐量和性能。

分片鍵的設計建議：

• 選擇具有共性的字段作爲分片鍵，即查詢中高頻出現的條件字段；

• 分片字段應具有高度離散的特點，分片鍵的內容不能被更新；

• 可均勻各分片的數據存儲和讀寫壓力，避免片內出現熱點數據；

• 儘量減少單次查詢所涉及的分片數量，降低數據庫壓力；

• 最後，不要更換分片鍵，更換分片鍵需重分佈數據，代價較大。

分片鍵的設計原則

• 選擇查詢頻率最高的字段

  分片鍵要能覆蓋絕大多數查詢場景，它決定了數據查詢的效率。

  正例：單號，id，時間字段

  反例：姓別、商品類別

• 分片鍵不可以更新

  分片鍵如果更新了，按原來的路由算法會計算出不同的庫表地址，舊的數據無法正確讀取

• 分片鍵不可以更換

  分片鍵更換，意味着數據要重新分佈，代價昂貴。

• 分片字段應有離散特性

  分片鍵越離散，越容易把數據均勻分佈在不同庫表。

分片鍵的設計方案

按分片鍵的查詢可以直接定位到目標庫表，那麼不按分片鍵的查詢，是否只能遍歷所有庫表了呢？

舉例：

• 電商領域有用戶表和訂單表。

• 訂單表按訂單號分庫分表，

• 同時訂單表有用戶 id 字段。

假如查詢某個用戶（比如 user-id=200）的訂單，怎麼查呢？

此時，如果無法預知這個用戶的數據存在訂單的哪個庫表，那麼，其實就需要走 全表路由， 把請求路由到 這個表的所有的數據分片。

全表路由 具體如下圖所示：

前面講到，Sharding key 的設計目標：

合理選擇 Sharding key，避免大多數的查詢變成重量級操作，比如：

• 跨庫查詢

• 全表路由

合理選擇 Sharding key， 盡一切可能減少 全表路由、跨庫查詢， 從而使得大部分查詢在 單庫實現結果閉環，從而減少 多庫之間大的數據合併和二次排序， 從而提升分庫分表的吞吐量和性能。

如何去掉這裏的 全表路由，提升查詢效率呢？

針對這種非分片鍵的查詢，有幾種設計思路提升查詢效率：

1 索引法

索引法的思路是，把非分片鍵和分片鍵的映射關係保存起來，

查詢數據時，先從這個映射關係查找分片鍵，再用分片鍵路由到目標庫表。

• 索引表

  額外建一張表保存訂單號和用戶 id 的映射關係。

優點：實現簡單

缺點：

• 查詢數據多查一次索引表，性能低。

• 索引表可能會很大，甚至索引表本身要分表。

緩存映射關係

尼恩的 3 高架構宇宙中，有一條亙古不變的天條： 性能不夠，緩存來湊。

既然索引表性能低，那麼 用 Redis 保存訂單號和用戶 id 的映射關係。

優點：查詢速度比索引錶快。

缺點：數據量大時，佔用大量內存，緩存不斷淘汰，命中率低，沒有命中緩存還是得查索引表。

無論是用索引表還是用 Redis，都無法在大數據量下有效查找分片鍵。

2 基因法

基因法的思路是，把非分片鍵到分片鍵的映射關係內嵌在非分片鍵字段，嵌入到非分片鍵的這部分內容就是基因。

基因法是大廠常常使用的方案，

比如，將買家 ID 融入到訂單 ID 中，作爲訂單 ID 後綴。這樣，指定買家的所有訂單就會與其訂單在同一分片內了，如下圖所示。

再具體一點：

• 假如訂單表用訂單號 %16 路由，分 16 庫表。

• 用戶下單生成訂單號時，訂單號的最後 4 個 bit 位，通過位運算，設置爲用戶 id 的最後 4bit 位，那麼，訂單號的最後 4 個 bit 位就是訂單號的用戶基因。

此情此景，如果在 查詢某個用戶的訂單，就不用全表路由了。

現在是單片路由，直接根據用戶 id 的最後 4bit 位，路由到訂單的目標庫表。

3 基因法的理論基礎

如果對一個 10 進制的數字按 10 取模，取模的結果只與這個數字最後 1 位有關：

199%10=9

19999%10=9

1234567899%10=9

同理，按 100(10^2) 取模，取模的結果只與這個數字最後 2 位有關：

199%100=99

19999%100=99

1234567899%100=99

同理，一個二進制的數字，按 2^n 取模，只與這個數字最後 n 位有關：

例：n=3，2^3=1000

10001111%(1000)=111, 即十進制的 143%8=7

10011111%(1000)=111, 即十進制的 159%8=7

因此，訂單表用訂單號 %16 分庫分表，對 16(2^4) 取模的結果只和二進制訂單號的最後 4 位有關，這 4 位決定了數據落在哪個庫表上。

4 數字類型的分片鍵設計

假如訂單號是雪花算法生成的 long 類型數字，要在雪花算法的 64 個 bit 位中預留 4 位，用 uid 的後 4 位填充。

5 字符串類型分片鍵設計

假如訂單號是一個字符串，將 uid 後 4bit 位轉爲字符串後拼接在訂單號後面即可。

按某個業務規則生成的訂單號：ORDER20240101

帶有 uid 基因的訂單號：ORDER20240101-0,ORDER20240101-15

6 基因法的優缺點：

• 優點：無論按照分片鍵還是按某個非分片鍵查數據，都可以直接定位到目標庫表，性能比索引法高。

• 缺點：需要提前規劃好庫表容量，不方便擴容。

擴展方案設計：多個非分片鍵的組合查詢

基因法解決了單個非分片鍵的數據查詢路由問題，減少了全表路由的出現。

但是，如果有多個非分片鍵查詢，是否要在分片鍵中融入多個基因呢？

No。

分片鍵的設計不應過於複雜，況且，即使能融入多個基因，又如何支持多個非分片鍵組合條件查詢呢？

數據庫不支持任意字段任意組合的高性能查詢，這不是數據庫的長項，應該用 ES、ClickHouse 等其他中間件來解決這類問題。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/JS7-Xu180704WY7LDrebYw