[發明專利]一種基于U-型設計的柔性部分重復碼的構造方法

有效

• 申請號: 201911134150.0
• 申請日: 2019-11-19
• 公開（公告）號: CN111125014B
• 公開（公告）日: 2023-02-28
• 發明（設計）人: 王靜;何亞錦;孫偉;沈克勤;張鑫楠
• 申請（專利權）人: 長安大學
• 主分類號: G06F16/13
• 分類號: G06F16/13;G06F16/172;G06F16/182;G06F11/10
• 代理公司: 西安恒泰知識產權代理事務所 61216
• 代理人: 李鄭建

本發明公開了一種基于U?型設計的柔性部分重復碼的構造方法，首先將原始文件M分成k個原始數據塊，對k個原始數據塊采用(n,k)系統MDS碼進行編碼，根據編碼塊數選取相關參數，構造U?型設計表，得到一個n×m的矩陣，如果同一列中元素取相同水平，則將它們置于一個區組中，形成一個數據節點。若U?型設計表是等水平設計表，則構造出的FR碼是同構的，若U?型設計表是混合水平設計表，則構造出的FR碼是異構的。該方法構造FR碼更加簡單直觀，并且可以通過調整U?型設計表的參數構造同構和異構FR碼。

技術領域

本發明屬于計算機領域，具體涉及一種基于U-型設計的柔性部分重復碼的構造方法。

背景技術

目前，社會海量數據迅速增長，如何對這些海量數據進行高效可靠的存儲成為一個重要的問題。通常所采用的分布式存儲系統，存儲容量和失效修復帶寬是衡量系統存儲性能的兩大重要指標。分布式存儲系統大多使用“復制”和“糾刪碼”的方法來確保系統的可靠性。與傳統復制相比，糾刪碼雖然節約了存儲開銷，但在節點修復過程中修復帶寬開銷過大，修復較為復雜。

針對以上問題，Dimakis等人提出了再生碼，包括最小存儲再生(Minimum StorageRegenerating,MSR)碼和最小帶寬再生(MinimumBandwidth Regenerating,MBR)碼，但上述兩種編碼的修復局部性大，計算復雜度較高。

Rouayheb和Ramchandran于2010年提出一種精確修復的部分重復(FractionalRepetition，FR)碼，能夠容忍多節點失效，復雜度低，極大提高了系統的可靠性。現有的FR碼的構造方法有許多，如利用完全圖，仿射置換等方法構造FR碼。

發明內容

針對現有技術中存在缺陷或不足，本發明的目的在于，提出一種基于U-型設計的柔性部分重復(Fractional Repetition，FR)碼的構造方法，該方法利用U-型設計表得到同構和異構FR碼。

為了實現上述任務，本發明采用如下技術方案：

一種基于U-型設計的柔性部分重復碼的構造方法，其特征在于，具體按以下步驟實施：

步驟1，將原始文件M分成k個數據塊，k≥2，對k個原始數據塊采用(n,k)MDS編碼(n≥k)，得到n個編碼數據塊c₁,c₂,...,c_k,c_k+1,...,c_n，其中，n個編碼數據塊包括k個原始數據塊和n-k個校驗數據塊；

步驟2，U-型設計表為：U((n；q₁,q₂,...,q_m)，其中，q₁,...,q_m為n的正約數(1qn)，該U-型設計表對應一個n×m矩陣：X＝(X₁,X₂,...X_m)，且滿足：

1)第i列X_i取元素q₁,q₂,...q_i，且這q_i個元素在該列中等重復出現；

2)X沒有全混雜的列，即X中沒有一列能夠由另一列通過行變換得到；

對一個U-型設計表，如果它的所有因子水平組合等重復出現，則稱之為正交表，記作L_n(q₁,...,q_m)，當對所有i＝1,...,m,q_i＝q時，記作Ln(q^m)；

步驟3，給定一個U-型設計表，若其任兩行之間有λ個位置取相同水平，則可以構造平衡不完全的區組設計(n,s,m,t,λ)；其中：

λ表示任一處理都出現在λ個區組中；