一致性哈希的簡單認識
簡介
在分佈式集群中，對機器的添加、刪除或者是機器故障後自動脫離集群等操作是分佈式集群管理最基本的功能。如果採用的是常見的取模哈希算法，當有機器添加、刪除之後，需要對數據做遷移，非常麻煩。
而一致性哈希利用哈希環的概念，保證增加或減少服務器，數據存儲的改變最少，相比取模哈希算法大大節省了數據移動的開銷，非常方便。
一致性哈希認為在動態變化的緩存空間環境中，良好的哈希算法應該滿足以下幾個方面：
- 平衡性：指哈希的結果能夠儘可能分佈到所有的緩存中，這樣可以使得所有的緩存空間都能得到利用
- 單調性：指當新的緩存空間加入時，原本已分配的數據可以被映射到原本或者新的緩存空間中，而不會被映射到舊的其他緩存空間中
- 分散性：避免出現相同的內容被不同的終端映射到不同的緩存空間中，降低系統存儲的效率
- 負載：與分散性結合理解，對於一個特定的緩衝區，避免被不同的終端映射為不同的內容
一致性哈希可以理解成普通取模哈希算法的改良版，改變的是將普通的線性哈希空間變成環狀的哈希空間，其中每一個緩存空間是環上的一個節點，數據一般存儲在沿順時針的方向找到的環上的第一個節點。
算法
哈希環
簡單的說，一致性哈希是將整個哈希值空間想像成一個虛擬的圓環。
比如，假設哈希函數 H 的值空間為 0 ~ \(2^{32}-1\)，整個哈希空間環如下：
假設這時有 k1、k2、k3、k4 這幾個 key 值，通過一定的哈希算法，將這幾個 key 值被平均分配到哈希環上。
同樣的，現在有 3 台 cache 服務器，通過一定的哈希算法，也被平均分配到哈希環上。
下圖展示的是 key 值被分配到哪一台 cache 服務器的一個示例：
如上所示：k1 存儲在 c3 上，k4、k3 存儲在 c1 上，k2 存儲在 c2 上。
哈希環會將哈希後的 key 值按照順時針的方向尋找最近的 cache 服務器，然後將數據存儲在這台服務器上。
刪除節點
假設 c3 服務器宕機，這時候需要從集群中將其摘除，其上的數據也需要做遷移。
按照一致性哈希的規則，原本存儲在 c3 上的 k1 按照順時針的方向尋找最近的 cache 服務器，即後續 k1 會存儲在 c1 上：
從這裡可知，當使用一致性哈希時，刪除節點 c3 會影響到被刪除節點 c3 上及其下一個節點 c1 的數據，遷移數據的時候，需要將被刪除節點 c3 上的數據遷移到其下一個節點 c1 上。
新增節點
假設現在需要新增 c4 服務器，會破壞現在集群的平衡，需要對數據做一些處理。
假設 c4 服務器定位在 k4 和 k3 之間，按照一致性哈希的規則，原本存儲在 c1 上的 k4 會遷移到 c4 上：
同樣的，新增節點會影響到新增節點所在位置的後一個節點 c1，遷移數據的時候，需要將新增節點所在位置到其上一個節點 c3 之間的數據從其下一個節點 c1 遷移到新增的節點 c4 上。
虛擬節點
一致性哈希理論上沒有什麼問題，但實際使用會存在以下問題：
- 當節點較少時，哈希環中的節點容易出現分佈不均衡，最終導致數據傾斜
- 當一個節點宕機時，數據會立馬遷移到下一個節點，下一個節點的流量壓力和內存壓力都會增大，可能會導致其宕機，繼而引發雪崩
這裡就衍生出一個虛擬節點的概念，即對每個物理節點計算多個哈希值，將原來單一的物理節點在哈希環上虛擬出幾個分身節點，這些分身節點稱為虛擬節點。
映射到分身節點上的數據實際上就是映射到分身對應的物理節點上，這樣一個物理節點可以通過虛擬節點的方式均勻分散在哈希環的各個部分，解決數據傾斜問題。
由於虛擬節點分散在哈希環各個部分，當某個節點宕機下線，虛擬節點所存儲的數據會被均勻分配給下一個虛擬節點，則物理節點也會得到均勻分配，避免了對單一節點突發壓力導致的節點雪崩問題。
在實際應用中，通常將虛擬節點數設置成 32 甚至更大，這樣可以保證即使很少的服務節點也能做到均勻的數據分佈。
優缺點
一致性哈希算法相比普通的哈希算法在擴展性和容錯性上都有一定的優勢：
- 擴展性：普通的哈希算法增加緩存空間的時候，需要對大量數據做遷移；一致性哈希算法擴展時僅需將下一個節點中的一部分數據遷移到這個新增節點上
- 容錯性：普通的哈希算法減少緩存空間的時候，會出現哈希映射大面積失效的情況；而對於一致性哈希算法，如果出現需要減少緩存空間的情況，其實就是需要將當前減少的節點數據遷移到下一個節點中
實際上，不會存在一勞永逸的哈希算法，一致性哈希算法在以下場景需要謹慎使用：
- 對於數據佔用空間大、但數量較小時，使用一致性哈希有些大材小用
- 一致性哈希解決了數據的均勻分佈，但是沒有解決流量和負載的均衡
- 數據和機器之間的映射通過哈希算法得到，這種關係比較固定，無法人工干涉
