[發(fā)明專利]一種用于分布式存儲系統(tǒng)節(jié)點(diǎn)修復(fù)的編碼方法

有效

• 申請?zhí)枺?/td>: 201611078518.2
• 申請日: 2016-11-29
• 公開（公告）號: CN106790408B
• 公開（公告）日: 2019-08-09
• 發(fā)明（設(shè)計(jì)）人: 袁帥;黃勤
• 申請（專利權(quán)）人: 中國空間技術(shù)研究院
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 中國航天科技專利中心 11009
• 代理人: 陳鵬

1.一種用于分布式存儲系統(tǒng)節(jié)點(diǎn)修復(fù)的編碼方法，其特征在于包括如下步驟：

(1)提取當(dāng)前分布式存儲系統(tǒng)所采用的糾刪碼參數(shù)，使用糾刪碼參數(shù)對原始信息進(jìn)行編碼并分別存儲在分布式存儲系統(tǒng)；

所述的提取當(dāng)前分布式存儲系統(tǒng)所采用的糾刪碼參數(shù)，使用糾刪碼參數(shù)對原始信息進(jìn)行編碼并分別存儲在分布式存儲系統(tǒng)的方法為：提取當(dāng)前分布式存儲系統(tǒng)所采用的糾刪碼參數(shù)，假設(shè)當(dāng)前分布式存儲系統(tǒng)采用系統(tǒng)型糾刪碼參數(shù)(n,k,r)，n表示系統(tǒng)型糾刪碼碼長，k表示系統(tǒng)型糾刪碼碼字中信息維度，r表示系統(tǒng)型糾刪碼碼字中校驗(yàn)信息個(gè)數(shù)，n＝r+k，在當(dāng)前分布式存儲系統(tǒng)中原始信息被分為k個(gè)數(shù)據(jù)段，然后利用參數(shù)為(n,k,r)的系統(tǒng)型糾刪碼將原始信息的k個(gè)數(shù)據(jù)段編碼成n個(gè)數(shù)據(jù)段，編碼后的n個(gè)數(shù)據(jù)段分別存儲在分布式存儲系統(tǒng)的n個(gè)離散節(jié)點(diǎn)中；所述的分布式存儲系統(tǒng)包括n個(gè)節(jié)點(diǎn)，k個(gè)系統(tǒng)節(jié)點(diǎn)，r個(gè)校驗(yàn)節(jié)點(diǎn)，采用的r個(gè)維度為k的編碼向量為p₁、p₂、…、p_r；

(2)生成多組分布式存儲系統(tǒng)編碼模型；

所述的生成多組分布式存儲系統(tǒng)編碼模型的方法為：引入變量s、p，用維度為k的向量u＝[u₁,u₂,…,u_k]代表分布式存儲系統(tǒng)需要編碼的原始信息，進(jìn)而得到當(dāng)i不大于k時(shí)分布式存儲系統(tǒng)中第i個(gè)節(jié)點(diǎn)存儲的數(shù)據(jù)用u_i表示，當(dāng)i大于k時(shí)分布式存儲系統(tǒng)中第i個(gè)節(jié)點(diǎn)存儲的數(shù)據(jù)用表示，i＝1,2,3,…,k,k+1,k+2,…,n，得到分布式存儲系統(tǒng)中各個(gè)節(jié)點(diǎn)存儲的數(shù)據(jù)分別用表示，并作為編碼模型，遍歷s+p次，得到s+p組編碼模型；其中，第j組編碼模型記為u_j＝[u_j,1,u_j,2,…,u_j,k]表示第j組編碼模型使用的原始信息代表向量，u_j,x表示u_j中的第x個(gè)原始信息，s表示保護(hù)列的列數(shù)，p表示設(shè)計(jì)列的列數(shù)，x＝1,2,…,k，j＝1,2,…,s+p，s為保護(hù)列的列數(shù)，p為設(shè)計(jì)列的列數(shù)；

(3)生成擴(kuò)展后的存儲結(jié)構(gòu)，其中，擴(kuò)展后的存儲結(jié)構(gòu)中每一行分別代表分布式存儲系統(tǒng)中的每一個(gè)存儲節(jié)點(diǎn)；

所述的生成擴(kuò)展后的存儲結(jié)構(gòu)的方法為：將第j組作為當(dāng)前分布式存儲系統(tǒng)擴(kuò)展后的存儲結(jié)構(gòu)的第j列，遍歷所有j的取值，得到擴(kuò)展后的存儲結(jié)構(gòu)，擴(kuò)展后的存儲結(jié)構(gòu)中每一行分別代表分布式存儲系統(tǒng)中的每一個(gè)存儲節(jié)點(diǎn)，將擴(kuò)展后的存儲結(jié)構(gòu)中第1到第k行的第1到第s列作為區(qū)域A，將第1到第k+1行的第s+1到第s+p列作為區(qū)域B，將擴(kuò)展后的存儲結(jié)構(gòu)中第k+1到第k+r行的第1到第s列作為區(qū)域C，將擴(kuò)展后的存儲結(jié)構(gòu)中第k+2到第k+r行的第s+1到第s+p列作為區(qū)域D；

