一種基于噴泉碼的本地數據存儲備份的方案

詹首道，龔洪波（廣東工業大學計算機學院，廣州　510006）

一種基于噴泉碼的本地數據存儲備份的方案

詹首道，龔洪波
（廣東工業大學計算機學院，廣州510006）

提出一種基于噴泉碼、網絡編碼思想的數據備份方案。該方案基于噴泉碼、網絡編碼的思想，并且具有糾刪碼的特性。在文件存儲時，將文件塊進行編碼，產生很多編碼塊，對原始文件塊和編碼塊進行挑選存儲，最后進行存儲的是原始塊與編碼塊的混合，這樣文件存儲空間會變大。數據讀取時，只需經過簡單編碼計算即可，一般都是線性運算。該方案利用空間和計算資源來換取數據的可靠性，在某種應用場景下有更好的魯棒性。

噴泉碼；網絡編碼；備份；魯棒性

國家自然科學基金項目（No.61272013）、廣東省現代信息服務業發展專項資金項目（No.GDEID2011IS022）、廣東省省部產學研合作專項資金項目（No.2013B090500007）

0　引言

隨著信息技術，尤其是人工智能、云計算的進一步發展，人們需要捕捉、管理和處理的數據正在以GB、TB甚至是PB為單位進行更新。越是龐大的數據計算，就需要越龐大的數據量。同時，存儲設備的發展同樣日新月異，大數據的爆發性增長也有了合適的存儲環境，高可靠性成為人們存儲技術的研究重點。數據的高可靠性變得更加重要，數據備份與恢復則是數據高可靠性的重要保證。

因為操作失誤、軟件故障、病毒、自然災害等［1］造成的數據丟失、損壞，每天都在發生。不同的用戶，會選擇的備份還原方案各不相同。而不同的備份方案會有不同的備份效率。數據備份與恢復是相輔相成的，數據備份的方案決定了數據恢復操作的效率與執行。

現在的技術，采用最多的備份還原技術是數據復制［2］和鏡像技術。數據復制最簡單，將文件直接在另一個存儲設備上復制一份，需要恢復時，直接讀取，操作便利。事實上，會存在一種情況就是備份是文件已經出現損壞，這樣同一數據塊就同時出錯，特別對于用于歸檔數據或用于容錯容災的目的情形［3］，更為突出。

考慮以下情景，存儲一個文件，這個文件很重要，但是并不是馬上使用，可能在幾年內都不會使用。但是，在需要使用時，發現文件出現了損壞。在恢復還原時，發現備份的文件的也同樣出現損壞。為了保證文件可以正常讀取，最簡單的方法就是在更多的設備上進行備份，而這種方法需要耗費更多的空間資源，問題卻依然存在。本文提出了一種基于噴泉碼與網絡編碼思想的數據備份技術，通過增加讀取計算和空間存儲，可以允許丟失部分數據，也能有效地讀取原文件。

1　理論基礎

時間復雜度、空間復雜度一直是算法和解決方案的優劣指標。然而，在某些情況下，空間比運算重要，有時卻相反。這樣就出現了以犧牲計算資源換取空間資源、提高效率的技術，如分布式存儲系統通過計算編碼提高了系統的性能；網絡編碼利用了中間結點的計算編碼提高了網絡的吞吐量等。下面簡要介紹與本文相關的技術理論。

1.1分布式存儲系統

分布式存儲系統將數據分散存儲在多臺獨立的設備上，利用分散在網絡上大量節點的協作實現可靠的數據存儲［5］。分布式存儲技術的主要目的是通過使用一些分布式的存儲節點（例如硬盤、無線傳感器節點和P2P網絡中的節點等）來長期地可靠地保存數據對象［6］。分布式存儲的特點有：1）高可靠性；2）高性能；3）訪問靈活；4）低成本。但同時主要有下面幾方面不足：1）還不完善的軟件體系；2）讀取的穩定性不夠；3）安全問題［5-6］。

1.2網絡編碼

在2000年由Yeung等發表的網絡編碼（Network Coding）［4］脫離了傳統網絡只能在中間節點存儲轉發的模式，提出了中間節點編碼計算的新模式。通過網絡編碼技術，提高帶寬的利用率，實現網絡吞吐的最大化。到了2003年，線性網絡中的網絡編碼的可行性［7］也被Yeung等人證明可行性。進一步研究發現，網絡編碼不單單能提高帶寬的利用率、吞吐量，均衡流量，還可以提高網絡的可靠性和安全性等［4，7］。

1.3噴泉碼

數字噴泉技術［8］最早是由Luby等于1998年提出。目前的噴泉碼有Reed Solomon編碼［9］、Luby Transform編碼［10］和Raptor編碼［11］等。

