一致性hash

轉(zhuǎn)載:http://www.reibang.com/p/e8fb89bb3a61

基本場(chǎng)景

比如你有 N 個(gè) cache 服務(wù)器(后面簡(jiǎn)稱(chēng) cache )俘侠,那么如何將一個(gè)對(duì)象 object 映射到 N 個(gè) cache 上呢晚吞,你很可能會(huì)采用類(lèi)似下面的通用方法計(jì)算 object 的 hash 值狐蜕,然后均勻的映射到到 N 個(gè) cache ;

求余算法: hash(object)%N

一切都運(yùn)行正常,再考慮如下的兩種情況;
1 一個(gè) cache 服務(wù)器 m down 掉了(在實(shí)際應(yīng)用中必須要考慮這種情況)盆昙,這樣所有映射到 cache m 的對(duì)象都會(huì)失效,怎么辦焊虏,需要把 cache m 從 cache 中移除淡喜,這時(shí)候 cache 是 N-1 臺(tái),映射公式變成了 hash(object)%(N-1) 诵闭;
2 由于訪問(wèn)加重炼团,需要添加 cache ,這時(shí)候 cache 是 N+1 臺(tái)疏尿,映射公式變成了 hash(object)%(N+1) 瘟芝;
1 和 2 意味著什么?這意味著突然之間幾乎所有的 cache 都失效了润歉。對(duì)于服務(wù)器而言模狭,這是一場(chǎng)災(zāi)難,洪水般的訪問(wèn)都會(huì)直接沖向后臺(tái)服務(wù)器踩衩;
再來(lái)考慮第三個(gè)問(wèn)題嚼鹉,由于硬件能力越來(lái)越強(qiáng),你可能想讓后面添加的節(jié)點(diǎn)多做點(diǎn)活驱富,顯然上面的 hash 算法也做不到锚赤。
有什么方法可以改變這個(gè)狀況呢,這就是 consistent hashing...

hash 算法和單調(diào)性

Hash 算法的一個(gè)衡量指標(biāo)是單調(diào)性( Monotonicity )褐鸥,定義如下:
單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過(guò)哈希分派到了相應(yīng)的緩沖中线脚,又有新的緩沖加入到系統(tǒng)中。哈希的結(jié)果應(yīng)能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖中去叫榕,而不會(huì)被映射到舊的緩沖集合中的其他緩沖區(qū)浑侥。
容易看到,上面的簡(jiǎn)單求余算法 hash(object)%N 難以滿(mǎn)足單調(diào)性要求晰绎。

Consistent Hashing 一致性hash的原理

consistent hashing 是一種 hash 算法寓落,簡(jiǎn)單的說(shuō),在移除 / 添加一個(gè) cache 時(shí)荞下,它能夠盡可能小的改變已存在key 映射關(guān)系伶选,盡可能的滿(mǎn)足單調(diào)性的要求。

1. 環(huán)形hash 空間

考慮通常的 hash 算法都是將 value 映射到一個(gè) 32 為的 key 值尖昏,也即是 0~2^32-1 次方的數(shù)值空間仰税;我們可以將這個(gè)空間想象成一個(gè)首( 0 )尾( 2^32-1 )相接的圓環(huán),如下面圖 1 所示的那樣抽诉。

img

circle space

2. 把需要緩存的內(nèi)容(對(duì)象)映射到hash 空間

接下來(lái)考慮 4 個(gè)對(duì)象 object1~object4 陨簇,通過(guò) hash 函數(shù)計(jì)算出的 hash 值 key 在環(huán)上的分布如圖 2 所示。
hash(object1) = key1;
… …
hash(object4) = key4;

img

object

3 .把服務(wù)器(節(jié)點(diǎn))映射到hash 空間

Consistent hashing 的基本思想就是將對(duì)象和 cache 都映射到同一個(gè) hash 數(shù)值空間中迹淌,并且使用相同的 hash算法塞帐。
假設(shè)當(dāng)前有 A,B 和 C 共 3 臺(tái)服務(wù)器(節(jié)點(diǎn)),那么其映射結(jié)果將如圖 3 所示巍沙,他們?cè)?hash 空間中葵姥,以對(duì)應(yīng)的 hash 值排列。
一般的方法可以使用 服務(wù)器(節(jié)點(diǎn)) 機(jī)器的 IP 地址或者機(jī)器名作為 hash輸入句携。
hash(cache A) = key A;
… …
hash(cache C) = key C;

img

cache

4 .把對(duì)象映射到cache

