分布式存儲系統(tǒng)的MDS陣列碼的研究
發(fā)布時間：2020-03-27 06:22
【摘要】：隨著現代社會數據信息量的迅猛增加,現代存儲系統(tǒng)的可靠性受到嚴重的挑戰(zhàn)。提高存儲系統(tǒng)的可靠性的主要方法是通過增加冗余信息來提高容錯能力。增加冗余信息的方法有兩種,一種是多副本方法,另一種是采用糾刪碼方法。由于多副本方法的存儲開銷很大,難以滿足海量數據存儲的要求,因此現代存儲技術常使用糾刪碼的方式來提高數據的可靠性和可用性。在糾刪碼技術中,陣列碼是一種不錯的技術,采用簡單的異或操作來進行運算,容易實現,應用廣泛。當陣列碼滿足Maximum Distance Seperable(MDS)特性時,可以達到理論上最優(yōu)的存儲利用率。本文對MDS陣列碼進行研究,首先針對BBV編碼的參數條件,在現有的下限值情況,進行優(yōu)化其下限值的研究工作。其次,對EVENODD碼的拓展碼,EVENODD(p,3)碼的修復問題進行研究。由于在現實情況下,單個數據列丟失的情況最為常見,為此本文重點研究EVENODD(p,3)碼單列數據列的修復問題。最后,從理論上分析EVENODD(p,4)碼和RDP(p,4)碼在修復單列數據列丟失時的信息位讀取量。本文以陣列碼為研究目標,重點研究其在滿足MDS特性和單列數據修復方面的情況。本文的主要工作有:1.針對具有超過8列檢驗列的BBV碼,在要滿足MDS特性的條件下,優(yōu)化其參數p的數學條件。結果表明,經過本文工作所優(yōu)化的參數p的下限值比已有的結果要低很多,這使得具有超過8列檢驗列的BBV碼在滿足MDS特性條件下,其參數條件更為緊湊。2.從理論上推導出EVENODD(p,3)碼單列數據列丟失時,其在修復時的最小信息位讀取量,并且給出一種對EVENODD(p,3)碼單列數據列丟失時的修復方案,該方案在修復單個數據丟失列時,所需的信息位讀取量要優(yōu)于EVENODD碼的最小信息位讀取量。3.從理論上對EVENODD(p,4)碼和RDP(p,4)碼在單列數據列丟失時,分析它們在修復時的信息位讀取量。對比分析EVENODD碼、EVENODD(p,3)碼和EVENODD(p,4)碼在修復單列數據列丟失時的信息位讀取量。對比分析RDP碼、RDP(p,3)碼和RDP(p,4)碼在修復單列數據列丟失時的信息位讀取量。
【圖文】：
圖 2-1 EVENODD 碼的編碼示意圖（p=5）有研究表明，EVENODD 碼的編碼復雜度為 k 1/2，而修復復雜度為 k，接近理論下界值 k-1，但是它的更新復雜度比較高，約為 3，是理論下界的 1.5 倍。雖然 EVENODD 只有兩列校驗列，第一列稱為水平校驗列，也稱斜率為 0 的校驗列。第二列稱為對角線校驗列，也稱斜率為 1 的校驗列。在參考文獻[32]中，EVENODD碼的作者通過追加其他斜率對角線所運算得到的校驗列，進一步把 EVENODD 碼拓展
圖 2-2 RDP 碼的編碼示意圖（p=5）在參考文獻[36]中，Mario Blaum 把類似 EVENODD 碼的拓展碼的生成方法，運用到 RDP 碼上，最終形成具有糾正多列丟失能力的 RDP 碼的拓展碼。有趣的一件事是日本的研究人員基于循環(huán)置換矩陣的方式來定義 RDP 碼的拓展碼[37]，并且與 MarBlaum 在同一屆的 ISIT 會議上提出 RDP 碼的推廣碼的概念。類似于 EVENODD 碼的拓展碼，RDP 碼的拓展碼只有在 r =3時才確定是 MDS 碼，在 r ≥4時，還需參數 p 滿足一定的條件才能是 MDS 碼。Liberation 碼在 2008 年的 FAST 會議上首次提出的 Liberation 碼[38]，其更新復雜度是所有水平陣列碼中最低的，接近理論下界 2。Liberation 碼是一個 p × ( p+2)的二維陣列，p 為素數。它的編碼復雜度與 EVENODD 碼差不多，當數據列數為 k 時，其編碼復雜度為k 1 +(k 1)/(2p)，當 p 遠遠大于 k 時，，則編碼復雜度接近下界 k-1。但是，Liberatio
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP333
本文編號：2602597
【圖文】：
圖 2-1 EVENODD 碼的編碼示意圖（p=5）有研究表明，EVENODD 碼的編碼復雜度為 k 1/2，而修復復雜度為 k，接近理論下界值 k-1，但是它的更新復雜度比較高，約為 3，是理論下界的 1.5 倍。雖然 EVENODD 只有兩列校驗列，第一列稱為水平校驗列，也稱斜率為 0 的校驗列。第二列稱為對角線校驗列，也稱斜率為 1 的校驗列。在參考文獻[32]中，EVENODD碼的作者通過追加其他斜率對角線所運算得到的校驗列，進一步把 EVENODD 碼拓展
圖 2-2 RDP 碼的編碼示意圖（p=5）在參考文獻[36]中，Mario Blaum 把類似 EVENODD 碼的拓展碼的生成方法，運用到 RDP 碼上，最終形成具有糾正多列丟失能力的 RDP 碼的拓展碼。有趣的一件事是日本的研究人員基于循環(huán)置換矩陣的方式來定義 RDP 碼的拓展碼[37]，并且與 MarBlaum 在同一屆的 ISIT 會議上提出 RDP 碼的推廣碼的概念。類似于 EVENODD 碼的拓展碼，RDP 碼的拓展碼只有在 r =3時才確定是 MDS 碼，在 r ≥4時，還需參數 p 滿足一定的條件才能是 MDS 碼。Liberation 碼在 2008 年的 FAST 會議上首次提出的 Liberation 碼[38]，其更新復雜度是所有水平陣列碼中最低的，接近理論下界 2。Liberation 碼是一個 p × ( p+2)的二維陣列，p 為素數。它的編碼復雜度與 EVENODD 碼差不多，當數據列數為 k 時，其編碼復雜度為k 1 +(k 1)/(2p)，當 p 遠遠大于 k 時，，則編碼復雜度接近下界 k-1。但是，Liberatio
【學位授予單位】：華南理工大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP333
【參考文獻】
相關期刊論文 前4條
1 羅象宏;舒繼武;;存儲系統(tǒng)中的糾刪碼研究綜述[J];計算機研究與發(fā)展;2012年01期
2 劉貝;湯斌;;云存儲原理及發(fā)展趨勢[J];科技信息;2011年05期
3 周可;王樺;李春花;;云存儲技術及其應用[J];中興通訊技術;2010年04期
4 陳全;鄧倩妮;;云計算及其關鍵技術[J];計算機應用;2009年09期
相關博士學位論文 前1條
1 黃志杰;容錯存儲系統(tǒng)中的MDS陣列碼研究[D];華中科技大學;2016年
相關碩士學位論文 前1條
1 林軒;面向多節(jié)點失效的糾刪碼及數據修復技術研究[D];國防科學技術大學;2014年
本文編號：2602597
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2602597.html
