苗斌 宋苗苗 李文慶 王文彥 董國(guó)法 王曉燕 張可可 徐宇柘 管萬(wàn)春

摘要：再生碼是一類分布式存儲(chǔ)編碼，由于在節(jié)點(diǎn)存儲(chǔ)和修復(fù)帶寬兩方面均有效而被廣泛研究?；诔朔e矩陣（PM）理論的最小存儲(chǔ)再生（PM-MSR）碼是一類同構(gòu)分布式存儲(chǔ)再生碼，具有最小的節(jié)點(diǎn)存儲(chǔ)。提出一種再生碼變換原理，能夠根據(jù)PM-MSR碼產(chǎn)生新的再生碼，新的再生碼用于異構(gòu)分布式存儲(chǔ)系統(tǒng)。嚴(yán)格證明了新再生碼結(jié)構(gòu)的數(shù)據(jù)重構(gòu)和數(shù)據(jù)修復(fù)性質(zhì)，并提供了編碼實(shí)例。新的再生碼與PM-MSR碼具有相同的存儲(chǔ)消耗和帶寬消耗，但新的再生碼具有更小的平均節(jié)點(diǎn)故障率，這對(duì)實(shí)際應(yīng)用具有吸引力。

關(guān)鍵詞：變換原理;再生碼;異構(gòu)分布式存儲(chǔ);數(shù)據(jù)重構(gòu);節(jié)點(diǎn)存儲(chǔ);對(duì)比分析

中圖分類號(hào)：TN915.41-34

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X（2019）24-0104-04

0 引言

近年來(lái)，分布式存儲(chǔ)已成為大規(guī)模數(shù)據(jù)存儲(chǔ)的主流方案，如谷歌的分布式文件系統(tǒng)GFS（ Google File Sys-tem），亞馬遜的EBS（ Elastic Block Store）[1]等。在一個(gè)分布式存儲(chǔ)系統(tǒng)（DSS）中，數(shù)據(jù)被編碼并分散地存儲(chǔ)在多個(gè)存儲(chǔ)節(jié)點(diǎn)來(lái)實(shí)現(xiàn)長(zhǎng)久穩(wěn)定的數(shù)據(jù)存儲(chǔ)，這些存儲(chǔ)節(jié)點(diǎn)通常單個(gè)是不穩(wěn)定的，容易發(fā)生故障。為了維持系統(tǒng)穩(wěn)定性，系統(tǒng)必須能夠修復(fù)故障節(jié)點(diǎn)。

相比傳統(tǒng)的兩種故障修復(fù)策略，即復(fù)制[2]和糾刪碼技術(shù)[3]，再生碼（RC）技術(shù)因在節(jié)點(diǎn)存儲(chǔ)和修復(fù)帶寬兩方面都有效而受到廣泛關(guān)注[4]。復(fù)制策略是最簡(jiǎn)單、最直接地增加冗余的方式，由于具有最小的修復(fù)帶寬（即修復(fù)一個(gè)故障節(jié)點(diǎn)所需下載數(shù)據(jù)的總量）并且沒(méi)有額外的計(jì)算消耗，因此應(yīng)用在早期的很多實(shí)際DSSc4]，然而，復(fù)制要求的存儲(chǔ)消耗是巨大的。作為復(fù)制策略的推廣，糾刪碼能夠提供更好的存儲(chǔ)效率，即原始文件大小與存儲(chǔ)空間的比率。然而，當(dāng)修復(fù)故障節(jié)點(diǎn)時(shí)，采用糾刪碼會(huì)導(dǎo)致大量修復(fù)帶寬。研究表明，在節(jié)點(diǎn)存儲(chǔ)和修復(fù)帶寬之間存在一個(gè)tradeoff，并且RC能夠獲得這個(gè)tradeoff曲線上的點(diǎn)[4]。

