通常的Sharding方案
我們假設(shè)現(xiàn)在有2臺(tái)機(jī)器禁熏，我們需要把User表橫向切分映射到這2臺(tái)機(jī)器上惕味。
一個(gè)簡(jiǎn)單的想法就是 userid % 2鬼癣，余數(shù)可能是 0, 1 分別是2臺(tái)機(jī)器的編號(hào)旬迹。
但是這樣做存在一個(gè)巨大的問題弄贿，就是如果加一臺(tái)機(jī)器怎么辦沟蔑？我們的算法肯定要有擴(kuò)展性湿诊，能自由加減機(jī)器。假設(shè)我們現(xiàn)在加了一臺(tái)機(jī)器瘦材，那么現(xiàn)在有3臺(tái)厅须，于是我們的sharding變成了 userid % 3。
這下可麻煩了食棕，因?yàn)楹芏嗟臄?shù)據(jù)這樣計(jì)算完了之后 余數(shù)都變了朗和，于是我們要把大量的數(shù)據(jù)進(jìn)行遷移，而且這個(gè)遷移必須停機(jī)做簿晓，在遷移完成之前系統(tǒng)是不可用的眶拉。
這種哈希算法就叫不一致性哈希算法，那么顯然這種方式是不可取的憔儿。
那么我們改進(jìn)一下忆植，這次我們?nèi)∫粋€(gè)比較大的數(shù)，比如 500，然后 userid % 500 來計(jì)算一個(gè)值朝刊，因?yàn)槲覀冎挥?臺(tái)機(jī)器吴侦，所以顯然這個(gè)余數(shù)不是機(jī)器編號(hào)，而是我們把 0 ~ 499 分配給這2臺(tái)機(jī)器坞古。
這里我們做一個(gè)簡(jiǎn)單的均勻分配：
0?號(hào)機(jī)器： 0~249
1 號(hào)機(jī)器： 250~499
現(xiàn)在我們加一臺(tái)機(jī)器的時(shí)候备韧，編號(hào)為2，那么我們把2號(hào)機(jī)器插入到現(xiàn)有的兩臺(tái)機(jī)器之間痪枫，于是變成了這樣：
0?號(hào)機(jī)器： 0~160
1 號(hào)機(jī)器： 161~320
2 號(hào)機(jī)器： 320~499
圖示如下
可以看到現(xiàn)在全部機(jī)器的壓力都降低了织堂。
這么做的缺點(diǎn)是什么呢？
依然需要做一部分的數(shù)據(jù)遷移
每加入一臺(tái)只能降低鄰居兩臺(tái)機(jī)器的壓力奶陈，這樣很容易導(dǎo)致壓力分布不均局易阳。比如如果有5臺(tái)機(jī)器，增加一臺(tái)之后依然有三臺(tái)機(jī)器壓力不變吃粒。
如何將數(shù)據(jù)均勻的分散到各個(gè)節(jié)點(diǎn)中潦俺，并且盡量的在加減節(jié)點(diǎn)時(shí)能使受影響的數(shù)據(jù)最少呢？
一致 Hash 算法
一致 Hash 算法是將所有的哈希值構(gòu)成了一個(gè)環(huán)徐勃，其范圍在?0 ~ 2^32-1事示。如下圖：
之后將各個(gè)節(jié)點(diǎn)散列到這個(gè)環(huán)上，可以用節(jié)點(diǎn)的 IP僻肖、hostname 這樣的唯一性字段作為 Key 進(jìn)行?hash(key)肖爵，散列之后如下：
之后需要將數(shù)據(jù)定位到對(duì)應(yīng)的節(jié)點(diǎn)上，使用同樣的?hash?函數(shù)將 Key 也映射到這個(gè)環(huán)上臀脏。
這樣按照順時(shí)針方向就可以把 k1 定位到?N1節(jié)點(diǎn)劝堪，k2 定位到?N3節(jié)點(diǎn)，k3 定位到?N2節(jié)點(diǎn)揉稚。
容錯(cuò)性
這時(shí)假設(shè) N1 宕機(jī)了：
依然根據(jù)順時(shí)針方向秒啦，k2 和 k3 保持不變，只有 k1 被重新映射到了 N3搀玖。這樣就很好的保證了容錯(cuò)性余境，當(dāng)一個(gè)節(jié)點(diǎn)宕機(jī)時(shí)只會(huì)影響到少少部分的數(shù)據(jù)。
拓展性
當(dāng)新增一個(gè)節(jié)點(diǎn)時(shí):
在 N2 和 N3 之間新增了一個(gè)節(jié)點(diǎn) N4 巷怜，這時(shí)會(huì)發(fā)現(xiàn)受印象的數(shù)據(jù)只有 k3葛超，其余數(shù)據(jù)也是保持不變，所以這樣也很好的保證了拓展性延塑。
虛擬節(jié)點(diǎn)
到目前為止該算法依然也有點(diǎn)問題:
當(dāng)節(jié)點(diǎn)較少時(shí)會(huì)出現(xiàn)數(shù)據(jù)分布不均勻的情況：
這樣會(huì)導(dǎo)致大部分?jǐn)?shù)據(jù)都在 N1 節(jié)點(diǎn)，只有少量的數(shù)據(jù)在 N2 節(jié)點(diǎn)答渔。
為了解決這個(gè)問題关带，一致哈希算法引入了虛擬節(jié)點(diǎn)。將每一個(gè)節(jié)點(diǎn)都進(jìn)行多次 hash，生成多個(gè)節(jié)點(diǎn)放置在環(huán)上稱為虛擬節(jié)點(diǎn):
計(jì)算時(shí)可以在 IP 后加上編號(hào)來生成哈希值宋雏。
這樣只需要在原有的基礎(chǔ)上多一步由虛擬節(jié)點(diǎn)映射到實(shí)際節(jié)點(diǎn)的步驟即可讓少量節(jié)點(diǎn)也能滿足均勻性芜飘。
