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

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

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

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

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

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

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