[發明專利]一種由極大距離可分存儲碼生成最小存儲再生碼的方法

有效

• 申請號: 201610237700.1
• 申請日: 2016-04-15
• 公開（公告）號: CN105721611B
• 公開（公告）日: 2019-03-01
• 發明（設計）人: 李杰;唐小虎
• 申請（專利權）人: 西南交通大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 成都信博專利代理有限責任公司 51200
• 代理人: 張澎

本發明公開了一種將系統節點具有最佳修復性質的極大距離可分存儲碼轉換成最小存儲再生碼的方法，所得的最小存儲再生碼適用于分布式存儲系統。該轉換方法所基于的極大距離可分存儲碼是非二元的，轉換過程不改變原存儲碼的字母表大小。若該轉換方法所基于的極大距離可分存儲碼的系統節點具有最佳存取性質，則轉換后得到的最小存儲再生碼具有最佳存取性質。本發明有益效果是：(I)系統的存儲開銷非常小；(II)任意一個失效節點都能被最佳修復，修復失效節點的過程中只消耗最小的帶寬資源；(III)若采用系統節點具有最佳I/O修復性質的MDS存儲碼作為基碼,修復失效節點時I/O開銷也最小。

技術領域

本發明涉及分布式存儲系統領域，特別涉及一種適用于分布式存儲系統的將系統節點具有最佳修復性質的極大距離可分存儲碼轉換成最小存儲再生碼的編碼技術。

背景技術

為提高分布式存儲系統的可靠性，冗余是不可或缺的。一般來說，有兩種增加冗余的機制：復制和糾刪。與重復碼相比，在冗余量相同的情況下糾刪碼能提供更多的可靠性，所以更具優勢。而在所有的糾刪碼中，極大距離可分(MDS)碼如Reed-Solomon碼因為在冗余量相同的情況下具有最大的糾刪錯誤能力，被廣泛用于Google Colossus、MicrosoftAzure等多個分布式云存儲系統。通常，將源文件均分成k份，采用一個(k+r,k)的MDS碼進行編碼后得到k+r份數據，然后分別存放在k+r個獨立的存儲設備上，這些設備也被稱為節點。

但是對于大型分布式云存儲系統，各個節點的可靠性不高，失效現象經常發生，節點失效會增加數據丟失的可能性、降低系統的可靠性，而其中單節點失效高達98.08％。為了維持一定的冗余量，系統會頻繁地進行節點修復，常用的修復方式是從其它存活的節點中下載數據以修復該失效節點，這些節點也被稱之為幫助節點。在修復過程中，所下載數據的量被稱為修復帶寬，實際系統中為降低開銷，修復帶寬應該最小化。然而，傳統MDS存儲碼的修復方法是連接任意k個幫助節點下載全部數據，從而重構源文件，然后再編碼產生失效節點里的數據，相應的修復帶寬最大，這給分布式存儲系統帶來極大的開銷。

文獻Network coding for distributed storage systems,IEEE Trans.onInformation Theory,vol.56,no.9,p.4539-4551,September 2010(基于網絡編碼的分布式存儲系統，IEEE信息論匯刊，第56卷，第9期，第4539-4551頁，2010年9月)確定了存儲編碼的最小修復帶寬，達到最小修復帶寬的節點被稱為具有最佳修復性質，所有節點都具有最佳修復性質被稱之為再生碼，其中最重要是兩類編碼：最小存儲再生(MSR)碼和最小修復帶寬再生(MBR)碼。

具體地，MSR編碼將一份大小為kN個元素的源文件均分成k份，每份包含N個元素，用長度為N的列向量f_i表示，0≤i<k.對原始數據編碼后得到r份校驗數據，同樣用長度為N的列向量f_i表示，k≤i<k+r。將這k+r份數據分別存放在一個包含在k+r個節點的分布式存儲系統中。一個(k+r,k)MSR碼具有：(1)MDS性質，即連接任意k個節點可以重構源文件，參見附圖1；(2)最佳修復性質，即一個失效節點的修復帶寬為γ＝dN/(d-k+1)，這可以通過連接d(k≤d≤k+r-1)個幫助節點個數，從每個幫助節點中下載N/(d-k+1)個元素實現，如附圖2所示。

特別需要指出，上述文獻中所構造的存儲碼是功能修復碼，即代替失效節點的新節點存儲的數據可以與失效節點原來的數據不一樣但在功能上等價；然而，要求代替失效節點的新節點存儲的數據與失效節點原來的數據完全一樣的精確修復MSR碼，能在實際應用中減小系統的復雜度，因而更受實際系統歡迎。此外，目前已知的精確修復MSR碼都考慮d＝k+r-1的情形來最大的減小修復帶寬。本發明也考慮這一種情況。