在這個(gè)存儲(chǔ)一帶寬tradeoff曲線上存在一個(gè)特殊點(diǎn)，稱作最小存儲(chǔ)再生（MSR）點(diǎn)，能夠獲得這個(gè)點(diǎn)的RC稱為MSR碼。文獻(xiàn)[5]采用積矩陣（PM）理論來(lái)為同構(gòu)DSS構(gòu)建了MSR碼結(jié)構(gòu)。這里同構(gòu)DSS指系統(tǒng)中的存儲(chǔ)節(jié)點(diǎn)具有相同的性能參數(shù)，如節(jié)點(diǎn)存儲(chǔ)容量、修復(fù)帶寬等。異構(gòu)系統(tǒng)包含具有不同特性的存儲(chǔ)節(jié)點(diǎn)，應(yīng)用實(shí)例包括P2P （Peer-to-Peer）云存儲(chǔ)[6]，用于視頻點(diǎn)播的互聯(lián)網(wǎng)緩存系統(tǒng)[7-8]以及異構(gòu)無(wú)線網(wǎng)絡(luò)中的緩存系統(tǒng)[9]。關(guān)于異構(gòu)DSS中的RC研究最近開始出現(xiàn)。文獻(xiàn)[10]提出了擴(kuò)展的PM （EPM）理論，并基于此設(shè)計(jì)了最優(yōu)的異構(gòu)RC結(jié)構(gòu)，然而，提出的EPM理論以及異構(gòu)RC結(jié)構(gòu)局限于修復(fù)帶寬異構(gòu)的場(chǎng)景，并不確定能否用于存儲(chǔ)異構(gòu)DSS。文獻(xiàn)[11]考慮一個(gè)存儲(chǔ)和帶寬均異構(gòu)DSS，其中，系統(tǒng)中存在一個(gè)超級(jí)（ Super）節(jié)點(diǎn)，相比其他節(jié)點(diǎn)，這個(gè)超級(jí)節(jié)點(diǎn)具有更大的存儲(chǔ)容量以及更高的穩(wěn)定性和可得性，作者提供了這種系統(tǒng)的異構(gòu)編碼方案。

在文獻(xiàn)[5]的基礎(chǔ)上，考慮文獻(xiàn)[11]中提出的超級(jí)節(jié)點(diǎn)模型，其中系統(tǒng)節(jié)點(diǎn)具有不同的存儲(chǔ)容量和修復(fù)帶寬，提出一種簡(jiǎn)單有效的編碼變換原理，能夠?qū)⑽墨I(xiàn)[5]中構(gòu)建的MSR碼（同構(gòu)RC）通過(guò)簡(jiǎn)單的變換得到新的RC，新的RC能夠適用于存儲(chǔ)和修復(fù)帶寬均異構(gòu)的超級(jí)節(jié)點(diǎn)模型。理論上證明了新RC的數(shù)據(jù)重構(gòu)和數(shù)據(jù)修復(fù)性質(zhì)。進(jìn)一步，通過(guò)編碼實(shí)例演示了新RC的數(shù)據(jù)修復(fù)過(guò)程。通過(guò)對(duì)比傳統(tǒng)同構(gòu)RC，即MSR碼，提供了新的存儲(chǔ)和帶寬異構(gòu)RC的性能分析。

1 系統(tǒng)模型

在同構(gòu)系統(tǒng)中，一個(gè)（n，k，d，α，β）RC能夠在一個(gè)含有n個(gè)存儲(chǔ)節(jié)點(diǎn)的DSS中存儲(chǔ)一個(gè)大小為B的數(shù)據(jù)文件，每個(gè)節(jié)點(diǎn)存儲(chǔ)α個(gè)符號(hào)，這些符號(hào)來(lái)自大小為q的有限域Fq。要求一個(gè)合法用戶（DC）能夠連接n個(gè)節(jié)點(diǎn)中的k個(gè)并下載數(shù)據(jù)實(shí)現(xiàn)原始文件的重構(gòu)，這個(gè)過(guò)程叫作數(shù)據(jù)重構(gòu)。此外，當(dāng)一個(gè)節(jié)點(diǎn)發(fā)生故障時(shí)，一個(gè)（n，k，d，a，β ）RC允許新的替換節(jié)點(diǎn)連接剩余n-l個(gè)存活節(jié)點(diǎn)中的d個(gè)節(jié)點(diǎn)（稱作幫助節(jié)點(diǎn)）.并從每個(gè)幫助節(jié)點(diǎn)下載β個(gè)數(shù)據(jù)來(lái)修復(fù)故障節(jié)點(diǎn)。其中，β稱為幫助節(jié)點(diǎn)的修復(fù)帶寬，這個(gè)過(guò)程稱為數(shù)據(jù)修復(fù)。修復(fù)一個(gè)故障節(jié)點(diǎn)所需的下載數(shù)據(jù)總量為d，β，稱為總修復(fù)帶寬γ，即γ=dβ（≥α）。

