分散式資料庫的存儲設計改進

在一次游泳的時候，想起一個問題，為什麼 hdfs 的 namenode 沒有存儲塊的對應節點信息，導致啟動 hdfs 的時候，datanode 需要掃描所有的數據塊，再將該 datanode 上的塊信息發送給 namenode，namenode 才能構建完整的元數據信息。根據文件和數據塊的多少，啟動 hdfs 的時候需要幾分鐘到幾個小時。

對比下分散式資料庫，如果把記錄對應的節點信息發送給 Master，那就不可想象了。所以在分散式資料庫中 hdfs 的存儲策略不可取。同時最近一直被目前的分散式資料庫的存儲上有幾個問題困擾著:

• 在節點數固定的時候，Hdfs 的數據是根據機器負載來決定存儲在哪個節點上的，這樣做的好處是數據平均分佈，可以根據機器的存儲大小加權平均，並且依據機器的負載情況動態調整；目前分散式分散式資料庫中做的很有限，該如何改進呢?

• 添加新節點的時候， Hdfs 配置好新節點指向的 namenode，然後啟動新節點即可，存儲過一段時間會收斂到平均，如果想加入后馬上使得數據平均分佈，可以執行 rebalance 操作；而分散式資料庫添加節點的時候，配置好新節點指向的 Master，然後啟動新節點之後，通常還需要根據分佈的規則進行數據重新分佈，甚至規則也可能需要進行拆分合併擴展等修改，分散式資料庫能做到什麼程度，如何做? 當然如果能做到數據重新分佈，rebalance 的操作也就可以加入到分散式資料庫中，兩者是共通的，都是做數據的移動，數據重新分佈關注過程，rebalance 關注結果。

在進一步的討論如何改進分散式資料庫的存儲之前，先看看分散式資料庫和 hadoop 中 hdfs 的對比。

Figure 1: 分散式資料庫的架構

Figure 2:hadoop 中 hdfs 的架構

前面提到分散式資料庫中把記錄對應的節點信息上報給 master 是不可行的方案，這裡其實是一種誇大的對比，兩者中的概念按照如下的類比更加合適：

從以上的對比可以看出，如果分散式資料庫的節點如果和 datanode 一樣，能夠在啟動的時候掃描該實例上的表信息，上報給 master，那麼分散式資料庫的做法就可以和 hadoop 中的 hdfs 方式一樣，即表的分區隨機分散在 dbnode 上，這樣元數據的大小也不會特別大。但我們需要注意到這種隨機的方式，使得讀寫數據的時候，客戶端需要知道數據位於哪個或者哪些節點，這樣對已有數據的讀寫需要經過兩步，首先請求 master 數據位於哪個節點，如 hadoop 中 hdfs 需要向 namenode 請求讀寫數據所在的 datanode 信息，然後在向 datanode 發送讀寫命令；如果數據是有規則的分佈在節點中，那麼可以將這些規則信息存儲在客戶端中，避免讀寫操作頻繁請求 master，這對高併發的場合非常有效。所以這篇文章我們還是拋棄隨機的分佈，採用有規則的方式來討論分散式資料庫的存儲。

從存儲架構和概念上看這兩者非常的相似，甚至都可以歸一化了，所以分散式資料庫的 sql 計算也可以借鑒 hadoop 中的 mapreduce 計算模型，這篇文章主要討論存儲的改進，為計算打好基礎；從上面的背景和問題可以看出，hdfs 有缺點，也有優點；目前的分散式資料庫有不足，也有比 hdfs 做的好地方；這篇文章基於這些優缺點，帶著這些問題，采眾家之長，對目前的分散式資料庫的存儲進行了分析和改進，為基於分散式資料庫的分散式 sql 計算能夠更好的利用 hadoop 生態圈中的 mapreduce，spark 等分散式計算模型打下良好的基礎。

從上面的問題中，經過思考可以發現，分散式資料庫的數據是不能隨機分佈的，是必須有規則的，但是規則需要能夠動態調整，才能解決以上問題，同時沒有 hdfs 啟動掃描數據塊導致啟動時間過長的問題。正因為規則是需要能夠動態調整的，所以需要採集資料庫節點的負載情況，因為這是規則動態調整的依據。下面就具體分析如何做，有哪些方式可以做。

需要採集的負載數據，大概包括如下方面:

• 機器的 cpu，內存使用，io 情況，網路流量，磁碟存儲大小等

• 資料庫的存儲大小，qps，tps，慢查詢，鎖，臨時表，連接數等

這些指標中比較關鍵的指標任何一個超過了它的閾值，這節點就不可以再插入數據，每個指標的閾值根據機器的配置決定；

