一、簡介
關于一緻性雜湊演算法介紹有許多類似文章，需要把一些理論轉為為自己的知識，是以有了這篇文章，本文部分實作也參照了原有的一些方法。
該算法在分布緩存的主機選擇中很常用，詳見 http://en.wikipedia.org/wiki/Consistent_hashing 。
二、算法誕生緣由
現在許多大型系統都離不開緩存(K/V)（由于高并發等因素照成的資料庫壓力(或磁盤IO等)超負荷，需要緩存緩解壓力），為了獲得良好的水準擴充性，
緩存主機互相不通信（如Mencached），通過用戶端計算Key而得到資料存放的主機節點，最簡單的方式是取模，假如：
----------------------------------------------------------------
現在有3台緩存主機，現在有一個key 為 cks 的資料需要存儲：
key = "cks"
hash(key) = 10
10 % 3 = 1 ---> 則代表選擇第一台主機存儲這個key和對應的value。
缺陷：
假如有一台主機當機或增加一台主機（必須考慮的情況），取模的算法将導緻大量的緩存失效（計算到其他沒有緩存該資料的主機），資料庫等突然承受巨大負荷，很大可能導緻DB服務不可用等。
三、一緻性雜湊演算法原理
該算法需要解決取模方法當增加主機或者當機時帶來的大量緩存抖動問題，要在生産環境中使用，算法需具備以下幾個特點：
1. 平衡性 ： 指緩存資料盡量平衡分布到所有緩存主機上，有效利用每台主機的空間。
2. 單調性 ： 當出現當機或有新主機加入時，盡量保護原有的緩存能繼續命中，即少量緩存需要重新配置設定。
3. 負載均衡 ： 每台緩存主機盡量平衡分擔壓力，即Key的配置設定比例在這些主機中應趨于平衡。
假如我們把鍵hash為int類型（32位元組），取值範圍為 -2^31 到 (2^31-1) ， 我們把這些值首尾相連形成一個圓環，如下圖：
可以發現，隻有少量緩存被重新配置設定的新主機，減少抖動帶來的壓力。
但同時出現一個問題，資料分布并不盡量均勻（當有大量緩存的時候可以看出來），這時候需要把真實的緩存節點虛拟為多個節點，分布在環上，
當順時針找到虛拟節點的時候再映射到真實節點，則可以知道資料緩存在哪台主機。
四、算法實作（Java版本）
算法的實作有許多，下面例子僅供參考，實際仍需要考慮其他多個問題：
假設有4主機：
192.168.70.1-5
public class Node {
private String ip;
// 代表主機中存放的K/V
private ConcurrentMap<Object, Object> map = new ConcurrentHashMap<Object, Object>();
public Node(String ip) {
this.ip = ip;
}
public String getIp() {
return ip;
}
public ConcurrentMap<Object, Object> getMap() {
return map;
}
@Override
public String toString() {
return ip;
}
} 下面是一個沒有虛拟節點的情況實作方法：
public class ConsistentHash {
// -2^31 - (2^31-1) 圓環, 用于存儲節點
private final SortedMap<Integer, Node> circle = new TreeMap<Integer, Node>();
private IHash hashIf;
public ConsistentHash(IHash hash) {
this.hashIf = hash;
}
public void addNode(Node node) {
circle.put(hashIf.hash(node.getIp()), node);
}
public void removeNode(Node node) {
circle.remove(hashIf.hash(node.getIp()));
}
public Node getNode(Object key) {
int hashCode = hashIf.hash(key);
if (!circle.containsKey(hashCode)) {
// 類似順時針取得最近的存儲節點
SortedMap<Integer, Node> tailMap = circle.tailMap(hashCode);
hashCode = tailMap.isEmpty()? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hashCode);
}
} 其中IHash 為散列方法接口，可實作不同的散列方式，下面是一個基于MD5算法得到的int值（還有其他算法）：
public interface IHash {
int hash(Object key);
} public class MD5HashImpl implements IHash {
MessageDigest digest;
public MD5HashImpl() throws NoSuchAlgorithmException {
digest = MessageDigest.getInstance("MD5");
}
@Override
public int hash(Object key) {
if (key == null) return 0;
int h = key.hashCode();
byte[] bytes = new byte[4];
for(int i=3; i>-1; i--) {
bytes[i] = (byte)( h>>(i*8) );
}
byte[] hashBytes ;
synchronized (digest) {
hashBytes = digest.digest(bytes);
}
int result = 0;
for (int i=0; i<4; i++) {
int idx = i*4;
result += (hashBytes[idx + 3]&0xFF << 24)
| (hashBytes[idx + 2]&0xFF << 16)
| (hashBytes[idx + 1]&0xFF << 8)
| (hashBytes[idx + 0]&0xFF);
}
return result;
}
} 測試方法如下：
public class ConsistentHashTest {
public static void main(String[] args) throws Exception {
ConsistentHash cHash = new ConsistentHash(new MD5HashImpl());
// Nodes
List<Node> nodes = new ArrayList<Node>();
for (int i=1; i<5; i++) {
Node node = new Node("192.168.70." + i); // Fake
nodes.add(node);
cHash.addNode(node);
}
Map<String, Set<Integer>> counter = new HashMap<String, Set<Integer>>();
for (Node n : nodes) {
counter.put(n.getIp(), new HashSet<Integer>());
}
// 随機KEY測試分布情況
Set<Integer> allKeys = new HashSet<Integer>();
Random random = new Random();
int testTimes = 1000000;
for (int i=0; i<testTimes; i++) {
int randomInt = random.nextInt();
Node node = cHash.getNode(randomInt);
Set<Integer> count = counter.get(node.getIp());
count.add(randomInt);
allKeys.add(randomInt);
}
for (Map.Entry<String, Set<Integer>> entry : counter.entrySet()) {
System.out.println(entry.getKey() + "\t" + entry.getValue().size()
+ "\t" + (entry.getValue().size()*100/(float)allKeys.size()) + "%");
}
}
} 測試結果（每次運作的實際結果不同）：
IP Count Percent
--------------------------------------
192.168.70.1 216845 21.6845%
192.168.70.4 7207 0.7207%
192.168.70.2 749929 74.9929%
192.168.70.3 25891 2.5891%
-------------------------------------
這結果表示每個節點配置設定并不均勻，需要把每個節點虛拟為多個節點，ConsistentHash 算法更改如下：
public class ConsistentHash {
// -2^31 - (2^31-1) 圓環, 用于存儲節點
private final SortedMap<Integer, Node> circle = new TreeMap<Integer, Node>();
private IHash hashIf;
private int virtualNum; // 把實際節點虛拟為多個節點
public ConsistentHash(IHash hash, int virtualNum) {
this.hashIf = hash;
this.virtualNum = virtualNum;
}
public void addNode(Node node) {
for (int i=0; i<virtualNum; i++) {
circle.put(hashIf.hash(i + node.getIp()), node);
}
}
public void removeNode(Node node) {
for (int i=0; i<virtualNum; i++) {
circle.remove(hashIf.hash(i + node.getIp()));
}
}
public Node getNode(Object key) {
int hashCode = hashIf.hash(key);
if (!circle.containsKey(hashCode)) {
// 類似順時針取得最近的存儲節點
SortedMap<Integer, Node> tailMap = circle.tailMap(hashCode);
hashCode = tailMap.isEmpty()? circle.firstKey() : tailMap.firstKey();
}
return circle.get(hashCode);
}
} 隻需要在測試函數裡面修改：
// 這裡每個節點虛拟為120個，根據實際情況考慮修改合理的值，虛拟數量少則導緻部分不均勻，數量大則導緻樹的查找效率降低，兩者需要權衡。
ConsistentHash cHash = new ConsistentHash(new MD5HashImpl(), 120);
--------------------------- 添加虛拟節點後的分布情況 ----------------------------------------
192.168.70.1 277916 27.7916%
192.168.70.4 251437 25.1437%
192.168.70.2 226645 22.6645%
192.168.70.3 243871 24.3871%
------------------------------------------------------------------------------------------------
下面再模拟當機和新增主機情況下面的緩存失效率：
public class HitFailureTest {
public static void main(String[] args) throws Exception {
ConsistentHash cHash = new ConsistentHash(new MD5HashImpl(), 120);
List<Node> nodes = new ArrayList<Node>();
for (int i=1; i<5; i++) {
Node node = new Node("192.168.70." + i); // Fake
nodes.add(node);
cHash.addNode(node);
}
Set<Integer> allKeys = new HashSet<Integer>();
Random random = new Random();
int testTimes = 1000000;
for (int i=0; i<testTimes; i++) {
int randomInt = random.nextInt();
cHash.getNode(randomInt).getMap().put(randomInt, 0);
allKeys.add(randomInt);
}
// 移除主機序号
int removeIdx = 1;
cHash.removeNode(nodes.get(removeIdx));
int failureCount = 0;
for (Integer key : allKeys) {
if(!cHash.getNode(key).getMap().containsKey(key)) {
failureCount ++;
}
}
System.out.println("FailureCount \t Percent");
System.out.println(failureCount + "\t" + (failureCount*100/(float)allKeys.size()) + "%");
}
} 結果如下：
FailureCount Percent
231669 23.16975%
結果說明具有比較低的緩存失效率，當主機越多則失效率越低。
五、總結
一緻性雜湊演算法能比較好地保證分布緩存的可用性與擴充性，目前大多緩存用戶端都基于這方式實作（考慮的因素比上面多很多，如性能問題等），
上面實作方式在當機或新增機器時候小部分緩存丢失，但有些情況下緩存不允許丢失，則需要做緩存備份，有兩種方式：
1. 修改用戶端，保證資料被緩存到兩台不同機器，任一一台當機資料仍能找到。
2. 由緩存服務端實作備份，采用無固定主節點（當主節點失效時重新選舉最老的機器作為主節點）模式，節點互備份。