原文
有關(guān)一致性哈希算法原理及其應用討論的文章已經(jīng)足夠多财松,如果對一致性哈希算法一點概念都沒有的同學可以先參考這篇文章:一致性哈希瘪贱。
相對來說纱控,一致性哈希算法的原理還是比較容易理解的,但在日常開發(fā)過程中發(fā)現(xiàn)雖然大部分同事對一致性哈希算法的原理有個大概的認識菜秦,然而能知道該算法具體實現(xiàn)的人卻寥寥無幾甜害。當然一致性哈希算法的實現(xiàn)不同語言有不同的實現(xiàn)方式,其中較為有名的一種實現(xiàn)叫Ketama算法球昨,該算法最初是由Last.fm的程序員實現(xiàn)的并得到了廣泛的應用尔店,一些開源框架譬如spymemcached,twemproxy等都內(nèi)置了該算法的實現(xiàn)主慰。
本文主要從spymemcached的源碼出發(fā)嚣州,分析Ketama算法的具體實現(xiàn)。
在類KetamaNodeLocator.java里有個setKetamaNodes()方法負責一致性哈希環(huán)的初始化工作共螺, 代碼如下:
protected void setKetamaNodes(List<MemcachedNode> nodes) {
TreeMap<Long, MemcachedNode> newNodeMap = new TreeMap<Long, MemcachedNode>();
int numReps = config.getNodeRepetitions();
for (MemcachedNode node : nodes) {
// Ketama does some special work with md5 where it reuses chunks.
if (hashAlg == DefaultHashAlgorithm.KETAMA_HASH) {
for (int i = 0; i < numReps / 4; i++) {
byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));
for (int h = 0; h < 4; h++) {
Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
| ((long) (digest[2 + h * 4] & 0xFF) << 16)
| ((long) (digest[1 + h * 4] & 0xFF) << 8)
| (digest[h * 4] & 0xFF);
newNodeMap.put(k, node);
getLogger().debug("Adding node %s in position %d", node, k);
}
}
} else {
for (int i = 0; i < numReps; i++) {
newNodeMap.put(hashAlg.hash(config.getKeyForNode(node, i)), node);
}
}
}
assert newNodeMap.size() == numReps * nodes.size();
ketamaNodes = newNodeMap;
}
下面我們來具體分析下setKetamaNodes函數(shù)的實現(xiàn)该肴,首先MemcachedNode這個類對Memcached節(jié)點的網(wǎng)絡連接參數(shù)及方法進行了封裝。TreeMap在這里用于模擬一致性哈希環(huán)的環(huán)狀結(jié)構(gòu)璃谨。
int numReps = config.getNodeRepetitions();
getNodeRepetitions()方法負責讀取配置信息沙庐,返回一個真實的Memcached節(jié)點對應的虛擬節(jié)點數(shù),默認情況下返回160佳吞,也就是說一個Memcached節(jié)點在一致性哈希環(huán)上對應有160個虛擬節(jié)點拱雏。
config.getKeyForNode(node, i)
getKeyForNode()根據(jù)傳進去的MemcacheNode對象和變量i生成key值,返回值示例:“127.0.0.1:11311-0”
computeMd5()根據(jù)key生成16位的MD5摘要底扳, 因此digest數(shù)組共16位:
byte[] digest = DefaultHashAlgorithm.computeMd5(config.getKeyForNode(node, i));
將digest數(shù)組按每四位一組铸抑,通過位操作產(chǎn)生一個最大32位的長整數(shù)。之所以是32位是因為一致性哈希環(huán)取值范圍為0~2^32; 回到上面的例子衷模,對于一個Memcached節(jié)點譬如“127.0.0.1:11311”, 將通過for循環(huán)產(chǎn)生“127.0.0.1:11311-0”鹊汛,“127.0.0.1:11311-1”... “127.0.0.1:11311-39”共40個副本,對于每個副本譬如“127.0.0.1:11311-0”, 將會產(chǎn)生4個長整數(shù)阱冶,對應一致性哈希環(huán)上的4個位置刁憋,所以默認配置的情況下,一個Memcached節(jié)點將在一致性哈希環(huán)上占據(jù)4×40=160個位置木蹬。
Long k = ((long) (digest[3 + h * 4] & 0xFF) << 24)
| ((long) (digest[2 + h * 4] & 0xFF) << 16)
| ((long) (digest[1 + h * 4] & 0xFF) << 8)
| (digest[h * 4] & 0xFF);
以k為key將MemcacheNode對象放到TreeMap里:
newNodeMap.put(k, node);
由于TreeMap中的value是按Key排序的至耻,因此可以通過TreeMap來模擬一致性哈希的環(huán)狀結(jié)構(gòu),k值小的排在前镊叁,k值大的排在后尘颓。
以上就是一致性哈希環(huán)初始化過程的的基本分析,下面我們來看看查詢的過程晦譬, getPrimary()函數(shù)傳入一個key疤苹,譬如"123", 先計算出該key的哈希值。
public MemcachedNode getPrimary(final String k) {
MemcachedNode rv = getNodeForKey(hashAlg.hash(k));
assert rv != null : "Found no node for key " + k;
return rv;
}
MemcachedNode getNodeForKey(long hash) {
final MemcachedNode rv;
if (!ketamaNodes.containsKey(hash)) {
// Java 1.6 adds a ceilingKey method, but I'm still stuck in 1.5
// in a lot of places, so I'm doing this myself.
SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
if (tailMap.isEmpty()) {
hash = getKetamaNodes().firstKey();
} else {
hash = tailMap.firstKey();
}
}
rv = getKetamaNodes().get(hash);
return rv;
}
重點在于下面這句, TreeMap的tailMap()方法會返回一個SortedMap對象tailMap, tailMap中包含的所有key值都比傳參hash大敛腌,這個操作相當于給定一個hash值卧土,從一致性哈希環(huán)中按順時針順序查找節(jié)點惫皱,直到查找到第一個key值比傳參hash大的節(jié)點,該節(jié)點就是該hash值所對應的Memcached節(jié)點尤莺。
SortedMap<Long, MemcachedNode> tailMap = getKetamaNodes().tailMap(hash);
以上就是對Sypmencached源碼中Ketama算法的實現(xiàn)分析逸吵。