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

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

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

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

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

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

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