分庫分表在 sharding 中的實現

爲什麼要分庫分表？

隨着公司業務快速發展，數據庫中數據量猛增，訪問性能變慢。關係型數據庫本身比較容易成爲系統瓶頸、單機存儲容量、連接數、處理能力有限。當單表的數據量達到 1000W 或 100G 以後，由於查詢緯度較多，即使添加從庫、優化索引，做很多操作時性能仍下降嚴重。

方案一：通過提升硬件來提高數據處理能力，比如增加存儲容量、CPU 等，這種方案成本較高，並且瓶頸在數據庫服務本身，通過提高硬件得到的提升有限;

方案二：分庫分表，使得單一數據庫、單一數據表的數據量變小，從而達到提升數據庫性能的目的。

分庫分表的方式

垂直拆分

通過將一個表按字段拆分成多張表，每張表只存儲其中的部分字段。

帶來的提升：

  1. 減少了 IO 爭搶，並減少了鎖表的概率，瀏覽商品的用戶，跟運營配置商品使用規則不會互相沖突。

  2. 提升數據庫 IO 效率，防止跨頁，提高索引效率，充分發揮熱門數據的操作效率，商品信息的操作效率不會被拖累。

垂直拆分後，可以對商品信息表再做水平拆分。

水平拆分

按照業務將一張大表裏的數據根據規則拆分到多張表中。（對數據的拆分，不影響表結構）

一致性 hash 算法

傳統 hash 取模方式的侷限性

  1. 減少節點時;

  2. 增加節點時;

一致性哈希算法通過一個叫作一致性哈希環的數據結構實現。這個環的起點是 0，終點是 2^32 - 1，並且起點與終點連接，故這個環的整數分佈範圍是 [0, 2^32-1]，如下圖所示：

假設，我們現在對認領記錄 t，按 opportunity_id 維度分表，分成了 t_0,t_1,t_2,t_3 四張表，然後我們將這 4 張表分別進行 hash 運算，取值範圍是 0-2^32-1，這樣，我們可以得到 hash 環上的 4 個點，分別標記爲 4 張表的位置。

然後我們用同樣的 hash 函數對接下來收到的每一條認領記錄的 opportunity_id 進行運算，這樣我們也得到了每一條認領記錄在 hash 環上的位置。

然後接下來，在 hash 環上按順時針方向找到離認領記錄最近的一張表，將認領記錄保存到這張表中。

新增表節點

假設在 t1/t2 表節點中間新增了一張表 t5，那麼需要移動的數據只有 t1-t5 之間的數據，相比於普通的 hash 算法，需要轉移的數據大大減少。

數據遷移

  1. 停機遷移

  2. 雙寫

shardingJDBC 中的路由引擎

改寫引擎

正確性改寫

在包含分表的場景中，需要將分表配置中的邏輯表名稱改寫爲路由之後所獲取的真實表名稱。僅分庫則不需要表名稱的改寫。除此之外，還包括補列和分頁信息修正等內容。

標誌符改寫

需要改寫的標識符包括表名稱、索引名稱以及 Schema 名稱。

表名稱改寫是指將找到邏輯表在原始 SQL 中的位置，並將其改寫爲真實表的過程。表名稱改寫是一個典型的需要對 SQL 進行解析的場景。從一個最簡單的例子開始，若邏輯 SQL 爲：

SELECT order_id FROM t_order WHERE order_id=1;

假設該 SQL 配置分片鍵 order_id，並且 order_id=1 的情況，將路由至分片表 1。那麼改寫之後的 SQL 應該爲：

SELECT order_id FROM t_order_1 WHERE order_id=1;

補列

需要在查詢語句中補列通常由兩種情況導致。第一種情況是 ShardingSphere 需要在結果歸併時獲取相應數據，但該數據並未能通過查詢的 SQL 返回。這種情況主要是針對 GROUP BY 和 ORDER BY。結果歸併時，需要根據 GROUP BY 和 ORDER BY 的字段項進行分組和排序，但如果原始 SQL 的選擇項中若並未包含分組項或排序項，則需要對原始 SQL 進行改寫。先看一下原始 SQL 中帶有結果歸併所需信息的場景：

SELECT order_id, user_id FROM t_order ORDER BY user_id;