噴泉碼利用編碼計算，提高用戶接收文件的效率。目前的應用環境都與網絡相關，與本地文件的讀取無關。受到噴泉碼的啟發，本文結合網絡編碼將這種編碼思想應用在存儲備份中，將需要存儲的數據進行編碼，并增加的額外存儲空間，提高文件的可靠性。

1.4糾刪碼

目前針對數據恢復使用比較多的技術是糾刪碼。這個技術是利用原有數據，通過簡單編碼，增加少量數據冗余來實現數據恢復。當前的糾刪碼，有不同的冗余生成方案，其容錯能力、效率不一樣，如容1錯（RAID-5碼），容 2錯（EVENODD碼［12］，X碼［13］等），容多錯（STAR碼［14］，WEAVER碼［15］以及Cauchy Reed Solomon碼［16］等）。最近，文獻［17］提出了4種關于糾刪碼的新方案。這些方案的核心是通過編碼，增加數據冗余，提高數據的穩定性。

下文簡單介紹容2錯的EVENODD碼和容多錯的STAR碼。

EVENODD碼，是第一種提出的容二錯陣列碼，也是一種常見的陣列碼，其編碼是基于一個大小為（p-1）×（p+2）的陣列（P為素數）。陣列中存放原始數據的是前P列；增加了兩列存放冗余校驗數據做為校驗列。（0≤i≤p-2，0≤j≤p+1）用于表示磁盤j中的第i塊數據。將第p列，也就是兩列校驗列中的第一列稱為行校驗列，由第i行所有原始數據塊進行異或得到對應的作為該列的校驗塊；最后一列稱為對角線校驗列，將調節因子s于對應對角線上所有原始數據塊進行異或得到對應的，作為對角線校驗列的校驗塊。

因為EVENODD碼在編碼、解碼操作時使用簡單的異或操作，所以計算復雜度比較低。

STAR可以說是EVENODD碼的擴展，從容二錯擴展到容三錯，在EVENODD碼的水平校驗，對角線校驗的基礎上，增加了一個輔助對角線校驗，增加了一個校驗位，使得容錯能力提高了一位。其編碼是基于一個（p-1）×（p+2）陣列，符號（0≤i≤p-2，0≤j≤p+1）用于表示磁盤j中的第i塊數據。前P塊盤存放數據信息，第p、p+1個盤存放的與EVENODD碼存放的一樣，都是行校驗與對角線校驗，區別在于第p+2個盤存放的是輔助對角線校驗位。

STAR碼是在EVENODD碼的基礎上增加了第三個校驗位輔助對角線校驗，EVENODD碼的特點STAR碼也有，由于多了一個校驗位，容錯能力從容二錯增強到了容三錯。

目前，除了糾刪碼技術是處理本地數據的，其他技術針對的都是網絡在線數據，基本沒有涉及到本地數據，本文主要利用編碼技術提高本地備份數據的可靠性。

2　優化編碼存儲規則

2.1編碼規則

本文方案中，存儲的文件塊并不是所有原始塊與編碼規則相同的編碼塊，而是存儲部分原始塊與部分編碼塊，其中關于編碼塊的規則是任意k個原始塊組合成一個編碼塊，這里的k＜=n（n為原始塊數目）。在這個方案中，本文存儲的文件大小會比原始文件稍大，但是相對一個方案來講，存儲的大小會大幅減少。

關于存儲多少個原始塊，多少個編碼塊，本文會在下面進行研究。為了方便研究，本文將對文件進行分4塊，分別以a、b、c、d表示，其中，可以組成的編碼塊有ab、ac、ad、bc、bd、cd、abc、abc、acd、bcd、abcd，實際存儲的塊將在這15個塊中選取。

這種方案的主要過程是∶文件存儲前，先把文件分塊，之后把所有可能的組合列出來，總共有s=種組合（k為分塊數），然后從s個組合中隨機挑選m（k＜m＜s）個，進行存儲，這m個文件塊不要求一定要有原始塊或者要編碼塊，只需要數目達到要求。文件讀取時，先判斷原始塊是否足夠，若足夠，則直接讀取，若不足夠，則利用已有的編碼塊與原始塊進行解碼，還原出原文件。

本文做了個簡單程序去驗證這分塊編碼存儲的可靠性。

在這個程序的算法中，利用二進制運算的特性，可以模擬編碼解碼過程，具體過程如下：

（1）創建4個數組分別代表A、B、C、D，其中A［0 0 0 1］，B［0 0 1 0］，C［0 1 0 0］，D［1 0 0 0］；