下面給出一個指標的閾值例子，如下表所示:

通過這隻指標可以計算一個值 db_node_load(0<=db_node_load<=1，0 表示沒有負載，1 表示負載已滿)，並且設置一個閾值 insert_load_threshold，db_node_load 小於 insert_load_threshold 的時候，這個節點是可以插入數據的； db_node_load 大於等於 insert_load_threshold 的時候，這個節點是不可以插入數據的；這裡只考慮了插入；對於刪除，都必須在這個節點執行；對於更新，如果更新前和更新后的數據都在該節點上，也必須在這個節點執行；如果不在同一個節點，那麼在當前節點刪除，重新按照規則加負載情況選擇一個新的節點進行插入。計算 db_node_load 的公式是每個因素的當前值除以該因素的最大值的加權平均，指標的最大值根據機器的配置決定，各個指標的所佔比例的例子如下：

那麼 db_node_load = 20%*300/600+8%*5/100+20%*10/100+2%*80/100+20%*200/500+10%*1000/10000+10%*50/1000+10%*2/50=0.239

所謂的分佈規則，包含兩個要素

• 分割欄位，也叫均衡欄位， 存儲數據的時候決定將數據插入分散式表的某個節點的依據欄位，可以是一個或者多個有順序關係的欄位，欄位可以是數字，也可以是字元串，字元串通常轉換為數字；如常用的用戶 id

• 分割方法，也叫均衡策略， 存儲的時候決定如何根據分割欄位將數據插入分散式表的某個節點的方法，如列表，範圍，取余

先簡單舉例說明基本的均衡策略，基本信息如下：表名字：tab_user_login表描述：用於存儲用戶登錄信息節點數：4，分別為 0、1、2、3欄位信息：

列表

以登錄省份作為均衡欄位

範圍

從 0 到一億，以用戶 id 作為均衡欄位

取余 (節點數為除數，即除以節點數取餘數)

以用戶 id 作為均衡欄位，節點數為 4

• 列表的均衡策略使用的場景主要是依據幾個列表值，如省份，大區，按月存儲等，多個列表值可以存儲到同一個節點中；

• 範圍的均衡策略，根據需求確定數據的最大最小值，然後根據每個節點的存儲計算能力和節點數決定每個節點分配範圍，即按照節點能力進行加權平均分配，範圍小的數據分為到 id 小的節點上；需要增加節點的時候，從以前最大節點的最大值開始，為新添加的節點重新分配數據的範圍；這種均衡策略的應用場景比較廣泛， 可以使用在自增的虛擬 id，用戶 id，時間等欄位上面；而且在分散式資料庫中執行 select 查詢的時候，涉及到 order，group，非等值 join 等需要排序的操作，並且這些操作的欄位是均衡欄位的時候，洗牌 (shuffle) 就可以忽略，因為節點 id 是順序的，節點 id 小的節點中存儲的數據小，再加上均衡欄位上通常有索引，排序的操作會非常高效。 這種均衡策略也有一些不足，數據是否平均分佈依賴為每個節點分配的最大最小值；如果數據是虛擬 id 作為分割欄位，遞增，插入的數據基本上都是在最大的節點中，其他節點基本上沒有插入，只有查詢；如果數據是用戶 id 作為分割欄位，新註冊的用戶 id 是遞增，那麼新註冊的用戶數據基本上都是在最大的節點中，數據分步有個明顯的特徵，連續註冊的用戶的數據基本都在相同的節點中，這樣在高峰期，推廣期，活動期某些節點的負載比較高，負載就會出現不均衡；

• 取余的均衡策略能夠解決範圍的均衡策略節點負載可能不均衡的問題，數據理論上是平均分佈的；但是如果節點之間的性能是不平均的，那麼就存在木桶效應，每個節點的存儲容量和性能最大值 (性能瓶頸) 就是性能最差的那個節點；同時這種均衡策略不具備範圍的均衡策略中某些場景中洗牌和排序的高效特徵。

前面提到規則需要動態調整，或者數據重新分佈，這裡指的是調整某個均衡策略內部的參數或者規則數據本身，而非轉換均衡策略， 這三種均衡策略下的數據重新分佈如下：

• 列表的均衡策略需要將變動的列表數據重新分佈，如上面的例子中將黑龍江省的數據從 2 號節點移動到 3 號節點，那麼只需要移動黑龍江省的數據；

• 範圍的均衡策略，可以移動節點中的整個範圍，也可以移動節點中的部分範圍，從這點來說，範圍的均衡策顯得更加靈活，如上面例子中將用戶 id 範圍為 2500w <=value<5000w 的整體範圍從 2 號節點移動到 3 號節點，也可以將用戶 id 範圍為 4500w <=value<5000w 的部分範圍從 2 號節點移動到 3 號節， 用戶 id 範圍為 2500w <=value<4500w 的部分範圍保留在 2 號節點；

