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

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

本文編號(hào)：2602597