[科普中國]-一致性哈希

一致性哈希算法在1997年由麻省理工學院提出，是一種特殊的哈希算法，在移除或者添加一個服務器時，能夠盡可能小地改變已存在的服務請求與處理請求服務器之間的映射關系。在使用一致哈希算法后，哈希表槽位數(shù)（大?。┑母淖兤骄恍枰獙/N 個關鍵字重新映射，其中K是關鍵字的數(shù)量，N是槽位數(shù)量。然而在傳統(tǒng)的哈希表中，添加或刪除一個槽位的幾乎需要對所有關鍵字進行重新映射。一致性哈希算法實現(xiàn)了為服務器和存儲信息均實時變化的情況下較為合理地分配網(wǎng)絡緩存。

簡介一致性哈希算法是1997年在論文Consistent hashing and random trees中被提出1，在分布式系統(tǒng)中應用非常廣泛。一致性哈希是一種哈希算法，簡單地說在移除或者添加一個服務器時，此算法能夠盡可能小地改變已存在的服務請求與處理請求服務器之間的映射關系，盡可能滿足單調(diào)性的要求。在普通分布式集群中，服務請求與處理請求服務器之間可以一一對應，也就是說固定服務請求與處理服務器之間的映射關系，某個請求由固定的服務器去處理。這種方式無法對整個系統(tǒng)進行負載均衡，可能會造成某些服務器過于繁忙以至于無法處理新來的請求。而另一些服務器則過于空閑，整體系統(tǒng)的資源利用率低，并且當分布式集群中的某個服務器宕機，會直接導致某些服務請求無法處理。

進一步的改進可以利用hash算法對服務請求與處理服務器之間的關系進行映射，以達到動態(tài)分配的目的。通過hash算法對服務請求進行轉(zhuǎn)換，轉(zhuǎn)換后的結(jié)果對服務器節(jié)點值進行取模運算，取模后的值就是服務請求對應的請求處理服務器。這種方法可以應對節(jié)點失效的情況，當某個分布式集群節(jié)點宕機，服務請求可以通過hash算法重新分配到其他可用的服務器上。避免了無法處理請求的狀況出現(xiàn)。

但這種方法的缺陷也很明顯，如果服務器中保存有服務請求對應的數(shù)據(jù)，那么如果重新計算請求的hash值，會造成大量的請求被重定位到不同的服務器而造成請求所要使用的數(shù)據(jù)失效，這種情況在分布式系統(tǒng)中是非常糟糕的。一個設計良好的分布式系統(tǒng)應該具有良好的單調(diào)性，即服務器的添加與移除不會造成大量的哈希重定位，而一致性哈希恰好可以解決這個問題。一致性哈希算法將整個哈希值空間映射成一個虛擬的圓環(huán)，整個哈希空間的取值范圍為0~232-1。整個空間按順時針方向組織。0~232-1在零點中方向重合。接下來使用如下算法對服務請求進行映射，將服務請求使用哈希算法算出對應的hash值，然后根據(jù)hash值的位置沿圓環(huán)順時針查找，第一臺遇到的服務器就是所對應的處理請求服務器。當增加一臺新的服務器，受影響的數(shù)據(jù)僅僅是新添加的服務器到其環(huán)空間中前一臺的服務器（也就是順著逆時針方向遇到的第一臺服務器）之間的數(shù)據(jù)，其他都不會受到影響。綜上所述，一致性哈希算法對于節(jié)點的增減都只需重定位環(huán)空間中的一小部分數(shù)據(jù)，具有較好的容錯性和可擴展性2。

特性David Karger及其合作者列出了使得一致哈希在互聯(lián)網(wǎng)分布式緩存中非常有用的幾個特性：

冗余少

負載均衡

過渡平滑

存儲均衡

關鍵詞單調(diào)

哈希算法哈希的英文名為 hash，意思為散列，它將任意長度的輸入值通過散列算法，變換成固定長度的輸出值，這個值就是散列值，即哈希值。哈希值的輸出空間一般要比輸入空間小很多，不一樣的輸入也會散列成相同的輸出，并且不可能從散列值來唯一確定輸入值。因此，可以利用散列值的這一特點來檢驗數(shù)據(jù)的完整性。哈希表也叫做散列表，它根據(jù)已經(jīng)設定好的哈希算法和處理數(shù)據(jù)問題的計算方式，將輸入值映射到一個有限的位置空間中，這種存放記錄的數(shù)組形成的表叫做哈希表，對應的映射函數(shù)叫做哈希函數(shù)。在算法中所得到的存放空間就是哈希地址，也叫做散列地址3。

哈希算法的適應條件一致性哈希提出了在動態(tài)變化的Cache環(huán)境中，哈希算法應該滿足的4個適應條件：

均衡性（Balance）

平衡性是指哈希的結(jié)果能夠盡可能分布到所有的緩沖中去，這樣可以使得所有的緩沖空間都得到利用。很多哈希算法都能夠滿足這一條件。

單調(diào)性（Monotonicity）

