[發明專利]一種針對二進制編碼冗余存儲系統的低帶寬數據重構方法

有效

• 申請號: 201410048536.0
• 申請日: 2014-02-11
• 公開（公告）號: CN103761171B
• 公開（公告）日: 2017-04-05
• 發明（設計）人: 蔣海波;陳建中;李娜;周星梅;王曉京;蔣小強;陳怡;李范
• 申請（專利權）人: 中國科學院成都生物研究所
• 主分類號: G06F11/14
• 分類號: G06F11/14
• 代理公司: 成都賽恩斯知識產權代理事務所(普通合伙)51212
• 代理人: 朱月仙

技術領域

本發明涉及電子信息數據的編碼存儲技術領域，特別涉及數據在分布式基礎存儲架構上的數據容災與丟失數據低帶寬重構技術。

背景技術

隨著有線網絡技術與無線網絡技術的飛速發展，利用網絡構建分布式存儲系統已成為趨勢。然而，在邏輯上，網絡覆蓋范圍寬廣，任何節點因一些無法預測的偶發性變故都可能導致分布式系統上存儲的某些重要數據永久性丟失或損毀，如包括人為操作失誤、設備元器件故障、地震、水災、火災、臺風、乃至惡意竊取等，由此可能造成難以估量的損失；特別是用于野外監測的傳感器網絡節點，由于野外環境變化較大，有些極端環境較為惡劣，數據采集節點會出現頻繁損毀的情況，因而，如何實現已采集數據的完好保存，急需新的存儲技術，以滿足存儲數據的高可靠性存儲。

當前數據存儲主要是基于“數據備份——多機備份與熱切換”這種數據冗余機制，其技術路線的核心是文件復制技術，例如異地鏡像備份、設置不同地點的備份服務器等都是常用的方法，如谷歌存儲系統的重要文件均有3個甚至多個副本。雖然文件復制技術具有存儲操作簡單、讀取操作快速的優點，但文件復制技術路線的數據冗余高，用于“災難備份”存在著諸多弊端，若主要采用文件復制技術來防范，顯然在網絡上將有大量的備份服務器在多數時間里至少要閑置一倍乃至多倍的存儲空間，這將造成驚人的資源浪費，網絡規模越大這種浪費越巨大。

當前，基于二進制編碼冗余存儲策略已逐漸成為新型信息系統基礎存儲架構的關鍵技術。該種技術在數據中心存儲系統、野外傳感器網絡等方面具有廣闊的應用價值；對系統工作環境變化大、較為惡劣，數據節點存儲容量有限、數據容易丟失的情況具有很好的應對作用。

如越來越多的系統利用糾刪碼冗余策略存儲系統的關鍵數據。當系統采用糾刪碼時，大小為M的原文件f被分割為s個大小相同的初始分塊，每個分塊大小為M/s；由s個初始分塊計算得到大小相同的r個編碼塊，s個初始分塊和r個編碼塊組成了待存儲的數據。由初始分塊得到校驗塊的方法采用的是糾刪碼編碼技術，該種技術通常稱這種糾刪碼為“（s+r,s）糾刪碼”。對于糾刪碼冗余模式，所有的s+r個數據塊最終被存儲在s+r個不同的存儲節點中，只要故障節點數不多于r個，那么未故障節點中的數據就能恢復出原文件，因此對于參數為s和r的糾刪碼冗余，系統允許某一時刻發生故障的節點的個數最多為r。如果要修復故障節點中的數據，那么糾刪碼冗余就比復制冗余復雜多了。以編碼技術采用RS碼為例，當一個數據塊丟失時，系統需要將任意的s個未丟失數據塊傳輸到新節點中，先譯碼得到原文件，再編碼產生丟失的數據塊。

由于在恢復丟失的數據塊時，需要將任意的s個未丟失數據塊傳輸到新節點中進行譯碼，當數據量較大時，利用傳統的數據重構方法就會給存儲系統帶來巨大的網絡帶寬壓力，降低丟失數據塊恢復的時間。

發明內容

針對現有技術存在的問題，本發明的主要目的在于提供一種降低對丟失數據塊進行恢復時給存儲系統帶來的網絡帶寬壓力的針對二進制編碼冗余存儲系統的低帶寬數據重構方法。

為實現上述目的，本發明提供一種針對二進制編碼冗余存儲系統的低帶寬數據重構方法，該二進制編碼冗余存儲系統包含一編碼矩陣和一數據校驗矩陣，該數據校驗矩陣包含行向量和列向量，當二進制編碼冗余存儲系統的存儲節點發生損毀導致數據塊丟失，對丟失的數據塊進行恢復，該低帶寬數據重構方法包括如下步驟（1）至步驟（4）：

（1）建立該丟失的數據塊與該數據校驗矩陣行向量之間的對應關系，并根據二進制編碼冗余存儲系統中未丟失數據塊所對應的數據校驗矩陣的列向量所構成的子矩陣確定低帶寬校驗矩陣；

（2）判斷低帶寬校驗矩陣是否多于一個；

（3）若低帶寬校驗矩陣多于一個，則判斷利用各個低帶寬校驗矩陣對丟失數據塊進行恢復所需要的未丟失數據塊數量是否相同，即判斷利用不同低帶寬校驗矩陣對丟失數據塊進行恢復給二進制編碼冗余存儲系統各存儲節點帶來的I/O壓力是否相同；

（4）若利用不同低帶寬校驗矩陣對丟失數據塊進行恢復給二進制編碼冗余存儲系統各存儲節點帶來的I/O壓力不相同，則選擇所需重構數據塊（未丟失的數據塊）最少的，即對存儲節點I/O壓力影響最小的低帶寬校驗矩陣對丟失的數據塊進行數據重構。

進一步地，當該步驟（2）判斷低帶寬校驗矩陣只有一個，則利用該低帶寬校驗矩陣對丟失的數據塊進行數據重構。