一致哈希 是一種特殊的哈希算法。在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙?duì)K/n個(gè)關(guān)鍵字重新映射，其中K是關(guān)鍵字的數(shù)量，n是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個(gè)槽位的幾乎需要對(duì)所有關(guān)鍵字進(jìn)行重新映射。
分布式緩存問(wèn)題
一個(gè)網(wǎng)站隨著流量增加，服務(wù)器壓力越來(lái)越大，之前直接讀寫數(shù)據(jù)庫(kù)的方式遭遇I/O和連接數(shù)的瓶頸，于是我們引入Memcached作為緩存服務(wù)器減輕DB壓力。
如果我們有三臺(tái)Memcached緩存服務(wù)器，如何路由數(shù)據(jù)到不同的緩存服務(wù)器呢？
我們很容易想到通過(guò)hash的方法來(lái)路由請(qǐng)求，通過(guò)target=hash(key) %n，其中n是服務(wù)器數(shù)量。
但是以上方法會(huì)有一個(gè)問(wèn)題，就是當(dāng)某臺(tái)服務(wù)器宕機(jī)或者新增服務(wù)器時(shí)，大量的緩存內(nèi)容會(huì)變更目標(biāo)地址，所以會(huì)導(dǎo)致大量的緩存失效和重設(shè)。
這個(gè)時(shí)候，就需要一種一致性哈希算法來(lái)盡可能使同一個(gè)資源映射到同一臺(tái)緩存服務(wù)器。
一致哈希算法的主要思想是將每個(gè)緩存服務(wù)器與一個(gè)或多個(gè)哈希值域區(qū)間關(guān)聯(lián)起來(lái)，其中區(qū)間邊界通過(guò)計(jì)算緩存服務(wù)器對(duì)應(yīng)的哈希值來(lái)決定。如果一個(gè)緩存服務(wù)器被移除，則它所對(duì)應(yīng)的區(qū)間會(huì)被并入到鄰近的區(qū)間，其他的緩存服務(wù)器不需要任何改變。
算法背景
一致性哈希算法在1997年由麻省理工學(xué)院的Karger等人在解決分布式Cache中提出的，設(shè)計(jì)目標(biāo)是為了解決因特網(wǎng)中的熱點(diǎn)(Hot spot)問(wèn)題。原文在http://dl.acm.org/citation.cfm?id=258660
實(shí)現(xiàn)
一致哈希將每個(gè)對(duì)象映射到圓環(huán)邊上的一個(gè)點(diǎn)，系統(tǒng)再將可用的節(jié)點(diǎn)機(jī)器映射到圓環(huán)的不同位置。
查找某個(gè)對(duì)象對(duì)應(yīng)的機(jī)器時(shí)，用一致哈希算法計(jì)算得到對(duì)象對(duì)應(yīng)圓環(huán)邊上位置，沿著圓環(huán)邊上查找直到遇到某個(gè)節(jié)點(diǎn)機(jī)器，這臺(tái)機(jī)器即為對(duì)象應(yīng)該保存的位置。
當(dāng)刪除一臺(tái)節(jié)點(diǎn)機(jī)器時(shí)，這臺(tái)機(jī)器上保存的所有對(duì)象都要移動(dòng)到下一臺(tái)機(jī)器。
添加一臺(tái)機(jī)器到圓環(huán)邊上某個(gè)點(diǎn)時(shí)，這個(gè)點(diǎn)的下一臺(tái)機(jī)器需要將這個(gè)節(jié)點(diǎn)前對(duì)應(yīng)的對(duì)象移動(dòng)到新機(jī)器上。
更改對(duì)象在節(jié)點(diǎn)機(jī)器上的分布可以通過(guò)調(diào)整節(jié)點(diǎn)機(jī)器的位置來(lái)實(shí)現(xiàn)。
- 首先求出memcached服務(wù)器（節(jié)點(diǎn)）的哈希值，并將其配置到0～2^32的圓環(huán)上
- 然后采用同樣的方法求出存儲(chǔ)數(shù)據(jù)的鍵的哈希值，并映射到相同的圓上
- 然后從數(shù)據(jù)映射到的位置開(kāi)始順時(shí)針查找，將數(shù)據(jù)保存到找到的第一個(gè)服務(wù)器上
- 如果超過(guò)2^32仍然找不到服務(wù)器，就會(huì)保存到第一臺(tái)memcached服務(wù)器上
當(dāng)添加一個(gè)新的服務(wù)器節(jié)點(diǎn)時(shí)，如下圖所示：
node5是新增的節(jié)點(diǎn)，此時(shí)原本原本全部在node4上的內(nèi)容，會(huì)有一部分轉(zhuǎn)移到node5上，其他節(jié)點(diǎn)的數(shù)據(jù)內(nèi)容不受影響。
同理，刪除一個(gè)節(jié)點(diǎn)，受影響的也只是與被刪除節(jié)點(diǎn)相鄰的服務(wù)器。
帶虛擬節(jié)點(diǎn)的一致性哈希算法
以上算法存在一個(gè)問(wèn)題，就是在節(jié)點(diǎn)數(shù)目很少，且節(jié)點(diǎn)的hash值較為集中的時(shí)候，會(huì)造成很明顯的數(shù)據(jù)分配不均的問(wèn)題。
如上圖所示，當(dāng)只存在兩個(gè)節(jié)點(diǎn)時(shí)，大量數(shù)據(jù)會(huì)分配在nodeA上，只有少量數(shù)據(jù)會(huì)分配在nodeB上，為了解決上述問(wèn)題，引入了虛擬節(jié)點(diǎn)的概念。即對(duì)每一個(gè)服務(wù)節(jié)點(diǎn)計(jì)算多個(gè)哈希，每個(gè)計(jì)算結(jié)果位置都放置一個(gè)此服務(wù)節(jié)點(diǎn)，稱為虛擬節(jié)點(diǎn)。具體做法可以在服務(wù)器ip或主機(jī)名的后面增加編號(hào)來(lái)實(shí)現(xiàn)。例如上面的情況，可以為每臺(tái)服務(wù)器計(jì)算三個(gè)虛擬節(jié)點(diǎn)，于是可以分別計(jì)算 “NodeA#1”、“NodeA#2”、“Node A#3”、“NodeB#1”、“NodeB#2”、“NodeB#3”的哈希值，于是形成六個(gè)虛擬節(jié)點(diǎn)。最后再根據(jù)虛擬節(jié)點(diǎn)-真實(shí)節(jié)點(diǎn)的映射規(guī)則，求出真實(shí)節(jié)點(diǎn)。
代碼實(shí)現(xiàn)（Java）
package com.zhuke.daily;
import java.util.Iterator;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.UUID;
import java.util.zip.CRC32;
/**
* 一致性hash算法
* <p>
* Created by ZHUKE on 2017/8/16.
*/
public class ConsistentHashing {
/**
* 服務(wù)器信息
*/
private static final String[] SERVERS = new String[]{"node1", "node2", "node3"};
/**
* 一致性哈希環(huán)
*/
private static SortedMap<Long, String> hashRing = new TreeMap<>();
/**
* 虛擬節(jié)點(diǎn)數(shù)目
*/
private static final int VIRTUAL_NODE_COUNT = 32;
/**
* hash環(huán)的最大位置2^32
*/
private static final long MAX_HASH_LOCATION = 1L << 32;
static {
//initHashRingWithoutVirtualNode();
initHashRingWithVirtualNode();
}
/**
* 初始化哈希環(huán)，沒(méi)有虛擬節(jié)點(diǎn)
*/
public static void initHashRingWithoutVirtualNode() {
for (String server : SERVERS) {
hashRing.put(hash(server), server);
}
}
/**
* 初始化哈希環(huán)，帶虛擬節(jié)點(diǎn)
*/
public static void initHashRingWithVirtualNode() {
for (String server : SERVERS) {
for (int i = 0; i < VIRTUAL_NODE_COUNT; i++) {
String virtualServer = server + "#virtual" + i;
hashRing.put(hash(virtualServer), virtualServer);
}
}
}
/**
* 為key分配server
*
* @param key key
* @return 分配的server
*/
public static String allocateServer(String key) {
long hashValue = hash(key);
/*
* TreeMap保證key的有序排列，可以當(dāng)作是一個(gè)首尾相連的環(huán),
* 所以為新的key分配server地址時(shí)，按照相同的hash算法得到hashValue，
* 在TreeMap的環(huán)狀結(jié)構(gòu)中，查找第一個(gè)比該hashValue大的key，其對(duì)應(yīng)的server即為分配的server
* */
SortedMap<Long, String> tailHashRing = hashRing.tailMap(hashValue);
String virtualNode;
if (tailHashRing.isEmpty()) {
virtualNode = hashRing.get(hashRing.firstKey());
} else {
virtualNode = hashRing.get(tailHashRing.firstKey());
}
return getRealNode(virtualNode);
}
private static long hash(String key) {
CRC32 crc32 = new CRC32();
crc32.update(key.getBytes());
return crc32.getValue() % MAX_HASH_LOCATION;
}
private static String getRealNode(String virtualNode) {
if (!virtualNode.contains("#")) {
return virtualNode;
}
return virtualNode.split("#")[0];
}
public static void main(String[] args) {
Iterator<Long> iterator = hashRing.keySet().iterator();
while (iterator.hasNext()) {
Long key = iterator.next();
System.out.println(key + "," + hashRing.get(key));
}
int node1Count = 0;
int node2Count = 0;
int node3Count = 0;
for (int i = 0; i < 1000; i++) {
String key = UUID.randomUUID().toString();
String server = allocateServer(key);
if (server.equals("node1")) node1Count++;
if (server.equals("node2")) node2Count++;
if (server.equals("node3")) node3Count++;
}
System.out.println("node1Count=" + node1Count);
System.out.println("node2Count=" + node2Count);
System.out.println("node3Count=" + node3Count);
}
}
