面向分布式存儲(chǔ)系統(tǒng)的具有最優(yōu)存取-更新性質(zhì)的最小存儲(chǔ)再生碼的設(shè)計(jì)與分析.pdf

1、隨著數(shù)據(jù)規(guī)模的爆炸式增長(zhǎng)，傳統(tǒng)的集中式存儲(chǔ)系統(tǒng)已不再能滿足日益增長(zhǎng)的存儲(chǔ)需求。分布式存儲(chǔ)系統(tǒng)因具有高可靠性、可擴(kuò)展性、廉價(jià)性等優(yōu)點(diǎn)因而在大數(shù)據(jù)中心，P2P存儲(chǔ)系統(tǒng)等方面得到了廣泛的應(yīng)用。為確?？煽啃裕哂鄬?duì)這些系統(tǒng)來說是至關(guān)重要的。常見的生成冗余數(shù)據(jù)的方法是采用糾刪碼，它能高效的存儲(chǔ)數(shù)據(jù)且能抵抗節(jié)點(diǎn)失效。然而，傳統(tǒng)的糾刪碼如RS(Reed-Solomon)碼等MDS(Maximum Distance Separable)碼的修復(fù)帶寬太大

2、。為了刻畫存儲(chǔ)開銷和修復(fù)帶寬，Dimakis等人給出了在功能修復(fù)下的存儲(chǔ)-修復(fù)帶寬的最優(yōu)折中，得到了給定存儲(chǔ)開銷下的最小（優(yōu)）修復(fù)帶寬，并提出了最小存儲(chǔ)再生(Minimum Storage Regenerating MSR)碼，即具有最優(yōu)修復(fù)性質(zhì)的MDS存儲(chǔ)碼。目前大多數(shù)已知的高碼率MDS存儲(chǔ)碼只有系統(tǒng)節(jié)點(diǎn)能被最優(yōu)修復(fù)，且有些高碼率MDS存儲(chǔ)碼在其它方面如更新性質(zhì)、存取性質(zhì)、系統(tǒng)節(jié)點(diǎn)的個(gè)數(shù)存在不足，而已知的高碼率MSR碼（即所有節(jié)點(diǎn)均能

3、被最優(yōu)修復(fù)的MDS存儲(chǔ)碼）非常稀少。本文給出了多類性質(zhì)優(yōu)良的系統(tǒng)節(jié)點(diǎn)具有最小修復(fù)帶寬的高碼率MDS存儲(chǔ)碼的構(gòu)造，以及給出現(xiàn)有高碼率MDS存儲(chǔ)碼校驗(yàn)節(jié)點(diǎn)的最優(yōu)修復(fù)策略。
　　首先，基于一種基集合的劃分方法，提出了高碼率MDS存儲(chǔ)碼的一種構(gòu)造框架，并在該框架的一般性構(gòu)造方法下，重新解釋了Hadamard design碼等四類已知的高碼率MDS存儲(chǔ)碼。
　　其次，給出了五類具有較多系統(tǒng)節(jié)點(diǎn)、具有最優(yōu)存取/更新性質(zhì)的（k+2，k)M

4、DS存儲(chǔ)碼，且其所需的有限域大小均已被確定。其中在給定的節(jié)點(diǎn)容量下，第一類碼是目前系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)最多的高碼率MDS存儲(chǔ)碼，第三類和第四類碼是目前具有最優(yōu)更新性質(zhì)的MDS存儲(chǔ)碼中系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)最多的碼，第五類碼是目前具有最優(yōu)存取性質(zhì)且系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)達(dá)到理論上界的碼中所需有限域最小的MDS存儲(chǔ)碼。
　　再次，給出了一種轉(zhuǎn)換系統(tǒng)節(jié)點(diǎn)具有最優(yōu)修復(fù)性質(zhì)的高碼率MDS存儲(chǔ)碼為MSR碼的一般方法，該方法得到的新MSR碼的校驗(yàn)節(jié)點(diǎn)具有最優(yōu)存取性質(zhì)，且能

5、保持之前的MDS存儲(chǔ)碼的其他優(yōu)良性質(zhì)，如:有限域的大小，系統(tǒng)節(jié)點(diǎn)的最優(yōu)存取性質(zhì)。此外，該轉(zhuǎn)換方法也能應(yīng)用于系統(tǒng)節(jié)點(diǎn)不具有最優(yōu)修復(fù)性質(zhì)的MDS存儲(chǔ)碼。將該轉(zhuǎn)換方法應(yīng)用于已知的MDS存儲(chǔ)碼時(shí)與已知的Piggyback碼和Ye-Barg碼相比具有明顯的優(yōu)勢(shì)，即1）校驗(yàn)節(jié)點(diǎn)具有最優(yōu)修復(fù)性質(zhì)，而已知的Piggyback碼的校驗(yàn)節(jié)點(diǎn)不具有最優(yōu)修復(fù)性質(zhì);2）在某些情況下相比Ye-Barg碼，所需的有限域和節(jié)點(diǎn)容量更小。
　　最后，討論了（k+2

6、，k）Zigzag碼校驗(yàn)節(jié)點(diǎn)的修復(fù)方法。給出了一種改造（k+2，k）Zigzag碼的方法，使得改造后的碼的校驗(yàn)節(jié)點(diǎn)也能被最優(yōu)修復(fù)且具有最優(yōu)存取性質(zhì)，同時(shí)保持系統(tǒng)節(jié)點(diǎn)的最優(yōu)存取性質(zhì)。該改造方法只需將（k+2，k）Zigzag碼的節(jié)點(diǎn)容量擴(kuò)大一倍，相比Wang等人需將（k+2，k）Zigzag碼的節(jié)點(diǎn)容量擴(kuò)大三倍的改造方法具有明顯優(yōu)勢(shì)。此外，通過迭代以矩陣形式給出了（k+2，k)Zigzag碼的構(gòu)造方法，并基于矩陣表示方法，給出了一種（k+