現(xiàn)在cache和對(duì)象都已經(jīng)通過(guò)同一個(gè) hash 算法映射到 hash 數(shù)值空間中了榔幸,接下來(lái)要考慮的就是如何將對(duì)象映射到 cache 上面了。
在這個(gè)環(huán)形空間中矮嫉,如果沿著順時(shí)針?lè)较驈膶?duì)象的 key 值出發(fā)削咆,直到遇見(jiàn)一個(gè) cache ,那么就將該對(duì)象存儲(chǔ)在這個(gè) cache 上蠢笋,因?yàn)閷?duì)象和 cache 的 hash 值是固定的拨齐,因此這個(gè) cache 必然是唯一和確定的。這樣不就找到了對(duì)象和 cache 的映射方法了嗎昨寞?瞻惋!
依然繼續(xù)上面的例子厦滤,那么根據(jù)上面的方法,對(duì)象 object1 將被存儲(chǔ)到 cache A 上歼狼; object2 和object3 對(duì)應(yīng)到 cache C 掏导; object4 對(duì)應(yīng)到 cache B ;

5. 考察cache 的變動(dòng)

前面講過(guò)羽峰,通過(guò) hash 然后求余的方法帶來(lái)的最大問(wèn)題就在于不能滿(mǎn)足單調(diào)性趟咆,當(dāng) cache 有所變動(dòng)時(shí), cache會(huì)失效梅屉,進(jìn)而對(duì)后臺(tái)服務(wù)器造成巨大的沖擊值纱,現(xiàn)在就來(lái)分析分析 consistent hashing 算法。

  • 5.1 移除 cache
    考慮假設(shè) cache B 掛掉了坯汤,根據(jù)上面講到的映射方法虐唠,這時(shí)受影響的將僅是那些沿 cache B 逆時(shí)針遍歷直到下一個(gè) cache ( cache C )之間的對(duì)象,也即是本來(lái)映射到 cache B 上的那些對(duì)象玫霎。
    因此這里僅需要變動(dòng)對(duì)象 object4 凿滤,將其重新映射到 cache C 上即可;參見(jiàn)圖 4 庶近。

    ?

    img

    圖 4 Cache B 被移除后的 cache 映射

    ?

  • 5.2 添加 cache
    再考慮添加一臺(tái)新的 cache D 的情況翁脆,假設(shè)在這個(gè)環(huán)形 hash 空間中, cache D 被映射在對(duì)象 object2 和object3 之間鼻种。這時(shí)受影響的將僅是那些沿 cache D 逆時(shí)針遍歷直到下一個(gè) cache ( cache B )之間的對(duì)象(它們是也本來(lái)映射到 cache C 上對(duì)象的一部分)反番,將這些對(duì)象重新映射到 cache D 上即可。

因此這里僅需要變動(dòng)對(duì)象 object2 叉钥,將其重新映射到 cache D 上罢缸;參見(jiàn)圖 5 。

img

圖 5 添加 cache D 后的映射關(guān)系

6 .虛擬節(jié)點(diǎn)

考量 Hash 算法的另一個(gè)指標(biāo)是平衡性 (Balance) 投队,定義如下:
平衡性
  平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去枫疆,這樣可以使得所有的緩沖空間都得到利用。
hash 算法并不是保證絕對(duì)的平衡敷鸦,如果 cache 較少的話息楔,對(duì)象并不能被均勻的映射到 cache 上,比如在上面的例子中扒披,僅部署 cache A 和 cache C 的情況下值依,在 4 個(gè)對(duì)象中, cache A 僅存儲(chǔ)了 object1 碟案,而 cache C 則存儲(chǔ)了object2 愿险、 object3 和 object4 ;分布是很不均衡的价说。
為了解決這種情況辆亏, consistent hashing 引入了“虛擬節(jié)點(diǎn)”的概念风秤,它可以如下定義:
“虛擬節(jié)點(diǎn)”( virtual node )是實(shí)際節(jié)點(diǎn)在 hash 空間的復(fù)制品( replica ),一實(shí)際個(gè)節(jié)點(diǎn)對(duì)應(yīng)了若干個(gè)“虛擬節(jié)點(diǎn)”褒链,這個(gè)對(duì)應(yīng)個(gè)數(shù)也成為“復(fù)制個(gè)數(shù)”唁情,“虛擬節(jié)點(diǎn)”在 hash 空間中以 hash 值排列疑苔。
仍以?xún)H部署 cache A 和 cache C 的情況為例甫匹,在圖 4 中我們已經(jīng)看到, cache 分布并不均勻〉敕眩現(xiàn)在我們引入虛擬節(jié)點(diǎn)兵迅,并設(shè)置“復(fù)制個(gè)數(shù)”為 2 ,這就意味著一共會(huì)存在 4 個(gè)“虛擬節(jié)點(diǎn)”薪贫, cache A1, cache A2 代表了 cache A恍箭; cache C1, cache C2 代表了 cache C ;假設(shè)一種比較理想的情況瞧省,參見(jiàn)圖 6 扯夭。

