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

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

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

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

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

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