介紹數(shù)據(jù)劃分方法：輪流放置（Round-Robin）捅彻、一致性哈希(Consistent Hashing)和區(qū)間劃分（Range-based Partitioning）劲绪。
一. 輪流放置
輪流放置是最簡單的劃分方法：即每條元組都會被依次放置在下一個節(jié)點上燕少，以此進行循環(huán)屈呕。一般在實際應(yīng)用中為了處理的方便，通常按照主鍵的值來決定次序從而進行劃分棺亭。即給定一個表T虎眨，表T的劃分鍵 (Partitioning Key) 是k，需要劃分的節(jié)點數(shù)目N镶摘，那么元組t ∈ T將會被放置在節(jié)點n上面嗽桩，其中n = t.k mod N。由于劃分只與劃分鍵有關(guān)凄敢，因此我們可以把對元組的劃分簡化為對數(shù)字的劃分碌冶，對于不是數(shù)字的鍵值可以通過其它方式比如哈希轉(zhuǎn)化為數(shù)字形式。下面給出一個例子來表示這種劃分方式涝缝，把9個元組分布到3個節(jié)點上的情況扑庞。
簡單的直接用劃分鍵上的值來計算放置節(jié)點的算法可能會造成數(shù)據(jù)的不均勻。因此拒逮，輪流放置有很多改進版罐氨，比如說哈希方式（Hashing），即n = hash(t.k) mod N滩援。先將劃分鍵的值進行hash操作栅隐，變成一個與輸入分布無關(guān)、輸出均勻的值，然后再進行取模操作租悄。
Pros(優(yōu)點): 輪流放置算法的實現(xiàn)非常簡單谨究，而且?guī)缀醪恍枰獢?shù)據(jù)就可以進行查詢的路由。
Cons(缺點)： 輪流放置當系統(tǒng)中添加或者刪除節(jié)點時泣棋，數(shù)據(jù)的遷移量非常巨大胶哲。
二. 一致性哈希
考慮通常的 hash 算法都是將 value 映射到一個 32 維的 key 值，也即是 0~2^32-1 次方的數(shù)值空間潭辈；我們可以將這個空間想象成一個首（ 0 ）尾（ 2^32-1 ）相接的圓環(huán)鸯屿，如下面圖 1 所示的那樣
把存儲對象和存儲服務(wù)器分別哈希到環(huán)上：
存儲對象按一致的方向落在離它最近的存儲服務(wù)器上。
Pros:
- 均勻：由于采用的哈希函數(shù)通常是與輸入無關(guān)的均勻函數(shù)萎胰，因此當鍵值和節(jié)點都非常的多的時候，一致性哈吓锪桑可以達到很好的分布式均勻性技竟。
- 遷移時數(shù)量小：并且由于特殊的放置規(guī)則屈藐，一致性哈希在節(jié)點數(shù)據(jù)發(fā)生變動時可以將影響控制在局部區(qū)間內(nèi)榔组，從而保證非常少的數(shù)據(jù)遷移（接近理論上的最小值）。當增加一個節(jié)點時联逻，只有這個節(jié)點所在的區(qū)間內(nèi)的數(shù)據(jù)需要被重新劃分搓扯，如下圖中，只需要將range 2上面的數(shù)據(jù)會從node 1中遷移到node 3上面包归。當刪除一個節(jié)點時锨推，只需要將這個節(jié)點上面的數(shù)據(jù)遷移到下一個節(jié)點上面，比如刪除node 3公壤，只把range 2上面的數(shù)據(jù)遷移到node 1上面就可以并换可，而其它的數(shù)據(jù)是不需要遷移變動的。
三. 區(qū)間劃分
區(qū)間劃分是現(xiàn)在很熱門的NoSQL數(shù)據(jù)庫MongoDB的sharding方案中所使用的算法厦幅。系統(tǒng)會首先把所有的數(shù)據(jù)劃分為多個區(qū)間沾鳄，然后再將這些區(qū)間分配到系統(tǒng)的各個節(jié)點上面。最簡單的區(qū)間劃分是一個節(jié)點只持有一個區(qū)間：在有n個節(jié)點的情況下确憨，將劃分鍵的取值區(qū)間均勻劃分（這里的均勻是指劃分后的每個partition的數(shù)據(jù)量盡量一樣大译荞，而并非值域區(qū)間一樣大）為n份，然后每個節(jié)點持有一塊休弃。例如吞歼，按照用戶名首字母進行劃分，可能有以下的劃分方案：
如果發(fā)生數(shù)據(jù)分布不均勻的情況塔猾，可以通過調(diào)整區(qū)間分布達到均勻情況浆熔，數(shù)據(jù)遷移同樣會很小。
但是另外一些情況下，可能會導致連鎖遷移医增。
情況一：數(shù)據(jù)分布不均慎皱，調(diào)整導致的連鎖遷移
情況二：增加或刪除節(jié)點導致的連鎖遷移：
為了解決這個問題，MongoDB采用的是每個節(jié)點持有多個區(qū)間的方案（Multiple range shards）叶骨。當需要進行遷移的時候茫多，將持有過多數(shù)據(jù)的節(jié)點上的區(qū)間分裂，使得分裂出來的區(qū)間剛好滿足遷移需要忽刽，然后再進行遷移天揖。舉例來說 (下圖)，如果shard 1中存有[a, f]區(qū)間的數(shù)據(jù)跪帝，數(shù)據(jù)量為500G今膊，此時需要從shard 1上面遷移100G到shard 4，以保證數(shù)據(jù)的均勻分布伞剑。經(jīng)統(tǒng)計斑唬，shard 1中的[a, d]段的數(shù)據(jù)為400G，[d, f]段數(shù)據(jù)為100G黎泣，因此將shard 1中的[d, f]段的數(shù)據(jù)直接遷移到shard 4上面恕刘。同理，需要從shard 2中遷移100G的數(shù)據(jù)到shard 3中抒倚。這種遷移方式的數(shù)據(jù)遷移量是理論上的最小值褐着。（簡單理解就是節(jié)點持有多個不連續(xù)區(qū)間。）
Cons: 每個節(jié)點多個區(qū)間的做法的缺點是使得對元數(shù)據(jù)的處理變得復雜托呕，我們需要記錄每個節(jié)點上面存儲的所有區(qū)間含蓉。但是一般來說，每個節(jié)點上面的區(qū)間數(shù)目不是很大项郊，因此元數(shù)據(jù)的數(shù)目不會很大谴餐。這種同時保證了數(shù)據(jù)的最小遷移，并且實現(xiàn)也比較簡單的方案是一個很理想的做法呆抑，雖然它的無數(shù)據(jù)管理和同步上面會有一些問題岂嗓。
另外，區(qū)間劃分非常適合處理有區(qū)間查詢的查詢語句鹊碍，但是也帶來很大的一個trade-off厌殉。如果一個查詢需要訪問到多條元組，那么對區(qū)間的邊界的選取就變得非常棘手侈咕，如果選擇不當?shù)脑捁保苋菀自斐梢粋€查詢需要在多個節(jié)點上面進行運行的情況，這種跨節(jié)點的操作會對系統(tǒng)的性能進行很大的影響耀销。