考慮超級(jí)節(jié)點(diǎn)系統(tǒng)[11]，其中包含1個(gè)超級(jí)節(jié)點(diǎn)，它具有更高的存儲(chǔ)容量和修復(fù)帶寬，標(biāo)記其存儲(chǔ)容量和修復(fù)帶寬分別為αs和βs。此外，系統(tǒng)還包含h-l個(gè)普通節(jié)點(diǎn)，它們之間具有相同的存儲(chǔ)容量和相同的修復(fù)帶寬，標(biāo)記每個(gè)普通節(jié)點(diǎn)的存儲(chǔ)容量和修復(fù)帶寬分別為αu和βu，并滿足αs= 2au，βs=2βu。這樣，系統(tǒng)整體上是一個(gè)存儲(chǔ)異構(gòu)，即αs≠αu，修復(fù)帶寬也異構(gòu)的系統(tǒng)，即βs≠βu。這種情況在實(shí)際中是有可能的，比如在一個(gè)P2P備份系統(tǒng)中，這個(gè)超級(jí)節(jié)點(diǎn)可能是服務(wù)器（ServiceProvider），它比其他的Peers具有更高的可得性，提供更大的容量和帶寬。

當(dāng)αs=au并且βs=βu時(shí)，考慮的系統(tǒng)模型就變成了一個(gè)同構(gòu)系統(tǒng)，即每個(gè)節(jié)點(diǎn)的存儲(chǔ)容量和修復(fù)帶寬均相同。

2 存儲(chǔ)和帶寬異構(gòu)編碼變換原理

針對(duì)存儲(chǔ)和修復(fù)帶寬均異構(gòu)的超級(jí)節(jié)點(diǎn)場(chǎng)景，將同構(gòu)RC，即PM-MSR碼C進(jìn)行變換得到新的RC，標(biāo)記為碼C，具體的編碼變換原理如下：

碼C是在p=i時(shí)設(shè)計(jì)的，因此在碼C中令βu=1，并令αu=a，這樣編碼變換原理的條件為：C中剩余的每1行分別對(duì)應(yīng)h-l個(gè)普通節(jié)點(diǎn)中的每一個(gè)，即c1，c2表示存儲(chǔ)在超級(jí)節(jié)點(diǎn)V1上的內(nèi)容。ci（i∈[3，n]）表示存儲(chǔ)在普通節(jié)點(diǎn)Vi-1上的數(shù)據(jù)，這樣得到新的再生碼C。碼C的數(shù)據(jù)重構(gòu)和數(shù)據(jù)修復(fù)性質(zhì)將由下面兩個(gè)定理給出。

定理1（數(shù)據(jù)重構(gòu)）：在碼C中，任意用戶（DC）能夠連接k個(gè)普通節(jié)點(diǎn)或者連接1個(gè)超級(jí)節(jié)點(diǎn)和k-2個(gè)普通節(jié)點(diǎn)，實(shí)現(xiàn)原始文件的重構(gòu)。

