前言

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

分庫分表方法

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

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

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

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

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

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

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

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

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

但是有一種方法可以降低遷移量以及帶來的風險，那就是一致性哈希。

一致性哈希

介紹

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

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

原理

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

當需數(shù)據(jù)插入某個節(jié)點或查找數(shù)據(jù)在某個節(jié)點時，這個數(shù)據(jù)對應的哈希值只需在這個環(huán)上順時針找到第一個節(jié)點進行操作即可。當節(jié)點數(shù)量改變時，只需要重新分配一小部分數(shù)據(jù)即可，從而降低數(shù)據(jù)遷移風險。

分庫分表的應用

以分庫分表為例子。

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

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

那當添加一個節(jié)點后數(shù)據(jù)怎么遷移？

如下圖，當添加“節(jié)點4“后，只需要將“節(jié)點2“中的部分數(shù)據(jù)遷移到“節(jié)點4“中。

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

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

虛擬節(jié)點

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

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

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

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

總結

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