點擊上方?好好學java?，選擇?星標?公眾號

重磅資訊、干貨，第一時間送達 今日推薦：干掉 Navicat：這個 IDEA 的兄弟真香！個人原創100W+訪問量博客：點擊前往，查看更多

轉自：MarkLux'Pub ?作者：MarkLux

marklux.cn/blog/90

簡介

一致性Hash是一種特殊的Hash算法，由于其均衡性、持久性的映射特點，被廣泛的應用于負載均衡領域，如nginx和memcached都采用了一致性Hash來作為集群負載均衡的方案。

本文將介紹一致性Hash的基本思路，并討論其在分布式緩存集群負載均衡中的應用。同時也會進行相應的代碼測試來驗證其算法特性，并給出和其他負載均衡方案的一些對比。

一致性Hash算法簡介

在了解一致性Hash算法之前，先來討論一下Hash本身的特點。普通的Hash函數最大的作用是散列，或者說是將一系列在形式上具有相似性質的數據，打散成隨機的、均勻分布的數據。

比如，對字符串abc和abcd分別進行md5計算，得到的結果如下：

可以看到，兩個在形式上非常相近的數據經過md5散列后，變成了完全隨機的字符串。負載均衡正是利用這一特性，對于大量隨機的請求或調用，通過一定形式的Hash將他們均勻的散列，從而實現壓力的平均化。（當然，并不是只要使用了Hash就一定能夠獲得均勻的散列，后面會分析這一點。）

舉個例子，如果我們給每個請求生成一個Key，只要使用一個非常簡單的Hash算法Group = Key % N來實現請求的負載均衡，如下：

（如果將Key作為緩存的Key，對應的Group儲存該Key的Value，就可以實現一個分布式的緩存系統，后文的具體例子都將基于這個場景）

附上我歷時三個月總結的?Java 面試 + Java 后端技術學習指南，筆者這幾年及春招的總結，github 1.1k star，拿去不謝！下載方式1.?首先掃描下方二維碼 2.?后臺回復「Java面試」即可獲取

不難發現，這樣的Hash只要集群的數量N發生變化，之前的所有Hash映射就會全部失效。如果集群中的每個機器提供的服務沒有差別，倒不會產生什么影響，但對于分布式緩存這樣的系統而言，映射全部失效就意味著之前的緩存全部失效，后果將會是災難性的。

一致性Hash通過構建環狀的Hash空間代替線性Hash空間的方法解決了這個問題，如下圖：

整個Hash空間被構建成一個首尾相接的環，使用一致性Hash時需要進行兩次映射。

第一次，給每個節點（集群）計算Hash，然后記錄它們的Hash值，這就是它們在環上的位置。

第二次，給每個Key計算Hash，然后沿著順時針的方向找到環上的第一個節點，就是該Key儲存對應的集群。

分析一下節點增加和刪除時對負載均衡的影響，如下圖：

可以看到，當節點被刪除時，其余節點在環上的映射不會發生改變，只是原來打在對應節點上的Key現在會轉移到順時針方向的下一個節點上去。增加一個節點也是同樣的，最終都只有少部分的Key發生了失效。不過發生節點變動后，整體系統的壓力已經不是均衡的了，下文中提到的方法將會解決這個問題。

問題與優化

最基本的一致性Hash算法直接應用于負載均衡系統，效果仍然是不理想的，存在諸多問題，下面就對這些問題進行逐個分析并尋求更好的解決方案。

數據傾斜

如果節點的數量很少，而hash環空間很大（一般是 0 ~ 2^32），直接進行一致性hash上去，大部分情況下節點在環上的位置會很不均勻，擠在某個很小的區域。最終對分布式緩存造成的影響就是，集群的每個實例上儲存的緩存數據量不一致，會發生嚴重的數據傾斜。

緩存雪崩

如果每個節點在環上只有一個節點，那么可以想象，當某一集群從環中消失時，它原本所負責的任務將全部交由順時針方向的下一個集群處理。例如，當group0退出時，它原本所負責的緩存將全部交給group1處理。這就意味著group1的訪問壓力會瞬間增大。

