# 概述 在解決分布式系統中負載均衡的問題時候可以使用Hash算法讓固定的一部分請求落到同一臺服務器上，這樣每臺服務器固定處理一部分請求，起到負載均衡的作用。 但是普通的余數hash（hash\(比如用戶id\)%服務器機器數）算法伸縮性很差，當新增或者下線服務器機器時候，用戶id與服務器的映射關系會大量失效。一致性hash則利用hash環對其進行了改進 ### 一致性哈希算法特性 一致性哈希算法在1997年由麻省理工學院提出的一種分布式哈希（DHT）實現算法，設計目標是為了解決因特網中的熱點\(Hot spot\)問題，初衷和CARP十分類似。一致性哈希修正了CARP使用的簡單哈希算法帶來的問題，使得分布式哈希（DHT）可以在P2P環境中真正得到應用。 一致性hash算法提出了在動態變化的Cache環境中，判定哈希算法好壞的四個定義： 1. 平衡性\(Balance\)：平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。 2. 單調性\(Monotonicity\)：單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到原有的或者新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。 3. 分散性\(Spread\)：在分布式環境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結果不一致，最終的結果是相同的內容被不同的終端映射到不同的緩沖區中。這種情況顯然是應該避免的，因為它導致相同內容被存儲到不同緩沖中去，降低了系統存儲的效率。分散性的定義就是上述情況發生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發生，也就是盡量降低分散性。 4. 負載\(Load\)：負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內容映射到不同的緩沖區中，那么對于一個特定的緩沖區而言，也可能被不同的用戶映射為不同的內容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷 # 一致性Hash概述 為了能直觀的理解一致性hash原理，這里結合一個簡單的例子來講解，假設有4臺服務器，地址為ip1,ip2,ip3,ip4。 * 一致性hash是首先計算四個ip地址對應的hash值 hash\(ip1\),hash\(ip2\),hash\(ip3\),hash\(ip3\)，計算出來的hash值是0~最大正整數直接的一個值，這四個值在一致性hash環上呈現如下圖：  * hash環上順時針從整數0開始，一直到最大正整數，我們根據四個ip計算的hash值肯定會落到這個hash環上的某一個點，至此我們把服務器的四個ip映射到了一致性hash環 * 當用戶在客戶端進行請求時候，首先根據hash\(用戶id\)計算路由規則（hash值），然后看hash值落到了hash環的那個地方，根據hash值在hash環上的位置順時針找距離最近的ip作為路由ip  如上圖可知user1,user2的請求會落到服務器ip2進行處理，User3的請求會落到服務器ip3進行處理，user4的請求會落到服務器ip4進行處理，user5,user6的請求會落到服務器ip1進行處理。 下面考慮當ip2的服務器掛了的時候會出現什么情況？ 當ip2的服務器掛了的時候，一致性hash環大致如下圖：  根據順時針規則可知user1,user2的請求會被服務器ip3進行處理，而其它用戶的請求對應的處理服務器不變，也就是只有之前被ip2處理的一部分用戶的映射關系被破壞了，并且其負責處理的請求被順時針下一個節點委托處理。 下面考慮當新增機器的時候會出現什么情況？ 當新增一個ip5的服務器后，一致性hash環大致如下圖：  根據順時針規則可知之前user1的請求應該被ip1服務器處理，現在被新增的ip5服務器處理，其他用戶的請求處理服務器不變，也就是新增的服務器順時針最近的服務器的一部分請求會被新增的服務器所替代 # 虛擬節點 當服務器節點比較少的時候會出現上節所說的一致性hash傾斜的問題，一個解決方法是多加機器，但是加機器是有成本的，那么就加虛擬節點，比如上面三個機器，每個機器引入1個虛擬節點后的一致性hash環的圖如下：  其中ip1-1是ip1的虛擬節點，ip2-1是ip2的虛擬節點，ip3-1是ip3的虛擬節點。 可知當物理機器數目為M，虛擬節點為N的時候，實際hash環上節點個數為M\*N。比如當客戶端計算的hash值處于ip2和ip3或者處于ip2-1和ip3-1之間時候使用ip3服務器進行處理 # 均勻一致性hash 上節我們使用虛擬節點后的圖看起來比較均衡，但是如果生成虛擬節點的算法不夠好很可能會得到下面的環  可知每個服務節點引入1個虛擬節點后，情況相比沒有引入前均衡性有所改善，但是并不均衡。 均衡的一致性hash應該是如下圖：  均勻一致性hash的目標是如果服務器有N臺，客戶端的hash值有M個，那么每個服務器應該處理大概M/N個用戶的。也就是每臺服務器負載盡量均衡 實際應用中，通常將虛擬節點數設置為32甚至更大，因此即使很少的節點也能做到相對均勻的數據分布 【參考資料】 《大型網站技術架構：核心原理與案例分析》6.3.3章節