由於使用 user_id 進行排序，在結果歸併中需要能夠獲取到 user_id 的數據，而上面的 SQL 是能夠獲取到 user_id 數據的，因此無需補列。

如果選擇項中不包含結果歸併時所需的列，則需要進行補列，如以下 SQL：

SELECT order_id FROM t_order ORDER BY user_id;

由於原始 SQL 中並不包含需要在結果歸併中需要獲取的 user_id，因此需要對 SQL 進行補列改寫。補列之後的 SQL 是：

SELECT order_id, user_id AS ORDER_BY_DERIVED_0 FROM t_order ORDER BY user_id;

補列的另一種情況是使用 AVG 聚合函數。在分佈式的場景中，使用 avg1 + avg2 + avg3 / 3 計算平均值並不正確，需要改寫爲 (sum1 + sum2 + sum3) / (count1 + count2 + count3)。這就需要將包含 AVG 的 SQL 改寫爲 SUM 和 COUNT，並在結果歸併時重新計算平均值。例如以下 SQL：

SELECT AVG(price) FROM t_order WHERE user_id=1;

需要改寫爲：

SELECT COUNT(price) AS AVG_DERIVED_COUNT_0, SUM(price) AS AVG_DERIVED_SUM_0 FROM t_order WHERE user_id=1;

然後才能夠通過結果歸併正確的計算平均值。

分頁修正

從多個數據庫獲取分頁數據與單數據庫的場景是不同的。假設每 10 條數據爲一頁，取第 2 頁數據。在分片環境下獲取 LIMIT 10, 10，歸併之後再根據排序條件取出前 10 條數據是不正確的。舉例說明，若 SQL 爲：

SELECT score FROM t_score ORDER BY score DESC LIMIT 1, 2;

下圖展示了不進行 SQL 的改寫的分頁執行結果。

通過圖中所示，想要取得兩個表中共同的按照分數排序的第 2 條和第 3 條數據，應該是 95 和 90。由於執行的 SQL 只能從每個表中獲取第 2 條和第 3 條數據，即從 t_score_0 表中獲取的是 90 和 80；從 t_score_0 表中獲取的是 85 和 75。因此進行結果歸併時，只能從獲取的 90，80，85 和 75 之中進行歸併，那麼結果歸併無論怎麼實現，都不可能獲得正確的結果。

正確的做法是將分頁條件改寫爲 LIMIT 0, 3，取出所有前兩頁數據，再結合排序條件計算出正確的數據。下圖展示了進行 SQL 改寫之後的分頁執行結果。

越獲取偏移量位置靠後數據，使用 LIMIT 分頁方式的效率就越低。有很多方法可以避免使用 LIMIT 進行分頁。比如構建行記錄數量與行偏移量的二級索引，或使用上次分頁數據結尾 ID 作爲下次查詢條件的分頁方式等。

分頁信息修正時，如果使用佔位符的方式書寫 SQL，則只需要改寫參數列表即可，無需改寫 SQL 本身。

批量拆分

在使用批量插入的 SQL 時，如果插入的數據是跨分片的，那麼需要對 SQL 進行改寫來防止將多餘的數據寫入到數據庫中。插入操作與查詢操作的不同之處在於，查詢語句中即使用了不存在於當前分片的分片鍵，也不會對數據產生影響；而插入操作則必須將多餘的分片鍵刪除。舉例說明，如下 SQL：

INSERT INTO t_order (order_id, xxx) VALUES (1, 'xxx'), (2, 'xxx'), (3, 'xxx');

假設數據庫仍然是按照 order_id 的奇偶值分爲兩片的，僅將這條 SQL 中的表名進行修改，然後發送至數據庫完成 SQL 的執行 ，則兩個分片都會寫入相同的記錄。雖然只有符合分片查詢條件的數據才能夠被查詢語句取出，但存在冗餘數據的實現方案並不合理。因此需要將 SQL 改寫爲：

INSERT INTO t_order_0 (order_id, xxx) VALUES (2, 'xxx');

INSERT INTO t_order_1 (order_id, xxx) VALUES (1, 'xxx'), (3, 'xxx');

使用 IN 的查詢與批量插入的情況相似，不過 IN 操作並不會導致數據查詢結果錯誤。通過對 IN 查詢的改寫，可以進一步的提升查詢性能。如以下 SQL：

