概述
一致Hash在分佈式應用中,是常見的負載均衡方式,多用於資源請求映射分散到具體某一臺節點服務器,使得每一臺服務器能固定處理部分請求,同時,能較小的減少由於動態增減服務器節點帶來請求的失效，保證系統更好對外提供服務。
從問題的發展引入思考
圖1.假設現在有200萬張圖片資源，需要隨機的分配到3臺服務器
除餘法
很多人一下子就想到了除餘法,通過給每個圖片唯一編號(較少的情況),或者通過hash文件名(假設文件名不重複)得到唯一的數字串,然後除餘就能隨機存放到服務器。
<code>hash(文件名) % n/<code>
正常情況下這個算法已經基本滿足,因為每次除餘之後必然會得到0,1,2三個數,分別對應三臺服務器,下次需要找回這些圖片資源只要按同樣的方式hash之後就能在對應服務器找到。
但是當圖片資源過多無法滿足需要增加一臺服務器的時候,因為除數的改變,帶來餘數的改變,也就是服務器數量的改變,帶來存儲位置的改變,之前存儲的圖片資源失去了意義,在緩存服務器中,這會導致大量緩存失效,造成緩存的雪崩,為了解決這些問題,一致性hash應運而生。
揭開一致性Hash神秘面紗
首先了解一下計算一致性hash時採用的方式和步驟：
- 在一個0~2^32區間的圓環上，計算服務器節點的hash值,。
- 用同樣的方式計算存儲數據的hash,並映射到相同的圓上。
- 然後從數據映射到的位置開始順時針查找，那麼在圓上必然能映射到具體一臺節點服務器。
圖2.一致hash算法映射到圓環
這裡解釋一下,一致性Hash也是採用取模的方法,其hash計算的區間同樣是在0~2^32,這算法很多語言都有,比如go語言的crc32.ChecksumIEEE就有實現此算法,那麼這個一致性hash有什麼優勢呢?
圖3.NodeB宕機/摘除的情況(虛線圓)
圖4.新增一個節點的情況
如圖3.在NodeB宕機或摘除節點之後,存儲數據對象ObjectB按照順時針原則重新映射到NodeC服務器節點。
如圖4.在新增節點NodeD之後，存儲數據對象ObjectB同樣映射到了NodeD服務器節點，但是新增和摘除節點都沒有影響到ObjectA和ObjectC,這就使得這種一致hash算法在增減節點時候並不會導致大面積請求資源的失效。
並且隨著服務器節點的增加，影響會越來越小。但是理想很豐滿,現實卻很骨感,當服務節點比較少的情況下,其實並不是如圖3,圖4這樣分配均勻的，而是有可能出現數據傾斜的,下面拿摘除NodeA做舉例：
圖5.一致hash可能出現數據傾斜的情況
圖6.NodeA宕機/摘除,大量存儲數據映射到了NodeB
如圖5、6不難看出，當服務器較少並且數據出現一定傾斜的時候,假設NodeA出現宕機,這時候資源請求會重新映射到NodeB,那麼NodeB機器的壓力就會暴漲,在硬件資源有限的情況下,又怎麼更好的處理這個問題呢？
虛擬節點
上面提到的過程基本上就是一致性hash的基本原理了,不過還有一個問題就是當服務器節點較少的時候,如何解決這個負載不均衡的問題，那就是虛擬節點。
其實就是將每臺物理機器,映射成n多個虛擬機器,再將這些虛擬機器hash之後映射到圓環上。
圖7.虛擬機器和物理機器的映射
圖8.生成多個虛擬節點進行映射，圖中省略了hash過程
數據定位到圓環算法是不變的，只是多了一步虛擬節點到實際節點的映射。
你品,你細品一下!!
最後,表述一下在動態變化的Cache環境中，判定哈希算法好壞的四個定義：
1、平衡性(Balance)：平衡性是指哈希的結果能夠儘可能分佈到所有的緩衝中去，這樣可以使得所有的緩衝空間都得到利用。很多哈希算法都能夠滿足這一條件。
2、單調性(Monotonicity)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩衝中，又有新的緩衝加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩衝中去，而不會被映射到舊的緩衝集合中的其他緩衝區。
3、分散性(Spread)：在分佈式環境中，終端有可能看不到所有的緩衝，而是隻能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩衝上時，由於不同終端所見的緩衝範圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩衝區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩衝中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應能夠儘量避免不一致的情況發生，也就是儘量降低分散性。
4、負載(Load)
：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩衝區中，那麼對於一個特定的緩衝區而言，也可能被不同的用戶映射為不同 的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠儘量降低緩衝的負荷。4、平滑性(Smoothness)：平滑性是指緩存服務器的數目平滑改變和緩存對象的平滑改變是一致的。
下節課將給童鞋們講解一下一致hash算法的代碼實現,喜歡童鞋可以關注一哈
聰明出於勤奮，天才在於積累。
閱讀更多 詩一樣的程序員 的文章
