[發明專利]平方部分重復碼構造方法、節點修復方法及容量計算方法

有效

• 申請號: 202110349037.5
• 申請日: 2021-03-31
• 公開（公告）號: CN112799605B
• 公開（公告）日: 2021-06-29
• 發明（設計）人: 朱兵;曾志偉;趙旭煜;王偉平;王建新
• 申請（專利權）人: 中南大學
• 主分類號: G06F3/06
• 分類號: G06F3/06;G06F11/10;H03M13/03;H04L29/08
• 代理公司: 長沙永星專利商標事務所(普通合伙) 43001
• 代理人: 周詠;米中業

本發明公開了一種平方部分重復碼構造方法，包括對原數據文件進行MDS編碼，得到若干個編碼塊；處理得到的編碼塊，并將其劃分成不同的集合；按照設定參數，對存儲系統進行劃分，得到若干個存儲節點集群；將不同的編碼塊存儲到存儲節點集群中，構造出平方部分重復碼。本發明還公開了一種基于所述的平方部分重復碼構造方法的節點修復方法及容量計算方法。本發明方法構造簡單、節點修復開銷小并且修復局部度較小。

技術領域

本發明具體涉及一種平方部分重復碼構造方法、節點修復方法及容量計算方法。

背景技術

隨著計算機技術的飛速發展和網絡應用的不斷普及，網絡信息量呈現出爆炸性的增長。在當今大數據時代，日益增長的海量數據對存儲系統提出了嚴峻的挑戰。傳統集中式的文件系統已經無法滿足大數據的存儲和處理需求，因此建立支持海量數據存儲的新型文件系統已經成了大數據領域的一個重要研究課題。近年來，云計算技術的不斷發展使得分布式存儲技術成為一種有效的海量數據存儲解決方案。分布式存儲系統采用云計算的理念，通過集群網格技術和分布式文件系統等功能，將分布在不同區域的獨立存儲設備通過網絡聯合起來進行協同工作，共同對用戶提供數據存儲和訪問功能。

實際的大規模分布式文件系統通常采用廉價的商業計算機或者存儲硬盤作為存儲節點，存儲開銷較低且具有良好的擴展性。然而，不斷擴大的系統規模增加了系統故障發生的概率，如節點離線、突發斷電等，使得存儲系統可靠性面臨嚴峻的考驗。為了保證數據的可靠性，大規模文件系統需要引入數據冗余機制。傳統的基于數據拷貝的方案簡單易于管理，并且支持高效的數據恢復。但是，傳統的數據備份機制的缺點在于存儲開銷大、存儲效率低，特別是在存儲大數據文件的時候，副本引起的開銷是不可忽略的。

研究表明，在相同冗余信息的情況下，糾刪碼技術可以大幅地提高系統的存儲效率。在當前基于糾刪碼的分布式存儲系統中，編碼方案通常采用MDS (Maximum DistanceSeparable)碼。具體來說，一個參數為(n, k)的MDS碼將大小為M的原數據文件均分成k個大小相等的數據塊，通過編碼生成n個大小相等的編碼塊，并分別存儲在n個不同節點上，其中系統中任意k個節點存儲的數據就可重構出原始文件。如圖1 MDS碼的編解碼方式示意圖所示，這一過程稱為數據重構過程，該數據重構特性稱為MDS屬性。MDS編碼技術能夠在保證系統容錯性的情況下降低存儲開銷，因此適合大文件存儲和檔案數據備份應用。特別地，RS(Reed-Solomon)碼是一種典型的滿足MDS特性的碼字。

當存儲系統中出現節點失效時，為了保持存儲系統的完整性，需要恢復該失效節點存儲的數據并存儲到替換節點中，該過程稱為節點修復過程。對傳統的MDS碼，其修復過程首先需要從k個存儲節點下載數據并重構出原文件，重新編碼出丟失的數據并存儲到新引入的節點上，如圖2 MDS碼的節點修復方式示意圖所示。但是，為了恢復一個節點丟失的數據而解碼出整個原文件，對網絡帶寬來說是一種巨大的浪費。

為了降低節點修復過程中的帶寬消耗，文獻[A. G. Dimakis, P. B. Godfrey,Y. Wu, M. Wainwright, and K. Ramchandran, “Network coding for distributedstorage systems,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4539-4551,Sep. 2010]利用網絡編碼的思想提出了再生碼(Regenerating Codes)的概念。再生碼同樣滿足MDS屬性，即系統n個節點中的任意k個節點存儲的數據可以重構出原數據文件。傳統的再生碼修復過程中，替換節點需要在剩下的n-1個可用存儲節點中隨機連接d個并分別從這d個存儲節點下載大小為β的數據，所以其修復帶寬為dβ。再生碼的節點修復過程中下載的數據量小于原文件的大小，因此修復帶寬優于RS碼。此外，Dimakis等人給出了再生碼的功能修復模型并給出了兩類最優碼字：最小存儲再生(MSR，Minimum-Storage Regenerating)碼和最小帶寬再生(MBR，Minimum-Bandwidth Regenerating)碼。