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

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

[[222254]]

那么OStorage-EOS分布式對象存儲是如何讓數(shù)據(jù)均勻分布到各個盤上的呢？原來是使用了一個算法叫做“一致性哈希（Consistent Hashing）”，并且在一致性哈?；A上做了改進，增加了權重、副本、機柜感知、地域感知等機制。

一致性哈希算法也是分布式系統(tǒng)領域的經(jīng)典算法，在很多地方都有應用，下面，我們就一起來了解一下它：

哈希函數(shù)

仔細研究一致性哈希之前，我們先來了解一下基本的哈希，舉個例子說明了我們?nèi)绾问褂霉：瘮?shù)來確定對象存儲在哪里。

先看一個定位數(shù)據(jù)相對簡單的方法，使用MD5算法來得到對象的邏輯位置的哈希值，然后除以可用的磁盤數(shù)量，得到余數(shù)。***將余數(shù)值映射到驅(qū)動器ID。

例如，對象的存儲位置為 /accountA/container1/objectX ，并且使用四個磁盤來存儲數(shù)據(jù)，我們稱之為磁盤0到磁盤3。這里我們先計算MD5值:

md5 -s /accountA/container1/objectX    
MD5 ("/account/container/object") =  
f9db0f833f1545be2e40f387d6c271de 

然后我們用哈希值（十六進制數(shù)值）除以磁盤數(shù)，取余數(shù)（取模）。以上十六進制數(shù)值轉化為十進制為：

332115198597019796159838990710599741918

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

332115198597019796159838990710599741918 % 4 = 2

因為余數(shù)是2，所以對象將被存儲在磁盤2。

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

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

一致性哈希算法

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

當一個對象需要被存儲時，先計算對象的哈希值，然后定位到環(huán)上，如圖所示“hash of object”的位置。系統(tǒng)按順時針搜索環(huán)上面下一個磁盤的哈希然后定位該磁盤，用這個磁盤存儲數(shù)據(jù)。上圖中可以看到，對象將被存儲在磁盤4。按照這種算法，哈希環(huán)上某個區(qū)間的哈希值會被映射到一個磁盤上，如圖所示，我們用不同顏色表示不同區(qū)間和它們對應的磁盤，若某個對象的哈希值落在藍色的區(qū)間內(nèi)，則它會被存儲在磁盤1上。

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

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

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

以上就是一致性哈希的基本原理，OStorage-EOS基于一致性哈希算法實現(xiàn)了數(shù)據(jù)的均勻分布，并加以改進，引入副本、權重、機柜感知、地域感知等機制，以滿足企業(yè)級用戶的需求。