設想一下，如果group1因為壓力過大而崩潰，那么更大的壓力又會向group2壓過去，最終服務壓力就像滾雪球一樣越滾越大，最終導致雪崩。

引入虛擬節點

解決上述兩個問題最好的辦法就是擴展整個環上的節點數量，因此我們引入了虛擬節點的概念。一個實際節點將會映射多個虛擬節點，這樣Hash環上的空間分割就會變得均勻。

同時，引入虛擬節點還會使得節點在Hash環上的順序隨機化，這意味著當一個真實節點失效退出后，它原來所承載的壓力將會均勻地分散到其他節點上去。

如下圖：

代碼測試

現在我們嘗試編寫一些測試代碼，來看看一致性hash的實際效果是否符合我們預期。

首先我們需要一個能夠對輸入進行均勻散列的Hash算法，可供選擇的有很多，memcached官方使用了基于md5的KETAMA算法，但這里處于計算效率的考慮，使用了FNV1_32_HASH算法，如下：

public class HashUtil {/*** 計算Hash值, 使用FNV1_32_HASH算法* @param str* @return*/public static int getHash(String str) {final int p = 16777619;int hash = (int)2166136261L;for (int i = 0; i < str.length(); i++) {hash =( hash ^ str.charAt(i) ) * p;}hash += hash << 13;hash ^= hash >> 7;hash += hash << 3;hash ^= hash >> 17;hash += hash << 5;if (hash < 0) {hash = Math.abs(hash);}return hash;} }

實際使用時可以根據需求調整。

接著需要使用一種數據結構來保存hash環，可以采用的方案有很多種，最簡單的是采用數組或鏈表。但這樣查找的時候需要進行排序，如果節點數量多，速度就可能變得很慢。

針對集群負載均衡狀態讀多寫少的狀態，很容易聯想到使用二叉平衡樹的結構去儲存，實際上可以使用TreeMap（內部實現是紅黑樹）來作為Hash環的儲存結構。

先編寫一個最簡單的，無虛擬節點的Hash環測試：? ?

