分佈式存儲之數據切片

在大數據時代，稍大型企業的數據量已經達到 TB 甚至 PB 級別，顯然單機無法存儲於處理如此規模的數據量。分佈式數據的存儲必然涉及到數據的分片，本篇分析了幾種常用的數據分片模型。

1. 數據分片概念

目前主流的大數據存儲於計算系統通常採用橫向擴展方式支持系統的可擴展性，即通過增加機器數據獲得水平擴展能力。

對於待存儲的海量數據，需要通過數據分片（Shard / Partition）來將數據進行切分、並通過數據路由（Route）機制分配到各個機器中。

這裏需要區分數據分片與數據複製的概念。

2. 分片模型

下圖爲數據分片與路由的通用模型。相當於經過了二級映射。

哈希分片和範圍分片都可以映射到這個抽象模型中。哈希分片，主要是通過哈希函數來建立 key-partition 映射關係，只能根據某個記錄的主鍵獲得記錄內容，但是哈希方法需要記錄的元信息非常的簡單，只需要知道哈希函數的計算方式就行。範圍 / 順序分片，該分片方式在分佈式表格系統中比較常見，能夠根據指定的主鍵範圍一次性讀取多條滿足條件的記錄。

3. 哈希分片

通過哈希函數進行數據分片是常用手段，常用的三種哈希分片是：Round Robin、虛擬桶、一致性哈希等方法。

3.1 Round Robin / 哈希取模

該方法是非常常用的數據分片方法。將哈希值與服務器個數作除法取模映射，假設有 K 臺物理機，則通過以下哈希函數即可實現數據分片：

H(Key) = hash(key)mod K

H(Key) 的數值即爲存儲該數據的物理機的編號。但是當服務器上線或者下線時，K 的值發生變化，數據映射完全被打亂，幾乎所有的額數據都需要重新分佈，這將帶來大量的數據遷移工作。

3.2 虛擬桶 / 內存表

該思路不再簡單的將哈希值和服務器個數做除法取摸映射，而是將哈希值與服務器的對應關係作爲元數據，交給專門的虛擬桶 / 內存表來管理。所有記錄首先通過哈希函數映射到對應的虛擬桶（多對一映射），第二層映射是虛擬桶和物理機之間的映射關係（多對一映射），可以通過查內存表來管理。

該方式相比於 Round Roubin，由原先記錄直接到物理機的單層映射解耦成兩層映射，大大加強了系統的擴展靈活性。這樣，集羣擴容是，可以將部分哈希值分配給新加入的機器並遷移對應的數據。

3.3 一致性哈希

分佈式哈希（DHT） 是 P2P(Peer-to-Peer) 網絡（對等網絡）和分佈式存儲中常見的一項技術。即考慮在多機分佈環境，每臺機器負責承載部分數據的存儲情形下，如何通過哈希方式對數據進行增 / 刪 / 改 / 查等數據操作的方法。

算法思想：給系統中每個節點（物理機器）分配一個 token（根據物理機器 IP、端口映射到哈希空間），這些 token 構成一個哈希環。執行數據增加操作時，先計算數據 Key 的哈希值，然後存放到順時針方向第一個大於等於該哈希值的 token 所在的節點。

一致性的優點在於節點加入、刪除時只會影響在哈希環中相鄰的節點，而對其他節點沒有影響。

假設哈希空間表示的長度爲 n, 則哈希空間所表達的數值範圍是 (0-2^n) , 一致性哈希算法大致如下：

  1. 首先求出每個服務器的 hash 值，將其配置到一個 (0-2^n) 圓環區間上；

  2. 使用同樣的方法求出待存儲的主鍵 hash 值，也將其配置到這個圓環上；

  3. 數據的路由，將數據存儲到找到合適的服務器節點上（下面的路由問題）。

3.3.1 路由問題

上述方法能夠將海量數據分佈到集羣中的不同機器集羣, 實現數據分片功能。那對於接收到查詢請求的節點（該服務器節點可以是 hash 環中的任意一個），如何根據數據記錄的主鍵以及哈希函數來定位到記錄的內容呢？

下面列舉了基於空間複雜度的幾種路由方式：

O(1) 順序查找法

這是一種最直觀的查找方法。每臺服務器只要記錄它的前一個以及後一個節點的位置信息。接收到查詢請求的節點計算出數據主鍵的 Hash 值，然後判斷是否在自身範圍內，不在則轉交給後繼節點繼續查找，如此循環直到找到某個機器節點。

該做法維護的節點位置信息的空間複雜度爲 O(1), 但是有可能遍歷 hash 環中所有服務器，所以時間複雜度爲 O(N)。