SELECT * FROM t_order WHERE order_id IN (1, 2, 3);

改寫爲：

SELECT * FROM t_order_0 WHERE order_id IN (2);

SELECT * FROM t_order_1 WHERE order_id IN (1, 3);

可以進一步的提升查詢性能。

歸併引擎

排序歸併

由於在 SQL 中存在 ORDER BY 語句，因此每個數據結果集自身是有序的，因此只需要將數據結果集當前遊標指向的數據值進行排序即可。這相當於對多個有序的數組進行排序，歸併排序是最適合此場景的排序算法。

ShardingSphere 在對排序的查詢進行歸併時，將每個結果集的當前數據值進行比較（通過實現 Java 的 Comparable 接口完成），並將其放入優先級隊列。每次獲取下一條數據時，只需將隊列頂端結果集的遊標下移，並根據新遊標重新進入優先級排序隊列找到自己的位置即可。

通過一個例子來說明 ShardingSphere 的排序歸併，下圖是一個通過分數進行排序的示例圖。

圖中展示了 3 張表返回的數據結果集，每個數據結果集已經根據分數排序完畢，但是 3 個數據結果集之間是無序的。將 3 個數據結果集的當前遊標指向的數據值進行排序，並放入優先級隊列，t_score_0 的第一個數據值最大，t_score_2 的第一個數據值次之，t_score_1 的第一個數據值最小，因此優先級隊列根據 t_score_0，t_score_2 和 t_score_1 的方式排序隊列。

分組歸併

分組歸併的情況最爲複雜，它分爲流式分組歸併和內存分組歸併。流式分組歸併要求 SQL 的排序項與分組項的字段以及排序類型（ASC 或 DESC）必須保持一致，否則只能通過內存歸併才能保證其數據的正確性。

舉例說明，假設根據科目分片，表結構中包含考生的姓名（爲了簡單起見，不考慮重名的情況）和分數。通過 SQL 獲取每位考生的總分，可通過如下 SQL：

SELECT name, SUM(score) FROM t_score GROUP BY name ORDER BY name;

在分組項與排序項完全一致的情況下，取得的數據是連續的，分組所需的數據全數存在於各個數據結果集的當前遊標所指向的數據值，因此可以採用流式歸併。如下圖所示。

聚合歸併

比較類型的聚合函數是指 MAX 和 MIN。它們需要對每一個同組的結果集數據進行比較，並且直接返回其最大或最小值即可。

累加類型的聚合函數是指 SUM 和 COUNT。它們需要將每一個同組的結果集數據進行累加。

求平均值的聚合函數只有 AVG。它必須通過 SQL 改寫的 SUM 和 COUNT 進行計算。

分頁歸併

上文所述的所有歸併類型都可能進行分頁。分頁也是追加在其他歸併類型之上的裝飾器，ShardingSphere 通過裝飾者模式來增加對數據結果集進行分頁的能力。分頁歸併負責將無需獲取的數據過濾掉。

ShardingSphere 的分頁功能比較容易讓使用者誤解，用戶通常認爲分頁歸併會佔用大量內存。在分佈式的場景中，將 LIMIT 10000000, 10 改寫爲 LIMIT 0, 10000010，才能保證其數據的正確性。用戶非常容易產生 ShardingSphere 會將大量無意義的數據加載至內存中，造成內存溢出風險的錯覺。其實，通過流式歸併的原理可知，會將數據全部加載到內存中的只有內存分組歸併這一種情況。除了內存分組歸併這種情況之外，其他情況都通過流式歸併獲取數據結果集，因此 ShardingSphere 會通過結果集的 next 方法將無需取出的數據全部跳過，並不會將其存入內存。

但同時需要注意的是，由於排序的需要，大量的數據仍然需要傳輸到 ShardingSphere 的內存空間。因此，採用 LIMIT 這種方式分頁，並非最佳實踐。由於 LIMIT 並不能通過索引查詢數據，因此如果可以保證 ID 的連續性，通過 ID 進行分頁是比較好的解決方案，例如：

SELECT * FROM t_order WHERE id > 100000 AND id <= 100010 ORDER BY id;

或通過記錄上次查詢結果的最後一條記錄的 ID 進行下一頁的查詢，例如：

SELECT * FROM t_order WHERE id > 10000000 LIMIT 10；

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

猜你喜歡