前言

大家應(yīng)該都知道一些哈希算法，比如MD5、SHA-1、SHA-256等，通常被用于唯一標(biāo)識(shí)、安全加密、數(shù)據(jù)校驗(yàn)等場(chǎng)景。除此之外，還有一個(gè)哈希算法是用于快速定位、分庫(kù)分表數(shù)據(jù)分配等場(chǎng)景。本文將以分庫(kù)分表為主題，介紹另外一種哈希算法，并詳細(xì)說(shuō)明其在分庫(kù)分表中的應(yīng)用與優(yōu)勢(shì)。

分庫(kù)分表方法

在對(duì)數(shù)據(jù)進(jìn)行分庫(kù)分表時(shí)，通常有兩個(gè)策略（這里主要說(shuō)的是水平分庫(kù)分表）：

第一種是范圍分庫(kù)分表，比如將ID1～1000W的數(shù)據(jù)存放在第一個(gè)表或庫(kù)中，或者將某個(gè)時(shí)間段的數(shù)據(jù)放在第一個(gè)表或庫(kù)中，以此類推。這種方式會(huì)帶來(lái)幾個(gè)問(wèn)題：

數(shù)據(jù)傾斜：因?yàn)槟承r(shí)間段的數(shù)據(jù)的多少是不確定的，可能會(huì)出現(xiàn)數(shù)據(jù)量超過(guò)預(yù)期而造成的查詢性能下降，或者是數(shù)據(jù)量遠(yuǎn)遠(yuǎn)小于預(yù)期造成的空間浪費(fèi)。
未分擔(dān)壓力：分庫(kù)分表的一個(gè)主要目的是避免單節(jié)點(diǎn)的數(shù)據(jù)量過(guò)大造成性能下降。另一個(gè)目的是可以在高并發(fā)的場(chǎng)景下分擔(dān)壓力，但是范圍策略中總是在對(duì)一個(gè)庫(kù)或者表在操作，起不到分擔(dān)壓力的作用，畢竟一個(gè)數(shù)據(jù)庫(kù)的連接和處理能力是有限的。

第二種是哈希分庫(kù)分表，通常都是將某個(gè)數(shù)據(jù)進(jìn)行哈希后進(jìn)行取模，然后映射到對(duì)應(yīng)的庫(kù)或表中，這個(gè)模一般就是庫(kù)的個(gè)數(shù)或者表的個(gè)數(shù)，所以個(gè)數(shù)是固定的。

同樣，如果哈希不當(dāng)也會(huì)存在數(shù)據(jù)傾斜問(wèn)題，所以通常對(duì)那些隨機(jī)、不連續(xù)的數(shù)據(jù)進(jìn)行哈希的分庫(kù)分表效果比較好。

但是存在一個(gè)問(wèn)題那就是：當(dāng)現(xiàn)有的表和庫(kù)容量不足，也就是需要擴(kuò)容的時(shí)候涉及到數(shù)據(jù)遷移的問(wèn)題，因?yàn)槟?shù)變了，之前的數(shù)據(jù)都需要重新取模重新分配到新的庫(kù)和表中，不然就會(huì)出現(xiàn)“查無(wú)此人”的錯(cuò)誤了。

如下圖，在添加“DB4“后，數(shù)據(jù)再次進(jìn)行hash后會(huì)映射到“DB0“上，如果不遷移數(shù)據(jù)就會(huì)出現(xiàn)問(wèn)題。

很顯然，以上兩種方法都存在問(wèn)題，但是哈希這種方法更能體現(xiàn)分庫(kù)分表的作用，但是帶來(lái)的代價(jià)是全量數(shù)據(jù)的遷移，需要考慮遷移帶來(lái)的風(fēng)險(xiǎn)，比如，遷移之后的數(shù)據(jù)一致性、完整性等各種因素。

那有沒(méi)有方法可以避免遷移，答案是沒(méi)有的，只要是使用哈希這種方式，在改變模個(gè)數(shù)后一定是要遷移數(shù)據(jù)的。

但是有一種方法可以降低遷移量以及帶來(lái)的風(fēng)險(xiǎn)，那就是一致性哈希。

一致性哈希

介紹

一致性哈希算法是一種特殊的哈希算法，通常用于分布式系統(tǒng)中，比如分布式緩存、分布式數(shù)據(jù)庫(kù)等解決數(shù)據(jù)的分配和負(fù)載均衡的場(chǎng)景。

