[發(fā)明專利]一種基于一致性hash算法存儲(chǔ)資源的方法

有效

• 申請?zhí)枺?/td>: 201310165280.7
• 申請日: 2013-05-07
• 公開（公告）號(hào): CN103281358A
• 公開（公告）日: 2013-09-04
• 發(fā)明（設(shè)計(jì)）人: 周瑜
• 申請（專利權(quán)）人: 漢柏科技有限公司
• 主分類號(hào): H04L29/08
• 分類號(hào): H04L29/08
• 代理公司: 北京路浩知識(shí)產(chǎn)權(quán)代理有限公司 11002
• 代理人: 王瑩

技術(shù)領(lǐng)域

本發(fā)明涉及云計(jì)算技術(shù)領(lǐng)域，尤其涉及一種基于一致性hash算法存儲(chǔ)資源的方法。

背景技術(shù)

在云存儲(chǔ)中，存儲(chǔ)的資源與存儲(chǔ)位置之間的關(guān)系往往記錄在一臺(tái)元數(shù)據(jù)服務(wù)器中，在元數(shù)據(jù)服務(wù)器中往往使用hash（哈希）算法進(jìn)行處理。傳統(tǒng)的哈希算法是指一個(gè)集合M，通過某種算法，映射到另外一個(gè)較小的集合N。比如現(xiàn)在當(dāng)前存儲(chǔ)的資源有1M的文件，存儲(chǔ)在100臺(tái)機(jī)器上，1M的文件與100臺(tái)機(jī)器之間通過某種算法進(jìn)行映射，可以使用IO請求通過該算法查找文件位置。

在現(xiàn)有算法中，在集合N的樣本空間變化之后，集合M與集合N的映射關(guān)系將會(huì)發(fā)生變化，這種變化在云存儲(chǔ)中會(huì)帶來很大的影響。例如，在上述100臺(tái)機(jī)器增加到101臺(tái)時(shí)，1M文件的位置需要重新計(jì)算和定位，這種運(yùn)算量是非常大的。一旦元數(shù)據(jù)服務(wù)器死機(jī)，會(huì)導(dǎo)致云存儲(chǔ)服務(wù)中斷，而云存儲(chǔ)使用集中元數(shù)據(jù)設(shè)計(jì)的原因，主要是沒有合適的彈性哈希算法，來計(jì)算存儲(chǔ)的資源所在的存儲(chǔ)位置。傳統(tǒng)的哈希算法比較注重沖突處理，而在云存儲(chǔ)中的哈希算法，更注重hash映射空間變化之后，希望能夠盡可能地保持資源與hash值關(guān)系的穩(wěn)定。一旦能保持穩(wěn)定，則可以拋棄元數(shù)據(jù)服務(wù)器，采用無中心結(jié)構(gòu)來存儲(chǔ)資源傳統(tǒng)的hash值算法。

但是現(xiàn)有技術(shù)中的算法還無法實(shí)現(xiàn)當(dāng)用于存儲(chǔ)資源的機(jī)器數(shù)量發(fā)生改變時(shí)，仍能保持資源與hash值關(guān)系的穩(wěn)定，降低映射關(guān)系的變化。

發(fā)明內(nèi)容

（一）要解決的技術(shù)問題

針對上述缺陷，本發(fā)明要解決的技術(shù)問題是如何解決映射空間變化時(shí)降低映射關(guān)系的變化，對資源的定位產(chǎn)生盡量小的影響。

（二）技術(shù)方案

為解決上述問題，本發(fā)明提供了一種基于一致性hash算法存儲(chǔ)資源的方法，其特征在于，所述方法具體包括：

S1、從資源集合中選取元素，并計(jì)算所述元素的哈希值，計(jì)算公式為h=m%n，其中h為所述哈希值，m為資源集合M中元素的值，n為大于等于樣本空間N的值的最小2次冪；

S2、比較h與n的值的大小，如果h小于n則所述資源集合M中的資源對應(yīng)于所述樣本空間N的h值的位置，否則對應(yīng)于所述樣本空間N的h/2值的位置。

進(jìn)一步地，步驟S2中對應(yīng)于所述樣本空間N的h/2值的位置還包括：

對于寫請求，當(dāng)存儲(chǔ)系統(tǒng)中所述樣本空間N的存儲(chǔ)空間增大時(shí)，n的值變大，并在增加后的樣本空間N1的h/2位置處進(jìn)行寫操作。

進(jìn)一步地，所述步驟S2中對應(yīng)于所述樣本空間N的h/2值的位置還包括：

對于寫請求，當(dāng)存儲(chǔ)系統(tǒng)中所述樣本空間N的存儲(chǔ)空間減小時(shí)，n的值變小，并在減小后的樣本空間N2的h/2位置處進(jìn)行寫操作。

進(jìn)一步地，所述步驟S2中對應(yīng)于所述樣本空間N的h/2值的位置還包括：

對于讀請求，在所述樣本空間N的h/2位置處進(jìn)行一級查找，如果找到則直接在所述讀請求中相應(yīng)的操作位置進(jìn)行讀操作，否則繼續(xù)在所述樣本空間N的h/4位置處進(jìn)行二級查找，并循環(huán)上述操作在所述樣本空間M的h/2^s位置進(jìn)行s級查找，知道找到為止，其中s為整數(shù)且s≥3。

進(jìn)一步地，所述讀請求或?qū)懻埱笾邪x操作或?qū)懖僮鞯牟僮魑恢谩?/p>

進(jìn)一步地，在所述讀請求中相應(yīng)的操作位置進(jìn)行讀操作之后還包括根據(jù)查找到的位置對所述資源集合中元素的存儲(chǔ)位置進(jìn)行糾正。

（三）有益效果

本發(fā)明提供了一種基于一致性hash算法存儲(chǔ)資源的方法，通過對計(jì)算的hash值進(jìn)行伙伴處理，避免在映射空間發(fā)生變化后hash關(guān)系發(fā)生激烈變化，解決了云存儲(chǔ)的節(jié)點(diǎn)發(fā)生動(dòng)態(tài)變化時(shí)導(dǎo)致資源定位變化的問題，同時(shí)還能夠提高資源存儲(chǔ)和讀取的速度。

附圖說明

圖1為本發(fā)明實(shí)施例中一種基于一致性hash算法存儲(chǔ)資源的方法的步驟流程圖。

具體實(shí)施方式

下面結(jié)合附圖和實(shí)施例，對本發(fā)明的具體實(shí)施方式作進(jìn)一步詳細(xì)描述。以下實(shí)施例用于說明本發(fā)明，但不用來限制本發(fā)明的范圍。

本發(fā)明實(shí)施例中提供了本發(fā)明提供了一種基于一致性hash算法存儲(chǔ)資源的方法，步驟流程如圖1所示，具體包括以下步驟：

步驟S1：從資源集合中選取元素，并計(jì)算該元素的哈希值。

計(jì)算哈希值的公式為h=m%n，其中h為計(jì)算得到的哈希值，m為資源集合M中元素的值，n為大于等于樣本空間N的值的最小2次冪。