當(dāng)緩存集群的節(jié)點(diǎn)有所增加的時(shí)候，整個(gè)環(huán)形空間的映射仍然會(huì)保持一致性哈希的順時(shí)針規(guī)則，所以有一小部分key的歸屬會(huì)受到影響。

作者：IT知識(shí)課堂來(lái)源

一年之前——

未來(lái)兩年內(nèi)，系統(tǒng)預(yù)估的總訂單數(shù)量可達(dá)一億條左右。

按Mysql單表存儲(chǔ)500萬(wàn)條記錄來(lái)算，暫時(shí)不必分庫(kù)，單庫(kù)30個(gè)分表是比較合適的水平分表方案。

于是小灰設(shè)計(jì)了這樣的分表邏輯：

訂單表創(chuàng)建單庫(kù)30個(gè)分表

對(duì)用戶ID和30進(jìn)行取模，取模結(jié)果決定了記錄存于第幾個(gè)分表

查詢時(shí)需要以用戶ID作為條件，根據(jù)取模結(jié)果確定查詢哪一個(gè)分表

分表方式如下圖(為了便于描述，簡(jiǎn)化為5個(gè)分表)：

過(guò)了兩個(gè)月——

又過(guò)了半年多——

小灰的回憶告一段落——

1.首先，我們把全量的緩存空間當(dāng)做一個(gè)環(huán)形存儲(chǔ)結(jié)構(gòu)。環(huán)形空間總共分成2^32個(gè)緩存區(qū)，在Redis中則是把緩存key分配到16384個(gè)slot。

2.每一個(gè)緩存key都可以通過(guò)Hash算法轉(zhuǎn)化為一個(gè)32位的二進(jìn)制數(shù)，也就對(duì)應(yīng)著環(huán)形空間的某一個(gè)緩存區(qū)。我們把所有的緩存key映射到環(huán)形空間的不同位置。

3.我們的每一個(gè)緩存節(jié)點(diǎn)(Shard)也遵循同樣的Hash算法，比如利用IP做Hash，映射到環(huán)形空間當(dāng)中。

4.如何讓key和節(jié)點(diǎn)對(duì)應(yīng)起來(lái)呢?很簡(jiǎn)單，每一個(gè)key的順時(shí)針?lè)较蜃罱?jié)點(diǎn)，就是key所歸屬的存儲(chǔ)節(jié)點(diǎn)。所以圖中key1存儲(chǔ)于node1，key2，key3存儲(chǔ)于node2，key4存儲(chǔ)于node3。

1.增加節(jié)點(diǎn)

當(dāng)緩存集群的節(jié)點(diǎn)有所增加的時(shí)候，整個(gè)環(huán)形空間的映射仍然會(huì)保持一致性哈希的順時(shí)針規(guī)則，所以有一小部分key的歸屬會(huì)受到影響。

有哪些key會(huì)受到影響呢?圖中加入了新節(jié)點(diǎn)node4，處于node1和node2之間，按照順時(shí)針規(guī)則，從node1到node4之間的緩存不再歸屬于node2，而是歸屬于新節(jié)點(diǎn)node4。因此受影響的key只有key2。

最終把key2的緩存數(shù)據(jù)從node2遷移到node4，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。

2.刪除節(jié)點(diǎn)

當(dāng)緩存集群的節(jié)點(diǎn)需要?jiǎng)h除的時(shí)候(比如節(jié)點(diǎn)掛掉)，整個(gè)環(huán)形空間的映射同樣會(huì)保持一致性哈希的順時(shí)針規(guī)則，同樣有一小部分key的歸屬會(huì)受到影響。

有哪些key會(huì)受到影響呢?圖中刪除了原節(jié)點(diǎn)node3，按照順時(shí)針規(guī)則，原本node3所擁有的緩存數(shù)據(jù)就需要“托付”給node3的順時(shí)針后繼節(jié)點(diǎn)node1。因此受影響的key只有key4。

最終把key4的緩存數(shù)據(jù)從node3遷移到node1，就形成了新的符合一致性哈希規(guī)則的緩存結(jié)構(gòu)。

如上圖所示，假如node1的ip是192.168.1.109，那么原node1節(jié)點(diǎn)在環(huán)形空間的位置就是hash(“192.168.1.109”)。

我們基于node1構(gòu)建兩個(gè)虛擬節(jié)點(diǎn)，node1-1 和 node1-2，虛擬節(jié)點(diǎn)在環(huán)形空間的位置可以利用(IP+后綴)計(jì)算，例如：

hash(“192.168.1.109#1”)，hash(“192.168.1.109#2”)

此時(shí)，環(huán)形空間中不再有物理節(jié)點(diǎn)node1，node2，只有虛擬節(jié)點(diǎn)node1-1，node1-2，node2-1，node2-2。由于虛擬節(jié)點(diǎn)數(shù)量較多，緩存key與虛擬節(jié)點(diǎn)的映射關(guān)系也變得相對(duì)均衡了。

閱讀目錄（置頂)(長(zhǎng)期更新計(jì)算機(jī)領(lǐng)域知識(shí)）

閱讀目錄（置頂)(長(zhǎng)期更新計(jì)算機(jī)領(lǐng)域知識(shí)）

閱讀目錄（置頂)(長(zhǎng)期科技領(lǐng)域知識(shí)）

歌謠帶你看java面試題

總結(jié)

以上是生活随笔為你收集整理的第六十九期： 漫画说算法之什么是一致性哈希？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。