[[413431]]

一致性哈希

一致性哈希是一種哈希算法，就是在移除或者增加一個(gè)結(jié)點(diǎn)時(shí)，能夠盡可能小的改變已存在key的映射關(guān)系盡可能少的改變已有的映射關(guān)系，一般是沿著順時(shí)針進(jìn)行操作，回答之前可以先想想，真實(shí)情況如何處理一致性哈希將整個(gè)哈希值空間組織成一個(gè)虛擬的圓環(huán)，假設(shè)哈希函數(shù)的值空間為0~2^32-1，整個(gè)哈希空間環(huán)如下左圖所示

一致性hash的基本思想就是使用相同的hash算法將數(shù)據(jù)和結(jié)點(diǎn)都映射到圖中的環(huán)形哈希空間中，上右圖顯示了4個(gè)數(shù)據(jù)object1-object4在環(huán)上的分布圖

結(jié)點(diǎn)和數(shù)據(jù)映射

假如有一批服務(wù)器，可以根據(jù)IP或者主機(jī)名作為關(guān)鍵字進(jìn)行哈希，根據(jù)結(jié)果映射到哈希環(huán)中，3臺(tái)服務(wù)器分別是nodeA-nodeC

現(xiàn)在有一批的數(shù)據(jù)object1-object4需要存在服務(wù)器上，則可以使用相同的哈希算法對(duì)數(shù)據(jù)進(jìn)行哈希，其結(jié)果必然也在環(huán)上，可以沿著順時(shí)針?lè)较驅(qū)ふ?，找到一個(gè)結(jié)點(diǎn)(服務(wù)器)則將數(shù)據(jù)存在這個(gè)結(jié)點(diǎn)上，這樣數(shù)據(jù)和結(jié)點(diǎn)就產(chǎn)生了一對(duì)一的關(guān)聯(lián)，如下圖所示：

移除結(jié)點(diǎn)

如果一臺(tái)服務(wù)器出現(xiàn)問(wèn)題，如上圖中的nodeB，則受影響的是其逆時(shí)針?lè)较蛑料乱粋€(gè)結(jié)點(diǎn)之間的數(shù)據(jù)，只需將這些數(shù)據(jù)映射到它順時(shí)針?lè)较虻牡谝粋€(gè)結(jié)點(diǎn)上即可，下左圖

1566573901641

添加結(jié)點(diǎn)

如果新增一臺(tái)服務(wù)器nodeD，受影響的是其逆時(shí)針?lè)较蛑料乱粋€(gè)結(jié)點(diǎn)之間的數(shù)據(jù)，將這些數(shù)據(jù)映射到nodeD上即可，見(jiàn)上右圖

虛擬結(jié)點(diǎn)

假設(shè)僅有2臺(tái)服務(wù)器：nodeA和nodeC，nodeA映射了1條數(shù)據(jù)，nodeC映射了3條，這樣數(shù)據(jù)分布是不平衡的。引入虛擬結(jié)點(diǎn)，假設(shè)結(jié)點(diǎn)復(fù)制個(gè)數(shù)為2，則nodeA變成：nodeA1和nodeA2，nodeC變成：nodeC1和nodeC2，映射情況變成如下：

這樣數(shù)據(jù)分布就均衡多了，平衡性有了很大的提高