[[413431]]

一致性哈希

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

一致性hash的基本思想就是使用相同的hash算法將數據和結點都映射到圖中的環形哈希空間中，上右圖顯示了4個數據object1-object4在環上的分布圖

結點和數據映射

假如有一批服務器，可以根據IP或者主機名作為關鍵字進行哈希，根據結果映射到哈希環中，3臺服務器分別是nodeA-nodeC

現在有一批的數據object1-object4需要存在服務器上，則可以使用相同的哈希算法對數據進行哈希，其結果必然也在環上，可以沿著順時針方向尋找，找到一個結點(服務器)則將數據存在這個結點上，這樣數據和結點就產生了一對一的關聯，如下圖所示：

移除結點

如果一臺服務器出現問題，如上圖中的nodeB，則受影響的是其逆時針方向至下一個結點之間的數據，只需將這些數據映射到它順時針方向的第一個結點上即可，下左圖

1566573901641

添加結點

如果新增一臺服務器nodeD，受影響的是其逆時針方向至下一個結點之間的數據，將這些數據映射到nodeD上即可，見上右圖

虛擬結點

假設僅有2臺服務器：nodeA和nodeC，nodeA映射了1條數據，nodeC映射了3條，這樣數據分布是不平衡的。引入虛擬結點，假設結點復制個數為2，則nodeA變成：nodeA1和nodeA2，nodeC變成：nodeC1和nodeC2，映射情況變成如下：

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