一致性哈希算法之Ketama算法

原文

有關(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)分析逸吵。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌逃糟,老刑警劉巖,帶你破解...
    沈念sama閱讀 217,542評論 6 504
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件韩脑,死亡現(xiàn)場離奇詭異,居然都是意外死亡粹污,警方通過查閱死者的電腦和手機段多,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,822評論 3 394
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來壮吩,“玉大人进苍,你說我怎么就攤上這事⊙夹穑” “怎么了觉啊?”我有些...
    開封第一講書人閱讀 163,912評論 0 354
  • 文/不壞的土叔 我叫張陵,是天一觀的道長沈贝。 經(jīng)常有香客問我杠人,道長,這世上最難降的妖魔是什么宋下? 我笑而不...
    開封第一講書人閱讀 58,449評論 1 293
  • 正文 為了忘掉前任嗡善,我火速辦了婚禮,結(jié)果婚禮上学歧,老公的妹妹穿的比我還像新娘罩引。我一直安慰自己,他們只是感情好枝笨,可當我...
    茶點故事閱讀 67,500評論 6 392
  • 文/花漫 我一把揭開白布袁铐。 她就那樣靜靜地躺著,像睡著了一般伺帘。 火紅的嫁衣襯著肌膚如雪昭躺。 梳的紋絲不亂的頭發(fā)上忌锯,一...
    開封第一講書人閱讀 51,370評論 1 302
  • 那天伪嫁,我揣著相機與錄音,去河邊找鬼偶垮。 笑死张咳,一個胖子當著我的面吹牛帝洪,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播脚猾,決...
    沈念sama閱讀 40,193評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼葱峡,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了龙助?” 一聲冷哼從身側(cè)響起砰奕,我...
    開封第一講書人閱讀 39,074評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎提鸟,沒想到半個月后军援,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,505評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡称勋,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,722評論 3 335
  • 正文 我和宋清朗相戀三年胸哥,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片赡鲜。...
    茶點故事閱讀 39,841評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡空厌,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出银酬,到底是詐尸還是另有隱情嘲更,我是刑警寧澤,帶...
    沈念sama閱讀 35,569評論 5 345
  • 正文 年R本政府宣布揩瞪,位于F島的核電站哮内,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏壮韭。R本人自食惡果不足惜北发,卻給世界環(huán)境...
    茶點故事閱讀 41,168評論 3 328
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望喷屋。 院中可真熱鬧琳拨,春花似錦、人聲如沸屯曹。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,783評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽恶耽。三九已至密任,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間偷俭,已是汗流浹背浪讳。 一陣腳步聲響...
    開封第一講書人閱讀 32,918評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留涌萤,地道東北人淹遵。 一個月前我還...
    沈念sama閱讀 47,962評論 2 370
  • 正文 我出身青樓口猜,卻偏偏與公主長得像,于是被迫代替她去往敵國和親透揣。 傳聞我的和親對象是個殘疾皇子济炎,可洞房花燭夜當晚...
    茶點故事閱讀 44,781評論 2 354

推薦閱讀更多精彩內(nèi)容