一致性hash算法: cache、負載均衡應用

2019-11-06 06:43:32

字體：大中小

來源：轉載

供稿：網友

From http://blog.csdn.NET/yq76034150/article/details/6776044

現在的網站用戶量都很大，一臺服務器包打天下的時代一去不復返了，多臺服務器就存在一個問題，如何將訪問用戶轉向不同的服務器，并且各個服務器接受的請求數大致相當呢？這就是一致性hash算法要解決的問題。一致性hash算法在負載服務器（ngnix、haPRoxy等）、K/V 緩存系統memcache等就有相關的實現。這類的文章比較多，摘抄一篇供大家學習。

java實現的一個簡單一致性hash算法：（Spy Memcached client的實現和它類似，使用treemap模擬環）

[java] view plain copy print?import java.util.Collection; import java.util.SortedMap; import java.util.TreeMap; public class ConsistentHash<T> { private final HashFunction hashFunction; private final int numberOfReplicas; private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>(); public ConsistentHash(HashFunction hashFunction, int numberOfReplicas, Collection<T> nodes) { this.hashFunction = hashFunction; this.numberOfReplicas = numberOfReplicas; for (T node : nodes) { add(node); } } public void add(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.put(hashFunction.hash(node.toString() + i), node); } } public void remove(T node) { for (int i = 0; i < numberOfReplicas; i++) { circle.remove(hashFunction.hash(node.toString() + i)); } } public T get(Object key) { if (circle.isEmpty()) { return null; } int hash = hashFunction.hash(key); if (!circle.containsKey(hash)) { SortedMap<Integer, T> tailMap = circle.tailMap(hash); hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey(); } return circle.get(hash); } }

import java.util.Collection;  import java.util.SortedMap;  import java.util.TreeMap;  public class ConsistentHash<T> {   private final HashFunction hashFunction;   private final int numberOfReplicas;   private final SortedMap<Integer, T> circle = new TreeMap<Integer, T>();   public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,       Collection<T> nodes) {     this.hashFunction = hashFunction;     this.numberOfReplicas = numberOfReplicas;     for (T node : nodes) {       add(node);     }   }   public void add(T node) {     for (int i = 0; i < numberOfReplicas; i++) {       circle.put(hashFunction.hash(node.toString() + i), node);     }   }   public void remove(T node) {     for (int i = 0; i < numberOfReplicas; i++) {       circle.remove(hashFunction.hash(node.toString() + i));     }   }   public T get(Object key) {     if (circle.isEmpty()) {       return null;     }     int hash = hashFunction.hash(key);     if (!circle.containsKey(hash)) {       SortedMap<Integer, T> tailMap = circle.tailMap(hash);       hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();     }     return circle.get(hash);   }  }  現在文章抄來抄去太多了，不知道那篇是原創，我是摘抄這里的。
原文： http://blog.csdn.Net/sparkliang/article/details/5279393     
一致性hash算法（consistenthashing）
張亮
consistent hashing算法早在1997年就在論文Consistenthashing and random trees中被提出，目前在cache系統中應用越來越廣泛；
1基本場景
比如你有N個cache服務器（后面簡稱cache），那么如何將一個對象object映射到N個cache上呢，你很可能會采用類似下面的通用方法計算object的hash值，然后均勻的映射到到N個cache；
hash(object)%N
一切都運行正常，再考慮如下的兩種情況；
1 一個cache服務器m down掉了（在實際應用中必須要考慮這種情況），這樣所有映射到cache m的對象都會失效，怎么辦，需要把cache m從cache中移除，這時候cache是N-1臺，映射公式變成了hash(object)%(N-1)；
2 由于訪問加重，需要添加cache，這時候cache是N+1臺，映射公式變成了hash(object)%(N+1)；
1和2意味著什么？這意味著突然之間幾乎所有的cache都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器；
再來考慮第三個問題，由于硬件能力越來越強，你可能想讓后面添加的節點多做點活，顯然上面的hash算法也做不到。
 有什么方法可以改變這個狀況呢，這就是consistent hashing…
