## 一致性哈希算法 tencent2012筆試題附加題 問題描述： 例如手機朋友網有n個服務器，為了方便用戶的訪問會在服務器上緩存數據，因此用戶每次訪問的時候最好能保持同一臺服務器。 已有的做法是根據ServerIPIndex[QQNUM%n]得到請求的服務器，這種方法很方便將用戶分到不同的服務器上去。但是如果一臺服務器死掉了，那么n就變為了n-1，那么ServerIPIndex[QQNUM%n]與ServerIPIndex[QQNUM%（n-1）]基本上都不一樣了，所以大多數用戶的請求都會轉到其他服務器，這樣會發生大量訪問錯誤。 問： 如何改進或者換一種方法，使得： (1) 一臺服務器死掉后，不會造成大面積的訪問錯誤， (2)原有的訪問基本還是停留在同一臺服務器上； (3)盡量考慮負載均衡。（思路：往分布式一致哈希算法方面考慮。） 1. 最土的辦法還是用模余方法：做法很簡單，假設有N臺服務器，現在完好的是M（M<=N),先用N求模，如果不落在完好的機器上，然后再用N-1求模，直到M.這種方式對于壞的機器不多的情況下，具有更好的穩定性。 2. 一致性哈希算法。 下面，本文剩下部分重點來講講這個一致性哈希算法。 ### 應用場景 在做服務器負載均衡時候可供選擇的負載均衡的算法有很多，包括： 輪循算法（Round Robin）、哈希算法（HASH）、最少連接算法（Least Connection）、響應速度算法（Response Time）、加權法（Weighted ）等。其中哈希算法是最為常用的算法. 典型的應用場景是： 有N臺服務器提供緩存服務，需要對服務器進行負載均衡，將請求平均分發到每臺服務器上，每臺機器負責1/N的服務。 常用的算法是對hash結果取余數 (hash() mod N)：對機器編號從0到N-1，按照自定義的hash()算法，對每個請求的hash()值按N取模，得到余數i，然后將請求分發到編號為i的機器。但這樣的算法方法存在致命問題，如果某一臺機器宕機，那么應該落在該機器的請求就無法得到正確的處理，這時需要將當掉的服務器從算法從去除，此時候會有(N-1)/N的服務器的緩存數據需要重新進行計算；如果新增一臺機器，會有N /(N+1)的服務器的緩存數據需要進行重新計算。對于系統而言，這通常是不可接受的顛簸（因為這意味著大量緩存的失效或者數據需要轉移）。那么，如何設計一個負載均衡策略，使得受到影響的請求盡可能的少呢？ 在Memcached、Key-Value Store、Bittorrent DHT、LVS中都采用了Consistent Hashing算法，可以說Consistent Hashing 是分布式系統負載均衡的首選算法。 ### Consistent Hashing算法描述 下面以Memcached中的Consisten Hashing算法為例說明。 consistent hashing 算法早在 1997 年就在論文 [Consistent hashing and random trees](http://dl.acm.org/citation.cfm?id=258660) 中被提出，目前在 cache 系統中應用越來越廣泛； ### 基本場景 比如你有 N 個 cache 服務器（后面簡稱 cache ），那么如何將一個對象 object 映射到 N 個 cache 上呢，你很可能會采用類似下面的通用方法計算 object 的 hash 值，然后均勻的映射到到 N 個 cache ； hash(object)%N 一切都運行正常，再考慮如下的兩種情況； 1. 一個 cache 服務器 m down 掉了（在實際應用中必須要考慮這種情況），這樣所有映射到 cache m 的對象都會失效，怎么辦，需要把 cache m 從 cache 中移除，這時候 cache 是 N-1 臺，映射公式變成了 hash(object)%(N-1) ； 2. 由于訪問加重，需要添加 cache ，這時候 cache 是 N+1 臺，映射公式變成了 hash(object)%(N+1) ； 1 和 2 意味著什么？這意味著突然之間幾乎所有的 cache 都失效了。對于服務器而言，這是一場災難，洪水般的訪問都會直接沖向后臺服務器；再來考慮第三個問題，由于硬件能力越來越強，你可能想讓后面添加的節點多做點活，顯然上面的 hash 算法也做不到。 有什么方法可以改變這個狀況呢，這就是consistent hashing。 ### hash 算法和單調性 Hash 算法的一個衡量指標是單調性（ Monotonicity ），定義如下： 單調性是指如果已經有一些內容通過哈希分派到了相應的緩沖中，又有新的緩沖加入到系統中。哈希的結果應能夠保證原有已分配的內容可以被映射到新的緩沖中去，而不會被映射到舊的緩沖集合中的其他緩沖區。 容易看到，上面的簡單 hash 算法 hash(object)%N 難以滿足單調性要求。 ### consistent hashing 算法的原理 consistent hashing 是一種 hash 算法，簡單的說，在移除 / 添加一個 cache 時，它能夠盡可能小的改變已存在 key 映射關系，盡可能的滿足單調性的要求。 下面就來按照 5 個步驟簡單講講 consistent hashing 算法的基本原理。 ##### 環形hash 空間 考慮通常的 hash 算法都是將 value 映射到一個 32 為的 key 值，也即是 0~2^32-1 次方的數值空間；我們可以將這個空間想象成一個首（ 0 ）尾（ 2^32-1 ）相接的圓環，如下面圖 1 所示的那樣。  圖 1 環形 hash 空間 ##### 把對象映射到hash 空間 接下來考慮 4 個對象 object1~object4 ，通過 hash 函數計算出的 hash 值 key 在環上的分布如圖 2 所示。 hash(object1) = key1; … … hash(object4) = key4;  圖 2 4 個對象的 key 值分布 ##### 把cache 映射到hash 空間 Consistent hashing 的基本思想就是將對象和 cache 都映射到同一個 hash 數值空間中，并且使用相同的hash 算法。 假設當前有 A,B 和 C 共 3 臺 cache ，那么其映射結果將如圖 3 所示，他們在 hash 空間中，以對應的 hash值排列。 hash(cache A) = key A; … … hash(cache C) = key C;  圖 3 cache 和對象的 key 值分布 說到這里，順便提一下 cache 的 hash 計算，一般的方法可以使用 cache 機器的 IP 地址或者機器名作為hash 輸入。 ##### 把對象映射到cache 現在 cache 和對象都已經通過同一個 hash 算法映射到 hash 數值空間中了，接下來要考慮的就是如何將對象映射到 cache 上面了。 在這個環形空間中，如果沿著順時針方向從對象的 key 值出發，直到遇見一個 cache ，那么就將該對象存儲在這個 cache 上，因為對象和 cache 的 hash 值是固定的，因此這個 cache 必然是唯一和確定的。這樣不就找到了對象和 cache 的映射方法了嗎？！ 依然繼續上面的例子（參見圖 3 ），那么根據上面的方法，對象 object1 將被存儲到 cache A 上； object2和 object3 對應到 cache C ； object4 對應到 cache B ； ##### 考察cache 的變動 前面講過，通過 hash 然后求余的方法帶來的最大問題就在于不能滿足單調性，當 cache 有所變動時，cache 會失效，進而對后臺服務器造成巨大的沖擊，現在就來分析分析 consistent hashing 算法。 ###### 移除 cache 考慮假設 cache B 掛掉了，根據上面講到的映射方法，這時受影響的將僅是那些沿 cache B 逆時針遍歷直到下一個 cache （ cache C ）之間的對象，也即是本來映射到 cache B 上的那些對象。 因此這里僅需要變動對象 object4 ，將其重新映射到 cache C 上即可；參見圖 4 。  圖 4 Cache B 被移除后的 cache 映射 ###### 添加 cache 再考慮添加一臺新的 cache D 的情況，假設在這個環形 hash 空間中， cache D 被映射在對象 object2 和object3 之間。這時受影響的將僅是那些沿 cache D 逆時針遍歷直到下一個 cache （ cache B ）之間的對象（它們是也本來映射到 cache C 上對象的一部分），將這些對象重新映射到 cache D 上即可。 因此這里僅需要變動對象 object2 ，將其重新映射到 cache D 上；參見圖 5 。  圖 5 添加 cache D 后的映射關系 #### 虛擬節點 考量 Hash 算法的另一個指標是平衡性 (Balance) ，定義如下： ##### 平衡性 平衡性是指哈希的結果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。 hash 算法并不是保證絕對的平衡，如果 cache 較少的話，對象并不能被均勻的映射到 cache 上，比如在上面的例子中，僅部署 cache A 和 cache C 的情況下，在 4 個對象中， cache A 僅存儲了 object1 ，而 cache C 則存儲了 object2 、 object3 和 object4 ；分布是很不均衡的。 為了解決這種情況， consistent hashing 引入了“虛擬節點”的概念，它可以如下定義： “虛擬節點”（ virtual node ）是實際節點在 hash 空間的復制品（ replica ），一實際個節點對應了若干個“虛擬節點”，這個對應個數也成為“復制個數”，“虛擬節點”在 hash 空間中以 hash 值排列。 仍以僅部署 cache A 和 cache C 的情況為例，在圖 4 中我們已經看到， cache 分布并不均勻。現在我們引入虛擬節點，并設置“復制個數”為 2 ，這就意味著一共會存在 4 個“虛擬節點”， cache A1, cache A2 代表了 cache A ； cache C1, cache C2 代表了 cache C ；假設一種比較理想的情況，參見圖 6 。  圖 6 引入“虛擬節點”后的映射關系 此時，對象到“虛擬節點”的映射關系為： objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ； 因此對象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache C 上；平衡性有了很大提高。 引入“虛擬節點”后，映射關系就從 { 對象 -> 節點 } 轉換到了 { 對象 -> 虛擬節點 } 。查詢物體所在 cache時的映射關系如圖 7 所示。  圖 7 查詢對象所在 cache “虛擬節點”的 hash 計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 cache A 的 IP 地址為202.168.14.241 。 引入“虛擬節點”前，計算 cache A 的 hash 值： Hash(“202.168.14.241”); 引入“虛擬節點”后，計算“虛擬節”點 cache A1 和 cache A2 的 hash 值： Hash(“202.168.14.241#1”); // cache A1 Hash(“202.168.14.241#2”); // cache A2