前言

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

分庫分表方法

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

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

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

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

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

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

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

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

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

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

一致性哈希

介紹

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

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

原理

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

當(dāng)需數(shù)據(jù)插入某個(gè)節(jié)點(diǎn)或查找數(shù)據(jù)在某個(gè)節(jié)點(diǎn)時(shí)，這個(gè)數(shù)據(jù)對應(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)。

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

以分庫分表為例子。

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

圖中的“數(shù)據(jù)1”經(jīng)過相同的一致性哈希算法后也會映射到環(huán)中的某個(gè)點(diǎn)，這個(gè)時(shí)候如果要存儲或者查找該數(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ù)則不用遷移。

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

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

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

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

就是說真實(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ù)會均勻的分布到3個(gè)大節(jié)點(diǎn)中，如果需要添加一個(gè)大節(jié)點(diǎn)，同樣是分發(fā)給虛擬節(jié)點(diǎn)到環(huán)上，然后根據(jù)遷移規(guī)則進(jìn)行部分?jǐn)?shù)據(jù)的遷移。

總結(jié)

一致性哈希算法在分庫分表的應(yīng)用中提供了一種高效、均勻且易于擴(kuò)展的數(shù)據(jù)分布方式，同時(shí)在節(jié)點(diǎn)增減時(shí)最小化數(shù)據(jù)遷移成本，是一種還不錯(cuò)的分庫分表方案。