1.為什么需要一致性哈希？
在分布式服務集群中如MemCache（一個內(nèi)存中存在的Hashmap），需要提供存儲元素object的路由算法，來計算其應該所在的服務器位置。假設服務器集群是一個數(shù)組int[n-1] （n為服務器個數(shù)） ,如果使用這樣的hash算法：
路由到的服務器的數(shù)組位置：index = hash(object) / n;
當增加一個節(jié)點或者減少一個節(jié)點時生棍，會導致大量元素路由的服務器位置改變，導致請求object落空媳谁。
2.一致性哈希算法
一致性哈希的基本原理就是在一個hash環(huán)上（如范圍0-2^32-1）計算服務器節(jié)點的hash值涂滴，如果一個object要尋找應該路由的服務器節(jié)點，則計算其hash值晴音，并在環(huán)上順時針查找離它最近的節(jié)點柔纵。如圖：
如果刪除節(jié)點Cache B,則影響的是CacheA-CacheB之間的key，將會路由至 Cache C ,如object4.
如果增加一個節(jié)點Cache D,則原來一部分路由到Cache C的節(jié)點將會路由到Cache D,如object2
可以看出在節(jié)點發(fā)生變化時一致性哈希相對傳統(tǒng)的哈希取拇冈辏可以減少object重新路由的概率搁料，但是上述哈希分配仍然存在各個節(jié)點所分配的object不均勻的問題。
3.虛擬節(jié)點
如果讓一個物理節(jié)點在hash環(huán)上代表盡可能多的分散均勻的hash值系羞，那么object在各個物理節(jié)點的分配將會更加均勻郭计，如圖：
虛擬節(jié)點與物理節(jié)點的對應關系如下：
下圖橫軸表示需要為每臺福利服務器擴展的虛擬節(jié)點個數(shù)，縱軸表示的是實際物理服務器個數(shù)數(shù)椒振≌焉欤可以看出，物理服務器很少澎迎，需要更大的虛擬節(jié)點勋乾；反之物理服務器比較多宋下，虛擬節(jié)點就可以少一些嗡善。比如有10臺物理服務器辑莫，那么差不多需要為每臺服務器增加100~200個虛擬節(jié)點才可以達到真正的負載均衡。
4.代碼實現(xiàn)
存在兩個問題罩引，一是選取怎樣的hash算法才能夠使得數(shù)據(jù)分布均勻各吨，二是如何快速查找距離最近的服務器節(jié)點是哪個？
（1）String重寫的hashCode()方法在一致性Hash算法上的分布不好袁铐，KETAMA_HASH是默認的MemCache推薦的一致性Hash算法揭蜒，而FNV1_32_HASH算法的效率就會高一些。
（2）這是一個排序問題剔桨，采用紅黑樹時間復雜度為O(LogN),Java中有對應的實現(xiàn)TreeMap,并且TreeMap本身提供了一個tailMap(K fromKey)方法屉更，支持從紅黑樹中查找比fromKey大的值的集合，但并不需要遍歷整個數(shù)據(jù)結(jié)構(gòu)洒缀。
有虛擬節(jié)點的版本實現(xiàn)：
public interface HashFunction {
//hash函數(shù)
Integer hash(String key);
}
public class HashFunctionImpl implements HashFunction {
//FNV1_32_HASH算法
@Override
public Integer hash(String key) {
final int p = 16777619;
int hash = (int)2166136261L;
for (int i = 0; i < key.length(); i++)
hash = (hash ^ key.charAt(i)) * p;
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
// 如果算出來的值為負數(shù)則取其絕對值
if (hash < 0)
hash = Math.abs(hash);
return hash;
}
}
// 物理機節(jié)點模擬類瑰谜，保存節(jié)點的IP、名稱树绩、端口等信息
public class Node {
private String ip;// IP
private String name;// 名稱
public Node(String ip, String name) {
this.ip = ip;
this.name = name;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
public class ConsistentHash {
private final HashFunction hashFunction;// hash 函數(shù)接口
private final int numberOfReplicas;// 每個機器節(jié)點關聯(lián)的虛擬節(jié)點個數(shù)
private final SortedMap<Integer,Node> circle = new TreeMap<>();// 環(huán)形虛擬節(jié)點
/**
*
* @param hashFunction
* hash 函數(shù)接口
* @param numberOfReplicas
* 每個機器節(jié)點關聯(lián)的虛擬節(jié)點個數(shù)
* @param nodes
* 真實機器節(jié)點
*/
public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<Node> nodes) {
this.hashFunction = hashFunction;
this.numberOfReplicas = numberOfReplicas;
for (Node node : nodes) {
add(node);
}
}
/**
* 增加真實機器節(jié)點
*
* @param node
*/
public void add(Node node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.put(this.hashFunction.hash(node.getIp() + i), node);
}
}
/**
* 刪除真實機器節(jié)點
*
* @param node
*/
public void remove(Node node) {
for (int i = 0; i < this.numberOfReplicas; i++) {
circle.remove(this.hashFunction.hash(node.getIp() + i));
}
}
/**
* 取得真實機器節(jié)點
*
* @param key
* @return
*/
public Node get(String key) {
if (circle.isEmpty()) {
return null;
}
Integer hash = hashFunction.hash(key);
if (!circle.containsKey(hash)) {
SortedMap<Integer,Node> tailMap = circle.tailMap(hash);// 沿環(huán)的順時針找到一個虛擬節(jié)點
hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hash); // 返回該虛擬節(jié)點對應的真實機器節(jié)點的信息
}
}
public class ConHashTest {
private static final String IP_PREFIX = "192.168.1.";// 機器節(jié)點IP前綴
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<String, Integer>();// 每臺真實機器節(jié)點上保存的記錄條數(shù)
HashFunction hashFunction = new HashFunctionImpl();
//真實物理節(jié)點
List<Node> realNodes = new ArrayList<>();
for (int i = 1; i <= 10; i++) {
map.put(IP_PREFIX + i, 0);// 每臺真實機器節(jié)點上保存的記錄條數(shù)初始為0
Node node = new Node(IP_PREFIX + i, "node" + i);
realNodes.add(node);
}
ConsistentHash consistentHash = new ConsistentHash(hashFunction,100,realNodes);
// 將10000條記錄盡可能均勻的存儲到10臺機器節(jié)點
for (int i = 0; i < 10000; i++) {
// 產(chǎn)生隨機一個字符串當做一條記錄萨脑，可以是其它更復雜的業(yè)務對象,比如隨機字符串相當于對象的業(yè)務唯一標識
String data = UUID.randomUUID().toString() + i;
// 通過記錄找到真實機器節(jié)點
Node node = consistentHash.get(data);
// 這里可以通過其它工具將記錄存儲真實機器節(jié)點上，比如MemoryCache等
// ...
// 每臺真實機器節(jié)點上保存的記錄條數(shù)加1
map.put(node.getIp(), map.get(node.getIp()) + 1);
}
// 打印每臺真實機器節(jié)點保存的記錄條數(shù)
for (int i = 1; i <= 10; i++) {
System.out.println(IP_PREFIX + i + "節(jié)點記錄條數(shù)：" + map.get("192.168.1." + i));
}
}
}
參考資料：
https://cloud.tencent.com/developer/article/1084801
https://www.codeproject.com/Articles/56138/Consistent-hashing
http://sundoctor.iteye.com/blog/2104321
一致性哈希論文