單調(diào)性是指如果已經(jīng)有一些內(nèi)容通過哈希分派到了相應的緩沖中，又有新的緩沖區(qū)加入到系統(tǒng)中，那么哈希的結(jié)果應能夠保證原有已分配的內(nèi)容可以被映射到新的緩沖區(qū)中去，而不會被映射到舊的緩沖集合中的其他緩沖區(qū)。當緩沖區(qū)大小變化時一致性哈希(Consistent hashing)盡量保護已分配的內(nèi)容不會被重新映射到新緩沖區(qū)。

簡單的哈希算法往往不能滿足單調(diào)性的要求，如最簡單的線性哈希：

x → ax + b mod (P)在上式中，P表示全部緩沖的大小。不難看出，當緩沖大小發(fā)生變化時(從P1到P2)，原來所有的哈希結(jié)果均會發(fā)生變化，從而不滿足單調(diào)性的要求。

哈希結(jié)果的變化意味著當緩沖空間發(fā)生變化時，所有的映射關系需要在系統(tǒng)內(nèi)全部更新。而在P2P系統(tǒng)內(nèi)，緩沖的變化等價于Peer加入或退出系統(tǒng)，這一情況在P2P系統(tǒng)中會頻繁發(fā)生，因此會帶來極大計算和傳輸負荷。單調(diào)性就是要求哈希算法能夠應對這種情況。

分散性（Spread）

在分布式環(huán)境中，終端有可能看不到所有的緩沖，而是只能看到其中的一部分。當終端希望通過哈希過程將內(nèi)容映射到緩沖上時，由于不同終端所見的緩沖范圍有可能不同，從而導致哈希的結(jié)果不一致，最終的結(jié)果是相同的內(nèi)容被不同的終端映射到不同的緩沖區(qū)中。這種情況顯然是應該避免的，因為它導致相同內(nèi)容被存儲到不同緩沖中去，降低了系統(tǒng)存儲的效率。分散性的定義就是上述情況發(fā)生的嚴重程度。好的哈希算法應能夠盡量避免不一致的情況發(fā)生，也就是盡量降低分散性。

負載（Load）

負載問題實際上是從另一個角度看待分散性問題。既然不同的終端可能將相同的內(nèi)容映射到不同的緩沖區(qū)中，那么對于一個特定的緩沖區(qū)而言，也可能被不同的用戶映射為不同的內(nèi)容。與分散性一樣，這種情況也是應當避免的，因此好的哈希算法應能夠盡量降低緩沖的負荷。

從表面上看，一致性哈希針對的是分布式緩沖的問題，但是如果將緩沖看作P2P系統(tǒng)中的Peer，將映射的內(nèi)容看作各種共享的資源(數(shù)據(jù)，文件，媒體流等)，就會發(fā)現(xiàn)兩者實際上是在描述同一問題4。

路由算法中應用在一致性哈希算法中，每個節(jié)點(對應P2P系統(tǒng)中的Peer)都有隨機分配的ID。在將內(nèi)容映射到節(jié)點時，使用內(nèi)容的關鍵字和節(jié)點的ID進行一致性哈希運算并獲得鍵值。一致性哈希要求鍵值和節(jié)點ID處于同一值域。最簡單的鍵值和ID可以是一維的，比如從0000到9999的整數(shù)集合。

根據(jù)鍵值存儲內(nèi)容時，內(nèi)容將被存儲到具有與其鍵值最接近的ID的節(jié)點上。例如鍵值為1001的內(nèi)容，系統(tǒng)中有ID為1000，1010，1100的節(jié)點，該內(nèi)容將被映射到1000節(jié)點。

為了構建查詢所需的路由，一致性哈希要求每個節(jié)點存儲其上行節(jié)點(ID值大于自身的節(jié)點中最小的)和下行節(jié)點(ID值小于自身的節(jié)點中最大的)的位置信息(IP地址)。當節(jié)點需要查找內(nèi)容時，就可以根據(jù)內(nèi)容的鍵值決定向上行或下行節(jié)點發(fā)起查詢請求。收到查詢請求的節(jié)點如果發(fā)現(xiàn)自己擁有被請求的目標，可以直接向發(fā)起查詢請求的節(jié)點返回確認；如果發(fā)現(xiàn)不屬于自身的范圍，可以轉(zhuǎn)發(fā)請求到自己的上行/下行節(jié)點。

為了維護上述路由信息，在節(jié)點加入/退出系統(tǒng)時，相鄰的節(jié)點必須及時更新路由信息。這就要求節(jié)點不僅存儲直接相連的下行節(jié)點位置信息，還要知道一定深度(n跳)的間接下行節(jié)點信息，并且動態(tài)地維護節(jié)點列表。當節(jié)點退出系統(tǒng)時，它的上行節(jié)點將嘗試直接連接到最近的下行節(jié)點，連接成功后，從新的下行節(jié)點獲得下行節(jié)點列表并更新自身的節(jié)點列表。同樣的，當新的節(jié)點加入到系統(tǒng)中時，首先根據(jù)自身的ID找到下行節(jié)點并獲得下行節(jié)點列表，然后要求上行節(jié)點修改其下行節(jié)點列表，這樣就恢復了路由關系。

本詞條內(nèi)容貢獻者為:

孫銳 - 教授 - 合肥工業(yè)大學