（2）根據選取的文件塊所包含的原始塊信息，生成對應的數組，如有”AB”這個文件塊，則用str1［1 0 0 1］表示，總共可以得到7個數組str1～str7；

（3）從得到的7個數組中挑選4，組合成一個4×4的矩陣，通過判定該矩陣是否有解，就可以知道該文件塊組合能否還原文件；

（4）重復步驟（3），直到文件得到還原后或者所有文件塊組合都嘗試了，但文件無法還原才結束。

通過模擬程序的運行結果可以發現，將文件分成4塊，通過編碼增加了11塊，再從15塊中取7塊文件進行文件還原是存在問題的，雖然絕大部分都可以還原，但是仍然有少部分組合是無法還原的。

這種編碼方法，每個原始文件塊分別存儲在8個不同的塊中，也就是說有7個塊不包含這個原始文件塊的信息，這種情況下，若取的塊都是這7個塊，如a，b，c，ab，bc，ac，abc，則說明這個原始文件塊“d”的信息丟失了，無法還原出原始文件。

針對這種情況本文的方法是從15個塊中取8個，就可以完全避免這個情況了。

在存儲了8個塊之后，本文進一步嘗試，允許丟失塊，在存儲的過程中需要進行挑選編碼塊，而不是任意的8個塊。挑選的規則主要是存儲的塊必須包含有所有原始文件塊信息，而且不是單純的任意塊，而是每個原始文件塊的信息都必須存在于若干個文件塊中，如存儲的塊有b，ac，ad，bc，abc，abd，acd，bcd，在這種情況下包含“a”的信息塊有5個，包含“b”的信息塊有5個，包含“c”的信息塊有4個，包含“d”的信息塊有4個，每個原始信息的存在數目基本一致，且不小于文件分份數。完成存儲后，根據包含的文件塊信息最少的塊的數目，決定允許丟失的數目。

2.2數據分析

本文中，將文件分成n塊，可以組成2n-1個塊，每個原始信息塊存在的數目是（2n-1）-（2n-1-1）=2n-1個，所以每次存儲的數目為2n-1+1個塊，可以保證每個原始信息都被保存。但是如下圖所示，如果n的值超過4，存儲文件的大小將遠遠大于原文件，這樣效率會變得十分低。

圖1　文件分塊數與編碼數增長關系圖

根據本文方案，確保了原始文件信息的可靠性，使得需要存儲的塊數明顯降低。還有一點是容錯能力變成可控的，不是固定的容x錯（x為常數）。容錯能力根據存儲的文件塊中的原始信息數而變。

容錯分析：通過編碼理論可以知道，最大距離可分碼，也就是MDS碼，存儲效率是最高的，本文的方案不是MDS碼，考慮的第一優先的不是效率，而是可靠性，但是就效率而言，并不比簡單的容一錯、容二錯的編碼低，而且可靠性更強。根據本文的編碼存儲規則，我們很容易就可以得到整個方案的存儲效率E。

其中n為文件分塊數，m為實際存儲的文件塊數，m隨著n的不同而不同，且m≥n，容錯能力為V=mn。

下圖為編碼過程中所有文件塊的組合生成示意圖，每一個節點向上遍歷（只能向上）到第二層結束，這樣就得到了一個編碼塊。如從第三層第四個元素“c”開始，往上讀取“a”，到這里結束，就得到一個編碼塊”ac“，如從第五層第一個元素“d”開始，往上讀取“c”、”b”、”a”，到這里結束，就得到一個編碼塊”abcd“，如從第三層第六個元素“d”開始，往上讀取“c”，到這里結束，就得到一個編碼塊”cd“。當所有節點都讀取過后，原始文件塊所組成的編碼塊就全部組合完成。可以清楚地知道，生成編碼塊的復雜度為O（2n），隨著文件分塊的增多，復雜度會呈現指數型增長，因此，本文方案不適合文件塊過多的文件存儲。

圖2　文件塊組合示意圖

解碼過程中，由于存儲塊類型不是固定的，所以只能計算最糟情況下還原的復雜度。存儲文件塊的數目也不是固定的，所以在這里將文件分n塊，存儲的塊數為m。在最糟情況下，所有原始文件塊都沒有被存儲，而且兩兩編碼塊之間編碼過后不能還原出原始文件塊，每個原始文件塊的還原復雜度為O（nlog2m），還原出原始文件的需要還原n次，所以總的復雜度為O （nlog2m）。

與糾刪碼相比，使用這個方案，文件大小會增大，但是可靠性會明顯增加，而且不需要文件的總塊數是素數；缺點是增加了大量線性運算，不過增加的運算與增加的可靠性相比是值得的，特別是在某些特殊的情景下，需要保證文件可讀的時候，存儲空間的價值會降低。因此，在重要文件的存儲上使用本文方案是有應用價值的。

