[發(fā)明專利]一種基于Pyramid碼的局部性修復(fù)編碼方法

有效

• 申請?zhí)枺?/td>: 201710071734.2
• 申請日: 2017-02-09
• 公開（公告）號: CN106776112B
• 公開（公告）日: 2019-08-02
• 發(fā)明（設(shè)計）人: 王靜;張崇;楊洋
• 申請（專利權(quán)）人: 長安大學(xué)
• 主分類號: G06F11/10
• 分類號: G06F11/10;H04L29/08
• 代理公司: 西安恒泰知識產(chǎn)權(quán)代理事務(wù)所 61216
• 代理人: 李婷

本發(fā)明公開了一種基于Pyramid碼的局部性修復(fù)編碼方法，將Pyramid碼的最小編碼結(jié)構(gòu)C作為基本編碼結(jié)構(gòu)，把分布式存儲系統(tǒng)的存儲節(jié)點根據(jù)Pyramid碼的最小編碼結(jié)構(gòu)所需存儲節(jié)點數(shù)進(jìn)行分組。同時，本發(fā)明還公開了一種基于Pyramid碼的局部性修復(fù)編碼方法修復(fù)故障存儲節(jié)點的方法。在本發(fā)明構(gòu)造的基于Pyramid碼的局部性修復(fù)編碼結(jié)構(gòu)中，局部修復(fù)組內(nèi)存儲節(jié)點的校驗塊全部由局部修復(fù)組內(nèi)存儲的數(shù)據(jù)塊進(jìn)行局部編碼生成，基于此編碼結(jié)構(gòu)，當(dāng)局部修復(fù)組中存在單節(jié)點和兩節(jié)點故障時，都只需要通過連接局部修復(fù)組內(nèi)有限的存活節(jié)點快速實現(xiàn)局部修復(fù)組內(nèi)故障節(jié)點的數(shù)據(jù)重構(gòu)，恢復(fù)出故障存儲節(jié)點數(shù)據(jù)。

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

本發(fā)明屬于計算機(jī)領(lǐng)域，涉及一種基于Pyramid碼的局部性修復(fù)編碼方法。

背景技術(shù)

當(dāng)前分布式存儲系統(tǒng)通常采用糾刪碼提高存儲可靠性，其中最大距離可分(Maximum Distance Separable,MDS)碼，在確保系統(tǒng)可靠性的同時，能提高系統(tǒng)的存儲效率。然而，糾刪碼在修復(fù)故障節(jié)點時需要下載整個文件大小的數(shù)據(jù)量，修復(fù)帶寬開銷過大。為了降低傳統(tǒng)糾刪碼的修復(fù)帶寬開銷，Dimakis等人提出了再生碼，顯著降低了故障節(jié)點的修復(fù)帶寬開銷。通過對修復(fù)帶寬和存儲開銷進(jìn)行分析，Dimakis等人于2010年又提出了最小存儲再生(Minimum Storage Regeneration,MSR)碼和最小帶寬再生(Minimum BandwidthRegeneration,MBR)碼。簡單再生碼(Simple Regenerating Codes)以較高的存儲開銷為代價，在修復(fù)單節(jié)點故障時具有較好的修復(fù)局部性，但沒有進(jìn)一步考慮多故障節(jié)點的修復(fù)。MSR碼和MBR碼在修復(fù)故障節(jié)點時，只關(guān)注了修復(fù)帶寬開銷和存儲開銷，沒有考慮磁盤存儲開銷，不適用于云存儲系統(tǒng)。

云存儲系統(tǒng)中兩個或多個節(jié)點同時發(fā)生故障的概率很大，已有的SRC和LRC在修復(fù)一個節(jié)點故障時具有很好的修復(fù)局部性，但是在修復(fù)兩個或多個故障節(jié)點時需要連接多個存活節(jié)點，磁盤I/O開銷較高。

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

針對上述現(xiàn)有技術(shù)中存在的缺陷或不足，本發(fā)明的目的在于，提供一種基于Pyramid碼的局部性修復(fù)編碼方法，該方法可以降低故障節(jié)點修復(fù)過程中的磁盤I/O開銷，且具有較優(yōu)的節(jié)點存儲開銷。

為了實現(xiàn)上述目的，本發(fā)明采用如下技術(shù)方案：

一種基于Pyramid碼的局部性修復(fù)編碼方法，具體包括以下步驟：

分布式存儲系統(tǒng)中存儲節(jié)點數(shù)目眾多，設(shè)其中有n個存儲節(jié)點存儲數(shù)據(jù)塊，將每8個存儲節(jié)點作為一個最小編碼結(jié)構(gòu)C，每個最小編碼結(jié)構(gòu)C視為一個局部修復(fù)組，則C＝D·G，D＝[d₁₁,d₁₂,...,d_ij,...,d_tj]，d_ij為第i個局部修復(fù)組存儲的j個數(shù)據(jù)塊，i表示第i個局部修復(fù)組，i≤t，j表示局部修復(fù)組內(nèi)存儲的數(shù)據(jù)塊數(shù)目，1≤j≤4且為整數(shù)，G＝[I|P]表示生成C所需的生成矩陣，其中I為單位矩陣，P為子矩陣，

其中g(shù)₁₂、g₁₃、g₂₁、g₂₄、g₃₁、g₃₄、g₄₂和g₄₃為Pyramid碼的編碼系數(shù)，且各列之間g線性獨立，保證子矩陣P滿秩，所述校驗塊為數(shù)據(jù)塊經(jīng)過生成矩陣G線性編碼生成；

根據(jù)Pyramid碼編碼方式和魯棒性得到Pyramid碼的最小編碼結(jié)構(gòu)C，將所述Pyramid碼的最小編碼結(jié)構(gòu)C作為基本編碼結(jié)構(gòu)，把分布式存儲系統(tǒng)的存儲節(jié)點根據(jù)Pyramid碼的最小編碼結(jié)構(gòu)所需存儲節(jié)點數(shù)進(jìn)行分組。若存儲節(jié)點個數(shù)n剛好能被8整除，則直接在每個局部修復(fù)組內(nèi)采用Pyramid碼進(jìn)行編碼；若存儲節(jié)點個數(shù)n不能被8整除，則將最后一組存儲節(jié)點和不能整除所得余數(shù)放在一組并采用MDS碼進(jìn)行編碼。