O(N) 路由表法

爲了加速查詢，可以在每個機器節點維護一個大小爲 N 的路由表（假設哈希空間爲 (0~2^n)，這裏 n 即爲 Hash 空間二進制數值比特位長度）, 路由表中的第 i 個元素記錄了編號爲 (p+2^{i-1}), 其中 p 爲服務器在 Hash 環中的編號。通過維護 O(N) 的位置信息，查找的時間複雜度可以改進爲 Olog(N)。

還有一種方式，就是在每個機器節點維護一個大小爲 N 的路由表，這裏的 N 不是 Hash 空間的長度，而是物理節點的個數。即在每個服務器維護整個集羣中所有服務器的位置信息，查找服務器的時間複雜度爲 Olog(N)。工程上一般採用這種方法，一般需要一個帶有總控節點的存儲系統來統一維護這張表。

3.3.2 節點的加入 / 離開

節點的加入根據 “路由問題 “可以找到後繼節點，則改變相應位置的前驅、後繼節點的位置關係，以體現新的網絡結構。同時需要將對應的數據重新進行分片，進行數據的遷移。

節點的離開需要考慮正常與異常離開。正常離開前需要做些準備工作，包括通知相應節點更新前驅後繼節點以及將本身持有數據遷移到後繼節點上。異常離開往往是機器故障導致，爲避免故障機器中數據可能丟失，需要採用將同一份數據在多臺機器上保留副本的方式。

3.3.3 虛擬節點

引入” 虛擬節點 “的概念，主要爲解決一致性哈希算法潛在的問題：機器節點映射到環狀結構的位置是隨機的，可能會導致機器負載不均衡；同時如果將所有機器平等看待會導致低配置機器高負載的情況。

虛擬節點即將一個物理節點虛擬成若干的虛擬節點，分別映射到一致性哈希的環狀結構的不同位置。一方面會有更佳的負載均衡，也可以兼顧到機器的異質性問題。

下面簡要展示實現的一致性 Hash 算法的主要結構。（注意：原文示例爲 Golang，這裏改用僞代碼示例）

class Consistent {
    //定義 Hash 環，切片中元素爲有序的物理節點 Hash 值
    int[] circle; 
    //虛擬節點個數
    int virtualNodes;
    //點到主機的映射（多對一的關係）
    HashMap<int, String> virtualMap;
    //主機列表
    HashMap<String, bool> members;
    //同步鎖
    ReentrantReadWriteLock syncMutex;
    //向Hash環中加入節點
    public void add(string elt) { /*...*/ }
    //從Hash環中刪除節點
    public void remote(string elt) { /*...*/ }
    //根據數據主鍵，獲取存儲的節點信息
    public string get(string key) { /*...*/ }
}

對照上面的結構，大致的結構圖如下：

當然，以上的實現是對於一致性 Hash 的基本操作，具體的業務還需要考慮數據的存儲、遷移、備份等等操作。

4. 範圍分片

範圍分片首先將所有記錄的主鍵進行排序，然後在排序好的主鍵空間裏將記錄劃分成連續的範圍（每個範圍稱爲一個子表），每個字表存儲有序的主鍵空間片段內的所有記錄，通過範圍分片能夠避免哈希分佈的數據散列問題。

範圍分片對應的 key-partition 映射表是通過記錄主鍵排序切割獲得的，而不同於哈希分片通過 Hash 函數獲得。

很多大規模存儲系統都支持上述範圍的分片模式，比如 Google 的 BigTable 也基本遵循上述模式。不同點在於其數據分片映射表不是單層結構，而是組織成類似 B+ 樹的層次結構，這樣可容納的數據分片個數獲得極大的提升。

B+ 樹的層次結構中，每個字表相當於葉子節點，隨着數據的插入和刪除，某些字表可能變得很大或很小，數據分佈不均勻。採用範圍分片設計時就需要考慮子表的分裂與合併，這也將極大的增加系統的複雜度。

子表分裂是指當一個子表太大超過一定的閾值時需要分裂爲兩個子表，從而有機會通過系統的負載均衡機制分散到多個存儲節點。

子表合併一般由數據刪除引起，當相鄰的兩個子表都很小時，可以合併爲一個子表。合併的目的是爲了防止系統中出現過多太小的子表，較少系統中的元數據。

5. 參考閱讀

一致性 Hash 算法背景：cnblogs.com/haippy/archive/2011/12/10/2282943.html

作者：Danping Mao

來源：maodanp.github.io/2016/06/25/bigdata-data-slice/

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

猜你喜歡