在一次游泳的時候，想起一個問題，為什么 hdfs 的 namenode 沒有存儲塊的對應節(jié)點信息，導致啟動 hdfs 的時候，datanode 需要掃描所有的數(shù)據(jù)塊，再將該 datanode 上的塊信息發(fā)送給 namenode，namenode 才能構(gòu)建完整的元數(shù)據(jù)信息。根據(jù)文件和數(shù)據(jù)塊的多少，啟動 hdfs 的時候需要幾分鐘到幾個小時。
對比下分布式數(shù)據(jù)庫，如果把記錄對應的節(jié)點信息發(fā)送給 Master，那就不可想象了。所以在分布式數(shù)據(jù)庫中 hdfs 的存儲策略不可取。同時最近一直被目前的分布式數(shù)據(jù)庫的存儲上有幾個問題困擾著:
在節(jié)點數(shù)固定的時候，Hdfs 的數(shù)據(jù)是根據(jù)機器負載來決定存儲在哪個節(jié)點上的，這樣做的好處是數(shù)據(jù)平均分布，可以根據(jù)機器的存儲大小加權(quán)平均，并且依據(jù)機器的負載情況動態(tài)調(diào)整；目前分布式分布式數(shù)據(jù)庫中做的很有限，該如何改進呢?
添加新節(jié)點的時候， Hdfs 配置好新節(jié)點指向的 namenode，然后啟動新節(jié)點即可，存儲過一段時間會收斂到平均，如果想加入后馬上使得數(shù)據(jù)平均分布，可以執(zhí)行 rebalance 操作；而分布式數(shù)據(jù)庫添加節(jié)點的時候，配置好新節(jié)點指向的 Master，然后啟動新節(jié)點之后，通常還需要根據(jù)分布的規(guī)則進行數(shù)據(jù)重新分布，甚至規(guī)則也可能需要進行拆分合并擴展等修改，分布式數(shù)據(jù)庫能做到什么程度，如何做? 當然如果能做到數(shù)據(jù)重新分布，rebalance 的操作也就可以加入到分布式數(shù)據(jù)庫中，兩者是共通的，都是做數(shù)據(jù)的移動，數(shù)據(jù)重新分布關注過程，rebalance 關注結(jié)果。
在進一步的討論如何改進分布式數(shù)據(jù)庫的存儲之前，先看看分布式數(shù)據(jù)庫和 hadoop 中 hdfs 的對比。
Figure 1: 分布式數(shù)據(jù)庫的架構(gòu)
Figure 2:hadoop 中 hdfs 的架構(gòu)
前面提到分布式數(shù)據(jù)庫中把記錄對應的節(jié)點信息上報給 master 是不可行的方案，這里其實是一種夸大的對比，兩者中的概念按照如下的類比更加合適：
從以上的對比可以看出，如果分布式數(shù)據(jù)庫的節(jié)點如果和 datanode 一樣，能夠在啟動的時候掃描該實例上的表信息，上報給 master，那么分布式數(shù)據(jù)庫的做法就可以和 hadoop 中的 hdfs 方式一樣，即表的分區(qū)隨機分散在 dbnode 上，這樣元數(shù)據(jù)的大小也不會特別大。但我們需要注意到這種隨機的方式，使得讀寫數(shù)據(jù)的時候，客戶端需要知道數(shù)據(jù)位于哪個或者哪些節(jié)點，這樣對已有數(shù)據(jù)的讀寫需要經(jīng)過兩步，首先請求 master 數(shù)據(jù)位于哪個節(jié)點，如 hadoop 中 hdfs 需要向 namenode 請求讀寫數(shù)據(jù)所在的 datanode 信息，然后在向 datanode 發(fā)送讀寫命令；如果數(shù)據(jù)是有規(guī)則的分布在節(jié)點中，那么可以將這些規(guī)則信息存儲在客戶端中，避免讀寫操作頻繁請求 master，這對高并發(fā)的場合非常有效。所以這篇文章我們還是拋棄隨機的分布，采用有規(guī)則的方式來討論分布式數(shù)據(jù)庫的存儲。
從存儲架構(gòu)和概念上看這兩者非常的相似，甚至都可以歸一化了，所以分布式數(shù)據(jù)庫的 sql 計算也可以借鑒 hadoop 中的 mapreduce 計算模型，這篇文章主要討論存儲的改進，為計算打好基礎；從上面的背景和問題可以看出，hdfs 有缺點，也有優(yōu)點；目前的分布式數(shù)據(jù)庫有不足，也有比 hdfs 做的好地方；這篇文章基于這些優(yōu)缺點，帶著這些問題，采眾家之長，對目前的分布式數(shù)據(jù)庫的存儲進行了分析和改進，為基于分布式數(shù)據(jù)庫的分布式 sql 計算能夠更好的利用 hadoop 生態(tài)圈中的 mapreduce，spark 等分布式計算模型打下良好的基礎。
從上面的問題中，經(jīng)過思考可以發(fā)現(xiàn)，分布式數(shù)據(jù)庫的數(shù)據(jù)是不能隨機分布的，是必須有規(guī)則的，但是規(guī)則需要能夠動態(tài)調(diào)整，才能解決以上問題，同時沒有 hdfs 啟動掃描數(shù)據(jù)塊導致啟動時間過長的問題。正因為規(guī)則是需要能夠動態(tài)調(diào)整的，所以需要采集數(shù)據(jù)庫節(jié)點的負載情況，因為這是規(guī)則動態(tài)調(diào)整的依據(jù)。下面就具體分析如何做，有哪些方式可以做。
需要采集的負載數(shù)據(jù)，大概包括如下方面:
機器的 cpu，內(nèi)存使用，io 情況，網(wǎng)絡流量，磁盤存儲大小等
數(shù)據(jù)庫的存儲大小，qps，tps，慢查詢，鎖，臨時表，連接數(shù)等
這些指標中比較關鍵的指標任何一個超過了它的閾值，這節(jié)點就不可以再插入數(shù)據(jù)，每個指標的閾值根據(jù)機器的配置決定；
下面給出一個指標的閾值例子，如下表所示:
通過這只指標可以計算一個值 db_node_load(0<=db_node_load<=1，0 表示沒有負載，1 表示負載已滿)，并且設置一個閾值 insert_load_threshold，db_node_load 小于 insert_load_threshold 的時候，這個節(jié)點是可以插入數(shù)據(jù)的； db_node_load 大于等于 insert_load_threshold 的時候，這個節(jié)點是不可以插入數(shù)據(jù)的；這里只考慮了插入；對于刪除，都必須在這個節(jié)點執(zhí)行；對于更新，如果更新前和更新后的數(shù)據(jù)都在該節(jié)點上，也必須在這個節(jié)點執(zhí)行；如果不在同一個節(jié)點，那么在當前節(jié)點刪除，重新按照規(guī)則加負載情況選擇一個新的節(jié)點進行插入。計算 db_node_load 的公式是每個因素的當前值除以該因素的最大值的加權(quán)平均，指標的最大值根據(jù)機器的配置決定，各個指標的所占比例的例子如下：
那么 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
所謂的分布規(guī)則，包含兩個要素
分割字段，也叫均衡字段， 存儲數(shù)據(jù)的時候決定將數(shù)據(jù)插入分布式表的某個節(jié)點的依據(jù)字段，可以是一個或者多個有順序關系的字段，字段可以是數(shù)字，也可以是字符串，字符串通常轉(zhuǎn)換為數(shù)字；如常用的用戶 id
分割方法，也叫均衡策略， 存儲的時候決定如何根據(jù)分割字段將數(shù)據(jù)插入分布式表的某個節(jié)點的方法，如列表，范圍，取余
先簡單舉例說明基本的均衡策略，基本信息如下：表名字：tab_user_login表描述：用于存儲用戶登錄信息節(jié)點數(shù)：4，分別為 0、1、2、3字段信息：
列表
以登錄省份作為均衡字段
范圍
從 0 到一億，以用戶 id 作為均衡字段
取余 (節(jié)點數(shù)為除數(shù)，即除以節(jié)點數(shù)取余數(shù))
以用戶 id 作為均衡字段，節(jié)點數(shù)為 4
列表的均衡策略使用的場景主要是依據(jù)幾個列表值，如省份，大區(qū)，按月存儲等，多個列表值可以存儲到同一個節(jié)點中；
范圍的均衡策略，根據(jù)需求確定數(shù)據(jù)的最大最小值，然后根據(jù)每個節(jié)點的存儲計算能力和節(jié)點數(shù)決定每個節(jié)點分配范圍，即按照節(jié)點能力進行加權(quán)平均分配，范圍小的數(shù)據(jù)分為到 id 小的節(jié)點上；需要增加節(jié)點的時候，從以前最大節(jié)點的最大值開始，為新添加的節(jié)點重新分配數(shù)據(jù)的范圍；這種均衡策略的應用場景比較廣泛， 可以使用在自增的虛擬 id，用戶 id，時間等字段上面；而且在分布式數(shù)據(jù)庫中執(zhí)行 select 查詢的時候，涉及到 order，group，非等值 join 等需要排序的操作，并且這些操作的字段是均衡字段的時候，洗牌 (shuffle) 就可以忽略，因為節(jié)點 id 是順序的，節(jié)點 id 小的節(jié)點中存儲的數(shù)據(jù)小，再加上均衡字段上通常有索引，排序的操作會非常高效。 這種均衡策略也有一些不足，數(shù)據(jù)是否平均分布依賴為每個節(jié)點分配的最大最小值；如果數(shù)據(jù)是虛擬 id 作為分割字段，遞增，插入的數(shù)據(jù)基本上都是在最大的節(jié)點中，其他節(jié)點基本上沒有插入，只有查詢；如果數(shù)據(jù)是用戶 id 作為分割字段，新注冊的用戶 id 是遞增，那么新注冊的用戶數(shù)據(jù)基本上都是在最大的節(jié)點中，數(shù)據(jù)分步有個明顯的特征，連續(xù)注冊的用戶的數(shù)據(jù)基本都在相同的節(jié)點中，這樣在高峰期，推廣期，活動期某些節(jié)點的負載比較高，負載就會出現(xiàn)不均衡；
取余的均衡策略能夠解決范圍的均衡策略節(jié)點負載可能不均衡的問題，數(shù)據(jù)理論上是平均分布的；但是如果節(jié)點之間的性能是不平均的，那么就存在木桶效應，每個節(jié)點的存儲容量和性能最大值 (性能瓶頸) 就是性能最差的那個節(jié)點；同時這種均衡策略不具備范圍的均衡策略中某些場景中洗牌和排序的高效特征。
前面提到規(guī)則需要動態(tài)調(diào)整，或者數(shù)據(jù)重新分布，這里指的是調(diào)整某個均衡策略內(nèi)部的參數(shù)或者規(guī)則數(shù)據(jù)本身，而非轉(zhuǎn)換均衡策略， 這三種均衡策略下的數(shù)據(jù)重新分布如下：
列表的均衡策略需要將變動的列表數(shù)據(jù)重新分布，如上面的例子中將黑龍江省的數(shù)據(jù)從 2 號節(jié)點移動到 3 號節(jié)點，那么只需要移動黑龍江省的數(shù)據(jù)；
范圍的均衡策略，可以移動節(jié)點中的整個范圍，也可以移動節(jié)點中的部分范圍，從這點來說，范圍的均衡策顯得更加靈活，如上面例子中將用戶 id 范圍為 2500w <=value<5000w 的整體范圍從 2 號節(jié)點移動到 3 號節(jié)點，也可以將用戶 id 范圍為 4500w <=value<5000w 的部分范圍從 2 號節(jié)點移動到 3 號節(jié)， 用戶 id 范圍為 2500w <=value<4500w 的部分范圍保留在 2 號節(jié)點；
取余的均衡策略比較特殊， 列表和范圍的均衡策略在節(jié)點數(shù)不變的時候可以重新分布數(shù)據(jù)，而取余的均衡策略則不能重新分布；如果增加節(jié)點數(shù)，節(jié)點 id 依次增加，計算新的節(jié)點數(shù)和老的節(jié)點數(shù)的最小公倍數(shù)， 一條記錄的均衡字段對最小公倍數(shù)取余，如果余數(shù)小于等于老的節(jié)點數(shù) (小的節(jié)點數(shù))，那么這條記錄不用移動，否則需要移動這條記錄到均衡字段對新的節(jié)點數(shù)的余數(shù)對應的節(jié)點中；如果減少節(jié)點數(shù)，刪除節(jié)點 id 的大的節(jié)點， 計算新的節(jié)點數(shù)和老的節(jié)點數(shù)的最小公倍數(shù)， 一條記錄的均衡字段對最小公倍數(shù)取余，如果余數(shù)小于等于新的節(jié)點數(shù) (小的節(jié)點數(shù))，那么這條記錄不用移動，否則需要移動這條記錄到均衡字段對新的節(jié)點數(shù)的余數(shù)對應的節(jié)點中；舉例說明，增加節(jié)點的時候，從 4 個節(jié)點增加到 6 個節(jié)點，4 和 6 的公倍數(shù)是 12，用記錄的均衡字段對最小公倍數(shù)取余，結(jié)果為 0 到 11，那么余數(shù) 0 到 4 的記錄不用移動，余數(shù)為 5 到 11 的需要移動；減少節(jié)點的時候，從 8 個節(jié)點減少到 6 個節(jié)點，8 和 6 的公倍數(shù)是 24，用記錄的均衡字段對最小公倍數(shù)取余，結(jié)果為 0 到 23，那么余數(shù) 0 到 6 的記錄不用移動，余數(shù)為 7 到 23 的需要移動。
以上的均衡策略可以任意的組合，如果選擇兩個，則有六種組合的均衡策略。
挑選比較典型的序號為 4 的組合， 先使用范圍，再使用取余為例進行說明
先使用范圍，再使用取余
例如，以用戶 id 作為均衡字段，每個范圍有 10000 個值，節(jié)點數(shù)為 4，那么結(jié)果如下：
從這個例子中，可以發(fā)現(xiàn)， 先使用范圍，再使用取余的組合策略可以綜合兩者的優(yōu)勢，包含范圍的大小順序和取余的數(shù)據(jù)平均分布優(yōu)勢，但其實也在一定程度上削弱了優(yōu)勢，具體的說，某個表的記錄就不是總體上按照順序大小存儲，而是每 10000 條記錄這個小范圍內(nèi)是有順序大小的，每 10000 個的節(jié)點分布是按照取余規(guī)則的分布在不同的節(jié)點上；某個表的數(shù)據(jù)也不是在記錄級別上平均分布，而是以 10000 條記錄為粒度進行平均分布的；我們設計的時候需要根據(jù)實際情況來確定是選擇 10000，還是 1024 或者 1048576 等。選擇的越小 (細粒度)，在動態(tài)調(diào)整的時候也可以更加靈活；在實際中，節(jié)點數(shù)通常不多，那么細粒度就會打折扣；如 4 個節(jié)點，我們需要移動 1 億條記錄中的 1000 萬，那么每個節(jié)點平均需要移動的是 250w， 每個范圍有 10000 個值就顯得小了，導致范圍數(shù)就多，元數(shù)據(jù)就顯著增加；如果有 10 個節(jié)點，那么每個節(jié)點平均只需要移動 100w 記錄。同時觀察上面的例子，可以發(fā)現(xiàn)，取余之后的值 V2 和節(jié)點 id 是一一對應并且數(shù)量一致。但其實我們也采用其他方式，如列表，范圍和取余方式；處理方法是將取余計算中除數(shù)換成的節(jié)點數(shù)的倍數(shù) (而非節(jié)點數(shù)本身)，具體幾倍依據(jù)數(shù)據(jù)量的大小和以后系統(tǒng)的擴容需求； 這種實際上已經(jīng)是三個基本均衡策略的組合了，在下面的討論中，這種方式對元數(shù)據(jù)的大小沒有顯著的增加， 通常選擇較大的數(shù)比較好，如節(jié)點數(shù)的 8 倍，32 倍甚至 128 倍。
按照上面的分析， 三個基本均衡策略的組合是基于兩個個基本均衡策略的組合，如下：
先使用范圍，再使用取余，再使用范圍
例如，以用戶 id 作為均衡字段，每個范圍有 10000 個值，取余的除數(shù)為 32，結(jié)果如下：
在上一步得到 V2 的基礎上，如果節(jié)點數(shù)為 4， 那么每 8 個余數(shù)順序放到節(jié)點中，結(jié)果如下：
先使用范圍，再使用取余，再使用取余
例如，以用戶 id 作為均衡字段，每個范圍有 10000 個值，取余的除數(shù)為 32，結(jié)果如下：
在上一步得到 V2 的基礎上，如果節(jié)點數(shù)為 4， 那么 V2 按照 4 取余，意義對應到節(jié)點 id，結(jié)果如下：
這兩種均衡策略的結(jié)果從效果上看都是先使用范圍，再使用取余；最后使用范圍策略的使得每 8 萬一個范圍，最后使用取余策略的范圍還是 1 萬一個，除數(shù)都為節(jié)點數(shù)，這樣一來，使得數(shù)據(jù)重新分布的靈活性增加，同時不失規(guī)則性，為數(shù)據(jù)的動態(tài)重新分布打好基礎。
首先介紹一個概念移動邏輯數(shù)據(jù)塊，或者叫數(shù)據(jù)窗口 (move logic data chunk)， 移動數(shù)據(jù)時，一個節(jié)點內(nèi)可以移動到另外一個節(jié)點內(nèi)的連續(xù)實際數(shù)據(jù)記錄數(shù)。需要根據(jù)老的分布規(guī)則和新的分布規(guī)則的確定，通常是針對范圍的均衡策略或者包含范圍的組合均衡策略，窗口的大小要小于等于移動的數(shù)據(jù)所處的那個范圍的大小，如范圍的均衡策略例子中，0 號節(jié)點中 0<=value<2500w ， 那么數(shù)據(jù)窗口可以選擇 1 到 2500w 中 2500w 的因子，如 1000，100w 等，太小導致窗口數(shù)太多，太大導致窗口數(shù)小，并發(fā)數(shù)提高不了。 進一步說，窗口的大小是老的分布規(guī)則和新的分布規(guī)則中數(shù)據(jù)所處的那個范圍的大小的公約數(shù)，實際中兩者是倍數(shù)的關系，取小的即可，如果小的數(shù)也比較大，如 500w，還可以取這個數(shù)的足夠小的某個約數(shù)，如 1w。
下面從以下幾個場景說明數(shù)據(jù)動態(tài)重新分布:
插入數(shù)據(jù)的時候，本來這條記錄需要插入節(jié)點 A，發(fā)現(xiàn)節(jié)點 A 的負載高，不允許插入，這時調(diào)整規(guī)則，將節(jié)點 A 中的這條記錄所處范圍的一部分或者整體移動到 B 節(jié)點；
加入新節(jié)點的時候，需要將原來某幾個節(jié)點 (如 A1 到 A4) 上某些范圍的一部分或者整體移動到新節(jié)點上；刪除節(jié)點的時候， 需要將刪除的節(jié)點 (如 A3 到 A4) 上范圍整體移動到其他不刪除的節(jié)點上；
發(fā)現(xiàn)數(shù)據(jù)不均衡，人工手動觸發(fā)數(shù)據(jù)重新分布，這種場景和加入和刪除節(jié)點，本質(zhì)上沒有區(qū)別，就是在已有的節(jié)點中移動數(shù)據(jù)，而不涉及新加的或者要刪除的節(jié)點。
數(shù)據(jù)的移動，特別是大量數(shù)據(jù)的移動，勢必對業(yè)務的操作帶來影響，如果控制不好的話，可能是災難；問題列舉如下:
場景 1 下，插入的數(shù)據(jù)是先插入老節(jié)點再移動還是先移動再插入新節(jié)點，先插入情況下可能偶爾數(shù)據(jù)庫本身負載高到不能插入，先移動情況下，可能導致插入延遲又比較大，導致用戶響應比較慢；
場景 1，2，3 下，移動數(shù)據(jù)窗口的時候，業(yè)務上可能對這個窗口進行數(shù)據(jù)操作，插入，更新，刪除都有可能，時間上可能業(yè)務先操作和鎖定記錄，然后移動，也有可能先移動，移動過程中，操作了已經(jīng)移動的數(shù)據(jù)或者操作和鎖定還沒有移動的記錄；
設計好的系統(tǒng)，可能不太需要數(shù)據(jù)的移動，但是從一般的角度考慮，它是一個比較頻繁的操作，而且涉及跨節(jié)點的插入數(shù)據(jù)，刪除數(shù)據(jù)，修改規(guī)則元數(shù)據(jù)，這三者需要在一個事務中完成，所以需要使用分布式事務。為了保證移動數(shù)據(jù)的時候業(yè)務的正常運行，我們需要做如下的設計：
場景 1 的先插入還是先移動的問題，可以動態(tài)調(diào)整，在插入很少的記錄的時候，先插入，再移動，如果運行中先插入失敗，則退化為先移動在插入；在插入大量的數(shù)據(jù)的時候，先移動，再插入；這種場景應該不多見，很多情況可以直接插入，移動去讓后臺線程來完成。
場景 1，2，3 下業(yè)務操作了需要移動的數(shù)據(jù)的問題，調(diào)整移動的窗口大小，使得一個窗口的處理時間控制在可以接受的時間以內(nèi)，一個窗口的內(nèi)的數(shù)據(jù)一次鎖定，例如時間設置為 1s，窗口大小選擇 2k，使用 select for update 來鎖定，最后直接刪除這些記錄，最后更新規(guī)則元數(shù)據(jù)。對于窗口比較大的情況，可以數(shù)據(jù)操作可以將大窗口調(diào)整為小窗口，每個小窗口使用以上的處理方式，同時業(yè)務的操作使用類似觸發(fā)器的檢查機制來同步更新到新節(jié)點上，具體的說：
對于已經(jīng)移動的小窗口內(nèi)的插入或者覆蓋 (replace) 操作，插入或者覆蓋 (replace) 到新節(jié)點
對于已經(jīng)移動的小窗口內(nèi)的刪除操作，在新節(jié)點刪除對應記錄
對于已經(jīng)移動的小窗口內(nèi)的更新操作，在新節(jié)點更新對應記錄
以上所討論的數(shù)據(jù)重新分布主要是確定好前后的規(guī)則，后面的工作就是根據(jù)前后的規(guī)則去遷移數(shù)據(jù)和修改元數(shù)據(jù)
如老的均衡策略從 0 到一億，以用戶 id 作為均衡字段； 分布如下:
場景 1:4 個節(jié)點存儲或者性能都達到了閾值，需要擴容，計劃每個節(jié)點拆分成兩個相等的部分，那么新的分布結(jié)果如下：
場景二：3 號節(jié)點由于性能不足，添加一個 4 號節(jié)點， 3 號節(jié)點的數(shù)據(jù)拆到 3 號和 4 號中，同時擴大用戶范圍到 4 億，使用性能比較高的 5，6，7 號節(jié)點，每個節(jié)點存儲一個億，那么新的分布結(jié)果如下:
舉例說明，以上的先使用范圍，再使用取余作為老的分布，如下:
場景 1: 現(xiàn)在需要按照 20000 一個范圍，那么就是每 8w 條記錄平均分布在 4 個節(jié)點中，新的分布結(jié)果如下:
數(shù)據(jù)的均衡策略或者分布規(guī)則是一把雙刃劍，Hdfs 的數(shù)據(jù)是隨機的，節(jié)點上報的形式，所以能夠動態(tài)調(diào)整，無需數(shù)據(jù)重新分布，缺點是啟動需要掃描，導致啟動慢；分布式數(shù)據(jù)庫的均衡策略是有規(guī)則的，規(guī)則通常存在在元數(shù)據(jù)中，Master 啟動時加載元數(shù)據(jù)就可以，元數(shù)據(jù)通常很小，所以啟動很快；但是規(guī)則的動態(tài)調(diào)整比較麻煩， 數(shù)據(jù)的重新分布也是必須的工作；基本的規(guī)則比較簡單，但調(diào)整動態(tài)調(diào)整量比較大，耗時長；組合的規(guī)則稍微復雜，但調(diào)整的數(shù)據(jù)量會縮小，耗時短。
聽說可以快速學習成為雙料 DBA？
