分布式存儲系統(tǒng)中數(shù)據(jù)快速修復(fù)的糾刪碼.pdf

1、為防止因設(shè)備故障和網(wǎng)絡(luò)中斷而導(dǎo)致的數(shù)據(jù)不可用，糾刪碼廣泛地用于分布式存儲系統(tǒng)中保證數(shù)據(jù)可靠性。傳統(tǒng)的糾刪碼會遇到修復(fù)開銷大的問題：修復(fù)過程所需要的數(shù)據(jù)量遠(yuǎn)大于失效數(shù)據(jù)量。大量的修復(fù)數(shù)據(jù)會消耗寶貴的磁盤I/O和網(wǎng)絡(luò)帶寬，并將系統(tǒng)長期暴露在一種不穩(wěn)定的窗口期，使得任何額外故障將可能導(dǎo)致不可恢復(fù)的數(shù)據(jù)丟失，間接地降級了系統(tǒng)的可靠性。近期研究人員也提出了一些減少數(shù)據(jù)修復(fù)開銷的糾刪碼，但它們或犧牲了最小存儲開銷等有益性質(zhì)，或只能應(yīng)用于某些特定的編

2、碼系數(shù)上。另外，糾刪碼在數(shù)據(jù)編碼和數(shù)據(jù)修復(fù)時需要消耗大量的計算資源，如何減少計算開銷也是糾刪碼領(lǐng)域的研究重點(diǎn)。本文對分布式存儲系統(tǒng)上數(shù)據(jù)快速修復(fù)的糾刪碼從兩個方面展開研究：構(gòu)建具有靈活參數(shù)、減少修復(fù)開銷的糾刪碼和減少數(shù)據(jù)編碼和數(shù)據(jù)修復(fù)時的計算開銷。本文主要貢獻(xiàn)包括以下三點(diǎn)：
　　提出一類新的再生碼—GFR碼。GFR碼通過一個權(quán)衡參數(shù)實現(xiàn)分布式存儲系統(tǒng)中存儲開銷和修復(fù)開銷的權(quán)衡，使得其既可以達(dá)到理論最小存儲開銷、最小修復(fù)開銷，也可以

3、達(dá)到他們之間的平衡。GFR碼還使用一種啟發(fā)式算法尋找到修復(fù)單點(diǎn)失效數(shù)據(jù)的最小修復(fù)開銷，并利用一個閾值控制了啟發(fā)式算法中搜索空間和搜索時間的權(quán)衡。經(jīng)實驗分析，基于GFR碼的分布式存儲系統(tǒng)比基于RAID碼的系統(tǒng)具有更高的可靠性。GFR碼在實際系統(tǒng)中可以達(dá)到理論上最優(yōu)或近似最優(yōu)的修復(fù)開銷，其數(shù)據(jù)編碼性能和FMSR碼相近。
　　提出一種矩陣和數(shù)據(jù)塊在有限域上的快速乘法算法—預(yù)排移位乘法（SSM）。預(yù)排移位乘法通過合理調(diào)度運(yùn)算順序，合并了在

4、計算矩陣和數(shù)據(jù)塊乘法時的相同計算，減少了糾刪碼在有限域上數(shù)據(jù)編碼和數(shù)據(jù)修復(fù)時的計算開銷。實驗證明，預(yù)排移位乘法比傳統(tǒng)算法具有更小的預(yù)測分支，預(yù)排移位乘法能提高RS編碼速度和提高GFR碼的數(shù)據(jù)編碼速度和數(shù)據(jù)修復(fù)速度。通過對GFR碼修復(fù)性能分析，預(yù)排移位乘法對GFR碼修復(fù)開銷影響很小。
　　提出了一類最小存儲開銷下最優(yōu)修復(fù)開銷的糾刪碼—Z碼。Z碼以置換矩陣為元矩陣，可以組合構(gòu)造出具有最優(yōu)修復(fù)開銷的生成矩陣。Z碼還利用矩陣的張量乘積，可

5、迭代地構(gòu)造出任意參數(shù)下的生成矩陣，并保持了其最優(yōu)修復(fù)開銷。另外，Z碼是系統(tǒng)碼，因此數(shù)據(jù)編碼后原始數(shù)被保留。它們還具有更新開銷低和計算開銷小等優(yōu)點(diǎn)。Z碼的參數(shù)選擇靈活，理論上可以實現(xiàn)任意高的存儲效率和容錯能力。GZ碼以是Z碼在有限域上的擴(kuò)展，它具有MDS（Maximum Distance Separable）性質(zhì)，且保持了和Z碼相同的修復(fù)開銷和系統(tǒng)性等性質(zhì)。經(jīng)實驗分析，Z/GZ碼和RS碼有相近的編碼速度和修復(fù)速度，Z/GZ碼還具有最小的更

6、新開銷，Z/GZ碼在數(shù)據(jù)修復(fù)時減少了37.5％以上的響應(yīng)時間。
　　GFR碼和Z碼都是減少修復(fù)開銷的糾刪碼。前者是非系統(tǒng)碼，編碼后只有校驗數(shù)據(jù)，能夠減少存儲系統(tǒng)中每個節(jié)點(diǎn)的修復(fù)開銷；后者是系統(tǒng)碼，編碼后保留了原始數(shù)據(jù)，能夠減少原始數(shù)據(jù)部分的修復(fù)開銷。GFR還可以通過增加存儲開銷進(jìn)一步減少修復(fù)開銷，因此它更適合用于需要頻繁的數(shù)據(jù)修復(fù)和修復(fù)開銷大的分布式存儲系統(tǒng)，而Z碼的系統(tǒng)性、高編碼性能和低更新開銷使得其適合于高性能存儲系統(tǒng)。預(yù)排移