• 取余的均衡策略比較特殊， 列表和範圍的均衡策略在節點數不變的時候可以重新分佈數據，而取余的均衡策略則不能重新分佈；如果增加節點數，節點 id 依次增加，計算新的節點數和老的節點數的最小公倍數， 一條記錄的均衡欄位對最小公倍數取余，如果餘數小於等於老的節點數 (小的節點數)，那麼這條記錄不用移動，否則需要移動這條記錄到均衡欄位對新的節點數的餘數對應的節點中；如果減少節點數，刪除節點 id 的大的節點， 計算新的節點數和老的節點數的最小公倍數， 一條記錄的均衡欄位對最小公倍數取余，如果餘數小於等於新的節點數 (小的節點數)，那麼這條記錄不用移動，否則需要移動這條記錄到均衡欄位對新的節點數的餘數對應的節點中；舉例說明，增加節點的時候，從 4 個節點增加到 6 個節點，4 和 6 的公倍數是 12，用記錄的均衡欄位對最小公倍數取余，結果為 0 到 11，那麼餘數 0 到 4 的記錄不用移動，餘數為 5 到 11 的需要移動；減少節點的時候，從 8 個節點減少到 6 個節點，8 和 6 的公倍數是 24，用記錄的均衡欄位對最小公倍數取余，結果為 0 到 23，那麼餘數 0 到 6 的記錄不用移動，餘數為 7 到 23 的需要移動。

以上的均衡策略可以任意的組合，如果選擇兩個，則有六種組合的均衡策略。

挑選比較典型的序號為 4 的組合， 先使用範圍，再使用取余為例進行說明

先使用範圍，再使用取余

例如，以用戶 id 作為均衡欄位，每個範圍有 10000 個值，節點數為 4，那麼結果如下：

從這個例子中，可以發現， 先使用範圍，再使用取余的組合策略可以綜合兩者的優勢，包含範圍的大小順序和取余的數據平均分佈優勢，但其實也在一定程度上削弱了優勢，具體的說，某個表的記錄就不是總體上按照順序大小存儲，而是每 10000 條記錄這個小範圍內是有順序大小的，每 10000 個的節點分佈是按照取余規則的分佈在不同的節點上；某個表的數據也不是在記錄級別上平均分佈，而是以 10000 條記錄為粒度進行平均分佈的；我們設計的時候需要根據實際情況來確定是選擇 10000，還是 1024 或者 1048576 等。選擇的越小 (細粒度)，在動態調整的時候也可以更加靈活；在實際中，節點數通常不多，那麼細粒度就會打折扣；如 4 個節點，我們需要移動 1 億條記錄中的 1000 萬，那麼每個節點平均需要移動的是 250w， 每個範圍有 10000 個值就顯得小了，導致範圍數就多，元數據就顯著增加；如果有 10 個節點，那麼每個節點平均只需要移動 100w 記錄。同時觀察上面的例子，可以發現，取余之後的值 V2 和節點 id 是一一對應並且數量一致。但其實我們也採用其他方式，如列表，範圍和取余方式；處理方法是將取余計算中除數換成的節點數的倍數 (而非節點數本身)，具體幾倍依據數據量的大小和以後系統的擴容需求； 這種實際上已經是三個基本均衡策略的組合了，在下面的討論中，這種方式對元數據的大小沒有顯著的增加， 通常選擇較大的數比較好，如節點數的 8 倍，32 倍甚至 128 倍。

三個基本均衡策略的組合

按照上面的分析， 三個基本均衡策略的組合是基於兩個個基本均衡策略的組合，如下：

先使用範圍，再使用取余，再使用範圍

例如，以用戶 id 作為均衡欄位，每個範圍有 10000 個值，取余的除數為 32，結果如下：

在上一步得到 V2 的基礎上，如果節點數為 4， 那麼每 8 個餘數順序放到節點中，結果如下：

先使用範圍，再使用取余，再使用取余

在上一步得到 V2 的基礎上，如果節點數為 4， 那麼 V2 按照 4 取余，意義對應到節點 id，結果如下：

這兩種均衡策略的結果從效果上看都是先使用範圍，再使用取余；最後使用範圍策略的使得每 8 萬一個範圍，最後使用取余策略的範圍還是 1 萬一個，除數都為節點數，這樣一來，使得數據重新分佈的靈活性增加，同時不失規則性，為數據的動態重新分佈打好基礎。