img

圖 6 引入“虛擬節(jié)點(diǎn)”后的映射關(guān)系

此時(shí),對(duì)象到“虛擬節(jié)點(diǎn)”的映射關(guān)系為:
objec1->cache A2 鞍匾; objec2->cache A1 交洗; objec3->cache C1 ; objec4->cache C2 橡淑;
因此對(duì)象 object1 和 object2 都被映射到了 cache A 上构拳,而 object3 和 object4 映射到了 cache C 上;平衡性有了很大提高梁棠。
引入“虛擬節(jié)點(diǎn)”后置森,映射關(guān)系就從 { 對(duì)象 -> 節(jié)點(diǎn) } 轉(zhuǎn)換到了 { 對(duì)象 -> 虛擬節(jié)點(diǎn) } 。查詢(xún)物體所在 cache 時(shí)的映射關(guān)系如圖 7 所示符糊。

img

圖 7 查詢(xún)對(duì)象所在 cache

“虛擬節(jié)點(diǎn)”的 hash 計(jì)算可以采用對(duì)應(yīng)節(jié)點(diǎn)的 IP 地址加數(shù)字后綴的方式凫海。例如假設(shè) cache A 的 IP 地址為202.168.14.241 。
引入“虛擬節(jié)點(diǎn)”前男娄,計(jì)算 cache A 的 hash 值:
Hash(“202.168.14.241”);
引入“虛擬節(jié)點(diǎn)”后行贪,計(jì)算“虛擬節(jié)”點(diǎn) cache A1 和 cache A2 的 hash 值:
Hash(“202.168.14.241#1”); // cache A1
Hash(“202.168.14.241#2”); // cache A2

以下時(shí)代碼實(shí)現(xiàn)DEMO

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from zlib import crc32
import memcache


class HashConsistency(object):
    def __init__(self, nodes=None, replicas=5):
        # 虛擬節(jié)點(diǎn)與真實(shí)節(jié)點(diǎn)對(duì)應(yīng)關(guān)系
        self.nodes_map = []
        # 真實(shí)節(jié)點(diǎn)與虛擬節(jié)點(diǎn)的字典映射
        self.nodes_replicas = {}
        # 真實(shí)節(jié)點(diǎn)
        self.nodes = nodes
        # 每個(gè)真實(shí)節(jié)點(diǎn)創(chuàng)建的虛擬節(jié)點(diǎn)的個(gè)數(shù)
        self.replicas = replicas

        if self.nodes:
            for node in self.nodes:
                self._add_nodes_map(node)
            self._sort_nodes()

    def get_node(self, key):
        """ 根據(jù)KEY值的hash值,返回對(duì)應(yīng)的節(jié)點(diǎn)
        算法是: 返回最早比key_hash大的節(jié)點(diǎn)
        """
        key_hash = abs(crc32(key))
        #print '(%s' % key_hash
        for node in self.nodes_map:
            if key_hash > node[0]:
                continue
            return node
        return None

    def add_node(self, node):
        # 添加節(jié)點(diǎn)
        self._add_nodes_map(node)
        self._sort_nodes()

    def remove_node(self, node):
        # 刪除節(jié)點(diǎn)
        if node not in self.nodes_replicas.keys():
            pass
        discard_rep_nodes = self.nodes_replicas[node]
        self.nodes_map = filter(lambda x: x[0] not in discard_rep_nodes, self.nodes_map)

    def _add_nodes_map(self, node):
        # 增加虛擬節(jié)點(diǎn)到nodes_map列表
        nodes_reps = []
        for i in xrange(self.replicas):
            rep_node = '%s_%d' % (node, i)
            node_hash = abs(crc32(rep_node))
            self.nodes_map.append((node_hash, node))
            nodes_reps.append(node_hash)
        # 真實(shí)節(jié)點(diǎn)與虛擬節(jié)點(diǎn)的字典映射
        self.nodes_replicas[node] = nodes_reps

    def _sort_nodes(self):
        # 按順序排列虛擬節(jié)點(diǎn)
        self.nodes_map = sorted(self.nodes_map, key=lambda x:x[0])


memcache_servers = [
    '127.0.0.1:7001',
    '127.0.0.1:7002',
    '127.0.0.1:7003',
    '127.0.0.1:7004',
]

h = HashConsistency(memcache_servers)

for k in h.nodes_map:
    print k

mc_servers_dict = {}
for ms in  memcache_servers:
    mc = memcache.Client([ms], debug=0)
    mc_servers_dict[ms] = mc

# 循環(huán)10此給memcache 添加key沪伙,這里使用了一致性hash瓮顽,那么key將會(huì)根據(jù)hash值落點(diǎn)到對(duì)應(yīng)的虛擬節(jié)點(diǎn)上
for i in xrange(10):
    key = 'key_%s' % i
    print key
    server = h.get_node(key)[1]
    mc = mc_servers_dict[server]
    mc.set(key, i)
    print 'SERVER :%s' % server
    print mc


?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市围橡,隨后出現(xiàn)的幾起案子暖混,更是在濱河造成了極大的恐慌,老刑警劉巖翁授,帶你破解...
    沈念sama閱讀 216,692評(píng)論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拣播,死亡現(xiàn)場(chǎng)離奇詭異晾咪,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)贮配,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,482評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門(mén)谍倦,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人泪勒,你說(shuō)我怎么就攤上這事昼蛀。” “怎么了圆存?”我有些...
    開(kāi)封第一講書(shū)人閱讀 162,995評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵叼旋,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我沦辙,道長(zhǎng)夫植,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,223評(píng)論 1 292
  • 正文 為了忘掉前任油讯,我火速辦了婚禮详民,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘陌兑。我一直安慰自己沈跨,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,245評(píng)論 6 388
  • 文/花漫 我一把揭開(kāi)白布诀紊。 她就那樣靜靜地躺著谒出,像睡著了一般。 火紅的嫁衣襯著肌膚如雪邻奠。 梳的紋絲不亂的頭發(fā)上笤喳,一...
    開(kāi)封第一講書(shū)人閱讀 51,208評(píng)論 1 299
  • 那天,我揣著相機(jī)與錄音碌宴,去河邊找鬼杀狡。 笑死,一個(gè)胖子當(dāng)著我的面吹牛贰镣,可吹牛的內(nèi)容都是我干的呜象。 我是一名探鬼主播,決...
    沈念sama閱讀 40,091評(píng)論 3 418
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼碑隆,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼恭陡!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起上煤,我...
    開(kāi)封第一講書(shū)人閱讀 38,929評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤休玩,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體拴疤,經(jīng)...
    沈念sama閱讀 45,346評(píng)論 1 311
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡永部,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,570評(píng)論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了呐矾。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片苔埋。...
    茶點(diǎn)故事閱讀 39,739評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖蜒犯,靈堂內(nèi)的尸體忽然破棺而出组橄,到底是詐尸還是另有隱情,我是刑警寧澤愧薛,帶...
    沈念sama閱讀 35,437評(píng)論 5 344
  • 正文 年R本政府宣布晨炕,位于F島的核電站衫画,受9級(jí)特大地震影響毫炉,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜削罩,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,037評(píng)論 3 326
  • 文/蒙蒙 一瞄勾、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧弥激,春花似錦进陡、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,677評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至以蕴,卻和暖如春糙麦,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背丛肮。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,833評(píng)論 1 269
  • 我被黑心中介騙來(lái)泰國(guó)打工赡磅, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人宝与。 一個(gè)月前我還...
    沈念sama閱讀 47,760評(píng)論 2 369
  • 正文 我出身青樓焚廊,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親习劫。 傳聞我的和親對(duì)象是個(gè)殘疾皇子咆瘟,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,647評(píng)論 2 354

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

  • consistent hashing算法早在1997年就在論文Consistent hashing and...
    北風(fēng)第一支閱讀 804評(píng)論 0 5
  • 分布式緩存作為緩存水平擴(kuò)充的最佳辦法,當(dāng)前很實(shí)用诽里。假設(shè)一臺(tái)機(jī)器可支撐4GB的數(shù)據(jù)的緩存袒餐,如果需要支撐24GB,則需...
    TTTTTriM閱讀 1,656評(píng)論 0 2
  • 周末我們兩個(gè)到超市去買(mǎi)菜。在停車(chē)場(chǎng)下了車(chē)匿乃,牽手走向超市入口時(shí)桩皿,老婆突然沒(méi)頭沒(méi)腦地來(lái)了一句,“謝謝你幢炸,從來(lái)不限制我買(mǎi)...
    游老老閱讀 95評(píng)論 0 0
  • 幸福是一種能力 曾經(jīng) 剛畢業(yè)時(shí)泄隔,我對(duì)未來(lái)充滿(mǎn)了憧憬,我認(rèn)為以我的能力必然能在這個(gè)世上創(chuàng)出一片天地宛徊,獲得我想要的一切...
    宋文峰閱讀 473評(píng)論 0 4
  • 我是日記星球154號(hào)星寶寶佛嬉,這是我的第12篇原創(chuàng)日記。 2017年3月12日 星期日 晴 昨晚闸天,在中央六臺(tái)暖呕,又一次...
    小數(shù)點(diǎn)123閱讀 359評(píng)論 0 3