2 hash算法和單調性
　　Hash算法的一個衡量指標是單調性（Monotonicity），定義如下：
　　單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。
容易看到，上面的簡單hash算法hash(object)%N難以滿足單調性要求。
3 consistent hashing算法的原理
consistenthashing是一種hash算法，簡單的說，在移除/添加一個cache時，它能夠盡可能小的改變已存在key映射關系，盡可能的滿足單調性的要求。
下面就來按照5個步驟簡單講講consistent hashing算法的基本原理。
3.1環形hash空間
考慮通常的hash算法都是將value映射到一個32為的key值，也即是0~2^32-1次方的數值空間；我們可以將這個空間想象成一個首（0）尾（2^32-1）相接的圓環，如下面圖1所示的那樣。
3.2 把對象映射到hash空間
接下來考慮4個對象object1~object4，通過hash函數計算出的hash值key在環上的分布如圖2所示。
hash(object1) = key1;
… …
hash(object4) = key4;
3.3 把cache映射到hash空間
Consistenthashing的基本思想就是將對象和cache都映射到同一個hash數值空間中，并且使用相同的hash算法。
假設當前有A,B和C共3臺cache，那么其映射結果將如圖3所示，他們在hash空間中，以對應的hash值排列。
hash(cache A) = key A;
… …
hash(cache C) = key C;
說到這里，順便提一下cache的hash計算，一般的方法可以使用cache機器的ip地址或者機器名作為hash輸入。
3.4 把對象映射到cache
現在cache和對象都已經通過同一個hash算法映射到hash數值空間中了，接下來要考慮的就是如何將對象映射到cache上面了。
在這個環形空間中，如果沿著順時針方向從對象的key值出發，直到遇見一個cache，那么就將該對象存儲在這個cache上，因為對象和cache的hash值是固定的，因此這個cache必然是唯一和確定的。這樣不就找到了對象和cache的映射方法了嗎？！
依然繼續上面的例子（參見圖3），那么根據上面的方法，對象object1將被存儲到cache A上；object2和object3對應到cache C；object4對應到cache B；
3.5 考察cache的變動
前面講過，通過 hash然后求余的方法帶來的最大問題就在于不能滿足單調性，當cache有所變動時，cache會失效，進而對后臺服務器造成巨大的沖擊，現在就來分析分析consistenthashing算法。
3.5.1 移除cache
考慮假設cache B掛掉了，根據上面講到的映射方法，這時受影響的將僅是那些沿cache B逆時針遍歷直到下一個cache（cache C）之間的對象，也即是本來映射到cache B上的那些對象。
因此這里僅需要變動對象object4，將其重新映射到cache C上即可；參見圖4。
3.5.2 添加cache
再考慮添加一臺新的cache D的情況，假設在這個環形hash空間中，cache D被映射在對象object2和object3之間。這時受影響的將僅是那些沿cache D逆時針遍歷直到下一個cache（cache B）之間的對象（它們是也本來映射到cache C上對象的一部分），將這些對象重新映射到cache D上即可。
 
因此這里僅需要變動對象object2，將其重新映射到cache D上；參見圖5。
4 虛擬節點
考量Hash算法的另一個指標是平衡性(Balance)，定義如下：
平衡性
　　平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。
hash算法并不是保證絕對的平衡，如果cache較少的話，對象并不能被均勻的映射到cache上，比如在上面的例子中，僅部署cache A和cache C的情況下，在4個對象中，cache A僅存儲了object1，而cache C則存儲了object2、object3和object4；分布是很不均衡的。
為了解決這種情況，consistent hashing引入了“虛擬節點”的概念，它可以如下定義：
“虛擬節點”（virtual node）是實際節點在hash空間的復制品（replica），一實際個節點對應了若干個“虛擬節點”，這個對應個數也成為“復制個數”，“虛擬節點”在hash空間中以hash值排列。
仍以僅部署cache A和cache C的情況為例，在圖4中我們已經看到，cache分布并不均勻?，F在我們引入虛擬節點，并設置“復制個數”為2，這就意味著一共會存在4個“虛擬節點”， cache A1, cache A2代表了cache A；cache C1, cache C2代表了cache C；假設一種比較理想的情況，參見圖6。
此時，對象到“虛擬節點”的映射關系為：
objec1->cache A2；objec2->cache A1；objec3->cache C1；objec4->cache C2；
因此對象object1和object2都被映射到了cache A上，而object3和object4映射到了cache C上；平衡性有了很大提高。
引入“虛擬節點”后，映射關系就從{對象->節點}轉換到了{對象->虛擬節點}。查詢物體所在cache時的映射關系如圖7所示。
“虛擬節點”的hash計算可以采用對應節點的IP地址加數字后綴的方式。例如假設cache A的IP地址為202.168.14.241。
引入“虛擬節點”前，計算cacheA的hash值：
Hash(“202.168.14.241”);
引入“虛擬節點”后，計算“虛擬節”點cache A1和cache A2的hash值：
Hash(“202.168.14.241#1”);  // cache A1
Hash(“202.168.14.241#2”);  // cache A2
5 小結
Consistenthashing的基本原理就是這些，具體的分布性等理論分析應該是很復雜的，不過一般也用不到。
http://weblogs.java.net/blog/2007/11/27/consistent-hashing上面有一個java版本的例子，可以參考。
http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx轉載了一個php版的實現代碼。
http://www.codeproject.com/KB/recipes/lib-conhash.aspx C語言版本
 
一些參考資料地址：
http://portal.acm.org/citation.cfm?id=258660
http://en.wikipedia.org/wiki/Consistent_hashing
http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/
 http://weblogs.java.net/blog/2007/11/27/consistent-hashing
http://tech.idv2.com/2008/07/24/memcached-004/
http://blog.csdn.net/mayongzhan/archive/2009/06/25/4298834.aspx