基于網(wǎng)絡(luò)編碼和金字塔碼的分布式存儲(chǔ)編碼研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的來臨，每天都有大量的數(shù)據(jù)產(chǎn)生，如何將大量數(shù)據(jù)進(jìn)行有效存儲(chǔ)越來越受到關(guān)注。和集中式存儲(chǔ)相比，分布式存儲(chǔ)具有較高的可擴(kuò)展性、可靠性和存儲(chǔ)效率，更能適應(yīng)大數(shù)據(jù)的存儲(chǔ)需要。在分布式存儲(chǔ)系統(tǒng)中常采用冗余存儲(chǔ)來保證整個(gè)系統(tǒng)的可靠性，冗余策略主要有復(fù)制和編碼兩種方式。糾刪碼作為傳統(tǒng)的編碼冗余策略，存在修復(fù)帶寬太大以及訪問效率低的問題。網(wǎng)絡(luò)編碼和金字塔是兩種新的編碼方案，將網(wǎng)絡(luò)編碼應(yīng)用到分布式存儲(chǔ)中可以解決修復(fù)帶寬太大的問題；采用金字塔

2、碼存儲(chǔ)數(shù)據(jù)，可以提高分布式存儲(chǔ)系統(tǒng)的訪問效率。
　　基于網(wǎng)絡(luò)編碼的分布式存儲(chǔ)，是將網(wǎng)絡(luò)編碼應(yīng)用在節(jié)點(diǎn)修復(fù)的過程中，從而可以有效減小修復(fù)帶寬。存儲(chǔ)量和修復(fù)帶寬之間存在權(quán)衡關(guān)系，在這條最優(yōu)權(quán)衡曲線上的碼稱為再生碼。有兩類特殊的再生碼，稱為最小存儲(chǔ)再生（MSR)碼和最小帶寬再生（MBR)碼，分別對應(yīng)有最小的存儲(chǔ)量和最小的修復(fù)帶寬。
　　金字塔碼的主要思想是通過增加額外的冗余來換取訪問效率的提高。有兩類金字塔碼，基本金字塔碼和廣義金

3、字塔碼。其中基本金字塔碼是簡單的由任意現(xiàn)有的碼構(gòu)造得到的，因此可以直接應(yīng)用現(xiàn)有的編譯碼優(yōu)化方法，而廣義金字塔碼則是一類從根本上改進(jìn)的新碼。
　　本文的主要工作包括：在前人工作的基礎(chǔ)上，對基本金字塔碼在有限域上進(jìn)行了推廣，將現(xiàn)有的基于(2)的基本金字塔碼推廣到GF(pm)上，從而為分布式存儲(chǔ)提供了更靈活的編碼方案；實(shí)現(xiàn)了用一種確定的MDS碼一R S碼來構(gòu)造得到基本金字塔碼；對分布式存儲(chǔ)中的幾種冗余策略進(jìn)行了比較，具體工作內(nèi)容如下

4、r>　　1、基于GF(pm)的基本金字塔碼的構(gòu)造、譯碼和多層擴(kuò)展的研究。本文研究了在GF(pm)上構(gòu)造基本金字塔碼的方法和與之對應(yīng)的基本金字塔碼的譯碼過程。本文還研究了如何將兩層基本金字塔碼擴(kuò)展到多層。并分別通過例子具體說明了上述的構(gòu)造、譯碼和多層擴(kuò)展過程。
　　2、關(guān)于用一種確定構(gòu)造的M DS碼來生成基本金字塔碼的研究。本文選取了一類重要的MDS碼一R S碼，研究了如何應(yīng)用R S碼來構(gòu)造基本金字塔碼，并用一個(gè)具體參數(shù)的RS碼，完

5、成了對基本金字塔碼的構(gòu)造和譯碼，對于金字塔碼在分布式存儲(chǔ)系統(tǒng)中的實(shí)際應(yīng)用具有一定意義。
　　3、分布式存儲(chǔ)中的幾種冗余策略的比較。首先，在比特位上比較了GF(2)上的基本金字塔碼和本文中推廣的GF(pm)上的基本金字塔碼的修復(fù)能力、平均讀開銷和平均修復(fù)開銷。然后，從修復(fù)能力和平均讀開銷方面，比較了 RS碼和由它構(gòu)造得到的基本金字塔碼。最后，對復(fù)制策略、最大距離可分（MDS)碼、兩層和三層構(gòu)造的基本金字塔碼進(jìn)行了比較，并對比較結(jié)果進(jìn)