1.前言

對于非常龐大的數(shù)據(jù)量，經(jīng)常需要分片分區(qū)
在分片分區(qū)的模式下：每一個數(shù)據(jù)（一行記錄）只屬于一個分區(qū)拍嵌，每個分區(qū)是整個數(shù)據(jù)庫的一部分遭赂。
分區(qū)為了更好的伸縮性。本章就討論索引是如何利用分區(qū)的横辆。在討論數(shù)據(jù)的平衡等問題撇他。

2.分區(qū)和備份的關(guān)系

兩者經(jīng)常都是結(jié)合起來的，這樣每個分區(qū)的數(shù)據(jù)都存有備份狈蚤，存儲在其他的節(jié)點上困肩。
一個節(jié)點能可以存儲多個分區(qū)，在單leader模型中脆侮，每個節(jié)點可以成為某個分區(qū)的leader锌畸，也可以成為其他分區(qū)的follower
如下圖所示

分區(qū)和備份的關(guān)系

3.kv數(shù)據(jù)的分區(qū)

如何進行分區(qū)，決定某個記錄屬于某個節(jié)點呢靖避？
目標(biāo)是讓各個分區(qū)的數(shù)據(jù)大小盡可能的均勻潭枣。如果分區(qū)的規(guī)則不公平，可能某些分區(qū)會有更多的數(shù)據(jù)量幻捏。稱為傾斜.
如果一個分區(qū)有不合適的高負載盆犁，那么會被稱為熱點

3.1根據(jù)key范圍分區(qū)

一種方式是根據(jù)key的范圍來分區(qū)，如下圖

范圍分區(qū)

keys范圍分區(qū)中篡九，邊界的選擇不一定需要平均谐岁，只要適合自己的數(shù)據(jù)即可。
可以通過人工選擇榛臼，也可以根據(jù)數(shù)據(jù)自動選擇（后面講）
每個分區(qū)內(nèi)伊佃，保證keys是有序的，利用前面講過的SSTables和LSM trees完成沛善。

當(dāng)然航揉，范圍分區(qū)的缺陷是特定的訪問模式會導(dǎo)致熱點的出現(xiàn)。
比如按照日期分區(qū)金刁，那么每天的寫操作只會寫到當(dāng)天對應(yīng)的分區(qū)迷捧，成為熱點织咧。

3.2根據(jù)key的hash值分區(qū)

由于傾斜以及熱點的問題胀葱，很多分不是db選擇hash來分區(qū)漠秋。
這樣的話，分區(qū)也就根據(jù)hash值而不是原來的key來劃分了抵屿，每個key根據(jù)自己的hash值決定落在哪一個分區(qū)庆锦。如下圖

key的hash來分區(qū)

但是，hash分區(qū)相對于key分區(qū)來說轧葛，進行范圍查詢就很不容易了搂抒。
因為原本相鄰的兩個key，可能hash到完全不同的兩個分區(qū)尿扯。排序結(jié)構(gòu)被破壞了求晶。
因此，一些db的解決辦法是：范圍查詢的語句衷笋，讓所有分區(qū)一起執(zhí)行芳杏，最后再匯總。

3.3負載傾斜以及熱點緩解

hash能減緩熱點問題但是不能完全避免辟宗。極端情況下一個key會受到大量的讀寫請求爵赵。
比如說社交媒體上某個大V有重大消息，粉絲會有大量的讀寫操作泊脐。常見的解決方法如下

如果已知某些key是熱點空幻，給這個key加一個隨機數(shù)（比如rand(100)）作為前綴或者后綴。
這樣相當(dāng)于把原有的一個key拆分成100個子key了容客，寫的時候就能隨機分布到不同的分區(qū)了秕铛。
但是讀的時候需要額外的工作量，需要讀取這100個key的數(shù)量缩挑，并把他們merge起來.

4.分區(qū)以及二級索引

二級索引經(jīng)常指向的是多行數(shù)據(jù)而不是一行（比如顏色為紅色的車）
由于實現(xiàn)復(fù)雜但两，一個kv存儲（如HBase）避免了二級索引。
二級索引的問題是他們不能和分區(qū)進行方便的map调煎。
目前二級索引分區(qū)主要兩種方式：基于文檔和基于詞語的

4.1 文檔分區(qū)二級索引

假設(shè)有這個場景镜遣，賣二手車，每一輛車有一個唯一id士袄。分區(qū)按照id來（即key范圍分區(qū)）
現(xiàn)在二級索引是顏色和制造商

文檔二級索引

在上圖中悲关，每個分區(qū)獨立，維持自己的二級索引結(jié)構(gòu)娄柳，指向在當(dāng)前分區(qū)中的文檔寓辱。
當(dāng)對該分區(qū)的數(shù)據(jù)進行改動時，只用更新該分區(qū)中的二級索引結(jié)構(gòu)赤拒，因此稱為local index
讀取二級索引的時候秫筏，需要讀取所有分區(qū)的記錄诱鞠，并且結(jié)合起來。
比如說找紅色的車这敬，那么就要去每個分區(qū)找到紅色的車航夺，最后結(jié)合起來。
這種方式稱為scatter/gather(分散/聚集).
優(yōu)劣如下

