一、背景??

? ? 無論是傳統(tǒng)的關系數(shù)據(jù)庫還是非關系數(shù)據(jù)庫，擴展問題都是一個永恒的話題。?? 早期傳統(tǒng)的關系數(shù)據(jù)庫，采用縱向擴展（Scale Up）的方式，即買更好的機器添加更多的資源來取得更好的性能。關系數(shù)據(jù)庫通過Scale Up方式已在傳統(tǒng)的企業(yè)應用環(huán)境中統(tǒng)治了將近三十多年。?? 但是硬件資源始終存在性能極限，縱向擴展無法一直持續(xù)下去。近年來隨著數(shù)據(jù)量的暴增，尤其是云計算模式的出現(xiàn)，縱向擴展的方式已經無法滿足需求。這時便出現(xiàn)了橫向擴展 （Scale Out）模式。這種方式采用數(shù)據(jù)庫主從配置（Master-Slave）、數(shù)據(jù)庫復制 （Replication）技術以及服務器緩存（Server Cache）等，將負載分布到多個物理節(jié)點上去。本文討論的sharding技術就是一種常見的橫向擴展模式。?

二、什么是sharding

? ? ?shard是“碎片”的意思，將整個數(shù)據(jù)庫打碎的過程就叫做sharding，可以翻譯為分片。sharding 是把數(shù)據(jù)庫Scale Out到多個物理節(jié)點上的一種有效方式。sharding可以簡單理解為將大數(shù)據(jù)庫分布到多個物理節(jié)點上的一個分區(qū)方案。每一個分區(qū)包含數(shù)據(jù)庫的某一部分，稱為一個shard。?

三、常見sharding方案

1.基于功能切分?

? ? ?將功能不同的表放在不同的數(shù)據(jù)庫中。?

2.基于區(qū)間范圍切分??

將數(shù)據(jù)根據(jù)數(shù)值區(qū)間sharding到不同分片上，例如將uid在[1, 10000000]區(qū)間的數(shù)據(jù)放到shard1上，uid在[10000001, 20000000]區(qū)間的數(shù)據(jù)放到shard2上，以此類推......?

擴展方案

（1）數(shù)據(jù)擴容 ? ?當數(shù)據(jù)量增長，超過預留的最大數(shù)值時就需要進行數(shù)據(jù)擴容。比如預留的最大uid為30000000，當該值快要達到時就需要進行擴容，將最大uid擴容到40000000。?

?（2）數(shù)據(jù)遷移 ? ?在設計初期，由于沒有足夠的數(shù)據(jù)作為sharding的參考，簡單的方式就是把數(shù)據(jù)平均分到不同shard上，如每個shard均存放10000000用戶的數(shù)據(jù)。系統(tǒng)上線后發(fā)現(xiàn)，如果用戶id采用自增方式分配，即越早注冊用戶uid越小。通常情況下，系統(tǒng)早期用戶都是比較活躍的用戶。由于shard1上的用戶更活躍，那么它的負載高于其他shard，當其性能出現(xiàn)瓶頸時就需要進行數(shù)據(jù)遷移。?

?? 于是將uid在區(qū)間[5000001, 10000000]上的用戶數(shù)據(jù)從shard1遷移到shard2，此時數(shù)據(jù)落在shard2上的用戶區(qū)間為[5000001, 20000000]。不幸的是當我們把數(shù)據(jù)從shard1遷移到shard2上后，shard2由于數(shù)據(jù)量增加也出現(xiàn)性能瓶頸，這時我們又需要把shard2上的數(shù)據(jù)往shard3上遷移，這就造成了惡性的連鎖遷移?？梢圆捎萌缦聝煞N方案解決連鎖遷移問題：

多區(qū)間sharding?即一個shard存儲多個區(qū)間的數(shù)據(jù)。針對上述連鎖遷移問題，先擴容出一個shard4，其負責的新用戶范圍為[30000001, 35000000]，并將[1, 5000000]范圍內的用戶數(shù)據(jù)遷移到shard4上。mongodb就是使用多區(qū)間sharding的方案進行擴展。

VIP sharding 另一種解決連鎖遷移問題的方案是把特殊用戶(VIP)sharding到獨立的shard上，預先規(guī)劃好熱點用戶。例如，QQ使用QQ號登陸，位數(shù)少的QQ號、有特殊含義的靚號容易記憶，也就更有價值。擁有這些QQ號的用戶不是早期用戶就是花了大價錢選號的用戶，他們通常更活躍也更在乎用戶體驗，可將他們分配到專屬的shard上。

3.基于hash切分??

? ? 基于區(qū)間范圍切分非常適合處理有區(qū)間查詢需求的場景，但是各個shard上負載的均衡很難保證。hash切分能夠較均勻地分配數(shù)據(jù)，一開始便要確定切分的shard個數(shù)，通過hash取模來決定使用哪個 shard。但是隨著數(shù)據(jù)量增大，需要進行擴展的時候，就比較麻煩了。每增加一個shard，就需要對hash算法重新運算，數(shù)據(jù)需要重新切分。?