與其他哈希算法一樣，具有單向性、離散性、平衡性。不同的是，一致性哈希算法在取模時(shí)這個(gè)模足夠大，比如 Fowler–Noll–Vo (FNV) 哈希函數(shù)，就是是一種高效、分布均勻的哈希函數(shù)，其模數(shù)也就是輸出域在0～2^32^-1區(qū)間。

原理

其原理是將輸出域構(gòu)成一個(gè)環(huán)，數(shù)據(jù)和節(jié)點(diǎn)通過(guò)一致性哈希算法后映射到環(huán)中的某個(gè)點(diǎn)。

當(dāng)需數(shù)據(jù)插入某個(gè)節(jié)點(diǎn)或查找數(shù)據(jù)在某個(gè)節(jié)點(diǎn)時(shí)，這個(gè)數(shù)據(jù)對(duì)應(yīng)的哈希值只需在這個(gè)環(huán)上順時(shí)針找到第一個(gè)節(jié)點(diǎn)進(jìn)行操作即可。當(dāng)節(jié)點(diǎn)數(shù)量改變時(shí)，只需要重新分配一小部分?jǐn)?shù)據(jù)即可，從而降低數(shù)據(jù)遷移風(fēng)險(xiǎn)。

分庫(kù)分表的應(yīng)用

以分庫(kù)分表為例子。

如下圖，共有3個(gè)節(jié)點(diǎn)（也可以理解成3個(gè)數(shù)據(jù)庫(kù)實(shí)例），經(jīng)過(guò)一致性哈希算法后映射到輸出域中的某個(gè)點(diǎn)。

圖中的“數(shù)據(jù)1”經(jīng)過(guò)相同的一致性哈希算法后也會(huì)映射到環(huán)中的某個(gè)點(diǎn)，這個(gè)時(shí)候如果要存儲(chǔ)或者查找該數(shù)據(jù)就需要順時(shí)針找到第一個(gè)節(jié)點(diǎn)，也就是“節(jié)點(diǎn)2”。

那當(dāng)添加一個(gè)節(jié)點(diǎn)后數(shù)據(jù)怎么遷移？

如下圖，當(dāng)添加“節(jié)點(diǎn)4“后，只需要將“節(jié)點(diǎn)2“中的部分?jǐn)?shù)據(jù)遷移到“節(jié)點(diǎn)4“中。

就是將“節(jié)點(diǎn)2“中的哈希值大于“節(jié)點(diǎn)3“小于等于“節(jié)點(diǎn)4“的數(shù)據(jù)遷移到“節(jié)點(diǎn)4“中，其它節(jié)點(diǎn)數(shù)據(jù)則不用遷移。

這樣在分庫(kù)分表中就最大程度減少的數(shù)據(jù)的遷移，也降低了遷移數(shù)據(jù)的風(fēng)險(xiǎn)。

虛擬節(jié)點(diǎn)

通常在進(jìn)行分庫(kù)分表時(shí)我們的節(jié)點(diǎn)個(gè)數(shù)時(shí)有限的，前期可能如圖1的分布一樣，由于節(jié)點(diǎn)在環(huán)中分配不均勻，數(shù)據(jù)映射到環(huán)中也不均勻，就會(huì)有大量的數(shù)據(jù)會(huì)分布到“節(jié)點(diǎn)2”中，同樣會(huì)造成數(shù)據(jù)傾斜問(wèn)題。

怎么辦？那就讓節(jié)點(diǎn)分布均勻，這時(shí)候就要引入虛擬節(jié)點(diǎn)了。

就是說(shuō)真實(shí)的節(jié)點(diǎn)雖然只有三個(gè)，但是我們可以讓每個(gè)節(jié)點(diǎn)作為大節(jié)點(diǎn)管理1000、10000、100000個(gè)虛擬的節(jié)點(diǎn)，使得每個(gè)大節(jié)點(diǎn)在環(huán)中分布均勻，如下圖。

這樣，根據(jù)哈希的平衡性，數(shù)據(jù)會(huì)均勻的分布到3個(gè)大節(jié)點(diǎn)中，如果需要添加一個(gè)大節(jié)點(diǎn)，同樣是分發(fā)給虛擬節(jié)點(diǎn)到環(huán)上，然后根據(jù)遷移規(guī)則進(jìn)行部分?jǐn)?shù)據(jù)的遷移。