【摘要】：隨著現(xiàn)代社會數(shù)據(jù)信息量的迅猛增加,現(xiàn)代存儲系統(tǒng)的可靠性受到嚴(yán)重的挑戰(zhàn)。提高存儲系統(tǒng)的可靠性的主要方法是通過增加冗余信息來提高容錯能力。增加冗余信息的方法有兩種,一種是多副本方法,另一種是采用糾刪碼方法。由于多副本方法的存儲開銷很大,難以滿足海量數(shù)據(jù)存儲的要求,因此現(xiàn)代存儲技術(shù)常使用糾刪碼的方式來提高數(shù)據(jù)的可靠性和可用性。在糾刪碼技術(shù)中,陣列碼是一種不錯的技術(shù),采用簡單的異或操作來進(jìn)行運(yùn)算,容易實現(xiàn),應(yīng)用廣泛。當(dāng)陣列碼滿足Maximum Distance Seperable(MDS)特性時,可以達(dá)到理論上最優(yōu)的存儲利用率。本文對MDS陣列碼進(jìn)行研究,首先針對BBV編碼的參數(shù)條件,在現(xiàn)有的下限值情況,進(jìn)行優(yōu)化其下限值的研究工作。其次,對EVENODD碼的拓展碼,EVENODD(p,3)碼的修復(fù)問題進(jìn)行研究。由于在現(xiàn)實情況下,單個數(shù)據(jù)列丟失的情況最為常見,為此本文重點研究EVENODD(p,3)碼單列數(shù)據(jù)列的修復(fù)問題。最后,從理論上分析EVENODD(p,4)碼和RDP(p,4)碼在修復(fù)單列數(shù)據(jù)列丟失時的信息位讀取量。本文以陣列碼為研究目標(biāo),重點研究其在滿足MDS特性和單列數(shù)據(jù)修復(fù)方面的情況。本文的主要工作有:1.針對具有超過8列檢驗列的BBV碼,在要滿足MDS特性的條件下,優(yōu)化其參數(shù)p的數(shù)學(xué)條件。結(jié)果表明,經(jīng)過本文工作所優(yōu)化的參數(shù)p的下限值比已有的結(jié)果要低很多,這使得具有超過8列檢驗列的BBV碼在滿足MDS特性條件下,其參數(shù)條件更為緊湊。2.從理論上推導(dǎo)出EVENODD(p,3)碼單列數(shù)據(jù)列丟失時,其在修復(fù)時的最小信息位讀取量,并且給出一種對EVENODD(p,3)碼單列數(shù)據(jù)列丟失時的修復(fù)方案,該方案在修復(fù)單個數(shù)據(jù)丟失列時,所需的信息位讀取量要優(yōu)于EVENODD碼的最小信息位讀取量。3.從理論上對EVENODD(p,4)碼和RDP(p,4)碼在單列數(shù)據(jù)列丟失時,分析它們在修復(fù)時的信息位讀取量。對比分析EVENODD碼、EVENODD(p,3)碼和EVENODD(p,4)碼在修復(fù)單列數(shù)據(jù)列丟失時的信息位讀取量。對比分析RDP碼、RDP(p,3)碼和RDP(p,4)碼在修復(fù)單列數(shù)據(jù)列丟失時的信息位讀取量。
【圖文】：

圖 2-1 EVENODD 碼的編碼示意圖（p=5）有研究表明，EVENODD 碼的編碼復(fù)雜度為 k 1/2，而修復(fù)復(fù)雜度為 k，接近理論下界值 k-1，但是它的更新復(fù)雜度比較高，約為 3，是理論下界的 1.5 倍。雖然 EVENODD 只有兩列校驗列，第一列稱為水平校驗列，也稱斜率為 0 的校驗列。第二列稱為對角線校驗列，也稱斜率為 1 的校驗列。在參考文獻(xiàn)[32]中，EVENODD碼的作者通過追加其他斜率對角線所運(yùn)算得到的校驗列，進(jìn)一步把 EVENODD 碼拓展

圖 2-2 RDP 碼的編碼示意圖（p=5）在參考文獻(xiàn)[36]中，Mario Blaum 把類似 EVENODD 碼的拓展碼的生成方法，運(yùn)用到 RDP 碼上，最終形成具有糾正多列丟失能力的 RDP 碼的拓展碼。有趣的一件事是日本的研究人員基于循環(huán)置換矩陣的方式來定義 RDP 碼的拓展碼[37]，并且與 MarBlaum 在同一屆的 ISIT 會議上提出 RDP 碼的推廣碼的概念。類似于 EVENODD 碼的拓展碼，RDP 碼的拓展碼只有在 r =3時才確定是 MDS 碼，在 r ≥4時，還需參數(shù) p 滿足一定的條件才能是 MDS 碼。Liberation 碼在 2008 年的 FAST 會議上首次提出的 Liberation 碼[38]，其更新復(fù)雜度是所有水平陣列碼中最低的，接近理論下界 2。Liberation 碼是一個 p × ( p+2)的二維陣列，p 為素數(shù)。它的編碼復(fù)雜度與 EVENODD 碼差不多，當(dāng)數(shù)據(jù)列數(shù)為 k 時，其編碼復(fù)雜度為k 1 +(k 1)/(2p)，當(dāng) p 遠(yuǎn)遠(yuǎn)大于 k 時，，則編碼復(fù)雜度接近下界 k-1。但是，Liberatio
【學(xué)位授予單位】：華南理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP333

【參考文獻(xiàn)】

相關(guān)期刊論文 前4條

1 羅象宏;舒繼武;;存儲系統(tǒng)中的糾刪碼研究綜述[J];計算機(jī)研究與發(fā)展;2012年01期

2 劉貝;湯斌;;云存儲原理及發(fā)展趨勢[J];科技信息;2011年05期

3 周可;王樺;李春花;;云存儲技術(shù)及其應(yīng)用[J];中興通訊技術(shù);2010年04期

4 陳全;鄧倩妮;;云計算及其關(guān)鍵技術(shù)[J];計算機(jī)應(yīng)用;2009年09期

相關(guān)博士學(xué)位論文 前1條

1 黃志杰;容錯存儲系統(tǒng)中的MDS陣列碼研究[D];華中科技大學(xué);2016年

相關(guān)碩士學(xué)位論文 前1條

1 林軒;面向多節(jié)點失效的糾刪碼及數(shù)據(jù)修復(fù)技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2014年

本文編號：2602597