詹首道，龔洪波（廣東工業(yè)大學(xué)計算機學(xué)院，廣州　510006）

一種基于噴泉碼的本地數(shù)據(jù)存儲備份的方案

詹首道，龔洪波
（廣東工業(yè)大學(xué)計算機學(xué)院，廣州510006）

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

噴泉碼；網(wǎng)絡(luò)編碼；備份；魯棒性

國家自然科學(xué)基金項目（No.61272013）、廣東省現(xiàn)代信息服務(wù)業(yè)發(fā)展專項資金項目（No.GDEID2011IS022）、廣東省省部產(chǎn)學(xué)研合作專項資金項目（No.2013B090500007）

0　引言

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

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

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

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

1　理論基礎(chǔ)

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

1.1分布式存儲系統(tǒng)

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

1.2網(wǎng)絡(luò)編碼

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

1.3噴泉碼

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

噴泉碼利用編碼計算，提高用戶接收文件的效率。目前的應(yīng)用環(huán)境都與網(wǎng)絡(luò)相關(guān)，與本地文件的讀取無關(guān)。受到噴泉碼的啟發(fā)，本文結(jié)合網(wǎng)絡(luò)編碼將這種編碼思想應(yīng)用在存儲備份中，將需要存儲的數(shù)據(jù)進行編碼，并增加的額外存儲空間，提高文件的可靠性。

1.4糾刪碼

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

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

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

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

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

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

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

2　優(yōu)化編碼存儲規(guī)則

2.1編碼規(guī)則

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

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

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

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

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

（1）創(chuàng)建4個數(shù)組分別代表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）根據(jù)選取的文件塊所包含的原始塊信息，生成對應(yīng)的數(shù)組，如有”AB”這個文件塊，則用str1［1 0 0 1］表示，總共可以得到7個數(shù)組str1～str7；

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

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

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

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

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

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

2.2數(shù)據(jù)分析

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

圖1　文件分塊數(shù)與編碼數(shù)增長關(guān)系圖

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

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

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

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

圖2　文件塊組合示意圖

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

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

3　結(jié)語

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

［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］王禹.分布式存儲系統(tǒng)中的數(shù)據(jù)冗余與維護技術(shù)研究［D］.華南理工大學(xué)，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］朱云鋒.分布式存儲系統(tǒng)中基于糾刪碼的容錯技術(shù)研究［D］.中國科學(xué)技術(shù)大學(xué)，2014.

詹首道，在讀研究生，研究方向為網(wǎng)絡(luò)編碼

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

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