證明：在碼C中，任意k個(gè)普通節(jié)點(diǎn)對(duì)應(yīng)原始碼字矩陣C中除去前2行的任k行，這樣，一個(gè)用戶（DC）連接任意k個(gè)普通節(jié)點(diǎn)，等價(jià)于碼c中這個(gè)DC連接除去節(jié)點(diǎn)V1和V2的任意k個(gè)節(jié)點(diǎn)，根據(jù)碼c的數(shù)據(jù)重構(gòu)性質(zhì)（即任意k個(gè)節(jié)點(diǎn)可以實(shí)現(xiàn)原始文件的重構(gòu)）可知，這個(gè)DC能夠重構(gòu)原始文件;另一方面，在碼C中，超級(jí)節(jié)點(diǎn)對(duì)應(yīng)原始碼字矩陣c中前2行，一個(gè)DC連接1個(gè)超級(jí)節(jié)點(diǎn)和k -2個(gè)普通節(jié)點(diǎn)，等價(jià)于碼C中這個(gè)DC連接節(jié)點(diǎn)Vi和V2以及其余任意k-2個(gè)節(jié)點(diǎn)，根據(jù)碼C的數(shù)據(jù)重構(gòu)性質(zhì)可知，該DC能夠?qū)崿F(xiàn)原始文件重構(gòu)。

定理2（數(shù)據(jù)修復(fù)）：在碼C中，當(dāng)一個(gè)普通節(jié)點(diǎn)發(fā)生故障時(shí)，新的替換節(jié)點(diǎn)能夠連接任意d個(gè)存活的普通節(jié)點(diǎn)，并從每個(gè)普通節(jié)點(diǎn)下載βu=1個(gè)符號(hào)可以修復(fù)故障節(jié)點(diǎn);新的替換節(jié)點(diǎn)也可連接1個(gè)超級(jí)節(jié)和任意d-2個(gè)存活的普通節(jié)點(diǎn)，并從超級(jí)節(jié)點(diǎn)下載βs=2個(gè)符號(hào)，從每個(gè)普通節(jié)點(diǎn)下載βu=1個(gè)符號(hào)，可以修復(fù)這個(gè)故障節(jié)點(diǎn)。

證明：在碼C中，由于任意d個(gè)普通節(jié)點(diǎn)對(duì)應(yīng)原始碼字矩陣C中除去前2行的任意d行，一個(gè)故障的普通節(jié)點(diǎn)的替換節(jié)點(diǎn)連接任意d個(gè)普通節(jié)點(diǎn)并從每個(gè)普通節(jié)點(diǎn)下載βu=1個(gè)符號(hào)，等價(jià)于碼C中這個(gè)替換節(jié)點(diǎn)連接除去節(jié)點(diǎn)Vi和V2的任意d個(gè)節(jié)點(diǎn)，并從每個(gè)節(jié)點(diǎn)下載β=1個(gè)符號(hào)，根據(jù)碼c的數(shù)據(jù)修復(fù)性質(zhì)（即任意d個(gè)存活節(jié)點(diǎn)可以實(shí)現(xiàn)故障修復(fù)），該替換節(jié)點(diǎn)能夠修復(fù)這個(gè)故障節(jié)點(diǎn);此外，在碼C中，超級(jí)節(jié)點(diǎn)對(duì)應(yīng)原始碼字矩陣c中前2行，新的替換節(jié)點(diǎn)連接1個(gè)超級(jí)節(jié)和任意d-2個(gè)存活的普通節(jié)點(diǎn)，并從超級(jí)節(jié)點(diǎn)下載βs=2個(gè)符號(hào)，從每個(gè)普通節(jié)點(diǎn)下載βu=1個(gè)符號(hào)，這等價(jià)于碼c中這個(gè)替換節(jié)點(diǎn)連接節(jié)點(diǎn)V1和V2以及其余任意d-2個(gè)存活的節(jié)點(diǎn)，并從節(jié)點(diǎn)V1和V2一共下載2β=2個(gè)符號(hào)，從其余每個(gè)節(jié)點(diǎn)下載p=i個(gè)符號(hào)，根據(jù)碼C的數(shù)據(jù)修復(fù)性質(zhì)，該替換節(jié)點(diǎn)能夠?qū)崿F(xiàn)故障節(jié)點(diǎn)的修復(fù)。

理論上，超級(jí)節(jié)點(diǎn)發(fā)生故障，等價(jià)于2個(gè)普通節(jié)點(diǎn)故障，通過(guò)完成2個(gè)普通節(jié)點(diǎn)的修復(fù)即可實(shí)現(xiàn)超級(jí)節(jié)點(diǎn)的修復(fù)。

3 討論分析