(4)根據(jù)擴(kuò)展后的存儲結(jié)構(gòu)生成附加信息構(gòu)造矩陣，當(dāng)分布式存儲系統(tǒng)中系統(tǒng)節(jié)點(diǎn)數(shù)據(jù)損壞時(shí)，使用附加信息構(gòu)造矩陣完成當(dāng)前損壞節(jié)點(diǎn)修復(fù)；

所述的根據(jù)擴(kuò)展后的存儲結(jié)構(gòu)生成附加信息構(gòu)造矩陣，當(dāng)分布式存儲系統(tǒng)中系統(tǒng)節(jié)點(diǎn)數(shù)據(jù)損壞時(shí)，使用附加信息構(gòu)造矩陣完成當(dāng)前損壞節(jié)點(diǎn)修復(fù)的方法包括如下步驟：

(41)計(jì)算generalized piggybacking code的歸一化修復(fù)帶寬函數(shù)γ為

其中，

定義保護(hù)列、設(shè)計(jì)列的比例為

求出γ的下界為

將γ的下界記為Γ_low(p_p)，進(jìn)而得到

其中，s為保護(hù)列的列數(shù)，p為設(shè)計(jì)列的列數(shù)；

(42)求出Γ_low(p_p)關(guān)于p_p的偏導(dǎo)數(shù)為

然后令Γ_low(p_p)關(guān)于p_p的偏導(dǎo)數(shù)為0，確定Γ_low(p_p)取為正數(shù)的極小值時(shí)p_p的值為

(43)如果不是0.25的倍數(shù)，則在左側(cè)選取兩個(gè)與最近且為0.25倍數(shù)的數(shù)，記為d1、d2，在右側(cè)選取兩個(gè)與最近且為0.25倍數(shù)的數(shù)，記為d3、d4，進(jìn)而得到4組變量s、p取值，并記為(s1,p1)、(s2,p2)、(s3,p3)、(s4,p4)，其中，若(s1,p1)、(s2,p2)、(s3,p3)、(s4,p4)中存在1組取值令γ最小，將該組取值作為變量s、p取值，若(s1,p1)、(s2,p2)、(s3,p3)、(s4,p4)中存在至少兩組取值令γ最小且s+p的取值不等，將令γ最小且s+p最小的取值作為變量s、p取值，若(s1,p1)、(s2,p2)、(s3,p3)、(s4,p4)中存在至少兩組取值令γ最小且s+p的取值相等，從令令γ最小且s+p的取值相等的至少兩組取值中任選1組作為變量s、p取值；

如果是0.25的倍數(shù)，則將表示為最簡分?jǐn)?shù)，將最簡分?jǐn)?shù)的分子作為變量s取值，最簡分?jǐn)?shù)的分母減去分子作為變量p取值；

(44)根據(jù)步驟(43)得到的變量s、p取值，建立一個(gè)的附加信息構(gòu)造矩陣，從擴(kuò)展后的存儲結(jié)構(gòu)A區(qū)中按行依次取出數(shù)據(jù)，并按行將取出的數(shù)據(jù)依次填充到附加信息構(gòu)造矩陣的對應(yīng)位置，當(dāng)A區(qū)所有的數(shù)據(jù)被取出并填充到附加信息構(gòu)造矩陣后，把附加信息構(gòu)造矩陣的(r-1)p個(gè)列的值進(jìn)行疊加，進(jìn)而得到(r-1)p個(gè)累加值，將這些累加值命名為附加信息，然后按任意順序把(r-1)p個(gè)附加信息分別與擴(kuò)展后的存儲結(jié)構(gòu)D區(qū)的(r-1)p個(gè)校驗(yàn)數(shù)據(jù)相加，并分別替換存儲結(jié)構(gòu)D區(qū)的(r-1)p個(gè)校驗(yàn)數(shù)據(jù)，完成用于分布式存儲系統(tǒng)節(jié)點(diǎn)修復(fù)的編碼，其中，當(dāng)分布式存儲系統(tǒng)中一個(gè)系統(tǒng)節(jié)點(diǎn)數(shù)據(jù)損壞時(shí)，下載所有B區(qū)健全節(jié)點(diǎn)數(shù)據(jù)，進(jìn)而通過譯碼得到當(dāng)前損壞節(jié)點(diǎn)的B區(qū)數(shù)據(jù)，從D區(qū)下載與A區(qū)當(dāng)前損壞節(jié)點(diǎn)中相關(guān)的數(shù)據(jù)，得到A區(qū)當(dāng)前損壞節(jié)點(diǎn)相關(guān)的附加信息與校驗(yàn)數(shù)據(jù)的疊加，將附加信息與校驗(yàn)數(shù)據(jù)的疊加分別與D區(qū)的原始校驗(yàn)數(shù)據(jù)、A區(qū)健全數(shù)據(jù)做差，進(jìn)而得到當(dāng)前損壞節(jié)點(diǎn)的A區(qū)數(shù)據(jù)，完成當(dāng)前損壞節(jié)點(diǎn)修復(fù)。