算法之什么是一致性哈希？
一致性哈希
一致性哈希是一種哈希算法，就是在移除或者增加一個結(jié)點時，能夠盡可能小的改變已存在key的映射關(guān)系盡可能少的改變已有的映射關(guān)系，一般是沿著順時針進行操作，回答之前可以先想想，真實情況如何處理一致性哈希將整個哈希值空間組織成一個虛擬的圓環(huán)，假設(shè)哈希函數(shù)的值空間為0~2^32-1，整個哈希空間環(huán)如下左圖所示
一致性hash的基本思想就是使用相同的hash算法將數(shù)據(jù)和結(jié)點都映射到圖中的環(huán)形哈希空間中，上右圖顯示了4個數(shù)據(jù)object1-object4在環(huán)上的分布圖
結(jié)點和數(shù)據(jù)映射
假如有一批服務(wù)器，可以根據(jù)IP或者主機名作為關(guān)鍵字進行哈希，根據(jù)結(jié)果映射到哈希環(huán)中，3臺服務(wù)器分別是nodeA-nodeC
現(xiàn)在有一批的數(shù)據(jù)object1-object4需要存在服務(wù)器上，則可以使用相同的哈希算法對數(shù)據(jù)進行哈希，其結(jié)果必然也在環(huán)上，可以沿著順時針方向?qū)ふ遥业揭粋€結(jié)點(服務(wù)器)則將數(shù)據(jù)存在這個結(jié)點上，這樣數(shù)據(jù)和結(jié)點就產(chǎn)生了一對一的關(guān)聯(lián)，如下圖所示：
移除結(jié)點
如果一臺服務(wù)器出現(xiàn)問題，如上圖中的nodeB，則受影響的是其逆時針方向至下一個結(jié)點之間的數(shù)據(jù)，只需將這些數(shù)據(jù)映射到它順時針方向的第一個結(jié)點上即可，下左圖
1566573901641
添加結(jié)點
如果新增一臺服務(wù)器nodeD，受影響的是其逆時針方向至下一個結(jié)點之間的數(shù)據(jù)，將這些數(shù)據(jù)映射到nodeD上即可，見上右圖
虛擬結(jié)點
假設(shè)僅有2臺服務(wù)器：nodeA和nodeC，nodeA映射了1條數(shù)據(jù)，nodeC映射了3條，這樣數(shù)據(jù)分布是不平衡的。引入虛擬結(jié)點，假設(shè)結(jié)點復(fù)制個數(shù)為2，則nodeA變成：nodeA1和nodeA2，nodeC變成：nodeC1和nodeC2，映射情況變成如下：
這樣數(shù)據(jù)分布就均衡多了，平衡性有了很大的提高
