1.前言

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

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

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

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

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

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

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

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

范圍分區(qū)

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

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

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

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

key的hash來分區(qū)

但是，hash分區(qū)相對(duì)于key分區(qū)來說，進(jìn)行范圍查詢就很不容易了。
因?yàn)樵鞠噜彽膬蓚€(gè)key，可能hash到完全不同的兩個(gè)分區(qū)。排序結(jié)構(gòu)被破壞了。
因此，一些db的解決辦法是：范圍查詢的語(yǔ)句，讓所有分區(qū)一起執(zhí)行，最后再匯總。

3.3負(fù)載傾斜以及熱點(diǎn)緩解

hash能減緩熱點(diǎn)問題但是不能完全避免。極端情況下一個(gè)key會(huì)受到大量的讀寫請(qǐng)求。
比如說社交媒體上某個(gè)大V有重大消息，粉絲會(huì)有大量的讀寫操作。常見的解決方法如下

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

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

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

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

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

文檔二級(jí)索引

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

優(yōu):
寫操作時(shí)，只用改當(dāng)前分區(qū)的二級(jí)索引
劣：
讀操作因?yàn)橐闅v所有分區(qū)，存在分散聚集，使得二級(jí)索引查詢操作代價(jià)昂貴

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

4.2 詞語(yǔ)二級(jí)索引分區(qū)

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

詞語(yǔ)二級(jí)索引

優(yōu)：
讀操作更有效率，讀一次term就知道數(shù)據(jù)在哪幾個(gè)分區(qū)，而不用每次讀取所有分區(qū)
劣：
寫操作更復(fù)雜，因?yàn)榭赡芤鹚饕淖?，?dǎo)致幾個(gè)不同分區(qū)的數(shù)據(jù)數(shù)據(jù)一起變動(dòng)
實(shí)際場(chǎng)景下，這要求分布式事務(wù)的執(zhí)行，但是目前還沒有被任何db支持，
因此 global index的更新經(jīng)常是異步的.

5.分區(qū)的Rebalancing

數(shù)據(jù)庫(kù)存儲(chǔ)的量不斷變化，會(huì)有下面的場(chǎng)景需求

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

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

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

5.1 rebalancing策略

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

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

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

有種簡(jiǎn)單的方法是創(chuàng)建遠(yuǎn)比節(jié)點(diǎn)數(shù)量多的分區(qū)數(shù)量，把多個(gè)分區(qū)分配各一個(gè)幾點(diǎn)。
比如10個(gè)節(jié)點(diǎn)包含1000個(gè)分區(qū)。
如果有新的節(jié)點(diǎn)加入，那么新節(jié)點(diǎn)從原有的各個(gè)節(jié)點(diǎn)挪走一部分的分區(qū)，直到balance。

節(jié)點(diǎn)間移動(dòng)的是整個(gè)分區(qū)。
分區(qū)的總數(shù)不變
各個(gè)分區(qū)處理的keys不變
各個(gè)節(jié)點(diǎn)分配的分區(qū)會(huì)變

如下圖

image.png

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

但是固定分區(qū)個(gè)數(shù)會(huì)更簡(jiǎn)單，所以有固定分區(qū)個(gè)數(shù)的算法實(shí)現(xiàn)中，不會(huì)包含split的過程。
這種實(shí)現(xiàn)上，會(huì)選擇足夠大的分區(qū)個(gè)數(shù)，來應(yīng)對(duì)未來的增長(zhǎng)，雖然開始的管理會(huì)顯得麻煩一點(diǎn)。

另外，選擇何時(shí)的分區(qū)的size很難，因?yàn)榉謪^(qū)數(shù)量是固定的但是data size在變化。很難做到剛剛合適。

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

背景

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

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

實(shí)現(xiàn)

一個(gè)分區(qū)分配給一個(gè)節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)可以管理多個(gè)分區(qū)。
既可以進(jìn)行split（某個(gè)分區(qū)數(shù)據(jù)量過大），也可以進(jìn)行merge（幾個(gè)分區(qū)數(shù)據(jù)量過?。?br> 當(dāng)一個(gè)大的分區(qū)進(jìn)行split，會(huì)把一半的數(shù)據(jù)給另一個(gè)節(jié)點(diǎn)，來完成負(fù)載均衡。(書中這里不懂，應(yīng)該是給另一個(gè)分區(qū)吧)

優(yōu)劣

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

場(chǎng)景

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

5.1.3 按節(jié)點(diǎn)比例進(jìn)行分區(qū)

背景

動(dòng)態(tài)分區(qū)中，分區(qū)的數(shù)量和數(shù)據(jù)量的大小有關(guān)，因?yàn)椴徽搒plit還是merge，每個(gè)分區(qū)的size都會(huì)在一個(gè)固定配置的minSize，maxSize區(qū)間中
固定分區(qū)中，每個(gè)分區(qū)的size和數(shù)據(jù)量的size相關(guān)

因此，兩種場(chǎng)景中，分區(qū)的數(shù)量其實(shí)都和節(jié)點(diǎn)的數(shù)量沒有關(guān)系
因此，第三種方法是讓分區(qū)的數(shù)量和節(jié)點(diǎn)的數(shù)量相關(guān)，也就是一個(gè)節(jié)點(diǎn)有固定數(shù)量的分區(qū)。

實(shí)現(xiàn)

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

5.2 手動(dòng)還是自動(dòng)rebalancing

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

6.請(qǐng)求路由

背景

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

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

方式

有幾種方式

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

三種路由方式

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

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

現(xiàn)狀

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

7.總結(jié)

探討路分區(qū)的方式（key range， hash range）
探討了分區(qū)和二級(jí)索引的兩種方式(文檔分區(qū)的二級(jí)索引，詞語(yǔ)分區(qū)的二級(jí)索引)
探討了Rebalancing的三個(gè)策略（固定分區(qū)數(shù)量，動(dòng)態(tài)分區(qū)，按節(jié)點(diǎn)比例的分區(qū)）
探討了請(qǐng)求路由的幾種方式以及目前的一些現(xiàn)狀

思考

名詞

傾斜，熱點(diǎn)，local index，global index,scatter/gather
單個(gè)key熱點(diǎn)的解決
文檔二級(jí)索引與local index與scatter/gather， 文檔二級(jí)索引的優(yōu)劣

refer

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