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

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

[[222254]]

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

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

哈希函數(shù)

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

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

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

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

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

332115198597019796159838990710599741918

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

332115198597019796159838990710599741918 % 4 = 2

因?yàn)橛鄶?shù)是2，所以對(duì)象將被存儲(chǔ)在磁盤2。

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

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

一致性哈希算法

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

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

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

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

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

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