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

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

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

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

1、Consistent Hashing算法描述

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

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

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

Consistent Hashing原理示意圖

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

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

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

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

虛擬節(jié)點(diǎn)對(duì)Consistent Hashing結(jié)果的影響

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

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

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

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);  
 }  
 
}