文章出處

分布式一致性hash算法簡介

當你看到“分布式一致性hash算法”這個詞時，第一時間可能會問，什么是分布式，什么是一致性，hash又是什么。在分析分布式一致性hash算法原理之前，我們先來了解一下這幾個概念。

分布式

分布式（distributed）是指在多臺不同的服務器中部署不同的服務模塊，通過遠程調用協同工作，對外提供服務。

現有系統system，有modelA、modelB、modelC等服務模塊。現在要以集中式（集群，cluster）和分布式的方式進行部署，下面我們來看看它們部署的示意圖。

圖分布式部署示意圖

從上面的集中式示部署意圖和分布式部署示意圖中我們可以看出，集中式將一個系統的所有服務模塊部署到了不同的服務器上，構成一個集群，通過負載均衡設備對外提供服務。集中式部署就像茶水間同時有多個飲水機提供服務，服務冗余部署。分布式部署則將系統拆分成不同的服務模塊，然后將不同的服務模塊部署在不同的服務器上。

從上圖我們也可以看出，分布式部署方案中，不僅僅是分布式服務，還有分布式數據存儲、分布式靜態資源，分布式計算等。此時，可能你已經回憶起上提到的，memcached不就是一套分布式的緩存系統嗎。對，沒錯，memcached的分布式就體現在分布式數據存儲，“分布式一致性hash算法”中的“分布式”就是指緩存數據的分布性。

一致性

了解了分布式之后，一致性就好理解了。有分布式數據存儲數據，那就離不開分布式提取數據。一致性hash能保證在分布式環境中，對key進行哈希的結果或者說key與節點之間的映射關系不會受節點的增加和刪除而產生重大的變化。參考wiki中一致性hash的定義：

Consistent hashing is a special kind of hashing such that when a hash table is resized, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped because the mapping between the keys and the slots is defined by a modular operation.

大概意思就是“一致性哈希是一種特殊的哈希算法，提供了這樣的一個哈希表，當重新調整大小的時候，平均只有部分（k/n）key需要重新映射哈希槽，而不像傳統哈希表那樣幾乎所有key需要需要重新映射哈希槽”。

哈希

hash，俗稱“哈希”,也叫散列，是一種將任意長度的消息（數據）壓縮到某一固定長度的消息摘要（數據）的算法。常見的hash算法有MD5，SHA等。hash算法具有幾個重要的特性：不可逆性（即從hash值反推出原消息是不可能的）、抗沖突性（即給定消息M1,不存在另一個消息M2，使得Hash(M1)=Hash(M2)）和分布均勻性（即hash的結果是均勻分布的）。memcached中，存取數據時都要進行哈希映射。正是這這幾個特性，保證了memcached緩存中key值得唯一性。

三個詞已經介紹完了，那memcached為什么要使用分布式一致性hash算法呢，繼續看下文。

分布式一致性hash算法使用背景

我們已經知道，memcached的分布式主要在于客戶端的分布式算法。memcached客戶端就像一個網絡中的路由，經過特定的算法將數據分散的存在到memcached服務端的機器上，又從分散的memcached服務端的機器上提取數據。實際中，常見的存儲和提取數據的算法有取模算法和本文分析的一致性hash算法。

取模算法算法的原理是：

hash（key）%N

其中key 代表數據的鍵，代表memcached服務器的數量。取模的結果就是memcached客戶端要定位的memcached服務器。取模算法很明顯，結果很容易受N的影響，當服務器數量N增加或者減少的時候，原先的緩存數據定位幾乎失效，緩存數據定位失效意味著要到數據庫重新查詢，這對于高并發的系統來說是致命的。于是，人們提出了一致性hash算法，最終目的是實現在移除、添加一個memcached服務器時對已經存在的緩存數據的定位影響盡可能的降到最小。

分布式一致性hash算法的簡介和使用背景已經介紹完了，想必你對“分布式一致性hash算法”這個詞已經不陌生了，下面將開啟我們的”分布式一致性hash算法”原理的講解。

環形hash空間

