一種異構分布式存儲再生碼變換原理

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

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

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

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

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

1 系統(tǒng)模型

在同構系統(tǒng)中，一個（n，k，d，α，β）RC能夠在一個含有n個存儲節(jié)點的DSS中存儲一個大小為B的數(shù)據(jù)文件，每個節(jié)點存儲α個符號，這些符號來自大小為q的有限域Fq。要求一個合法用戶（DC）能夠連接n個節(jié)點中的k個并下載數(shù)據(jù)實現(xiàn)原始文件的重構，這個過程叫作數(shù)據(jù)重構。此外，當一個節(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)整體上是一個存儲異構，即αs≠αu，修復帶寬也異構的系統(tǒng)，即βs≠βu。這種情況在實際中是有可能的，比如在一個P2P備份系統(tǒng)中，這個超級節(jié)點可能是服務器（ServiceProvider），它比其他的Peers具有更高的可得性，提供更大的容量和帶寬。

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

2 存儲和帶寬異構編碼變換原理

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

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

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

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

定理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ù)修復性質（即任意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ù)修復性質，該替換節(jié)點能夠實現(xiàn)故障節(jié)點的修復。

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

3 討論分析

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

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

4 結論

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

參考文獻

[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.