[發明專利]一種用于分布式存儲系統節點修復的編碼方法

有效

• 申請號: 201611078518.2
• 申請日: 2016-11-29
• 公開（公告）號: CN106790408B
• 公開（公告）日: 2019-08-09
• 發明（設計）人: 袁帥;黃勤
• 申請（專利權）人: 中國空間技術研究院
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 中國航天科技專利中心 11009
• 代理人: 陳鵬

一種用于分布式存儲系統節點修復的編碼方法，首先提取分布式存儲系統的編碼參數并構建存儲系統的編碼模型，引入保護列、設計列，得到擴展后的編碼模型，然后根據歸一化修復帶寬的偏導確定兩者的比例，進而得到保護列、設計列取值，最后根據保護列、設計列取值建立附加信息構造矩陣并完成附加信息的構造，將附加信息疊加到設計列的檢驗信息之上，完成generalized piggybacking code的編碼構造。本發明沒有額外存儲開銷，在節點修復過程中能夠保持存儲系統原先的譯碼特性不變，另外在節點修復過程中不需要復雜的矩陣運算，只需要簡單的線性疊加運算，復雜度低，便于實現，具有很好的實用價值。

技術領域

本發明涉及分布式存儲領域，特別是一種用于分布式存儲系統節點修復的編碼方法。

背景技術

分布式存儲系統因其投入成本低，存儲效率高等優點而廣泛被大型網絡應用所采納，但是受到頻發的故障、維護等因素的影響，分布式存儲系統各個分離的存儲節點的可靠性已經成為影響分布式存儲系統性能的重要因素。目前，以糾刪碼為代表的差錯控制編碼技術已經應用到分布式存儲系統中。

最大距離可分(Maximum distance separable，MDS)碼是一種最常用于存儲系統的糾刪碼技術，在一個參數為(n,k,d)的MDS碼中，n代表碼長，k為信息的維度，它的最小漢明距離是d＝n-k+1。對于固定的參數n和k，MDS碼的最小漢明距離d＝n-k+1達到了最大的可能取值，因此最大距離可分碼可以糾正碼字中多達(n-k)個刪除錯誤。使用參數為(n,k)的最大距離可分碼進行編碼的分布式存儲系統如圖1所示，該分布式存儲系統首先將待存儲的原始數據分割成k個信息片段，然后使用(n,k)最大距離可分碼編碼成n個信息片段，最后再將這n個信息片段分散的存儲在n個分離的節點中去。這樣便可以用系統中任意k個節點信息恢復出原始數據，換言之，整個系統可以抵抗任意(n-k)的節點的損壞。

通過引入冗余信息，整個系統的可靠性有了大幅度的提升。當一些節點損壞后，利用健全節點的數據來恢復損壞節點內丟失的數據的節點修復技術也成為了保持整個分布式存儲系統可靠性的一個最主要的手段。節點修復的示意圖如圖2所示，衡量一個節點修復技術性能的一個關鍵指標叫做“修復帶寬”，修復帶寬是指為了修復分布式存儲系統中的單個損壞節點而需要從其他健全節點獲取的數據量。

對于采用MDS編碼的分布式存儲系統，當然可以利用MDS碼自身的刪除修復特性來進行節點修復，但是這個過程的修復帶寬比較大：假如采用參數為(n,k)的MDS編碼的分布式存儲的一個存儲節點發生損毀，利用剩下任意k個健全節點的數據就能恢復出整個文件系統，從而修復了損毀節點的數據。可見此過程的修復帶寬為k個節點的數據量，相當于原始存儲信息的大小。當前有很多研究者都致力于分布式存儲系統的節點修復的方法的研究，其中具有代表性的工作是再生碼(Regenerating Codes)。2010年美國南加州大學的A.G.Dimakis教授提出了用再生碼來減少分布式存儲系統修復節點數據時所需要的修復帶寬。再生碼利用網絡編碼的思想，將存儲和修復過程轉化為多播問題，并利用圖論中的最大流最小割理論推導出了再生碼可以達到的修復帶寬的理論下界。但是再生碼在面對實際系統的使用存在幾個很大的問題：1、再生碼不能在存儲系統原有的編碼基礎上升級，而是要重新設計部署整個系統，系統改造成本較大；2、再生碼并不是對所有碼參數(n,k為任意滿足n>k的整數)都有效；3、再生碼的構造過程復雜，其修復過程的計算復雜度也很大，因此目前幾乎沒有采用再生碼的分布式存儲系統。

發明內容

本發明解決的技術問題是：克服現有技術的不足，提供了一種用于分布式存儲系統節點修復的編碼方法。

本發明的技術解決方案是：一種用于分布式存儲系統節點修復的編碼方法，包括如下步驟：

(1)提取當前分布式存儲系統所采用的糾刪碼參數，使用糾刪碼參數對原始信息進行編碼并分別存儲在分布式存儲系統；

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