3　結語

本文方案最大的優化是容錯能力。容錯能力不再是簡單的容一錯、容二錯，而是根據文件分塊和編碼情況來決定，只要文件分塊超過5以上，容錯能力就會提高很多倍。缺點是編碼運算比之前多。不過都是線性運算，相對于容錯能力的提高，線性運算的增加是可以接受的；而對于一些重要而又不是常用的文件來說，可靠性的需求比空間需求更重要，所以，在針對這些文件，犧牲存儲空間來保證文件的可靠性是必須的。在存儲設備越來越大的大數據時代，普通用戶可以通過本文方案，犧牲平時用不上的空間，實現對一些重要文件的的保護。特別是一些忘了備份或者沒時間備份的文件。

［1］NAGAVARAPU S.A Review of Disaster Recovery Techniques and Online Data Backup in Cloud Computing［J］.2015.

［2］Geer D.Reducing the Storage Burden Via Data Deduplication［J］.Computer，2008（12）∶15-17.

［3］Xu W，Luo J.The Research on Electronic Data Backup and Recovery System Based on Network［C］//2015 International Conference on Intelligent Systems Research and Mechatronics Engineering.Atlantis Press，2015.

［4］Ahlswede R，Cai N，Li S Y R，et al.Network Information flow［J］.Information Theory，IEEE Transactions on，2000，46（4）∶1204-1216.

［5］王禹.分布式存儲系統中的數據冗余與維護技術研究［D］.華南理工大學，2011.

［6］Dimakis A G，Ramchandran K，Wu Y，et al.A Survey on Network Codes for Distributed Storage［J］.Proceedings of the IEEE，2011，99 （3）∶476-489.

［7］Li S Y R，Yeung R W，Cai N.Linear Network Coding［J］.Information Theory，IEEE Transactions on，2003，49（2）∶371-381.

［8］Byers J W，Luby M，Mitzenmacher M，et al.A Digital Fountain Approach to Reliable Distribution of Bulk Data［C］.Probabilistic Methods Applied to Power Systems，2006.PMAPS 2006.International Conference on.IEEE，2006∶1-6.

［9］Reed I S，Solomon G.Polynomial Codes Over Certain Finite Fields［J］.Journal of the Society for Industrial and Applied Mathematics，1960，8（2）∶300-304.

［10］Luby M.LT codes［C］//null.IEEE，2002∶271.

［11］Shokrollahi A.Raptor codes［J］.Information Theory，IEEE Transactions on，2006，52（6）∶2551-2567.

［12］Blaum M，Brady J，Bruck J，et al.EVENODD∶An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures［J］. Computers，IEEE Transactions on，1995，44（2）∶192-202.

［13］Xu L，Bruck J.X-code∶MDS Array Codes with Optimal Encoding［J］.Information Theory，IEEE Transactions on，1999，45（1）∶272-276.

［14］Huang C，Xu L.STAR∶An Efficient Coding Scheme for Correcting Triple Storage Node Failures［J］.Computers，IEEE Transactions on，2008，57（7）∶889-901.

［15］Hafner J L.WEAVER Codes∶Highly Fault Tolerant Erasure Codes for Storage Systems［C］.FAST.2005，5∶16-16.

［16］Blomer J，Kalfane M，Karp R，et al.An XOR-Based Erasure-Resilient Coding Scheme［J］.1999.

［17］朱云鋒.分布式存儲系統中基于糾刪碼的容錯技術研究［D］.中國科學技術大學，2014.

詹首道，在讀研究生，研究方向為網絡編碼

龔洪波，在讀研究生，研究方向為量子計算與量子信息

Fountain Code；Encoding；Backup；Robustness

A Scheme of Local Data Storage and Backup Based on Fountain Codes

ZHAN shou-dao，GONG hong-bo
（Department of Computer Science of Technology，Guangdong University of Technology，Guangdong 510006）

Proposes a data backup scheme which is based on fountain coding and network coding.This scheme is based on the idea of fountain coding and network coding，and it has the characteristics of erasure codes.When data are stored，the file blocks will be encoded then produce a lot of encoding blocks，after that the original block and file encoding block will be selected to storage and the store data is mixed with the original block and the encoding block so the file storage space becomes larger.When data are read，the original data can be recovered by a simple calculation which is generally linear operations.This scheme obtains the reliability of data by exploiting the space and calculation，it has a better robustness in some application scenes.

1007-1423（2016）20-0045-05

10.3969/j.issn.1007-1423.2016.20.009

2016-04-25

2016-07-05