概述
一致性哈希算法在 1997 年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個伺服器時，能夠儘可能小地改變已存在的服務請求與處理請求伺服器之間的映射關係。
一致性哈希算法很好地解決了分布式系統在擴容或者縮容時，發生大量的數據遷移的問題，一致哈希算法裡面用了取模運算，但與哈希算法不同的是，哈希算法是對節點的數量進行取模運算，而一致哈希算法是對 2^32 進行取模運算，是一個固定的值。
可以理解一致哈希算法是對 2^32 進行取模運算的結果值組織成一個圓環，就像鐘錶一樣，鐘錶的圓可以理解成由 60 個點組成的圓，而此處我們把這個圓想像成由 2^32 個點組成的圓，這個圓環被稱為哈希環，如下圖：
舉個例子，有 3 個節點經過哈希計算，映射到了如下圖的位置：
接著，對要查詢的 key1 進行哈希計算，確定此 key1 映射在哈希環的位置，然後從這個位置往順時針的方向找到第一個節點，就是存儲該 key1 數據的節點。
比如，下圖中的 key1 映射的位置，往順時針的方向找到第一個節點就是DB1
所以，當需要對指定 key 的值進行讀寫的時候，要通過下面 2 步進行尋址：
- • 首先，對 key 進行哈希計算，確定此 key 在環上的位置；
- • 然後，從這個位置沿著順時針方向走，遇到的第一節點就是存儲 key 的節點。
知道了一致哈希尋址的方式，我們來看看，如果增加一個節點或者減少一個節點會發生大量的數據遷移嗎？
可以看到，key1、key3 都不受影響，只有 key2 需要被遷移DB4。
假設節點數量這會從3 減少到了 2，將DB3 移除：
如上圖，可以看到key2和key1不受影響，只需要把key3遷移到DB1即可，因此在一致哈希算法中，如果增加或者移除一個節點，僅影響該節點在哈希環上順時針相鄰的後繼節點，其它數據也不會受到影響。
一致性hash存在的問題
上文中3 個節點映射在哈希環相對還是比較分散的，因此看起來請求都會「均衡」到每個節點，但是實際情況是一致性Hash並不能保證節點能夠在哈希環上均勻分布，這樣就會帶來一個問題，會有大量的請求集中在一個節點上。
這時候有一半以上的數據的尋址都會找到DB1，說好的負載均衡呢，這種情況一點都不均衡！
另外，在這種分布不均勻的情況下，進行容災與擴容時，哈希環上的相鄰節點容易受到過大影響，容易發生雪崩式的連鎖反應。
例如，上圖中如果DB1被移除了，當DB1宕機後，根據一致性哈希算法的規則，其上數據應該全部遷移到相鄰的DB2 上，這樣DB2數據量和訪問量都會迅速增加很多倍，一旦新增的壓力超過了DB2 的處理能力上限，就會導致DB2 崩潰，以此類推就會形成雪崩式的連鎖反應。
所以，一致性哈希算法雖然減少了數據遷移量，但是存在節點分布不均勻的問題。
通過虛擬節點提高均衡度
要想解決節點能在哈希環上分配不均勻的問題，就是要有更多的節點，節點數越多，哈希環上的分布節點就越均勻。
但實際中我們沒有那麼多節點。所以這個時候就需要加入虛擬節點，也就是對一個真實節點做映射節點。
具體做法是，不再將真實節點映射到哈希環上，而是將虛擬節點映射到哈希環上，並將虛擬節點映射到真實節點，所以這裡有「兩層」映射關係。
比如對每個節點分別設置 3 個虛擬節點：
- • 對DB1 加上編號來作為虛擬節點：DB1-1、DB1-2、DB1-3
- • 對DB2 加上編號來作為虛擬節點：DB2-1、DB2-2、DB2-3
- • 對DB3 加上編號來作為虛擬節點：DB3-1、DB3-2、DB3-3
引入虛擬節點後，原本哈希環上只有 3 個節點的情況，就會變成有 9 個虛擬節點映射到哈希環上，哈希環上的節點數量多了 3 倍。
你可以看到，節點數量多了後，節點在哈希環上的分布就相對均勻了。這時候，如果有訪問請求尋址到「DB1-1」這個虛擬節點，接著再通過「DB1-1」虛擬節點找到真實節點 DB1，這樣請求就能訪問到真實節點 DB1 了。
上面為了方便理解，每個真實節點僅包含 3 個虛擬節點，這樣能起到的均衡效果其實很有限。而在實際的工程中，虛擬節點的數量會大很多。
虛擬節點除了會提高節點的均衡度，還會提高系統的穩定性。當節點變化時，會有不同的節點共同分擔系統的變化，因此穩定性更高。
比如，當某個節點被移除時，對應該節點的多個虛擬節點均會移除，而這些虛擬節點按順時針方向的下一個虛擬節點，可能會對應不同的真實節點，即這些不同的真實節點共同分擔了節點變化導致的壓力。
而且有了虛擬節點後，還可以為硬體配置更好的節點增加權重，比如對權重更高的節點增加更多的虛擬機節點即可。
因此，帶虛擬節點的一致性哈希方法不僅適合硬體配置不同的節點的場景，而且適合節點規模會發生變化的場景。
一致性哈希算法實現
以下代碼摘自mycat的一致性hash代碼，並進行部分修改。
這裡設置虛擬節點為16個，計算1千萬數據的分布情況，hash類引用的guava包中的HashFunction，如果要測試，需要引入guava包
public class PartitionByMurmurHash {
private static final int DEFAULT_VIRTUAL_BUCKET_TIMES = 16;
private static final int DEFAULT_WEIGHT = 1;
private int seed;
private int count;
private int virtualBucketTimes = DEFAULT_VIRTUAL_BUCKET_TIMES;
private Map<Integer, Integer> weightMap = new HashMap<>();
private HashFunction hash;
private SortedMap<Integer, Integer> bucketMap;
public void init() {
try {
bucketMap = new TreeMap<>();
generateBucketMap();
} catch (Exception e) {
throw new MurmurHashException(e);
}
}
private void generateBucketMap() {
hash = Hashing.murmur3_32(seed);//計算一致性哈希的對象
for (int i = 0; i < count; i++) {//構造一致性哈希環，用TreeMap表示
StringBuilder hashName = new StringBuilder("SHARD-").append(i);
for (int n = 0, shard = virtualBucketTimes * getWeight(i); n < shard; n++) {
bucketMap.put(hash.hashUnencodedChars(hashName.append("-NODE-").append(n)).asInt(), i);
}
}
weightMap = null;
}
/**
* 得到桶的權重，桶就是實際存儲數據的DB實例
* 從0開始的桶編號為key，權重為值，權重默認為1。
* 鍵值必須都是整數
*
* @param bucket
* @return
*/
private int getWeight(int bucket) {
Integer w = weightMap.get(bucket);
if (w == null) {
w = DEFAULT_WEIGHT;
}
return w;
}
/**
* 虛擬節點倍數，virtualBucketTimes*count就是虛擬結點數量
*
* @param virtualBucketTimes
*/
public void setVirtualBucketTimes(int virtualBucketTimes) {
this.virtualBucketTimes = virtualBucketTimes;
}
/**
* 計算hash值
*
* @param columnValue
* @return
*/
public Integer calculate(String columnValue) {
//返回大於等於這個hash值得key
SortedMap<Integer, Integer> tail = bucketMap.tailMap(hash.hashUnencodedChars(columnValue).asInt());
if (tail.isEmpty()) {
return bucketMap.get(bucketMap.firstKey());
}
return tail.get(tail.firstKey());
}
private static void hashTest(Integer virtualBucketTimes, int count) throws IOException {
PartitionByMurmurHash hash = new PartitionByMurmurHash();
hash.count = count;//分片數
hash.setVirtualBucketTimes(virtualBucketTimes);
hash.init();
int[] bucket = new int[hash.count];
Map<Integer, List<Integer>> hashed = new HashMap<>();
int total = 1000_0000;//數據量
int c = 0;
for (int i = 100_0000; i < total + 100_0000; i++) {//假設分片鍵從100萬開始
c++;
//計算hash值
int h = hash.calculate(Integer.toString(i));
//更新對應節點的數據量
bucket[h]++;
//記錄每個節點的數據值
List<Integer> list = hashed.get(h);
if (list == null) {
list = new ArrayList<>();
hashed.put(h, list);
}
list.add(i);
}
//總數量占比
double d = 0;
//數據總數
c = 0;
//節點索引
int idx = 0;
System.out.println("節點 數據量 占比");
for (int i : bucket) {
//計算每個節點的數據量占比
double ratio = i / (double) total;
//計算總比例，所有節點數量加起來，最終應該等於1
d += ratio;
//累加數據量，後面列印出來應該與總數量相等
c += i;
//列印每個節點的數據量和數據占比
System.out.println((idx++) + " " + i + " " + ratio);
}
Properties props = new Properties();
//獲取虛擬節點key和實際對應的節點
for (Map.Entry entry : hash.bucketMap.entrySet()) {
props.setProperty(entry.getKey().toString(), entry.getValue().toString());
}
ByteArrayOutputStream out = new ByteArrayOutputStream();
props.store(out, null);
props.clear();
props.load(new ByteArrayInputStream(out.toByteArray()));
System.out.println("*************虛擬節點與物理節點映射關係***************");
//列印映射關係
System.out.println(props);
}
public static void main(String[] args) throws IOException {
}
}數據分布測試
修改main方法為以下代碼
public static void main(String[] args) throws IOException {
System.out.println("******************設虛擬節點數16,物理節點為2測試******************");
hashTest(16, 2);
System.out.println("\n\n");
System.out.println("******************虛擬節點數為0，物理節點為2測試******************");
hashTest(1, 2);
}以上代碼運行完會列印以下信息，有虛擬節點的和沒有虛擬節點的數據分布情況以及物理節點與虛擬節點的映射關係，可以看到沒有虛擬節點數據分布很不均衡
******************設虛擬節點數16測試******************
節點 數據量 占比
0 5002425 0.5002425
1 4997575 0.4997575
*************虛擬節點與物理節點映射關係***************
{200332588=1, 1296449864=0, 2057762094=1, 1572653839=1, 999922443=0, -645649416=1, -1807095086=0, -1388869216=0, 1542099937=0, 2069669860=0, 276793709=1, 1061899120=1, 1024545989=1, -915504677=1, 722846884=0, -1316369830=1, -1711177021=0, 450739710=1, 1447771381=1, -1576564361=1, -459771630=0, -713347722=0, -880637439=1, -167820385=1, -1598857122=0, 1102813202=0, -1497574221=0, -788019661=1, 1756943855=0, -1533394541=0, 1918189761=1, 1538310795=0}
******************虛擬節點數為0測試******************
節點 數據量 占比
0 8066217 0.8066217
1 1933783 0.1933783
*************虛擬節點與物理節點映射關係***************
{-880637439=1, -1711177021=0}
數據遷移測試
修改main方法為以下代碼，測試節點數由2修改3節點時需要遷移得數據量，正常結果應為總節點數由2節點變成3節點時，只有1個節點數據需要遷移
public static void main(String[] args) throws IOException {
System.out.println("***********************數據遷移測試******************");
System.out.println("物理節點為2，數據分布情況");
hashTest(1, 2);
System.out.println("\n\n");
System.out.println("物理節點為3，數據分布情況");
hashTest(1, 3);
}執行完以上代碼，可以看到只遷移到編號為0節點數據，編號為1的節點數據不需要遷移
***********************數據遷移測試******************
物理節點為2，數據分布情況
節點 數據量 占比
0 8066217 0.8066217
1 1933783 0.1933783
*************虛擬節點與物理節點映射關係***************
{-880637439=1, -1711177021=0}
物理節點為3，數據分布情況
節點 數據量 占比
0 6094467 0.6094467
1 1933783 0.1933783
2 1971750 0.197175
*************虛擬節點與物理節點映射關係***************
{-880637439=1, -1711177021=0, -33802706=2}總結
一致性哈希是指將「存儲節點」和「數據」都映射到一個首尾相連的哈希環上，增加或者移除一個節點，只影響該節點在哈希環上順時針相鄰的後繼節點，其它數據不會受到影響。
一致性哈希算法不能夠均勻的分布節點，會出現大量請求都集中在一個節點的情況，在這種情況下進行容災與擴容時，容易出現雪崩的連鎖反應。
為了解決一致性哈希算法不能夠均勻的分布節點的問題，就需要引入虛擬節點，對一個真實節點做多個映射節點。不再將真實節點映射到哈希環上，而是將虛擬節點映射到哈希環上，並將虛擬節點映射到真實節點，所以這裡有兩層映射關係。
引入虛擬節點後，可以會提高節點的均衡度，還會提高系統的穩定性。所以，帶虛擬節點的一致性哈希方法不僅適合硬體配置不同的節點的場景，而且適合節點規模會發生變化的場景