一、簡介
二、傳統hash演算法的問題
在快取場景，以結點取模為例，假設有5個快取結點，即資料存入及讀取分佈這5個結點上，請求hash值為x，那麼請求對應的結點為：x%5=(0,1,2,3,4)。
當新增1個結點 此時結點個數變為6，那麼請求hash值對應的結點變為x%6=(0,1,2,3,4,5)，以前hash值為5對應結點0，現在是hash值為6才對應結點0，其它hash值對應的結點類似，對應的相關操作如資料存入及讀取，都會發生改變，結點上的資料也隨著都會發生改變。影響太大。
三、一致性hash演算法特點
一致性hash演算法擁有均衡性（balance）、單調性（monotonicity）、分散性（spread）、負載（load）這些特點。最終表現，即是當有結點加入或刪除時，除少數結點外，大多數結點的對映關係不會改變，且新增結點時，請求要麼到新結點，要麼到原結點，而不會到其它舊結點，刪除時，請求到其它結點，只是刪除結點對應的原請求對映關係改變，其它結點對應的請求對映關係不會改變 。
均衡性（balance） 均衡性是指hash結果儘可能均衡分散在所有結點中。
單調性（monotonicity） 單調性是指某hash值一旦對映到某結點，當有新結點加入時，該hash值要麼對映到原結點，要麼對映到新加的結點，而不會對映到其它舊結點。
分散性（spread） 分散性是指分散式場景中，不同終端可能見不到所有所有輸出結點，進而相同hash值對映的結點可能不同。這需要避免。
負載（load) 負載是從另一角度看分散性，指同一輸出結點，不能被不同終端儲存不同的內容。
四、一致性hash演算法設計
一致性hash演算法設計，是將請求和輸出結點都對映到抽象的hash環上，結點查詢時，請求hash值在抽象hash環上，按順時針查詢結點，遇到的第一個結點即為輸出結點。
hash環 這是抽象的環，請求和結點按指的hash演算法，都對映到hash環上。
虛擬結點 為了更均衡地將請求對映到所有結點，可以將結點虛擬為多個虛擬結點，這樣各個結點在hash環上分佈的更均衡，相應的處理請求也更均衡。
五、一致性hash演算法的java實現
這裡使用java來實現一致性hash演算法，使用TreeMap作為hash環的資料結構，使用MurmurHash作為hash演算法（藉助guava27.1-jre的jar包），具體請參考程式碼註釋。
import com.google.common.collect.Lists;
import com.google.common.hash.HashCode;
import com.google.common.hash.HashFunction;
import com.google.common.hash.Hashing;
import java.nio.charset.Charset;
import java.util.List;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.stream.Stream;
public class ConsistentHashAlgMain {
public static void main(String[] args) {
/ 環境模擬 /
//模擬物理機器結點
List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");
//模擬請求
List<String> reqs = Lists.newArrayList("request one", "request two", "request three", "request four", "request five");
//生成抽象的hash環（使用TreeMap作為hash環的資料結構）
TreeMap<String, String> serverRing = new TreeMap<>();
//指定hash演算法為murmur
HashFunction hf = Hashing.murmur3_128();
/ 輔助方法 /
//生成hash值方法
Function<String, HashCode> hash = t -> hf.hashString(t, Charset.forName("utf8"));
//生成虛擬結點字尾列表的方法
List<Integer> virNum = Stream.iterate(1, n -> n + 1).limit(100).collect(Collectors.toList());
//單臺物理機器生成虛擬機器器結點列表的方法
Function<String, List<String>> buildVirServer = s -> virNum.stream().map(t -> s + "#" + t).collect(Collectors.toList());
//新增一臺物理機器方法
Consumer<String> addServer = t -> {
//獲取物理機對應的虛擬機器器列表
List<String> virServers = buildVirServer.apply(t);
//將虛擬機器器列表加入到hash環中
virServers.forEach(v -> {
//獲取虛擬機器器的hash值
HashCode h = hash.apply(v);
//將虛擬機器器加入到hash環中
serverRing.put(h.toString(), t);
});
};
Consumer<String> delServer = t -> {
//獲取物理機對應的虛擬機器器列表
List<String> virServers = buildVirServer.apply(t);
virServers.forEach(v -> {
//獲取虛擬機器器的hash值
HashCode h = hash.apply(v);
serverRing.remove(h.toString());
});
};
//初始化物理機器（每臺物理機器會先生成多臺虛擬機器器列表）到hash環方法
Consumer<List<String>> initServerRing = list -> {
list.forEach(t -> addServer.accept(t));
};
/ 請求處理方法 /
//處理請求方法
Function<String, String> ringHashHost = t -> {
//獲取請求的hash值
HashCode h = hash.apply(t);
//查詢請求hash值後對應的剩餘hash環機器
SortedMap<String, String> tailRing = serverRing.tailMap(h.toString());
//獲取請求hash值後找到的第一臺機器的key
String idx = tailRing.size() < 1 ? serverRing.firstKey() : tailRing.firstKey();
//獲取請求hash值後找到的第一臺機器
String s = serverRing.get(idx);
System.out.println(t + " : " + s);
return s;
};
//批次處理請求方法
Consumer<List<String>> handleReqs = list -> {
list.forEach(t -> ringHashHost.apply(t));
};
/ 測試 /
//初始化hash環
initServerRing.accept(servers);
//處理請求
handleReqs.accept(reqs);
//新增新機器並處理請求
System.out.println("###### add server #####");
addServer.accept("192.168.0.6");
handleReqs.accept(reqs);
System.out.println("###### del server #####");
delServer.accept("192.168.0.4");
handleReqs.accept(reqs);
}
}
結果輸出：
request one : 192.168.0.5
request two : 192.168.0.5
request three : 192.168.0.3
request four : 192.168.0.4
request five : 192.168.0.1
\###### add server #####
request one : 192.168.0.5
request two : 192.168.0.5
request three : 192.168.0.6
request four : 192.168.0.4
request five : 192.168.0.1
\###### del server #####
request one : 192.168.0.5
request two : 192.168.0.5
request three : 192.168.0.6
request four : 192.168.0.1
request five : 192.168.0.1
六、一致性hash演算法的簡單實現
另外也可以藉助google的guava包提供的一致性hash演算法的基本實現，直接使用，其關鍵使用程式碼（在此不詳解）如下：
//所有結點
List<String> servers = Lists.newArrayList("192.168.0.1", "192.168.0.2", "192.168.0.3", "192.168.0.4", "192.168.0.5");
//請求對映到結點
int idx = Hashing.consistentHash(Hashing.sha256().hashString("request one", Charset.forName("utf-8")), servers.size());