第Java實現(xiàn)一致性Hash算法詳情目錄1.實現(xiàn)原理2.解決數(shù)據(jù)傾斜的問題2.1什么是數(shù)據(jù)傾斜？2.2解決3.代碼實現(xiàn)3.1ConsistentHash3.2Hash3.3Utils3.4main

1.實現(xiàn)原理

將key映射到2^32-1的空間中，將這個數(shù)字的首尾相連，形成一個環(huán)

計算節(jié)點（使用節(jié)點名稱、編號、IP地址）的hash值，放置在環(huán)上計算key的hash值，放置在環(huán)上，順時針尋找到的第一個節(jié)點，就是應選取的節(jié)點

例如：p2、p4、p6三個節(jié)點，key11、key2、key27按照順序映射到p2、p4、p6上面，假設新增一個節(jié)點p8在p6節(jié)點之后，這個時候只需要將key27從p6調整到p8就可以了；也就是說，每次新增刪除節(jié)點時，只需要重新定位該節(jié)點附近的一小部分數(shù)據(jù)

2.解決數(shù)據(jù)傾斜的問題

2.1什么是數(shù)據(jù)傾斜？

如果服務器的節(jié)點過少，容易引起key的傾斜。例如上面的例子中p2、p4、p6分布在環(huán)的上半部分，下半部分是空的。那么映射到下半部分的key都會被分配給p2，key過度傾斜到了p2緩存間節(jié)點負載不均衡。

2.2解決

為了解決這個問題，引入了虛擬節(jié)點的概念，一個真實的節(jié)點對應多個虛擬的節(jié)點，假設1個真實的節(jié)點對應3個虛擬節(jié)點，那么p1對應的就是p1-1、p1-2、p1-3

計算虛擬節(jié)點的Hash值，放置在環(huán)上計算key的Hash值，在環(huán)上順時針尋找到對應選取的虛擬節(jié)點，例如：p2-1，對應真實的節(jié)點p2

虛擬節(jié)點擴充了節(jié)點的數(shù)量，解決了節(jié)點較少的情況下數(shù)據(jù)傾斜的問題，而且代價非常小，只需要新增一個字典（Map）維護真實的節(jié)點與虛擬節(jié)點的映射關系就可以了

3.代碼實現(xiàn)

3.1ConsistentHash

這里使用了泛型的方式來保存數(shù)據(jù)，可以根據(jù)不同的類型，獲取到不同的節(jié)點存儲

publicclassConsistentHashT{

//自定義hash方法

privateHashObjecthashMethod;

//創(chuàng)建hash映射，虛擬節(jié)點映射真實節(jié)點

privatefinalMapInteger,ThashMap=newConcurrentHashMap();

//將所有的hash保存起來

privateListIntegerkeys=newArrayList();

//默認虛擬節(jié)點數(shù)量

privatefinalintreplicas;

publicConsistentHash(){

this(3,Utils::rehash);

publicConsistentHash(intreplicas,HashObjecthashMethod){

this.replicas=replicas;

this.hashMethod=hashMethod;

@SafeVarargs

publicfinalvoidadd(T...keys){

for(Tkey:keys){

//根據(jù)虛擬節(jié)點個數(shù)來計算虛擬節(jié)點

for(inti=0;ithis.replicas;i++){

//根據(jù)函數(shù)獲取到對應的hash值

inthash=this.hashMethod.hash(i+":"+key.toString());

this.keys.add(hash);

this.hashMap.put(hash,key);

//排序，因為是一個環(huán)狀結構

Collections.sort(this.keys);

*根據(jù)對應的key來獲取到節(jié)點信息

*@paramkey

*@return

publicTget(Objectkey){

Objects.requireNonNull(key,"key不能為空");

inthash=this.hashMethod.hash(key);

//獲取到對應的節(jié)點信息

intidx=Utils.search(this.keys.size(),h-this.keys.get(h)=hash);

//如果idx==this.keys.size()，就代表需要取this.keys.get(0);因為是環(huán)狀，所以需要使用%來進行處理

returnthis.hashMap.get(this.keys.get(idx%this.keys.size()));

}

3.2Hash

這里定義了一個函數(shù)結構，用于自定計算hash值

@FunctionalInterface

publicstaticinterfaceHashT{

*計算hash值

*@paramt

*@returnint類型

inthash(Tt);

}

3.3Utils

由于hashcode采用的int類型進行存儲，那么就需要考慮，hash是否超過了int最大存儲，如果超過了那么存儲的數(shù)字就是負數(shù)，會對獲取節(jié)點造成影響，所以這里在取hash值時，采用了hashmap中獲取到hashcode之后對其進行與操作，可以減少hash沖突，也可以避免負數(shù)的產生

publicstaticclassUtils{

//int類型的最大數(shù)據(jù)

staticfinalintHASH_BITS=0x7fffffff;

*通過二分查找法，定義數(shù)組索引位置

*@paramlen

*@paramf

*@return

publicstaticintsearch(intlen,FunctionInteger,Booleanf){

inti=0,j=len;

//通過二分查找發(fā)來定為索引位置

while(ij){

//長度除于2

inth=(i+j)1;

//調用函數(shù)，判斷當前的索引值是否大于

if(f.apply(h)){

//向低半段進行遍歷

j=h;

}else{

//向高半段進行遍歷

i=h+1;

returni;

*將返回的hash能夠平均的計算在int類型之間

*@paramo

*@return

publicstaticintrehash(Objecto){

inth=o.hashCode();

return(h^(h16))HASH_BITS;

}

3.4main

下面是main方法進行測試，在后面新增了一個節(jié)點之后，只會調整zs數(shù)據(jù)到109節(jié)點，而且其他兩個key的獲取不會受到影響

publicstaticvoidmain(String[]args){

ConsistentHashStringconsistentHash=newConsistentHash();

consistentHash.add("192.168.2.106","192.168.2.107","192.168.2.108");

MapString,Objectmap=newHashMap();

map.put("zs","192.168.2.108");

map.put("999999","192.168.2.106");

map.put("233333","192.168.2.106");

map.forEach((k,v)-{

Stringnode=consistentHash.get(k);

if(!v.equals(node)){

thrownewIllegalArgumentException("節(jié)點獲取錯誤，key："+k+"，獲取到的節(jié)點值為："+node);

consistentHash.add("192.168.2.109");

map.put("zs","192.