一種異構(gòu)分布式存儲再生碼變換原理

苗斌 宋苗苗 李文慶 王文彥 董國法 王曉燕 張可可 徐宇柘 管萬春

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

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

中圖分類號：TN915.41-34

文獻標識碼：A

文章編號：1004-373X（2019）24-0104-04

0 引言

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

針對存儲和修復帶寬均異構(gòu)的超級節(jié)點場景，將同構(gòu)RC，即PM-MSR碼C進行變換得到新的RC，標記為碼C，具體的編碼變換原理如下：

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

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

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

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

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

理論上，超級節(jié)點發(fā)生故障，等價于2個普通節(jié)點故障，通過完成2個普通節(jié)點的修復即可實現(xiàn)超級節(jié)點的修復。

3 討論分析

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

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

4 結(jié)論

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

參考文獻

[1]齊鳳林，宮慶媛，周揚州，等，分布式存儲再生碼數(shù)據(jù)修復的節(jié)點選擇方案 [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.