這篇文章給大家分享的是有關(guān)如何實現(xiàn)Consistent Hashing算法的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

宣恩網(wǎng)站建設(shè)公司成都創(chuàng)新互聯(lián)公司,宣恩網(wǎng)站設(shè)計制作，有大型網(wǎng)站制作公司豐富經(jīng)驗。已為宣恩上千多家提供企業(yè)網(wǎng)站建設(shè)服務(wù)。企業(yè)網(wǎng)站搭建\外貿(mào)網(wǎng)站建設(shè)要多少錢，請找那個售后服務(wù)好的宣恩做網(wǎng)站的公司定做！

在做服務(wù)器負載均衡時候可供選擇的負載均衡的算法有很多，包括： 輪循算法(Round Robin)、哈希算法(HASH)、最少連接算法(Least Connection)、響應(yīng)速度算法(Response Time)、加權(quán)法(Weighted )等。其中哈希算法是最為常用的算法.

典型的應(yīng)用場景是： 有N臺服務(wù)器提供緩存服務(wù)，需要對服務(wù)器進行負載均衡，將請求平均分發(fā)到每臺服務(wù)器上，每臺機器負責(zé)1/N的服務(wù)。

常用的算法是對hash結(jié)果取余數(shù) (hash() mod N )：對機器編號從0到N-1，按照自定義的 hash()算法，對每個請求的hash()值按N取模，得到余數(shù)i，然后將請求分發(fā)到編號為i的機器。但這樣的算法方法存在致命問題，如果某一臺機器宕機，那么應(yīng)該落在該機器的請求就無法得到正確的處理，這時需要將當(dāng)?shù)舻姆?wù)器從算法從去除，此時候會有(N-1)/N的服務(wù)器的緩存數(shù)據(jù)需要重新進行計算;如果新增一臺機器，會有N /(N+1)的服務(wù)器的緩存數(shù)據(jù)需要進行重新計算。對于系統(tǒng)而言，這通常是不可接受的顛簸(因為這意味著大量緩存的失效或者數(shù)據(jù)需要轉(zhuǎn)移)。那么，如何設(shè)計一個負載均衡策略，使得受到影響的請求盡可能的少呢?

在Memcached、Key-Value Store 、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以說Consistent Hashing 是分布式系統(tǒng)負載均衡的***算法。

1、Consistent Hashing算法描述

下面以Memcached中的Consisten Hashing算法為例說明(參考memcached的分布式算法 )。

由于hash算法結(jié)果一般為unsigned int型，因此對于hash函數(shù)的結(jié)果應(yīng)該均勻分布在[0,232 -1]間，如果我們把一個圓環(huán)用232 個點來進行均勻切割，首先按照hash(key)函數(shù)算出服務(wù)器(節(jié)點)的哈希值， 并將其分布到0～232 的圓上。

用同樣的hash(key)函數(shù)求出需要存儲數(shù)據(jù)的鍵的哈希值，并映射到圓上。然后從數(shù)據(jù)映射到的位置開始順時針查找，將數(shù)據(jù)保存到找到的***個服務(wù)器(節(jié)點)上。

Consistent Hashing原理示意圖

1. 新增一個節(jié)點：只有在圓環(huán)上新增節(jié)點到逆時針方向的***個節(jié)點之間的數(shù)據(jù)會受到影響(增加節(jié)點順時針的***個節(jié)點的信息需要遷移到增加節(jié)點上)。

2. 刪除一個節(jié)點：只有在圓環(huán)上原來刪除節(jié)點到 逆時針 方向的***個節(jié)點之間的數(shù)據(jù)會受到影響(刪除節(jié)點的信息需要遷移到順時針的***個節(jié)點上) ，因此通過Consistent Hashing很好地解決了負載均衡中由于新增節(jié)點、刪除節(jié)點引起的hash值顛簸問題。

Consistent Hashing添加服務(wù)器示意圖

虛擬節(jié)點(virtual nodes)： 之所以要引進虛擬節(jié)點是因為在服務(wù)器(節(jié)點)數(shù)較少的情況下(例如只有3臺服務(wù)器)，通過hash(key)算出節(jié)點的哈希值在圓環(huán)上并不是均勻分布的(稀疏的)，仍然會出現(xiàn)各節(jié)點負載不均衡的問題。虛擬節(jié)點可以認(rèn)為是實際節(jié)點的復(fù)制品(replicas)，本質(zhì)上與實際節(jié)點實際上是一樣的(key并不相同)。引入虛擬節(jié)點后，通過將每個實際的服務(wù)器(節(jié)點)數(shù)按照一定的比例(例如200倍)擴大后并計算其hash(key)值以均勻分布到圓環(huán)上。在進行負載均衡時候，落到虛擬節(jié)點的哈希值實際就落到了實際的節(jié)點上。由于所有的實際節(jié)點是按照相同的比例復(fù)制成虛擬節(jié)點的，因此解決了節(jié)點數(shù)較少的情況下哈希值在圓環(huán)上均勻分布的問題。

虛擬節(jié)點對Consistent Hashing結(jié)果的影響

從上圖可以看出，在節(jié)點數(shù)為10個的情況下，每個實際節(jié)點的虛擬節(jié)點數(shù)為實際節(jié)點的100-200倍的時候，結(jié)果還是很均衡的。

2、Consistent Hashing算法實現(xiàn)：

文章Consistent Hashing 中描述了Consistent Hashing的Java實現(xiàn)，很簡潔。

import java.util.Collection;  import java.util.SortedMap;  import java.util.TreeMap;   public class ConsistentHash {    private final HashFunction hashFunction;   private final int numberOfReplicas;   private final SortedMap circle = new TreeMap();    public ConsistentHash(HashFunction hashFunction, int numberOfReplicas,       Collection 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 tailMap = circle.tailMap(hash);       hash = tailMap.isEmpty() ? circle.firstKey() : tailMap.firstKey();     }     return circle.get(hash);   }   }

感謝各位的閱讀！關(guān)于“如何實現(xiàn)Consistent Hashing算法”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！