一致性哈希演算法及其在分散式存儲中的應用

OStorage的老大李明宇隨手發了一個朋友圈，是該公司企業級對象存儲產品OStorage-EOS的監控界面截圖，感慨一個200多TB的集群很快被用戶用到了92%以上。

「外行看熱鬧，內行看門道」，一位做分散式存儲的同仁看到了說：接近93%的存儲利用率，還在不停寫數據進去，說明OStorage-EOS數據分布的均勻性很好，否則，如果數據分布不夠均勻，就有可能出現其他的節點或盤還有很多空間，但某一個盤或者某一個節點寫滿了，這時還繼續寫數據進去就會出問題。

那麼OStorage-EOS分散式對象存儲是如何讓數據均勻分布到各個盤上的呢？原來是使用了一個演算法叫做「一致性哈希（Consistent Hashing）」，並且在一致性哈希基礎上做了改進，增加了權重、副本、機櫃感知、地域感知等機制。

一致性哈希演算法也是分散式系統領域的經典演算法，在很多地方都有應用，下面，我們就一起來了解一下它：

哈希函數

仔細研究一致性哈希之前，我們先來了解一下基本的哈希，舉個例子說明了我們如何使用哈希函數來確定對象存儲在哪裡。

先看一個定位數據相對簡單的方法，使用MD5演算法來得到對象的邏輯位置的哈希值，然後除以可用的磁碟數量，得到餘數。最後將餘數值映射到驅動器ID。

例如，對象的存儲位置為 /accountA/container1/objectX ，並且使用四個磁碟來存儲數據，我們稱之為磁碟0到磁碟3。這裡我們先計算MD5值:

md5-s/accountA/container1/objectX

MD5("/account/container/object")=

f9db0f833f1545be2e40f387d6c271de

然後我們用哈希值（十六進位數值）除以磁碟數，取餘數（取模）。以上十六進位數值轉化為十進位為：

332115198597019796159838990710599741918

取模函數在大多數編程語言中用%運算符表示:

332115198597019796159838990710599741918 % 4 = 2

因為餘數是2，所以對象將被存儲在磁碟2。

這種演算法最大的缺點是計算結果取決於除數也就是磁碟數量。任何時候添加或移除某個磁碟(除數變化了)，同一個對象可能得到不同的餘數，從而映射到不同的磁碟。為了說明這一點，下面的表顯示了當添加磁碟時，哪一個磁碟將成為對象新的存儲位置。

注意，幾乎每次添加新磁碟，對象都必須移動到新的磁碟上，這僅僅一個對象的情況，將這種行為推廣開來，在增加或者移除節點、磁碟時，幾乎集群中的所有數據都需要進行移動。集群將不得不花費大量資源來進行這些遷移，還將產生繁重的網路負載，以及數據不可讀取的情況。

一致性哈希演算法

當從集群中的增加或者移除磁碟、節點時，一致性哈希（Consistent Hashing）可以減少移動的對象數量。一致性哈希不是將每個值直接映射到一個磁碟，而是通過將所有可能的哈希值建模為一個環。一致性哈希演算法除了計算對象的哈希以外，還計算設備的哈希，根據磁碟的IP地址、盤符等計算哈希值，每個磁碟被映射到哈希環的某個點上，如圖所示。

當一個對象需要被存儲時，先計算對象的哈希值，然後定位到環上，如圖所示「hash of object」的位置。系統按順時針搜索環上面下一個磁碟的哈希然後定位該磁碟，用這個磁碟存儲數據。上圖中可以看到，對象將被存儲在磁碟4。按照這種演算法，哈希環上某個區間的哈希值會被映射到一個磁碟上，如圖所示，我們用不同顏色表示不同區間和它們對應的磁碟，若某個對象的哈希值落在藍色的區間內，則它會被存儲在磁碟1上。

有了這樣的哈希環，當我們添加一塊新的磁碟時，比如磁碟5，那麼圖中粉色部分將不再屬於磁碟4，因為這部分數據目前全部屬於新的磁碟5。所以這部分位於磁碟4上的對象將會被移動到磁碟5，而其他數據均不受影響。

使用這種方案，添加一個盤或者一個節點，只需要移動少量數據，比前面那種最基本的依靠計算哈希值並模除來確定數據存放位置的方案要好很多，在前面那種方案中需要移動很多數據。

在實際應用的一致性哈希演算法中，每個實際的磁碟或節點會對在環上對應到多個標記，這些標記在一些文獻中也被成為「虛節點（Virtual Node）」，實際應用中，一個磁碟會對應很多標記/虛節點，甚至每個磁碟對應數百個標記。多個標記意味著每塊磁碟對應環的哈希值範圍從一個大區域切分成了數個小區域。這樣做有兩個效果，一個效果是一個新添加的磁碟可能從多個磁碟那裡遷移對象數據，進一步降低了數據遷移的壓力，另一個效果是總體的數據分布更加的平均。

以上就是一致性哈希的基本原理，OStorage-EOS基於一致性哈希演算法實現了數據的均勻分布，並加以改進，引入副本、權重、機櫃感知、地域感知等機制，以滿足企業級用戶的需求。

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！