通常，一個緩存數據的key經過hash后會得到一個32位的值，也就是0~2^32 - 1數值范圍。我們可以把這個數值范圍抽象成一個首尾相連環形的空間，我們稱這個空間為環形hash空間。如下圖所示：

圖環形hash空間

映射key到環形hash空間

有了環形hash空間之后，緩存數據的key經過hash后得到的值就映射到了環形hash空間。假設有key1、key2、key3、key4，經過hash后，映射到環形hash空間如下圖所示：

圖 key映射到環形hash空間

回到頂部

映射server節點到hash空間

同理，我們可以把memcached服務器抽象成網絡上的節點經過hash后映射到環形hash空間。假設有server1（可以是服務器的某些唯一標志信息，如ip等）、server2、server3，經過hash后，映射到環形hash空間如下圖所示：

圖 server節點映射到環形hash空間

回到頂部

映射key到server節點

現在緩存key和server節點都經過一致性hash算法映射到了環形hash空間，現在就可以將緩存key和server節點的關系進行映射了。順時針沿著環形hash空間，從某個緩存key開始，直到遇到一個server節點，那么該緩存key就存儲到這個server節點上。如圖：

圖 key映射到server節點

了解了key、server節點、hash空間之間的映射關系之后，現在我們已經清楚了緩存數據是怎樣分布的存儲到memcached服務器了。查找緩存數據的時候，也采用同樣的映射方法來定位。

回到頂部

添加server節點

現在我們已經知道memcached存儲和訪問數據的策略了。那么當在server集群中增加一個server節點時，對數據訪問的命中率又有什么影響呢。如下圖，我在server1和server2節點之間增加一個節點server4。

圖增加server4節點

從上圖可以看出，增加server4節點后，原有的緩存數據分布中，僅有server1~server4節點的數據進行了重新分布，這部分數據需要重新到數據庫查找再次映射到新添加的server4節點上。盡管不能命中的緩存數據仍然存在，但相對于取模算法，已經是最大限度地抑制了hash鍵的重新分布。

回到頂部

刪除server節點

同理，當在server集群中刪除server2節點時，受影響的也僅是server1~server2之間的緩存數據，這部分數據需要重新到數據庫查找再次映射到server3節點上。如下圖所示：

圖刪除server2節點

虛擬節點的引入

我們已經知道，添加和刪除節點都會影響緩存數據的分布。盡管hash算法具有分布均勻的特性，但是當集群中server數量很少時，他們可能在環中的分布并不是特別均勻，進而導致緩存數據不能均勻分布到所有的server上。為解決這個問題，需要使用虛擬節點的思想：為每個物理節點（server）在環上分配100～200個點，這樣環上的節點較多，就能抑制分布不均勻。當為cache定位目標server時，如果定位到虛擬節點上，就表示cache真正的存儲位置是在該虛擬節點代表的實際物理server上。另外，如果每個實際server節點的負載能力不同，可以賦予不同的權重，根據權重分配不同數量的虛擬節點。

虛擬節點的hash計算可以采用對應節點的 IP 地址加數字后綴的方式。例如假設 serverA 的 IP 地址為 127.0.0.1 。引入虛擬節點前，計算serverA 的 hash 值：

hash(“127.0.0.1”);

引入虛擬節點后，計算虛擬節點serverA1 和 serverA12 的 hash 值：hash(“127.0.0.1#1”);

hash(“127.0.0.1#2”);

節點變化數據分流的問題

上面討論的節點變化都會導致部分緩存數據的重新分布，hash算法還有一個重要的衡量指標：hash算法的結果能夠保證需要重新分布的緩存數據能映射到新的server節點中。

一致性hash算法與取模算法的比較

取模算法的方法簡單，數據的分散性也可以，但其主要缺點是當添加或移除server節點時，緩存重新映射的代價相當巨大。添加或移除server節點時，余數就會產生巨變，這樣就無法定位與存儲時相同的server節點，從而影響緩存的命中率。而一致性hash算法則最大限度的減少了server節點變化帶來的影響，當節點變化時，只影響一個server節點的部分數據，且hash算法能夠保證需要重新分布的緩存數據能映射到新的server節點中。