public class ConsistentHashingWithoutVirtualNode {/*** 集群地址列表*/private static String[] groups = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111","192.168.0.3:111", "192.168.0.4:111"};/*** 用于保存Hash環上的節點*/private static SortedMap<Integer, String> sortedMap = new TreeMap<>();/*** 初始化，將所有的服務器加入Hash環中*/static {// 使用紅黑樹實現，插入效率比較差，但是查找效率極高for (String group : groups) {int hash = HashUtil.getHash(group);System.out.println("[" + group + "] launched @ " + hash);sortedMap.put(hash, group);}}/*** 計算對應的widget加載在哪個group上** @param widgetKey* @return*/private static String getServer(String widgetKey) {int hash = HashUtil.getHash(widgetKey);// 只取出所有大于該hash值的部分而不必遍歷整個TreeSortedMap<Integer, String> subMap = sortedMap.tailMap(hash);if (subMap == null || subMap.isEmpty()) {// hash值在最尾部，應該映射到第一個group上return sortedMap.get(sortedMap.firstKey());}return subMap.get(subMap.firstKey());}public static void main(String[] args) {// 生成隨機數進行測試Map<String, Integer> resMap = new HashMap<>();for (int i = 0; i < 100000; i++) {Integer widgetId = (int)(Math.random() * 10000);String server = getServer(widgetId.toString());if (resMap.containsKey(server)) {resMap.put(server, resMap.get(server) + 1);} else {resMap.put(server, 1);}}resMap.forEach((k, v) -> {System.out.println("group " + k + ": " + v + "(" + v/1000.0D +"%)");});} }

生成10000個隨機數字進行測試，最終得到的壓力分布情況如下：

[192.168.0.1:111] launched @ 8518713 [192.168.0.2:111] launched @ 1361847097 [192.168.0.3:111] launched @ 1171828661 [192.168.0.4:111] launched @ 1764547046 group 192.168.0.2:111: 8572(8.572%) group 192.168.0.1:111: 18693(18.693%) group 192.168.0.4:111: 17764(17.764%) group 192.168.0.3:111: 27870(27.87%) group 192.168.0.0:111: 27101(27.101%)

可以看到壓力還是比較不平均的，所以我們繼續，引入虛擬節點：

public class ConsistentHashingWithVirtualNode {/*** 集群地址列表*/private static String[] groups = {"192.168.0.0:111", "192.168.0.1:111", "192.168.0.2:111","192.168.0.3:111", "192.168.0.4:111"};/*** 真實集群列表*/private static List<String> realGroups = new LinkedList<>();/*** 虛擬節點映射關系*/private static SortedMap<Integer, String> virtualNodes = new TreeMap<>();private static final int VIRTUAL_NODE_NUM = 1000;static {// 先添加真實節點列表realGroups.addAll(Arrays.asList(groups));// 將虛擬節點映射到Hash環上for (String realGroup: realGroups) {for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {String virtualNodeName = getVirtualNodeName(realGroup, i);int hash = HashUtil.getHash(virtualNodeName);System.out.println("[" + virtualNodeName + "] launched @ " + hash);virtualNodes.put(hash, virtualNodeName);}}}private static String getVirtualNodeName(String realName, int num) {return realName + "&&VN" + String.valueOf(num);}private static String getRealNodeName(String virtualName) {return virtualName.split("&&")[0];}private static String getServer(String widgetKey) {int hash = HashUtil.getHash(widgetKey);// 只取出所有大于該hash值的部分而不必遍歷整個TreeSortedMap<Integer, String> subMap = virtualNodes.tailMap(hash);String virtualNodeName;if (subMap == null || subMap.isEmpty()) {// hash值在最尾部，應該映射到第一個group上virtualNodeName = virtualNodes.get(virtualNodes.firstKey());}else {virtualNodeName = subMap.get(subMap.firstKey());}return getRealNodeName(virtualNodeName);}public static void main(String[] args) {// 生成隨機數進行測試Map<String, Integer> resMap = new HashMap<>();for (int i = 0; i < 100000; i++) {Integer widgetId = i;String group = getServer(widgetId.toString());if (resMap.containsKey(group)) {resMap.put(group, resMap.get(group) + 1);} else {resMap.put(group, 1);}}resMap.forEach((k, v) -> {System.out.println("group " + k + ": " + v + "(" + v/100000.0D +"%)");});} }

這里真實節點和虛擬節點的映射采用了字符串拼接的方式，這種方式雖然簡單但很有效，memcached官方也是這么實現的。將虛擬節點的數量設置為1000，重新測試壓力分布情況，結果如下：

group 192.168.0.2:111: 18354(18.354%) group 192.168.0.1:111: 20062(20.062%) group 192.168.0.4:111: 20749(20.749%) group 192.168.0.3:111: 20116(20.116%) group 192.168.0.0:111: 20719(20.719%)

可以看到基本已經達到平均分布了，接著繼續測試刪除和增加節點給整個服務帶來的影響，相關測試代碼如下：

private static void refreshHashCircle() {// 當集群變動時，刷新hash環，其余的集群在hash環上的位置不會發生變動virtualNodes.clear();for (String realGroup: realGroups) {for (int i = 0; i < VIRTUAL_NODE_NUM; i++) {String virtualNodeName = getVirtualNodeName(realGroup, i);int hash = HashUtil.getHash(virtualNodeName);System.out.println("[" + virtualNodeName + "] launched @ " + hash);virtualNodes.put(hash, virtualNodeName);}} } private static void addGroup(String identifier) {realGroups.add(identifier);refreshHashCircle(); }private static void removeGroup(String identifier) {int i = 0;for (String group:realGroups) {if (group.equals(identifier)) {realGroups.remove(i);}i++;}refreshHashCircle(); }

測試刪除一個集群前后的壓力分布如下：

running the normal test. group 192.168.0.2:111: 19144(19.144%) group 192.168.0.1:111: 20244(20.244%) group 192.168.0.4:111: 20923(20.923%) group 192.168.0.3:111: 19811(19.811%) group 192.168.0.0:111: 19878(19.878%) removed a group, run test again. group 192.168.0.2:111: 23409(23.409%) group 192.168.0.1:111: 25628(25.628%) group 192.168.0.4:111: 25583(25.583%) group 192.168.0.0:111: 25380(25.38%)

同時計算一下消失的集群上的Key最終如何轉移到其他集群上：

[192.168.0.1:111-192.168.0.4:111] :5255 [192.168.0.1:111-192.168.0.3:111] :5090 [192.168.0.1:111-192.168.0.2:111] :5069 [192.168.0.1:111-192.168.0.0:111] :4938

可見，刪除集群后，該集群上的壓力均勻地分散給了其他集群，最終整個集群仍處于負載均衡狀態，符合我們的預期，最后看一下添加集群的情況。

壓力分布：

running the normal test. group 192.168.0.2:111: 18890(18.89%) group 192.168.0.1:111: 20293(20.293%) group 192.168.0.4:111: 21000(21.0%) group 192.168.0.3:111: 19816(19.816%) group 192.168.0.0:111: 20001(20.001%) add a group, run test again. group 192.168.0.2:111: 15524(15.524%) group 192.168.0.7:111: 16928(16.928%) group 192.168.0.1:111: 16888(16.888%) group 192.168.0.4:111: 16965(16.965%) group 192.168.0.3:111: 16768(16.768%) group 192.168.0.0:111: 16927(16.927%)

壓力轉移：

[192.168.0.0:111-192.168.0.7:111] :3102 [192.168.0.4:111-192.168.0.7:111] :4060 [192.168.0.2:111-192.168.0.7:111] :3313 [192.168.0.1:111-192.168.0.7:111] :3292 [192.168.0.3:111-192.168.0.7:111] :3261

綜上可以得出結論，在引入足夠多的虛擬節點后，一致性hash還是能夠比較完美地滿足負載均衡需要的。

優雅縮擴容

緩存服務器對于性能有著較高的要求，因此我們希望在擴容時新的集群能夠較快的填充好數據并工作。但是從一個集群啟動，到真正加入并可以提供服務之間還存在著不小的時間延遲，要實現更優雅的擴容，我們可以從兩個方面出發：

1.高頻Key預熱

負載均衡器作為路由層，是可以收集并統計每個緩存Key的訪問頻率的，如果能夠維護一份高頻訪問Key的列表，新的集群在啟動時根據這個列表提前拉取對應Key的緩存值進行預熱，便可以大大減少因為新增集群而導致的Key失效。

具體的設計可以通過緩存來實現，如下：

不過這個方案在實際使用時有一個很大的限制，那就是高頻Key本身的緩存失效時間可能很短，預熱時儲存的Value在實際被訪問到時可能已經被更新或者失效，處理不當會導致出現臟數據，因此實現難度還是有一些大的。

2.歷史Hash環保留

回顧一致性Hash的擴容，不難發現新增節點后，它所對應的Key在原來的節點還會保留一段時間。因此在擴容的延遲時間段，如果對應的Key緩存在新節點上還沒有被加載，可以去原有的節點上嘗試讀取。

舉例，假設我們原有3個集群，現在要擴展到6個集群，這就意味著原有50%的Key都會失效（被轉移到新節點上），如果我們維護擴容前和擴容后的兩個Hash環，在擴容后的Hash環上找不到Key的儲存時，先轉向擴容前的Hash環尋找一波，如果能夠找到就返回對應的值并將該緩存寫入新的節點上，找不到時再透過緩存，如下圖：

這樣做的缺點是增加了緩存讀取的時間，但相比于直接擊穿緩存而言還是要好很多的。優點則是可以隨意擴容多臺機器，而不會產生大面積的緩存失效。

談完了擴容，再談談縮容。

1.熔斷機制

縮容后，剩余各個節點上的訪問壓力都會有所增加，此時如果某個節點因為壓力過大而宕機，就可能會引發連鎖反應。因此作為兜底方案，應當給每個集群設立對應熔斷機制來保護服務的穩定性。

2.多集群LB的更新延遲

這個問題在縮容時比較嚴重，如果你使用一個集群來作為負載均衡，并使用一個配置服務器比如ConfigServer來推送集群狀態以構建Hash環，那么在某個集群退出時這個狀態并不一定會被立刻同步到所有的LB上，這就可能會導致一個暫時的調度不一致，如下圖：

如果某臺LB錯誤地將請求打到了已經退出的集群上，就會導致緩存擊穿。解決這個問題主要有以下幾種思路：

- 緩慢縮容，等到Hash環完全同步后再操作。可以通過監聽退出集群的訪問QPS來實現這一點，等到該集群幾乎沒有QPS時再將其撤下。

- 手動刪除，如果Hash環上對應的節點找不到了，就手動將其從Hash環上刪除，然后重新進行調度，這個方式有一定的風險，對于網絡抖動等異常情況兼容的不是很好。

- 主動拉取和重試，當Hash環上節點失效時，主動從ZK上重新拉取集群狀態來構建新Hash環，在一定次數內可以進行多次重試。

對比：HashSlot

了解了一致性Hash算法的特點后，我們也不難發現一些不盡人意的地方：

• 整個分布式緩存需要一個路由服務來做負載均衡，存在單點問題（如果路由服務掛了，整個緩存也就涼了）

• Hash環上的節點非常多或者更新頻繁時，查找性能會比較低下

針對這些問題，Redis在實現自己的分布式集群方案時，設計了全新的思路：基于P2P結構的HashSlot算法，下面簡單介紹一下：

1.使用HashSlot

類似于Hash環，Redis Cluster采用HashSlot來實現Key值的均勻分布和實例的增刪管理。

首先默認分配了16384個Slot（這個大小正好可以使用2kb的空間保存），每個Slot相當于一致性Hash環上的一個節點。接入集群的所有實例將均勻地占有這些Slot，而最終當我們Set一個Key時，使用CRC16(Key) % 16384來計算出這個Key屬于哪個Slot，并最終映射到對應的實例上去。

那么當增刪實例時，Slot和實例間的對應要如何進行對應的改動呢？

舉個例子，原本有3個節點A,B,C，那么一開始創建集群時Slot的覆蓋情況是：? ?

節點A 0－5460節點B 5461－10922節點C 10923－16383

現在假設要增加一個節點D，RedisCluster的做法是將之前每臺機器上的一部分Slot移動到D上（注意這個過程也意味著要對節點D寫入的KV儲存），成功接入后Slot的覆蓋情況將變為如下情況：

節點A 1365-5460節點B 6827-10922節點C 12288-16383節點D 0-1364,5461-6826,10923-1228

同理刪除一個節點，就是將其原來占有的Slot以及對應的KV儲存均勻地歸還給其他節點。

2.P2P節點尋找

現在我們考慮如何實現去中心化的訪問，也就是說無論訪問集群中的哪個節點，你都能夠拿到想要的數據。其實這有點類似于路由器的路由表，具體說來就是：

* 每個節點都保存有完整的HashSlot - 節點映射表，也就是說，每個節點都知道自己擁有哪些Slot，以及某個確定的Slot究竟對應著哪個節點。

* 無論向哪個節點發出尋找Key的請求，該節點都會通過CRC(Key) % 16384計算該Key究竟存在于哪個Slot，并將請求轉發至該Slot所在的節點。

總結一下就是兩個要點：映射表和內部轉發，這是通過著名的**Gossip協議**來實現的。

最后我們可以給出Redis Cluster的系統結構圖，和一致性Hash環還是有著很明顯的區別的：

對比一下，HashSlot + P2P的方案解決了去中心化的問題，同時也提供了更好的動態擴展性。但相比于一致性Hash而言，其結構更加復雜，實現上也更加困難。

而在之前的分析中我們也能看出，一致性Hash方案整體上還是有著不錯的表現的，因此在實際的系統應用中，可以根據開發成本和性能要求合理地選擇最適合的方案。總之，兩者都非常優秀，至于用哪個、怎么用，就是仁者見仁智者見智的問題了。

最后，再附上我歷時三個月總結的?Java 面試 + Java 后端技術學習指南，筆者這幾年及春招的總結，github 1.1k star，拿去不謝！下載方式1.?首先掃描下方二維碼 2.?后臺回復「Java面試」即可獲取

總結

以上是生活随笔為你收集整理的一致性 Hash 在负载均衡中的应用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。