基于FRC碼的分布式存儲編碼優(yōu)化算法研究.pdf

1、隨著計算機技術(shù)的快速進步，數(shù)據(jù)的爆炸性增長迫使人們對計算機存儲系統(tǒng)提出了越來越高的要求。分布式存儲系統(tǒng)由于其低廉的價格和優(yōu)異的性能而被人們所青睞。由分布式存儲系統(tǒng)所衍生的云存儲技術(shù)被各大IT企業(yè)采用且全面走向商業(yè)化。然而，網(wǎng)絡(luò)存儲節(jié)點的不可靠性使得系統(tǒng)需使用大量的存儲空間存放冗余數(shù)據(jù)，同時在節(jié)點失效時進行高頻的節(jié)點修復(fù)。這嚴重浪費了系統(tǒng)有限的網(wǎng)絡(luò)帶寬和存儲資源，降低存儲服務(wù)的質(zhì)量。因此，分布式存儲系統(tǒng)不僅需要保證容多節(jié)點故障，而且需要降

2、低修復(fù)過程中的網(wǎng)絡(luò)消耗。于是，各種容錯編碼技術(shù)，尤其是再生碼，得到深入研究。文獻提出一種Fractional Repetition(分片復(fù)制)編碼，在修復(fù)過程中不需要編碼計算，帶寬消耗最小，并且具有比最小帶寬再生（MBR）編碼更優(yōu)的存儲能力。已有的FRC編碼往往依賴于特定的組合構(gòu)造，僅僅適用于有限的參數(shù)情形。對于一般參數(shù)下情形，如何構(gòu)造最優(yōu)的存儲能力的FRC編碼被認為是一個開放性的問題。
　　本文對基于分片復(fù)制碼（FRC碼）的分布

3、式存儲系統(tǒng)，抽象出編碼矩陣的數(shù)學(xué)模型，提出了在任意參數(shù)下給出FRC碼數(shù)據(jù)分布策略的方法，使得用戶在取數(shù)據(jù)時需連接的存儲節(jié)點數(shù)量達到最小。本文的主要工作在以下幾個方面。
　?。?）為了找到FRC碼的最優(yōu)編碼矩陣，本文提出了基于楊氏矩陣遍歷搜索最優(yōu)編碼矩陣的方法。首先將FRC碼抽象為布爾矩陣，然后利用楊氏矩陣和布爾矩陣間的雙射實現(xiàn)FRC碼編碼矩陣與楊氏矩陣間的對應(yīng)，之后根據(jù)楊氏矩陣的特殊性質(zhì)提出了幾種剪枝優(yōu)化方法。本文提出的枚舉算法能

4、在任意參數(shù)下完整的遍歷存在最優(yōu)FRC碼的編碼矩陣集合，且算法的剪枝優(yōu)化方法能減少95％以上的搜索項。通過實驗表明算法的效果較好。
　　（2）在FRC編碼的布爾矩陣描述的基礎(chǔ)上，本文提出了一種在基于布爾矩陣交換操作的禁忌搜索算法。根據(jù)FRC碼的性質(zhì)，本文研究了其存儲能力與編碼矩陣中1的分布間的關(guān)系，提出并證明了FRC碼存儲能力與編碼矩陣中的充分條件定理。在此基礎(chǔ)上，本文提出了以C4圈計數(shù)為啟發(fā)式準(zhǔn)則的禁忌搜索算法。算法可在任意參數(shù)下