一種基于噴泉碼的本地?cái)?shù)據(jù)存儲(chǔ)備份的方案

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

一種基于噴泉碼的本地?cái)?shù)據(jù)存儲(chǔ)備份的方案

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

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

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

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

0　引言

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

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

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

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

1　理論基礎(chǔ)

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

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

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

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

在2000年由Yeung等發(fā)表的網(wǎng)絡(luò)編碼（Network Coding）［4］脫離了傳統(tǒng)網(wǎng)絡(luò)只能在中間節(jié)點(diǎn)存儲(chǔ)轉(zhuǎn)發(fā)的模式，提出了中間節(jié)點(diǎn)編碼計(jì)算的新模式。通過(guò)網(wǎng)絡(luò)編碼技術(shù)，提高帶寬的利用率，實(shí)現(xiàn)網(wǎng)絡(luò)吞吐的最大化。到了2003年，線性網(wǎng)絡(luò)中的網(wǎng)絡(luò)編碼的可行性［7］也被Yeung等人證明可行性。進(jìn)一步研究發(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］等。

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

1.4糾刪碼

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

下文簡(jiǎn)單介紹容2錯(cuò)的EVENODD碼和容多錯(cuò)的STAR碼。

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

因?yàn)镋VENODD碼在編碼、解碼操作時(shí)使用簡(jiǎn)單的異或操作，所以計(jì)算復(fù)雜度比較低。

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

STAR碼是在EVENODD碼的基礎(chǔ)上增加了第三個(gè)校驗(yàn)位輔助對(duì)角線校驗(yàn)，EVENODD碼的特點(diǎn)STAR碼也有，由于多了一個(gè)校驗(yàn)位，容錯(cuò)能力從容二錯(cuò)增強(qiáng)到了容三錯(cuò)。

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

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

2.1編碼規(guī)則

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

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

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

本文做了個(gè)簡(jiǎn)單程序去驗(yàn)證這分塊編碼存儲(chǔ)的可靠性。

在這個(gè)程序的算法中，利用二進(jìn)制運(yùn)算的特性，可以模擬編碼解碼過(guò)程，具體過(guò)程如下：

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

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

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

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

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

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

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

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

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

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

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

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

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

下圖為編碼過(guò)程中所有文件塊的組合生成示意圖，每一個(gè)節(jié)點(diǎn)向上遍歷（只能向上）到第二層結(jié)束，這樣就得到了一個(gè)編碼塊。如從第三層第四個(gè)元素“c”開(kāi)始，往上讀取“a”，到這里結(jié)束，就得到一個(gè)編碼塊”ac“，如從第五層第一個(gè)元素“d”開(kāi)始，往上讀取“c”、”b”、”a”，到這里結(jié)束，就得到一個(gè)編碼塊”abcd“，如從第三層第六個(gè)元素“d”開(kāi)始，往上讀取“c”，到這里結(jié)束，就得到一個(gè)編碼塊”cd“。當(dāng)所有節(jié)點(diǎn)都讀取過(guò)后，原始文件塊所組成的編碼塊就全部組合完成?？梢郧宄刂溃删幋a塊的復(fù)雜度為O（2n），隨著文件分塊的增多，復(fù)雜度會(huì)呈現(xiàn)指數(shù)型增長(zhǎng)，因此，本文方案不適合文件塊過(guò)多的文件存儲(chǔ)。

圖2　文件塊組合示意圖

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

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

3　結(jié)語(yǔ)

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

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

詹首道，在讀研究生，研究方向?yàn)榫W(wǎng)絡(luò)編碼

龔洪波，在讀研究生，研究方向?yàn)榱孔佑?jì)算與量子信息

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