優(yōu):
寫操作時崔涂，只用改當(dāng)前分區(qū)的二級索引
劣：
讀操作因為要遍歷所有分區(qū)阳掐，存在分散聚集，使得二級索引查詢操作代價昂貴

盡管如此冷蚂，它仍受廣泛應(yīng)用缭保，如ES，SolrCloud等

4.2 詞語二級索引分區(qū)

相對于每個分區(qū)自己維持二級索引結(jié)構(gòu)（local index）蝙茶，可以建立global index艺骂，來包含所有分區(qū)的數(shù)據(jù)
當(dāng)然global index也不能建立在一個節(jié)點上，global index也需要分區(qū)

詞語二級索引

優(yōu)：
讀操作更有效率吮廉，讀一次term就知道數(shù)據(jù)在哪幾個分區(qū)苞尝，而不用每次讀取所有分區(qū)
劣：
寫操作更復(fù)雜，因為可能引起索引改變宦芦，導(dǎo)致幾個不同分區(qū)的數(shù)據(jù)數(shù)據(jù)一起變動
實際場景下宙址，這要求分布式事務(wù)的執(zhí)行，但是目前還沒有被任何db支持调卑，
因此 global index的更新經(jīng)常是異步的.

5.分區(qū)的Rebalancing

數(shù)據(jù)庫存儲的量不斷變化抡砂，會有下面的場景需求

1.查詢量上升,希望加CPU
2.數(shù)據(jù)量上升，想加磁盤
3.機器宕機恬涧，其他機器接管它的職責(zé)

上面的變化都要求數(shù)據(jù)從一個分區(qū)移動到另外一個分區(qū)注益，稱之為rebalancing，它往往有幾個要求

rebalancing要求負載盡可能平衡
rebalancing發(fā)生時數(shù)據(jù)庫要能保證讀寫能夠正常進行
rebalancing發(fā)生時要盡量減少不必要的數(shù)據(jù)移動溯捆，來減少網(wǎng)絡(luò)和磁盤IO

5.1 rebalancing策略

先問一個問題,為什么分區(qū)不用mod N

如果N變化了丑搔，那么數(shù)據(jù)就得從一個分區(qū)移動到另外一個分區(qū)了
比如初始10個分區(qū)，key為123456
mod 10到6這個區(qū)提揍。后來有11個分區(qū)了啤月，mod 11到了3這個分區(qū)。
這樣就移動了不必要的數(shù)據(jù)

5.1.1 固定的分區(qū)數(shù)量

有種簡單的方法是創(chuàng)建遠比節(jié)點數(shù)量多的分區(qū)數(shù)量劳跃，把多個分區(qū)分配各一個幾點谎仲。
比如10個節(jié)點包含1000個分區(qū)。
如果有新的節(jié)點加入刨仑，那么新節(jié)點從原有的各個節(jié)點挪走一部分的分區(qū)郑诺，直到balance夹姥。

節(jié)點間移動的是整個分區(qū)。
分區(qū)的總數(shù)不變
各個分區(qū)處理的keys不變
各個節(jié)點分配的分區(qū)會變

如下圖

image.png

這種方式下辙诞，分區(qū)數(shù)量是固定的辙售。
原則上允許split和merge各個分區(qū)

但是固定分區(qū)個數(shù)會更簡單，所以有固定分區(qū)個數(shù)的算法實現(xiàn)中倘要，不會包含split的過程圾亏。
這種實現(xiàn)上，會選擇足夠大的分區(qū)個數(shù)封拧，來應(yīng)對未來的增長，雖然開始的管理會顯得麻煩一點夭问。

另外泽西，選擇何時的分區(qū)的size很難，因為分區(qū)數(shù)量是固定的但是data size在變化缰趋。很難做到剛剛合適捧杉。

5.1.2 動態(tài)分區(qū)

背景

對于利用key range來分區(qū)的數(shù)據(jù)庫來說，固定分區(qū)數(shù)量非常不方便：
如果range的值定的不合理秘血，那么會造成某些分區(qū)數(shù)據(jù)多而某些分區(qū)數(shù)量少味抖，即數(shù)據(jù)不均衡。
然而手動重新配置各個range又顯得麻煩

因此灰粮，對于HBase這樣的key range數(shù)據(jù)庫來說仔涩，分區(qū)是動態(tài)創(chuàng)建的。

實現(xiàn)

一個分區(qū)分配給一個節(jié)點粘舟，一個節(jié)點可以管理多個分區(qū)熔脂。
既可以進行split（某個分區(qū)數(shù)據(jù)量過大），也可以進行merge（幾個分區(qū)數(shù)據(jù)量過懈屉取）
當(dāng)一個大的分區(qū)進行split霞揉，會把一半的數(shù)據(jù)給另一個節(jié)點，來完成負載均衡晰骑。(書中這里不懂适秩，應(yīng)該是給另一個分區(qū)吧)

優(yōu)劣

