一種最小存儲再生碼的編碼和存儲節點修複方法
2023-10-11 18:03:24 1
一種最小存儲再生碼的編碼和存儲節點修複方法
【專利摘要】本發明涉及一種最小存儲再生碼的編碼方法，包括如下步驟：得到n個第一數據包，表示為Si,i=1,2,...,n；設置n個存儲節點及正整數k，使n=2k；分別以所述第i個第一數據包的下一個第一數據包為起點，對其隨後連續k個第一數據包的數據頭或尾部加入設定數量的比特0，得到k個第二數據包，運算所述k個第二數據包得到一個編碼數據包；重複上述步驟得到n個編碼數據包，表示為Pi,i=1,2,...,n；將第i個第一數據包和以該第一數據包的下一個第一數據包為起點得到的編碼數據包存儲在第i個存儲節點。本發明還涉及一種修復上述編碼的存儲節點的方法。實施本發明的最小存儲再生碼的編碼和存儲節點修複方法，具有以下有益效果：其運算簡單、開銷小、修復帶寬較小。
【專利說明】一種最小存儲再生碼的編碼和存儲節點修複方法
【技術領域】
[0001]本發明涉及分布式存儲領域，更具體地說，涉及一種最小存儲再生碼的編碼和存儲節點修複方法。
【背景技術】
[0002]隨著計算機網絡應用的迅速發展，網絡信息數據量變得越來越大，海量信息存儲變得尤為重要。傳統意義的文件存儲系統已經不能滿足現有應用的大容量、高可靠性、高性能等方面的要求，分布式存儲系統以其高效的可擴展性和高可用性成為存儲海量數據的有效系統。然而在分布式存儲系統中，存儲數據的節點是不可靠的。為了能夠由不可靠的存儲節點提供可靠的存儲服務，需要在存儲系統中引入冗餘。引入冗餘最簡單的方法就是對原始數據直接備份，直接備份雖然簡單但是其存儲效率和系統可靠性不高，而通過編碼引入冗餘的方法可以提高其存儲效率。在目前的存儲系統中，編碼方法一般採用MDS碼(Maximum Distance Separable最大距離可分離),MDS碼可以達到存儲空間效率的最佳,一個(n，k)MDS糾錯碼需要將一個原始文件分成k個大小相等的模塊，並通過線性編碼生成η個互不相關的編碼模塊，由η個節點存儲不同的模塊，並滿足MDS屬性(η個編碼模塊中任意k個就可重構原始文件)。這種編碼技術在提供有效的網絡存儲冗餘中佔有重要的地位，特別適合存儲大的文件以及檔案數據備份應用。
[0003]在分布式存儲系統中，把大小為B的數據存儲在η個存儲節點中，每個存儲節點存儲的數據大小為α。數據接收者只需要連接並下載η個存儲節點中的任意k個存儲節點的數據即可恢復出原始數據B，這一過程稱為數據重建過程。RS (Reed-Solomon裡德-所羅門)碼是滿足MDS碼特性的一種碼字。當存儲系統中的存儲節點失效時，為了保持存儲系統的冗餘量，需要恢復該失效節點存儲的數據並將該數據存儲在新節點中，該過程稱為修復過程。然而，在修復過程中，RS碼首先需要下載k個存儲節點的數據並恢復出原始數據，之後為新節點編碼出失效節點的存儲數據。為了恢復一個存儲節點的數據而解碼出整個原始數據顯然對傳輸帶寬是一種浪費。`
[0004]然而，系統節點失效或者文件損耗，系統的冗餘度會隨著時間而逐漸減小，因此需要一種機制來保證系統的冗餘。文獻[R.Rodrigues and B.Liskov, 「HighAvailability in DHTs:Erasure Coding vs.Replication，，，Workshop on Peer-to-PeerSystems (IPTPS) 2005.]中提出的EC碼(Erasure Codes糾錯碼)，該碼在存儲開銷上是比較有效的，然而支持冗餘恢復所需要的通信開銷也比較大。圖1表示只要系統中有效節點數d ^ k，就可以從現有節點中獲得原始文件；圖2表示恢復失效節點所存儲內容的過程。從圖1和圖2中可以看出整個恢復過程是:1)首先從系統中的k個存儲節點中下載數據並重構原始文件；2)由原始文件再重新編碼出新的模塊，存儲在新節點上。該恢復過程表明修復任何一個失效節點所需要的網絡負載至少為k個節點所存儲的內容。
[0005]同時，為了降低修復過程中所使用的帶寬，文獻[A.G.Dimakis, P.G.Godfrey,Μ.J.Wainwright,K.Ramchandran,「Network coding for distributed storage systems，，，IEEE Proc.1NFOCOM, Anchorage, Alaska, May2007.]利用網絡編碼理論的思想提出了再生碼(RGC, Regenerating Codes), RGC碼也滿足MDS碼特性。再生碼的修復過程中，新節點需要在剩下的存儲節點中連接d個存儲節點並分別從這d個存儲節點中下載P大小的數據，所以RGC碼的修復帶寬為。同時給出了 RGC碼功能修復的模型並提出了 RGC碼的兩類最佳碼:最小存儲再生碼(MSR, Minimum - storage Regenerating)和最小修復帶寬再生碼(MBR, Minimum - bandwidth Regenerating)。RGC 碼的修復帶寬優於 RS 碼，但 RGC 的修復過程需要連接d(d>k)個存儲節點(d稱為修復節點)。另外，修復節點需要對其存儲的數據執行隨機線性網絡編碼操作。為了滿足所有編碼包是相互獨立的，RGC碼的運算需要在一個較大的有限域內。
[0006]專利PCT/CN2012/083174中提出了一種實用射影自修復碼的編碼、數據重構及修複方法。實用射影自修復碼(PPSRC,Practical Projective Self-repairing Codes)同樣具有自修復碼的兩個典型屬性:丟失的編碼模塊可從其他編碼模塊中下載少於整個文件的數據進行修復；丟失的編碼模塊從一個給定數的模塊中修復，該給定數隻與丟失了多少模塊數有關，而與具體哪些模塊丟失無關。這些屬性使得修復一個丟失模塊的負載比較低，另外由於系統中各節點地位相同、負載均衡使得在網絡的不同位置，可以獨立並發地修復不同丟失模塊。
[0007]該碼字除了滿足以上條件外還有以下特性:當一個節點失效時，可以有(n -1)/2對修復節點可供選擇；當有(n -1)/2個節點同時失效時，我們仍然可以使用剩下的(n+1)/2個節點中的2兩個節點來修復失效節點。
[0008]PPSRC碼的編碼以及自修復過程僅涉及異或運算，並不像一般自修復碼，其編碼需要計算多項式相對較複雜，PPSRC碼的計算複雜度小於PSRC碼(Pro jectiveSelf-repairing Codes射影自修復碼)。同時,PPSRC碼的修復帶寬和修復節點優於MSR碼。PPSRC碼的冗餘是可控的，適用於一般的存儲系統，PPSRC碼的重建帶寬達到最佳。
[0009]總而言之，PPSRC碼有效地減少了數據存儲節點，降低了系統數據存儲的冗餘度，很大程度上提高了實用自修復碼的使用價值。
[0010]然而，PPSRC碼也存在一定的不足之處。首先，PPSRC碼的編解碼過程較為複雜，有限域及其子域的劃分運算量相對較大，並且數據重構過程比較繁瑣；其次，在PPSRC碼中，編碼模塊是不可再分的，因此修復編碼模塊也必須是不可再分的。同時，PPSRC碼的整個編解碼過程運算複雜度較高，冗餘量雖然可控但其實還是相當大的。通常PPSRC碼存儲節點數選取非常大，對於相對小一些的文件來說就顯得完全沒有必要了。這些均增加了 PPSRC碼在實際分布式存儲系統中實施難度，該射影自修復碼通用性不強。
[0011]專利PCT/CN2012/071177中提出了一種RGC碼，該方案中修復一個丟失的編碼模塊只需要一小部分的數據量，而不需要重構整個文件。RGC碼應用線性網絡編碼思想，利用NC (Network Coding)屬性(即最大流最小割)來改善修復一個編碼模塊所需要的開銷，從網絡資訊理論上可以證明用和丟失模塊相同數據量的網絡開銷就可修復丟失模塊。
[0012]RGC碼主要思想還是利用MDS屬性，當網絡中一些存儲節點失效，也就相當於存儲數據丟失，需要從現有有效節點中下載信息來使得丟失的數據修復丟失的數據模塊，並將其存儲在新的節點上。隨著時間的推移，很多原始節點可能都會失效，一些再生的新節點可以在自身再重新執行再生過程，繼而生成更多的新節點。因此再生過程需要確保兩點:1)失效的節點間是相互獨立的，再生過程可以循環遞推；2)任意k個節點就足夠恢復原始文件。
[0013]圖2描述了當一個節點失效後的再生過程。分布式系統中η個存儲節點各自存儲α個數據，當有一個節點失效，新節點通過從其他d > k個存活節點中下載數據並用於節點再生，每個節點的下載量為β，每個存儲節點i通過一對節點Xiin, Xiout來表示，這對節點通過一個容量為該節點的存儲量(即α)的邊連接。再生過程通過一個信息流圖描述，XinW
系統中任意d個可用節點中各自收集β個數據，通過
【權利要求】
1.一種最小存儲再生碼的編碼方法，其特徵在於，包括如下步驟: A)將原始數據平均分為n個數據塊，得到n個第一數據包；所述第一數據包表示為Si, i=l, 2，...，n ;其中,所述n為偶數； B)設置n個存儲節點及正整數k，使n=2k； C)分別以第i個第一數據包的下一個第一數據包為起點，對該起點及其隨後連續k-1個第一數據包的數據頭或尾部加入設定數量的比特O，得到k個第二數據包，運算所述k個第二數據包得到一個編碼數據包；重複上述步驟得到n個編碼數據包；所述編碼數據包表示為Pi, i=l, 2，...，n ;其中，所述第一數據包的第n個和第I個是連續的，連續的k個第一數據包中一個為第n個第一數據包時，其下一個連續的第一數據包是第I個第一數據包； D)將第i個第一數據包和以該第一數據包的下一個第一數據包為起點得到的編碼數據包存儲在第i個存儲節點。
2.根據權利要求1所述的最小存儲再生碼的編碼方法，其特徵在於，所述步驟C)進一步包括如下步驟: Cl)得到k個編碼識別碼； C2)以第i個第一數據包的下一個第一數據包為起點，對該起點及跟隨其後的、連續的k_l個第一數據包分別依據其對應的編碼識別碼進行在其數據頭部或尾部添加設定數量的比特O，得到k個第二數據包；對所述k個第二數據包進行運算，得到一個編碼數據包； C3)依次分別將步驟C2)中作為起點的第一數據包之後的第一數據包作為起點,重複步驟C2)，直到得到n個編碼數據包。
3.根據權利要求2所述的最小存儲再生碼的編碼方法，其特徵在於，所述步驟Cl)進一步包括: Cll)判斷k是否素數，如是，執行步驟C12);否則，執行步驟C13)；
C12)按照
4.根據權利要求3所述的最小存儲再生碼的編碼方法，其特徵在於，所述步驟C2)進一步包括: C21)取得編碼識別碼中的最大值，即
5.根據權利要求4所述的最小存儲再生碼的編碼方法，其特徵在於，所述存儲節點中的第一數據包和編碼數據包分別存儲，表示為第i個存儲節點存儲的數據包集合為(Si, Pi)
6.根據權利要求5所述的最小存儲再生碼的編碼方法，其特徵在於，所述原始文件的數據量為η。
7.一種修復如權利要求1所述的編碼方法中存儲節點的存儲節點修複方法，其特徵在於，包括如下步驟: I)確認第i個存儲節點失效，並取得編碼識別碼； J)依次下載第i+Ι到i+k個可用存儲節點上的第一數據包，所述下載的k個存儲節點是連續的；通過對下載的k個第一數據包進行編碼異或運算得到所述第i個存儲節點的編碼數據包； K)下載第1-Ι個存儲節點的編碼數據包，並取得所述第i+Ι到第i+k-Ι個存儲節點的第一數據包，所述下載第一數據包的k-Ι個存儲節點是連續的；對下載的編碼數據包和k-1個原始數據包異或運算後得到所述第i個存儲節點的第一數據包； L)組合所述運算得到的第一數據包和編碼數據包並存入新的第i個存儲節點。
8.根據權利要求7所述的存儲節點修複方法，其特徵在於，所述步驟J)進一步包括: Jl)取出k個編碼識別碼； J2)取得編碼識別碼中的最大值，即
9.權利要求9缺失。
10.根據權利要求9所述的存儲節點修複方法，其特徵在於，所述步驟K)進一步包括:Kl)下載第1-Ι個存儲節點的編碼數據包，並取得所述第i+Ι到第i+k-ι個存儲節點的第一數據包，所述下載第一數據包的k-Ι個存儲節點是連續的； K2)對下載的第1-Ι個存儲節點編碼數據包和k-Ι個第一數據包異或運算後得到所述第i個存儲節點對應的第二數據包，即表示
【文檔編號】H04L29/08GK103688514SQ201380001960
【公開日】2014年3月26日 申請日期:2013年2月26日 優先權日:2013年2月26日
【發明者】李揮, 侯韓旭, 朱兵 申請人:北京大學深圳研究生院, 李揮