通過(guò)對(duì)比傳統(tǒng)同構(gòu)再生碼PM-MSR碼C和存儲(chǔ)帶寬異構(gòu)再生碼C，在公式（1）下給出這兩種編碼的主要性能參數(shù)如表1所示。其中，假設(shè)普通節(jié)點(diǎn)單位時(shí)間的故障率為F，對(duì)于同構(gòu)再生碼C，平均節(jié)點(diǎn)故障率為fe =f;而對(duì)于碼e，由于超級(jí)節(jié)點(diǎn)具有更高的穩(wěn)定性和可靠性，因此可以假設(shè)超級(jí)節(jié)點(diǎn)的故障率為fs（

對(duì)比發(fā)現(xiàn)，碼C和碼C具有相同的總存儲(chǔ)消耗以及修復(fù)一個(gè)故障節(jié)點(diǎn)的帶寬消耗，然而，碼C具有更小的平均節(jié)點(diǎn)故障率，因而在一段時(shí)間A內(nèi)系統(tǒng)因修復(fù)故障維持穩(wěn)定性而消耗的總修復(fù)帶寬更小，這對(duì)實(shí)際應(yīng)用具有吸引力。此外，碼C可以具有更小的幫助節(jié)點(diǎn)個(gè)數(shù)，通常情況下，更少的幫助節(jié)點(diǎn)是更有利的，因?yàn)閹椭迯?fù)故障節(jié)點(diǎn)會(huì)給存活節(jié)點(diǎn)帶來(lái)額外的工作負(fù)擔(dān)，更少的幫助節(jié)點(diǎn)表明修復(fù)一個(gè)故障節(jié)點(diǎn)需要的存活節(jié)點(diǎn)更少，這樣引起系統(tǒng)的額外負(fù)擔(dān)更小。

4 結(jié)論

基于乘積矩陣（PM）的最小存儲(chǔ)再生碼（PM-MSR）能夠用于同構(gòu)分布式存儲(chǔ)系統(tǒng)，具有最小的節(jié)點(diǎn)存儲(chǔ)。提出的異構(gòu)再生碼變換原理能夠?qū)M-MSR碼變換得到新的存儲(chǔ)帶寬異構(gòu)再生碼。理論上證明了這個(gè)異構(gòu)再生碼的數(shù)據(jù)重構(gòu)和數(shù)據(jù)修復(fù)性質(zhì)，并通過(guò)實(shí)例演示了這個(gè)異構(gòu)再生碼的故障修復(fù)過(guò)程。通過(guò)對(duì)比分析PM-MSR碼，在相同的存儲(chǔ)消耗和相同的修復(fù)一個(gè)故障節(jié)點(diǎn)的帶寬消耗條件下，這個(gè)異構(gòu)再生碼具有更小的平均

參考文獻(xiàn)

[1]齊鳳林，宮慶媛，周揚(yáng)州，等，分布式存儲(chǔ)再生碼數(shù)據(jù)修復(fù)的節(jié)點(diǎn)選擇方案 [J].計(jì)算機(jī)研究與5發(fā)展 . 2015 （ z2） ： 68-74.

QI Fenglin， GONG Qingyuan， ZHOU Yangfan， et al. Hetero-geneity-aware node selection for data repair in distributed stor-age systems [J]. Journal of computer research and develop-ment. 2015（S2） ： 68-74.

[2] BHAGWAN R， MOORE D. SAVAGE S， et al. Replicationstrategies for highly available peer-to-peer storage [J]. Future di-rections in distributed computing， 2002， 2584（5） ： 153-158.

[3] WEATHERSPOON H， KUBIATOWICZ J D. Erasure codingvs. replication： a quantitative comparison [J]. Lecture notes incomputer science. 2002， 2429： 328-337.

[4] DIMAKIS A G. GODFREY P B， WU Y. et al. Network cod-ing for distributed storage systems [J]. IEEE transactions on in-formation theory. 2010. 56（9） ： 4539-4551.

[5] RASHMI K V. SHAH N B， KUMAR P V. Optimal exact-re-generating codes for distributed storage at the MSR and MBRpoints via a product-matrix construction [J]. IEEE transactionson information theory ， 2011， 57（ 8） ： 5227-5239.