摘要：
本部分首先簡單介紹sharding系統的基本架構，然後重點介紹sharding機制中常用的三種表資料劃分方法。
一. 資料劃分算法
1. Sharding 系統的基本結構
上節我們說到Sharding可以簡單定義為将大資料庫分布到多個實體節點上的一個分區方案。每個shard都被放置在一個節點上面。 Sharding系統是一個shared-nothing的系統，基本上都采用下圖中所示的架構。最下面是很多資料庫伺服器節點，每個節點上面都會運作一 個或多個資料庫的執行個體。中間一層叫做查詢路由器，用戶端的連接配接都通過它進行轉發。查詢路由器負責解析使用者的查詢語句，并将這些語句轉發到包含有所需要的數 據的shard節點上面去執行。執行的結果也會通過查詢路由器進行彙總并發送給相應的用戶端。
對于這樣一個sharding系統，我們需要考慮到下面幾個問題：如何将資料劃分到多個shard節點上面；使用者的查詢語句如何正确的轉發到相應的 節點上面去執行；當節點資料變化的時候怎樣重新劃分資料。對于資料劃分和查詢路由來說，所用的算法一般是對應的。下面就講一下一些常用的資料劃分的方法。 這裡的假設前提是：隻考慮單個表，并且這個表的劃分鍵（Partitioning Key）已經被指定。
2. 常見的表劃分算法
本節介紹三種常見的資料劃分方法：輪流放置（Round-Robin）、一緻性哈希(Consistent Hashing)和區間劃分（Range-based Partitioning）。
2.1 Round-Robin
輪流放置是最簡單的劃分方法：即每條元組都會被依次放置在下一個節點上，以此進行循環。一般在實際應用中為了處理的友善，通常按照主鍵的值來決定次 序進而進行劃分。即給定一個表T，表T的劃分鍵 (Partitioning Key) 是k，需要劃分的節點數目N，那麼元組t ∈ T将會被放置在節點n上面，其中n = t.k mod N。由于劃分隻與劃分鍵有關，是以我們可以把對元組的劃分簡化為對數字的劃分，對于不是數字的鍵值可以通過其它方式比如哈希轉化為數字形式。下面給出一個 例子來表示這種劃分方式，把9個元組分布到3個節點上的情況。
但是，簡單的直接用劃分鍵上的值來計算放置節點的算法可能會造成資料的不均勻。是以，輪流放置有很多改進版，比如說哈希 方式（Hashing），即n = hash(t.k) mod N。先将劃分鍵的值進行hash操作，變成一個與輸入分布無關、輸出均勻的值，然後再進行取模操作。哈希函數可以有很多選擇，你可以針對你的應用的特征去 選取。
Pros: 輪流放置算法的實作非常簡單，而且幾乎不需要中繼資料就可以進行查詢的路由，是以有着比較廣泛的應用。例如EMC的Greenplum的分布式資料倉庫采用的就是輪流放置和哈希相結合的方式。
Cons: 輪流放置同樣具有很明顯的缺點：當系統中添加或者删除節點時，資料的遷移量非常巨大。舉個有20個節點的例子（下表），當系統由4個節點變為5個節點時， 會有如下的放置結果：紅色部分是mod 4和mod 5時結果不相等的情況，不相等意味着這些元組當系統由4個節點變為5個節點時需要進行遷移。也就是說多達80%的元組都需要遷移。資料的遷移會對系統的性 能造成很大的影響，嚴重時可能會中斷系統的服務。當系統的節點數目頻繁變化時，是不提倡使用這種方式的。
資料遷移量大的問題可以通過改進輪流放置算法來達到，比較常見的兩個改進算法是一緻性哈希和分區劃分算法。
2.2 Consistent Hashing
一緻性哈希是一種特殊的哈希方式。傳統的哈希方式（在上一小節中講到）在當節點數目發生變化時，會引起大量的資料遷移。 而使用一緻性哈希則不會産生這種問題。一緻性哈希最早是一個分布式緩存（Distributed Caching）系統的放置算法（現在很熱門的Memcached就用的是一緻性哈希）。但是現在它已經被廣泛應用到了其它各個領域。對于任何一個哈希函 數，其輸出值都有一個取值範圍，我們可以将這個取值區間畫成一個環，如下圖所示：
通過哈希函數，每個節點都會被配置設定到環上的一個位置，每個鍵值也會被映射到環上的一個位置。這個鍵值最終被放置在距離該 它的位置最近的，且位置編号大于等于該值的節點上面，即放置到順時針的下一個節點上面。下圖形象的表示了這種放置方案，其中Node 0上面放置Range 0上面的資料，以此類推。
Pros: 由于采用的哈希函數通常是與輸入無關的均勻函數，是以當鍵值和節點都非常的多的時候，一緻性哈希可以達到很好的分布式均勻性。并且由于特殊的放置規則，一 緻性哈希在節點資料發生變動時可以将影響控制在局部區間内，進而保證非常少的資料遷移（接近理論上的最小值）。當增加一個節點時，隻有這個節點所在的區間 内的資料需要被重新劃分，如下圖中，隻需要将range 2上面的資料會從node 1中遷移到node 3上面。當删除一個節點時，隻需要将這個節點上面的資料遷移到下一個節點上面，比如删除node 3，隻把range 2上面的資料遷移到node 1上面就可以并，而其它的資料是不需要遷移變動的。
一緻性哈希有非常廣泛的應用，Key-Value系統，文檔資料庫或者分布式關系資料庫都可以使用。Amazon的 NoSQL系統Dynamo應用采用的就是一種改進的一緻性雜湊演算法。在這個系統中又引入了虛拟節點的概念，使得這個算法的load balance更加的好，并且同時考慮了複制技術。環上的點就變成了虛拟節點，然後再采用其它的方式将這些虛拟節點映射到實際的實體節點上面去。這使得系 統有很好的可擴充性和可用性。
2.3 Range-Based Partitioning
區間劃分是現在很熱門的NoSQL資料庫MongoDB的sharding方案中所使用的算法。系統會首先把所有的資料 劃分為多個區間，然後再将這些區間配置設定到系統的各個節點上面。最簡單的區間劃分是一個節點隻持有一個區間：在有n個節點的情況下，将劃分鍵的取值區間均勻 劃分（這裡的均勻是指劃分後的每個partition的資料量盡量一樣大，而并非值域區間一樣大）為n份，然後每個節點持有一塊。例如，按照使用者名首字母 進行劃分，可能有以下的劃分方案：
如果發生資料分布不均勻的情況，可以通過調整區間分布達到均勻情況，資料遷移同樣會很小。
但是另外一些情況下，可能會導緻連鎖遷移。
情況一：資料分布不均，調整導緻的連鎖遷移
情況二：增加或删除節點導緻的連鎖遷移：
為了解決這個問題，MongoDB采用的是每個節點持有多個區間的方案（Multiple range shards）。當需要進行遷移的時候，将持有過多資料的節點上的區間分裂，使得分裂出來的區間剛好滿足遷移需要，然後再進行遷移。舉例來說 (下圖)，如果shard 1中存有[a, f]區間的資料，資料量為500G，此時需要從shard 1上面遷移100G到shard 4，以保證資料的均勻分布。經統計，shard 1中的[a, d]段的資料為400G，[d, f]段資料為100G，是以将shard 1中的[d, f]段的資料直接遷移到shard 4上面。同理，需要從shard 2中遷移100G的資料到shard 3中。這種遷移方式的資料遷移量是理論上的最小值。
Cons: 每個節點多個區間的做法的缺點是使得對中繼資料的處理變得複雜，我們需要記錄每個節點上面存儲的所有區間。但是一般來說，每個節點上面的區間數目不是很大， 是以中繼資料的數目不會很大。這種同時保證了資料的最小遷移，并且實作也比較簡單的方案是一個很理想的做法，雖然它的無資料管理和同步上面會有一些問題。
另外，區間劃分非常适合處理有區間查詢的查詢語句，但是也帶來很大的一個trade-off。如果一個查詢需要通路到多 條元組，那麼對區間的邊界的選取就變得非常棘手，如果選擇不當的話，很容易造成一個查詢需要在多個節點上面進行運作的情況，這種跨節點的操作會對系統的性 能進行很大的影響。
當然了，對于分區劃分來說，對于很多應用還是非常适合的，但是對于某些應用就非常不适合。同樣上面介紹的輪流放置和一緻 性雜湊演算法也是如此，這些算法隻針對某些應用有用，我們需要一些更智能的算法來針對不同的應用選擇不同的合适的算法。下一章我們會介紹幾個比較智能的 sharding方案，這些方案會考慮并分析使用者應用的工作流（Workload）、實際資料的特征等等進而從中得到一個比較好的方案出來。