[發(fā)明專利]一種基于調(diào)節(jié)矩陣的異構(gòu)部分重復碼的構(gòu)造方法

有效

• 申請?zhí)枺?/td>: 201911135000.1
• 申請日: 2019-11-19
• 公開（公告）號: CN110990375B
• 公開（公告）日: 2023-01-31
• 發(fā)明（設(shè)計）人: 王靜;沈克勤;孫偉;張鑫楠;何亞錦
• 申請（專利權(quán)）人: 長安大學
• 主分類號: G06F16/21
• 分類號: G06F16/21;G06F16/22;G06F16/2453;G06F16/27;G06F11/07
• 代理公司: 西安恒泰知識產(chǎn)權(quán)代理事務(wù)所 61216
• 代理人: 李鄭建

本發(fā)明公開了一種基于調(diào)節(jié)矩陣的異構(gòu)部分重復碼的構(gòu)造方法，用于構(gòu)造節(jié)點存儲容量異構(gòu)的FRC，適用于分布式存儲系統(tǒng)中節(jié)點數(shù)n為奇數(shù)的情況，且構(gòu)造的FRC中數(shù)據(jù)塊的重復度ρ等于2。考慮到實際的分布式存儲系統(tǒng)大部分具有異構(gòu)的特點，故引入基于調(diào)節(jié)矩陣的方法來構(gòu)造異構(gòu)FRC，構(gòu)造的FRC可實現(xiàn)節(jié)點存儲容量的多樣性，同時構(gòu)造的FRC相比傳統(tǒng)的再生碼，具有無編碼修復、計算復雜度低的優(yōu)點。

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

本發(fā)明屬于計算機領(lǐng)域，具體涉及一種基于調(diào)節(jié)矩陣的異構(gòu)部分重復碼(Fractional Repetition Codes，F(xiàn)RC)的構(gòu)造方法。

背景技術(shù)

在分布式存儲系統(tǒng)中，數(shù)據(jù)存儲是一個多維優(yōu)化的問題。雖然再生碼可以優(yōu)化存儲消耗和修復帶寬，但其修復過程通常涉及大量有限域的運算，計算復雜度較高，于是提出部分重復碼的概念(Fractional Repetition Codes，F(xiàn)RC)，指出了FR碼可以提供精確有效的修復，并可以提供最小的修復帶寬。其結(jié)構(gòu)包含兩個部分的內(nèi)容，一個是外部MDS碼，另一個是內(nèi)部重復碼。數(shù)據(jù)塊經(jīng)過MDS編碼后，將輸出的編碼塊復制ρ倍再分散到各存儲節(jié)點。系統(tǒng)中發(fā)生節(jié)點故障時，可以通過從其他節(jié)點直接下載數(shù)據(jù)并存儲到替換節(jié)點來完成修復，不需要額外的運算，極大程度上降低了計算復雜度。

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

針對現(xiàn)有技術(shù)中存在缺陷或不足，本發(fā)明的目的在于，提供一種基于調(diào)節(jié)矩陣的異構(gòu)部分重復碼的構(gòu)造方法，該方法滿足實際分布式存儲系統(tǒng)異構(gòu)的要求，節(jié)點存儲容量異構(gòu)，且修復過程無需編碼操作。

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

一種基于調(diào)節(jié)矩陣的異構(gòu)部分重復碼的構(gòu)造方法，其特征在于，該方法用于構(gòu)造節(jié)點存儲容量異構(gòu)的FRC，適用于分布式存儲系統(tǒng)節(jié)點數(shù)n為奇數(shù)的情況，且構(gòu)造的FRC中數(shù)據(jù)塊的重復度ρ等于2；具體步驟如下：

步驟1：首先定義一個循環(huán)置換矩陣C_n(d-1)，該矩陣是一個n×n階的二進制矩陣，其中，n代表節(jié)點數(shù)，d-1表示每個節(jié)點存儲容量同時也表示矩陣中每一行1的個數(shù)，且d需滿足的條件為d3，d為奇數(shù)；

C_n(d-1)矩陣的第一行滿足下面的表達式：

c(t)＝t+t²+…+t^(d-1)/2+t^n-(d-1)/2+…+t^n-1；

矩陣的第一行確定后，后面的每一行依次向右移動一位，共移動n-1次，最后生成C_n(d-1)矩陣；

在這里C_n(d-1)矩陣同時也是一個關(guān)聯(lián)矩陣，關(guān)聯(lián)矩陣的行對應分布式存儲系統(tǒng)中的節(jié)點，列代表存儲的數(shù)據(jù)塊，同時這個關(guān)聯(lián)矩陣與未經(jīng)過調(diào)節(jié)矩陣構(gòu)造的同構(gòu)FRC是一一對應的關(guān)系；

為了更加直觀的看出內(nèi)部FRC的存儲結(jié)構(gòu)，進一步引入正則圖存儲同構(gòu)的FRC，所述正則圖可以通過關(guān)聯(lián)矩陣C_n(d-1)得出；正則圖的頂點n也就對應FRC中的節(jié)點數(shù)，正則圖的邊代表數(shù)據(jù)塊，d-1代表節(jié)點的度；

步驟2：引入一個矩陣S_n去調(diào)節(jié)步驟1中的C_n(d-1)矩陣，S_n矩陣生成方法為：在(n-1)階副對角線都為1，其他元素全為0的矩陣后面加一行0和一列0生成S_n矩陣；