?? ? 如上圖所示，當shard個數(shù)從2擴展到3時，shard1上的數(shù)據(jù)4需要遷移到shard2上，shard2上的數(shù)據(jù)3需要遷移到shard1上，shard1、shard2上也都有數(shù)據(jù)要遷移到新的shard3上。這種每個shard都會接收其他shard遷移過來的數(shù)據(jù)，每個shard也都有數(shù)據(jù)要遷移到其他眾多shard，這種混亂不堪的遷移簡直就是災難。導致這種混亂不堪的遷移的原因是hash取模算法不具備單調性，下面我們就說明何為hash算法的單調性。

hash算法單調性?hash算法的一個重要衡量指標就是單調性，其定義如下：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統(tǒng)中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。為了讓擴展更方便，我們需要保證hash算法具有單調性，下文介紹兩種hash擴展方案。

擴展方案

（1）一致性hash?? ? 著名的分布式緩存系統(tǒng)memcached就是采用一致性hash將數(shù)據(jù)sharding到不同節(jié)點上，算法如下：??首先求出memcached服務器（節(jié)點）的哈希值，并將其配置到0～232的圓（continuum）上； ?然后采用同樣的方法求出存儲數(shù)據(jù)的鍵的哈希值，并映射到相同的圓上； ?然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的第一個服務器上。如果超過232仍然找不到服務器，就會保存到第一臺memcached服務器上。?

??當需要增加一個新的節(jié)點node5時，如果是增加在node2和node4之間，那么只有node2和node4之間部分數(shù)據(jù)會遷移到node5上，其他數(shù)據(jù)均不需要遷移。?

?（2）二叉樹擴展?? ? 二叉樹擴展也能夠很好地解決遷移混亂問題，redis在rehash漸進式遷移時就采用的這種方案。二叉樹擴展要求shard的個數(shù)為2n個，只要滿足此要求即可進行二叉樹擴展。下面我們圖解數(shù)據(jù)庫如何進行二叉樹擴展?：???

? ??假設我們數(shù)據(jù)的范圍為[1, 2, 3, 4, 5, 6, 7, 8]，一開始我們有2個shard，數(shù)據(jù)為[2, 4, 6, 8]和[1, 3, 5, 7]，現(xiàn)在發(fā)現(xiàn)性能出現(xiàn)瓶頸，需要對其進行擴展；?? ? 對shard1和shard2分別建一個從庫，主從同步完成后將其作為新的分片shard3和shard4，同時將取模算法從mod 2改為mod 4；?? ? 此時每個shard上包含了不用遷移出去的數(shù)據(jù)，而需要遷移出去的數(shù)據(jù)其他shard上已經存在，不需要進行遷移，只需將其刪除即可。下圖中標紅的數(shù)據(jù)就是需要刪除的數(shù)據(jù)。?

?4.基于路由表切分??

? ? ?前面的幾種方式都是跟據(jù)應用的數(shù)據(jù)來決定操作的shard，基于路由表的切分是一種更加松散的方法。它單獨維護一張路由表，根據(jù)用戶的某一屬性來查找路由表決定使用哪個shard，這種方式是一種更加通用的方案。因為每次數(shù)據(jù)操作的時候都需要進行路由的查找，所以將這些內容存儲到一臺獨立cache上是一個非常好的方式，譬如memcached。這種切分的方式同時也帶來了另一個好處，當需要增加shard的時候，可以在不影響在線應用的情況下來執(zhí)行。

?四、總結

sharding優(yōu)點

（1）提高了數(shù)據(jù)庫的可擴展性。可以隨著應用的增長來增加更多的服務器，只需要將新增加的數(shù)據(jù)以及負載放到新加的服務器上即可。

（2）提高了數(shù)據(jù)庫的可用性。其中幾個shard服務器down掉之后，并不會使整個系統(tǒng)癱瘓，只會影響到需要訪問這幾個shard服務器上的數(shù)據(jù)的用戶。

（3）數(shù)據(jù)量小的數(shù)據(jù)庫的負載較小，查詢更快，性能更好。

（4）系統(tǒng)有更好的可維護性。對系統(tǒng)的升級和配置可以按照shard一個一個來做，并不會對服務產生大的影響。

常見sharding方案對比

基于功能切分是純粹業(yè)務上的隔離，更多的是業(yè)務層面的考量。?基于區(qū)間范圍切分非常適合處理有區(qū)間查詢需求的場景，但是各個shard上負載的均衡很難保證。?基于hash切分能夠較均勻地分配數(shù)據(jù)，但是擴展比較麻煩，需要保證hash算法單調性。?基于路由表切分，最靈活、最通用、最容易擴展和遷移，但是需要額外維護路由數(shù)據(jù)。