首先介紹三種分片方式：hash方式，一致性hash（consistent hash），按照數(shù)據(jù)范圍（range based）。對于任何方式，都需要思考以下幾個問題：
- 具體如何劃分原始數(shù)據(jù)集？
- 當原問題的規(guī)模變大的時候，能否通過增加節(jié)點來動態(tài)適應？
- 當某個節(jié)點故障的時候，能否將該節(jié)點上的任務均衡的分攤到其他節(jié)點？
- 對于可修改的數(shù)據(jù)（比如數(shù)據(jù)庫數(shù)據(jù)），如果某節(jié)點數(shù)據(jù)量變大，能否以及如何將部分數(shù)據(jù)遷移到其他負載較小的節(jié)點，及達到動態(tài)均衡的效果？
- 元數(shù)據(jù)的管理（即數(shù)據(jù)與物理節(jié)點的對應關系）規(guī)模？元數(shù)據(jù)更新的頻率以及復雜度？
為了方便后面分析不同的數(shù)據(jù)分片方式，假設有三個物理節(jié)點，編號為N0， N1， N2，N3；并且，有以下幾條記錄：
R0: {id: 95, name: 'aa', tag:'older'}
R1: {id: 302, name: 'bb',}
R2: {id: 759, name: 'aa',}
R3: {id: 607, name: 'dd', age: 18}
R4: {id: 904, name: 'ff',}
R5: {id: 246, name: 'gg',}
R6: {id: 148, name: 'ff',}
R7: {id: 533, name: 'kk',}
Hash方式
哈希表（散列表）是最為常見的數(shù)據(jù)結(jié)構(gòu)，根據(jù)記錄（或者對象）的關鍵值將記錄映射到表中的一個槽（slot），便于快速訪問。哈希表中，最為簡單的散列函數(shù)是 mod N（N為表的大小）。即首先將關鍵值計算出hash值（這里是一個整型），通過對N取余，余數(shù)即在表中的位置。
數(shù)據(jù)分片的hash方式也是這個思想，即按照數(shù)據(jù)的某一特征（key）來計算哈希值，并將哈希值與系統(tǒng)中的節(jié)點建立映射關系,從而將哈希值不同的數(shù)據(jù)分布到不同的節(jié)點上。
我們選擇id作為數(shù)據(jù)分片的key，那么各個節(jié)點負責的數(shù)據(jù)如下：
由此可以看到，按照hash方式做數(shù)據(jù)分片，映射關系非常簡單；需要管理的元數(shù)據(jù)也非常之少，只需要記錄節(jié)點的數(shù)目以及hash方式就行了。
但hash方式的缺點也非常明顯：當加入或者刪除一個節(jié)點的時候，大量的數(shù)據(jù)需要移動。比如在這里增加一個節(jié)點N3，因此hash方式變?yōu)榱薽od 4，數(shù)據(jù)的遷移如下：
在這種方式下，是不滿足單調(diào)性（Monotonicity）的：如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中，哈希的結(jié)果應能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。
在工程中，為了減少遷移的數(shù)據(jù)量，節(jié)點的數(shù)目可以成倍增長，這樣概率上來講至多有50%的數(shù)據(jù)遷移。
hash方式還有一個缺點，即很難解決數(shù)據(jù)不均衡的問題。有兩種情況：原始數(shù)據(jù)的特征值分布不均勻，導致大量的數(shù)據(jù)集中到一個物理節(jié)點上；第二，對于可修改的記錄數(shù)據(jù)，單條記錄的數(shù)據(jù)變大。在這兩種情況下，都會導致節(jié)點之間的負載不均衡，而且在hash方式下很難解決。
一致性Hash
一致性哈希修正了CARP使用的簡 單哈希算法帶來的問題，使得分布式哈希（DHT）可以在P2P環(huán)境中真正得到應用。
一致性hash算法提出了在動態(tài)變化的Cache環(huán)境中，判定哈希算法好壞的四個定義：
- 平衡性(Balance)：平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。
- 單調(diào)性(Monotonicity)：單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應能夠保證原有已分配的內(nèi)容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。
- 分散性(Spread)：在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內(nèi)容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應該避免的，因為它導致相同內(nèi)容被存儲到不同緩沖中去，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。
- 負載(Load)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同 的內(nèi)容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。
一致性hash是將數(shù)據(jù)按照特征值映射到一個首尾相接的hash環(huán)上，同時也將節(jié)點（按照IP地址或者機器名hash）映射到這個環(huán)上。
對于數(shù)據(jù)，從數(shù)據(jù)在環(huán)上的位置開始，順時針找到的第一個節(jié)點即為數(shù)據(jù)的存儲節(jié)點。也就是說，每一個key的順時針方向最近節(jié)點，就是key所歸屬的存儲節(jié)點。
這里仍然以上述的數(shù)據(jù)為例，假設id的范圍為［0， 1000］，N0， N1， N2在環(huán)上的位置分別是100， 400， 800，那么hash環(huán)示意圖與數(shù)據(jù)的分布如下：
可以看到相比于上述的hash方式，一致性hash方式需要維護的元數(shù)據(jù)額外包含了節(jié)點在環(huán)上的位置，但這個數(shù)據(jù)量也是非常小的。
一致性hash在增加或者刪除節(jié)點的時候，受到影響的數(shù)據(jù)是比較有限的，比如這里增加一個節(jié)點N3，其在環(huán)上的位置為600，因此，原來N2負責的范圍段（400， 800］現(xiàn)在由N3（400， 600] N2(600, 800]負責，因此只需要將記錄R7(id:533) 從N2,遷移到N3。不難發(fā)現(xiàn)一致性hash方式在增刪的時候只會影響到hash環(huán)上相鄰的節(jié)點，不會發(fā)生大規(guī)模的數(shù)據(jù)遷移。
但是如果按照上述方式，一致性hash方式在增加節(jié)點的時候，只能分攤一個已存在節(jié)點的壓力；同樣，在其中一個節(jié)點掛掉的時候，該節(jié)點的壓力也會被全部轉(zhuǎn)移到下一個節(jié)點。我們希望的是“一方有難，八方支援”，因此需要在增刪節(jié)點的時候，已存在的所有節(jié)點都能參與響應，達到新的均衡狀態(tài)。
因此，在實際工程中，一般會引入虛擬節(jié)點（virtual node）的概念。即不是將物理節(jié)點映射在hash環(huán)上，而是將虛擬節(jié)點映射到hash環(huán)上。虛擬節(jié)點的數(shù)目遠大于物理節(jié)點，因此一個物理節(jié)點需要負責多個虛擬節(jié)點的真實存儲。操作數(shù)據(jù)的時候，先通過hash環(huán)找到對應的虛擬節(jié)點，再通過虛擬節(jié)點與物理節(jié)點的映射關系找到對應的物理節(jié)點。
引入虛擬節(jié)點后的一致性hash需要維護的元數(shù)據(jù)也會增加：第一，虛擬節(jié)點在hash環(huán)上的問題，且虛擬節(jié)點的數(shù)目又比較多；第二，虛擬節(jié)點與物理節(jié)點的映射關系。但帶來的好處是明顯的，當一個物理節(jié)點失效是，hash環(huán)上多個虛擬節(jié)點失效，對應的壓力也就會發(fā)散到多個其余的虛擬節(jié)點，事實上也就是多個其余的物理節(jié)點。在增加物理節(jié)點的時候同樣如此。
工程中，Dynamo、Cassandra都使用了一致性hash算法，且在比較高的版本中都使用了虛擬節(jié)點的概念。在這些系統(tǒng)中，需要考慮綜合考慮數(shù)據(jù)分布方式和數(shù)據(jù)副本，當引入數(shù)據(jù)副本之后，一致性hash方式也需要做相應的調(diào)整， 可以參加cassandra的相關文檔。
Range based
簡單來說，就是按照關鍵值劃分成不同的區(qū)間，每個物理節(jié)點負責一個或者多個區(qū)間。其實這種方式跟一致性hash有點像，可以理解為物理節(jié)點在hash環(huán)上的位置是動態(tài)變化的。
還是以上面的數(shù)據(jù)舉例，三個節(jié)點的數(shù)據(jù)區(qū)間分別是N0(0, 200]， N1(200, 500]， N2(500, 1000]。那么數(shù)據(jù)分布如下：
注意，區(qū)間的大小不是固定的，每個數(shù)據(jù)區(qū)間的數(shù)據(jù)量與區(qū)間的大小也是沒有關系的。比如說，一部分數(shù)據(jù)非常集中，那么區(qū)間大小應該是比較小的，即以數(shù)據(jù)量的大小為片段標準。在實際工程中，一個節(jié)點往往負責多個區(qū)間，每個區(qū)間成為一個塊（chunk、block），每個塊有一個閾值，當達到這個閾值之后就會分裂成兩個塊。這樣做的目的在于當有節(jié)點加入的時候，可以快速達到均衡的目的。
如果一個節(jié)點負責的數(shù)據(jù)只有一個區(qū)間，range based與沒有虛擬節(jié)點概念的一致性hash很類似；如果一個節(jié)點負責多個區(qū)間，range based與有虛擬節(jié)點概念的一致性hash很類似。
range based的元數(shù)據(jù)管理相對復雜一些，需要記錄每個節(jié)點的數(shù)據(jù)區(qū)間范圍，特別單個節(jié)點對于多個區(qū)間的情況。而且，在數(shù)據(jù)可修改的情況下，如果塊進行分裂，那么元數(shù)據(jù)中的區(qū)間信息也需要同步修改。
range based這種數(shù)據(jù)分片方式應用非常廣泛，比如MongoDB, PostgreSQL， HDFS
