[發(fā)明專利]基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法

在審

• 申請?zhí)枺?/td>: 201310480833.8
• 申請日: 2013-10-15
• 公開（公告）號: CN103561057A
• 公開（公告）日: 2014-02-05
• 發(fā)明（設(shè)計）人: 陳康;高品;周佳祥
• 申請（專利權(quán)）人: 深圳清華大學(xué)研究院
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 深圳市鼎言知識產(chǎn)權(quán)代理有限公司 44311
• 代理人: 孔麗霞

1.一種基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于，該方法包括如下步驟：

節(jié)點創(chuàng)建步驟:?通過分布式哈希表建立各服務(wù)器節(jié)點的拓?fù)溥壿嫿Y(jié)構(gòu)，并通過一致性哈希算法，確定各個鍵key對應(yīng)的block塊所在的服務(wù)器的位置；

數(shù)據(jù)寫入步驟:?客戶端采用糾刪碼對原始數(shù)據(jù)進(jìn)行編碼，將每個鍵對應(yīng)的block塊編碼為若干個chunk塊，并通過寫操作將編碼后的若干個chunk塊存儲到多個服務(wù)器節(jié)點，其中，該若干個chunk塊包含預(yù)定數(shù)量的數(shù)據(jù)冗余塊；及

數(shù)據(jù)維護(hù)步驟:?每隔預(yù)設(shè)時間間隔，通過基于分布式哈希表的協(xié)議檢測服務(wù)器節(jié)點的增加和刪除，并依據(jù)糾刪碼的方式計算各個chunk塊所在的服務(wù)器節(jié)點的位置，維護(hù)數(shù)據(jù)冗余塊的個數(shù)保持在該預(yù)定數(shù)量。

2.如權(quán)利要求1所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于：

每個節(jié)點的服務(wù)器中存儲有一個路由表和一個數(shù)據(jù)塊表；

所述路由表存儲各個鍵對應(yīng)的block塊所在服務(wù)器的路由信息，將該block塊對應(yīng)的鍵key的id稱為RID，將服務(wù)器的id稱為NID；

所述數(shù)據(jù)塊表存儲block塊的基本信息、chunk塊的基本信息和chunk塊在服務(wù)器的文件系統(tǒng)中的存儲路徑。

3.如權(quán)利要求2所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于：

所述block塊的基本信息通過以下方式記錄，以block塊標(biāo)識block-ID為鍵key，以block塊對應(yīng)的最新的版本block-Version為值value；

所述chunk塊的基本信息通過以下方式記錄，以block-ID?+?$?+?block-Version+?$?+?chunk塊標(biāo)識chunk-ID?為鍵key，以chunk塊在服務(wù)器的文件系統(tǒng)中的存儲路徑為值value，其中，$為分割各個屬性的分割字符。

4.如權(quán)利要求2所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于：

所述路由表中，以當(dāng)前服務(wù)器的NID+2^Nk為鍵key，將這個key作為一個RID，以維護(hù)這個RID對應(yīng)的服務(wù)器編號NID為value，Nk取值為從0到log₂(N)，N為系統(tǒng)中服務(wù)器節(jié)點的個數(shù)。

5.如權(quán)利要求1所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于,?所述數(shù)據(jù)寫入步驟包括：

客戶端將block塊通過糾刪碼，產(chǎn)生m個chunk塊，其中，數(shù)據(jù)冗余塊為m-k個，m和k為預(yù)設(shè)值；

通過基于分布式哈希表的協(xié)議，從路由表中查找到鍵key對應(yīng)的服務(wù)器s1；

將第一個chunk塊傳輸?shù)綄?yīng)的服務(wù)器上，依次將后續(xù)的chunk塊傳輸?shù)絪1的后繼節(jié)點列表上；及

在數(shù)據(jù)塊表中更新block塊對應(yīng)的版本號。

6.如權(quán)利要求1所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于,?該方法還包括：

數(shù)據(jù)讀取步驟:?當(dāng)客戶端讀取一個指定鍵key對應(yīng)的block塊時，根據(jù)該指定鍵的鍵值通過讀操作從相應(yīng)的服務(wù)器節(jié)點中獲取若干個chunk塊，利用糾刪碼對獲取的若干個chunk塊進(jìn)行解碼，將獲取的若干個chunk塊還原成block塊。

7.如權(quán)利要求6所述的基于分布式哈希表和糾刪碼的數(shù)據(jù)存儲方法，其特征在于，所述數(shù)據(jù)讀取步驟包括：

通過基于分布式哈希表的協(xié)議，從路由表中找到對應(yīng)的管理該指定鍵key對應(yīng)block塊的服務(wù)器s1；

從數(shù)據(jù)塊表中獲取當(dāng)前block塊最新的版本號；

從s1及其后繼節(jié)點列表中選取k個節(jié)點，每個節(jié)點根據(jù)數(shù)據(jù)塊表中記錄的信息，查找到block塊標(biāo)識和block塊最新版本對應(yīng)的chunk塊在服務(wù)器的文件系統(tǒng)中的存儲路徑，將對應(yīng)的chunk塊返回給客戶端；及

客戶端獲取k個chunk塊，利用糾刪碼對該k個chunk塊進(jìn)行解碼，將該k個chunk塊還原成block塊。