首先介紹一個概念移動邏輯數據塊，或者叫數據窗口 (move logic data chunk)， 移動數據時，一個節點內可以移動到另外一個節點內的連續實際數據記錄數。需要根據老的分佈規則和新的分佈規則的確定，通常是針對範圍的均衡策略或者包含範圍的組合均衡策略，窗口的大小要小於等於移動的數據所處的那個範圍的大小，如範圍的均衡策略例子中，0 號節點中 0<=value<2500w ， 那麼數據窗口可以選擇 1 到 2500w 中 2500w 的因子，如 1000，100w 等，太小導致窗口數太多，太大導致窗口數小，併發數提高不了。 進一步說，窗口的大小是老的分佈規則和新的分佈規則中數據所處的那個範圍的大小的公約數，實際中兩者是倍數的關係，取小的即可，如果小的數也比較大，如 500w，還可以取這個數的足夠小的某個約數，如 1w。

下面從以下幾個場景說明數據動態重新分佈:

• 插入數據的時候，本來這條記錄需要插入節點 A，發現節點 A 的負載高，不允許插入，這時調整規則，將節點 A 中的這條記錄所處範圍的一部分或者整體移動到 B 節點；

• 加入新節點的時候，需要將原來某幾個節點 (如 A1 到 A4) 上某些範圍的一部分或者整體移動到新節點上；刪除節點的時候， 需要將刪除的節點 (如 A3 到 A4) 上範圍整體移動到其他不刪除的節點上；

• 發現數據不均衡，人工手動觸發數據重新分佈，這種場景和加入和刪除節點，本質上沒有區別，就是在已有的節點中移動數據，而不涉及新加的或者要刪除的節點。

數據的移動，特別是大量數據的移動，勢必對業務的操作帶來影響，如果控制不好的話，可能是災難；問題列舉如下:

場景 1 下，插入的數據是先插入老節點再移動還是先移動再插入新節點，先插入情況下可能偶爾資料庫本身負載高到不能插入，先移動情況下，可能導致插入延遲又比較大，導致用戶響應比較慢；

場景 1，2，3 下，移動數據窗口的時候，業務上可能對這個窗口進行數據操作，插入，更新，刪除都有可能，時間上可能業務先操作和鎖定記錄，然後移動，也有可能先移動，移動過程中，操作了已經移動的數據或者操作和鎖定還沒有移動的記錄；

設計好的系統，可能不太需要數據的移動，但是從一般的角度考慮，它是一個比較頻繁的操作，而且涉及跨節點的插入數據，刪除數據，修改規則元數據，這三者需要在一個事務中完成，所以需要使用分散式事務。為了保證移動數據的時候業務的正常運行，我們需要做如下的設計：

• 對於已經移動的小窗口內的插入或者覆蓋 (replace) 操作，插入或者覆蓋 (replace) 到新節點

• 對於已經移動的小窗口內的刪除操作，在新節點刪除對應記錄

• 對於已經移動的小窗口內的更新操作，在新節點更新對應記錄

以上所討論的數據重新分佈主要是確定好前後的規則，後面的工作就是根據前後的規則去遷移數據和修改元數據

如老的均衡策略從 0 到一億，以用戶 id 作為均衡欄位； 分佈如下:

場景 1:4 個節點存儲或者性能都達到了閾值，需要擴容，計劃每個節點拆分成兩個相等的部分，那麼新的分佈結果如下：

場景二：3 號節點由於性能不足，添加一個 4 號節點， 3 號節點的數據拆到 3 號和 4 號中，同時擴大用戶範圍到 4 億，使用性能比較高的 5，6，7 號節點，每個節點存儲一個億，那麼新的分佈結果如下:

使用先使用範圍，再使用取余的數據動態重新分佈

舉例說明，以上的先使用範圍，再使用取余作為老的分佈，如下:

場景 1: 現在需要按照 20000 一個範圍，那麼就是每 8w 條記錄平均分佈在 4 個節點中，新的分佈結果如下:

數據的均衡策略或者分佈規則是一把雙刃劍，Hdfs 的數據是隨機的，節點上報的形式，所以能夠動態調整，無需數據重新分佈，缺點是啟動需要掃描，導致啟動慢；分散式資料庫的均衡策略是有規則的，規則通常存在在元數據中，Master 啟動時載入元數據就可以，元數據通常很小，所以啟動很快；但是規則的動態調整比較麻煩， 數據的重新分佈也是必須的工作；基本的規則比較簡單，但調整動態調整量比較大，耗時長；組合的規則稍微複雜，但調整的數據量會縮小，耗時短。

聽說可以快速學習成為雙料 DBA？