java-memcachedrelease-2.6.3通過ConsistentHashing算法實(shí)現(xiàn)分布式的原理分析點(diǎn)滴

1、java_memcached-release_2.6.3通過ConsistentHashing算法實(shí)現(xiàn)分布式的原理分析點(diǎn)滴yinhongzhan-一個(gè)寫代碼的今天在封裝java_memcached_2.6.3版本的客戶端時(shí)候碰到了一個(gè)問題,所以研究了下它的ConsistentHashing根據(jù)key值生成散列服務(wù)器地址的原理.先說下ConsistentHashing,memcached的服務(wù)端程序是集中式并不支持分布式的,所以分布式的實(shí)現(xiàn)就要靠客戶端去實(shí)現(xiàn)了.ConsistentHashing算法就是一種比較好的實(shí)現(xiàn)方式,它不僅實(shí)現(xiàn)了分布式的效果，還能極大的減小擴(kuò)展memcached服務(wù)節(jié)點(diǎn)的

2、時(shí)候?qū)φ麄€(gè)緩存系統(tǒng)的影響.這邊簡單的說下它的原理,根據(jù)個(gè)人的理解就是:根據(jù)某個(gè)散列函數(shù)算出各個(gè)服務(wù)器的哈希值，將它們分配映射到一個(gè)0232的一個(gè)圓上.其后你在操作緩存數(shù)據(jù)的時(shí)候的key根據(jù)同樣的散列函數(shù)（不是必須）算出在圓上的哈希值,再按順時(shí)針的方向找到第一個(gè)服務(wù)器，就將這個(gè)key的值緩存到該服務(wù)器上,如果沒找到就存放到圓環(huán)的第一個(gè)節(jié)點(diǎn)上這大致就是ConsistentHashing的原理.至于為什么會減小緩存服務(wù)器的增減操作帶來的整個(gè)系統(tǒng)緩存的影響,大家可以想象一下在這個(gè)圓上你加入一個(gè)服務(wù)器節(jié)點(diǎn)那么他只會將這個(gè)節(jié)點(diǎn)逆時(shí)針方向到逆時(shí)針方向的第一個(gè)服務(wù)器節(jié)點(diǎn)之間的散列值其他都不會影響到,刪除一個(gè)節(jié)

3、點(diǎn)也是.java_memcached客戶端為了更好地將key值均勻的分配到各個(gè)服務(wù)器上,引入了一個(gè)虛擬節(jié)點(diǎn)的概念,這個(gè)具體的實(shí)現(xiàn)等會在下面分析源碼的時(shí)候會列出.好讓我們開始源碼之旅吧（下面的貼出的部分代碼是經(jīng)過我簡化的并不是全部的源碼）:根據(jù)原理首先要講服務(wù)器的hash值算出并散列到圓環(huán)上的方法這邊我要說下就是服務(wù)器對應(yīng)的HASH值是存放在一個(gè)TreeMap（這里就不介紹它了）中的javaprivateTreeMapconsistentBuckets;/javajava/初始化存放服務(wù)器的節(jié)點(diǎn)結(jié)構(gòu)privatevoidpopulateConsistentBuckets()this.consis

4、tentBuckets=newTreeMap();/初始化TreeMapMessageDigestmd5=MD5.get();this.totalWeight=this.servers.length;/簡單的處理下權(quán)重都分配為1for(inti=0;iservers.length;i+)intthisWeight=1;doublefactor=Math.floor(double)(40*this.servers.length*thisWeight)/(double)this.totalWeight);for(longj=0;jfactor;j+)/大家可以看到這邊他對同一個(gè)服務(wù)器進(jìn)行了多次散列

5、,這就是虛擬節(jié)點(diǎn)byted=md5.digest(serversi+-+j).getBytes();for(inth=0;h4;h+)/散列函數(shù),求出散列值Longk=(long)(d3+h*4&0 xFF)24)|(long)(d2+h*4&0 xFF)16)|(long)(d1+h*4&0 xFF)8)|(long)(d0+h*4&0 xFF);consistentBuckets.put(k,serversi);/java大家注意下上面的虛擬節(jié)點(diǎn)實(shí)現(xiàn)和散列函數(shù),在完成對服務(wù)器的映射后我們再來看下它是如何根據(jù)key值來生成需要散列到哪個(gè)服務(wù)器的地址的.在源碼中g(shù)etSock方法是負(fù)責(zé)尋找散列

6、到哪個(gè)服務(wù)器的地址的,我這邊簡化下，代碼如下：javapublicvoidgetSock(Stringkey,IntegerhashCode)根據(jù)getBucket方法找到存儲的剛才TreeMap的key(就是找到哪個(gè)桶)longbucket=getBucket(key,hashCode);再根據(jù)這個(gè)key找到所要散列到的服務(wù)器的地址Stringserver=consistentBuckets.get(bucket);System.out.println(server);/java大家可以看到該方法中主要是調(diào)用了getBucket方法來找生成key的散列值的,下面就看下getBucket方法:

7、javaprivatelonggetBucket(Stringkey,IntegerhashCode)/大家看到這邊它又通過getHash方法來得到散列值longhc=getHash(key,hashCode);/這個(gè)方法主要是實(shí)現(xiàn)上面原理所說的如果順時(shí)針尋找,找不到就將服務(wù)器的第一個(gè)節(jié)點(diǎn)放入其中returnfindPointFor(hc);privatelonggetHash(Stringkey,IntegerhashCode)/此方法主要通過2種方式獲得散列值if(hashCode!=null)returnhashCode.longValue()&0 xffffffffL;elseretu

8、rnmd5HashingAlg(key);privatestaticlongmd5HashingAlg(Stringkey)/這邊的散列函數(shù)大家可以和前面的生成服務(wù)器的散列函數(shù)對照一下可以看到是一樣的MessageDigestmd5=MD5.get();md5.reset();md5.update(key.getBytes();bytebKey=md5.digest();longres=(long)(bKey3&0 xFF)24)|(long)(bKey2&0 xFF)16)|(long)(bKey1&0 xFF)8)|(long)(bKey0&0 xFF);returnres;privateLongfindPointFor(Longhv)/thisworksinjava6,butstillwanttoreleasesupportforjava5/Longk=this.consistentBuckets.ceilingKey(hv);/return(k=null)?this.consistentBuckets.firstKey():k;SortedMaptmap=this.consistentBuckets.ta