優(yōu)：
能夠適應(yīng)總體的數(shù)據(jù)量：
  數(shù)據(jù)小的時候，小數(shù)量的分區(qū)就足夠硕舆，開銷很小
  數(shù)據(jù)大的時候秽荞，每個分區(qū)最大的容量根據(jù)一個配置的參數(shù)來定
劣：
  剛啟動時只有一個分區(qū)，所有讀寫都會到這個一分區(qū)岗宣。而其他的節(jié)點這時完全閑置蚂会。沒有達到負載均衡的效果。
  解決的一個辦法是類似于HBase進行一個預(yù)分區(qū)（當(dāng)然有先驗知識更好耗式，也就是知道數(shù)據(jù)分布的情況）胁住，也就是說一開始就有多個分區(qū)趁猴，這樣來避免初期的單分區(qū)造成的負載不均衡。

場景

適合key range分區(qū)彪见，也適合hash range分區(qū)

5.1.3 按節(jié)點比例進行分區(qū)

背景

動態(tài)分區(qū)中儡司，分區(qū)的數(shù)量和數(shù)據(jù)量的大小有關(guān)，因為不論split還是merge余指，每個分區(qū)的size都會在一個固定配置的minSize捕犬，maxSize區(qū)間中
固定分區(qū)中，每個分區(qū)的size和數(shù)據(jù)量的size相關(guān)

因此酵镜，兩種場景中碉碉，分區(qū)的數(shù)量其實都和節(jié)點的數(shù)量沒有關(guān)系
因此，第三種方法是讓分區(qū)的數(shù)量和節(jié)點的數(shù)量相關(guān)淮韭，也就是一個節(jié)點有固定數(shù)量的分區(qū)垢粮。

實現(xiàn)

當(dāng)節(jié)點數(shù)不變的時候，總共的分區(qū)數(shù)不變靠粪，此時數(shù)據(jù)量增大蜡吧，每個分區(qū)的數(shù)據(jù)也增大。
當(dāng)新節(jié)點加入占键，加多了固定數(shù)量的分區(qū)數(shù)昔善，每個分區(qū)會隨機把已經(jīng)存在的分區(qū)的部分?jǐn)?shù)據(jù)遷移過來（split），這會導(dǎo)致不公平的split.當(dāng)然有些實現(xiàn)會有些重平衡的策略畔乙，這里不展開君仆。

5.2 手動還是自動rebalancing

完全自動和完全手動rebalance是有平滑過度的。
全自動化很方便啸澡，但是這樣會造成結(jié)果不可預(yù)估袖订，比如數(shù)據(jù)在節(jié)點之間移動，造成網(wǎng)絡(luò)阻塞等
還是手動好嗅虏，雖然慢一點洛姑，但是安全穩(wěn)定

6.請求路由

背景

當(dāng)split或者merge之后，分區(qū)重平衡了皮服，每個節(jié)點對應(yīng)分區(qū)的內(nèi)容變了楞艾。
假如現(xiàn)在需要讀寫key值為”foo“，client到底應(yīng)該連哪一個ip和port呢龄广。
需要有一個角色在頂層來回答這個問題硫眯。

這個也稱為服務(wù)發(fā)現(xiàn)。

方式

有幾種方式

1.client隨便連node择同，node能處理就處理两入，不能就找到可以處理的nodeA,把nodeA的最終結(jié)果返回client
2.有一個路由層，專門告訴client去哪里請求敲才。作用類似負載均衡裹纳。
3.client自己感知各node負責(zé)的分區(qū)

三種路由方式

上面幾種方式都有一個關(guān)鍵問題
做路由決策的組件如何感知路由的變化
要達成一致性是一個很有挑戰(zhàn)性的問題择葡，有一些分布式一致性的協(xié)議，但是很難被正確的實現(xiàn)剃氧。

很多分布式數(shù)據(jù)系統(tǒng)都依賴一個協(xié)同服務(wù)類似Zookeeper來跟蹤cluster的元數(shù)據(jù)敏储。
（Zookeeper源碼之前都講過，比較熟悉）
就是client注冊watch來感知Zk上一些znode的創(chuàng)建朋鞍，刪除已添，內(nèi)容改動的行為

現(xiàn)狀

比如HBase，SolrCloud滥酥，Kafka都用Zookeeper
Cassanddra和Riak用gossip協(xié)議

7.總結(jié)

探討路分區(qū)的方式（key range更舞， hash range）
探討了分區(qū)和二級索引的兩種方式(文檔分區(qū)的二級索引，詞語分區(qū)的二級索引)
探討了Rebalancing的三個策略（固定分區(qū)數(shù)量恨狈，動態(tài)分區(qū)疏哗，按節(jié)點比例的分區(qū)）
探討了請求路由的幾種方式以及目前的一些現(xiàn)狀

思考

名詞

傾斜，熱點禾怠，local index，global index,scatter/gather
單個key熱點的解決
文檔二級索引與local index與scatter/gather贝搁， 文檔二級索引的優(yōu)劣

refer

了解預(yù)分區(qū)相關(guān)（沒有深入）
http://www.cnblogs.com/niurougan/p/3976519.html
http://blog.csdn.net/javajxz008/article/details/51913471