隨機(jī)化數(shù)據(jù)冗余方法及其在存儲(chǔ)系統(tǒng)中的應(yīng)用.pdf

1、利用網(wǎng)絡(luò)分布式存儲(chǔ)系統(tǒng)存儲(chǔ)大數(shù)據(jù)已成為數(shù)據(jù)存儲(chǔ)技術(shù)的發(fā)展趨勢(shì)。網(wǎng)絡(luò)分布式存儲(chǔ)系統(tǒng)通常由數(shù)量眾多的存儲(chǔ)節(jié)點(diǎn)構(gòu)成，由于人為或自然災(zāi)難的不可避免性，或是存儲(chǔ)節(jié)點(diǎn)本身的低可靠性，常常會(huì)發(fā)生部分存儲(chǔ)節(jié)點(diǎn)損壞或是無法及時(shí)使用的情況。而這一旦發(fā)生，存儲(chǔ)其中的重要數(shù)據(jù)就會(huì)丟失或是不可用，造成極大的損失。因此，為了保證存儲(chǔ)數(shù)據(jù)的安全性和可靠性，將數(shù)據(jù)冗余方法引入網(wǎng)絡(luò)分布式存儲(chǔ)系統(tǒng)成為一種必然。
　　已有的數(shù)據(jù)冗余方法，如基于復(fù)制的數(shù)據(jù)冗余方法，基于

2、陣列碼的數(shù)據(jù)冗余方法等均存在種種不足，或者是存儲(chǔ)冗余度過高，或者是容錯(cuò)能力有限，無法滿足網(wǎng)絡(luò)環(huán)境下分布式存儲(chǔ)系統(tǒng)的需求。針對(duì)這一問題，本文首次以隨機(jī)矩陣?yán)碚摓榛A(chǔ)，提出了一類新的數(shù)據(jù)冗余方法，稱之為隨機(jī)化數(shù)據(jù)冗余方法，并研究了其在兩類具體的網(wǎng)絡(luò)分布式存儲(chǔ)環(huán)境—分布式數(shù)據(jù)容災(zāi)存儲(chǔ)和傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)環(huán)境下的應(yīng)用。本文的主要研究成果包括以下幾個(gè)方面：
　　1．提出了性能優(yōu)異的隨機(jī)化數(shù)據(jù)冗余方法。
　　容錯(cuò)能力高、存儲(chǔ)冗余度低、運(yùn)

3、算速度快、修復(fù)帶寬低是網(wǎng)絡(luò)環(huán)境下的分布式存儲(chǔ)系統(tǒng)對(duì)數(shù)據(jù)冗余方法的需求?，F(xiàn)有的數(shù)據(jù)冗余方法往往無法同時(shí)滿足這些需求。本文以二元域上的隨機(jī)矩陣為基礎(chǔ)，提出了一類新的能滿足上述需求的隨機(jī)化數(shù)據(jù)冗余方法，給出了詳細(xì)的文件存儲(chǔ)、讀取、以及修復(fù)算法。在本文提出的隨機(jī)化數(shù)據(jù)冗余方法中：由源文件得到冗余文件、由冗余文件恢復(fù)出源文件均基于構(gòu)造好的隨機(jī)矩陣完成；隨機(jī)矩陣滿秩的高概率性質(zhì)保證了冗余方法的高容錯(cuò)能力和低存儲(chǔ)冗余度；同時(shí)，源文件和冗余文件之間的轉(zhuǎn)

4、換只依靠異或運(yùn)算進(jìn)行，降低了計(jì)算復(fù)雜度，提高了文件的處理速度；另外，隨機(jī)矩陣的稀疏性也使得修復(fù)丟失的部分冗余文件數(shù)據(jù)所需的修復(fù)帶寬有效降低；
　　2．提出了基于隨機(jī)化數(shù)據(jù)冗余方法的低冗余度數(shù)據(jù)容災(zāi)方案。
　　數(shù)據(jù)容災(zāi)方案是網(wǎng)絡(luò)分布式數(shù)據(jù)容災(zāi)存儲(chǔ)系統(tǒng)抵御大規(guī)模存儲(chǔ)節(jié)點(diǎn)損毀，保證數(shù)據(jù)生存能力的有效手段。傳統(tǒng)的容災(zāi)方案通常以復(fù)制冗余方法為基礎(chǔ)，以高存儲(chǔ)空間代價(jià)換取一定的容災(zāi)能力。本文在隨機(jī)化數(shù)據(jù)冗余方法的基礎(chǔ)上，提出了一類具有低存

5、儲(chǔ)冗余度的數(shù)據(jù)容災(zāi)方案。與復(fù)制容災(zāi)方案相比，本文方案在提供相同容災(zāi)能力的前提下，可將系統(tǒng)的存儲(chǔ)空間代價(jià)降到近似的理論最小值。本文方案的可行性和有效性在相關(guān)實(shí)驗(yàn)中得到了驗(yàn)證。
　　3．以隨機(jī)化數(shù)據(jù)冗余方法為基礎(chǔ)，提出了適用于無人值守傳感器網(wǎng)絡(luò)的具有低通信成本和低訪問成本的分布式存儲(chǔ)算法。
　　無人值守傳感器網(wǎng)絡(luò)可以看作是一類沒有路由表的特殊網(wǎng)絡(luò)分布式存儲(chǔ)系統(tǒng)，其目的在于感知數(shù)據(jù)并將感知到的數(shù)據(jù)可靠地存儲(chǔ)在整個(gè)網(wǎng)絡(luò)中。本文以隨機(jī)

6、化數(shù)據(jù)冗余方法為基礎(chǔ)，并與定向隨機(jī)游走機(jī)制相結(jié)合，提出了適用于無人值守傳感器網(wǎng)絡(luò)的分布式存儲(chǔ)算法。采用本文算法：可以有效地將網(wǎng)絡(luò)中 k個(gè)數(shù)據(jù)節(jié)點(diǎn)感知到的k個(gè)源數(shù)據(jù)包存儲(chǔ)到網(wǎng)絡(luò)所有的n個(gè)節(jié)點(diǎn)中（n> k），形成n個(gè)存儲(chǔ)數(shù)據(jù)包。當(dāng)存儲(chǔ)過程完成之后，即使有部分節(jié)點(diǎn)損壞而導(dǎo)致存儲(chǔ)其中的存儲(chǔ)數(shù)據(jù)包丟失，用戶也能通過從任意k+12個(gè)以上未損壞節(jié)點(diǎn)的存儲(chǔ)數(shù)據(jù)包還原出原來的k個(gè)源數(shù)據(jù)包。與具有代表性的基于LT碼的算法相比，本文算法將存儲(chǔ)過程中每個(gè)源數(shù)據(jù)