非MDS碼存儲系統(tǒng)的通用可靠性模型

聶世強，鄭旭達(dá)，劉釗華，伍衛(wèi)國，董小社，張興軍

(西安交通大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，陜西 西安 710049)

容錯機制在大規(guī)模分布式存儲系統(tǒng)中是不可或缺的。大規(guī)模存儲系統(tǒng)由成千上萬臺服務(wù)器組成，諸多研究報告指出節(jié)點失效成為常態(tài)[1-3]。近年來，谷歌等大型數(shù)據(jù)中心的統(tǒng)計數(shù)據(jù)表明，平均每天都會有1%～2%的節(jié)點失效[1]。服務(wù)器失效引起數(shù)據(jù)丟失造成的損失是無法估量的。目前存儲系統(tǒng)常用的數(shù)據(jù)冗余方法有多副本、糾刪碼等。多副本是將數(shù)據(jù)復(fù)制多份分別存放在不同的存儲節(jié)點，只要數(shù)據(jù)的副本所在節(jié)點不同時失效，數(shù)據(jù)便不會丟失[4]，糾刪碼是將數(shù)據(jù)分割為相等的數(shù)據(jù)塊，采用編碼策略生成校驗塊，部分?jǐn)?shù)據(jù)塊丟失后，可以通過編碼恢復(fù)[5]。不同于多副本對存儲空間的大量需求，糾刪碼可以顯著降低存儲開銷，因此被廣泛使用，如云存儲系統(tǒng)：Giza[6]、Hybris[7]等。然而目前糾刪碼在可靠性、存儲利用率等方面都不同程度地存在缺陷，難以同時達(dá)到理想的狀態(tài)[8-9]。

可靠性可以判斷系統(tǒng)或設(shè)備是否具備持續(xù)有效提供正確數(shù)據(jù)服務(wù)的能力，因此在存儲系統(tǒng)中，可靠性是與性能和費用等指標(biāo)重要性相當(dāng)?shù)囊粋€評價標(biāo)準(zhǔn)。為了探究存儲系統(tǒng)可靠性與諸多因素的關(guān)系，很多學(xué)者都對存儲系統(tǒng)可靠性展開了廣泛的研究。早期如PATTERSON采用馬爾可夫模型分析磁盤矩陣系統(tǒng)可靠性，并以平均數(shù)據(jù)丟失時間 (Mean Time To Data Loss，MTTDL) 作為可靠性評價指標(biāo)[10]。當(dāng)前研究的方向有考慮數(shù)據(jù)放置算法[11]、數(shù)據(jù)中心物理拓?fù)浣Y(jié)構(gòu)[12]等因素對系統(tǒng)可靠性的影響。穆飛等針對大規(guī)模副本存儲系統(tǒng)建立了馬爾可夫模型，度量了系統(tǒng)規(guī)模、副本階數(shù)、節(jié)點容量等對可靠性的影響[13]。HUANG等提出了在Windows Azure存儲系統(tǒng)使用局部修復(fù)碼(Locally Repairable Codes，LRC)以降低數(shù)據(jù)修復(fù)過程中的網(wǎng)絡(luò)傳輸數(shù)據(jù)量，并建立了馬爾可夫模型，對局部修復(fù)碼與里德-所羅門碼(Reed-Solomon codes，RS)進(jìn)行可靠性的比較[14]。同時也有大量對于糾刪碼的研究[15-17]。HU等人根據(jù)存儲介質(zhì)的可靠性提出變長的UFP-LRC碼[18]，并對其可靠性進(jìn)行數(shù)值分析。郝曉慧等也對局部修復(fù)碼的構(gòu)造進(jìn)行了研究[19]。HAFNER等對低密度奇偶校驗碼( Low-Density Parity-Check，LDPC)和WEAVER碼兩種非最大距離可分碼(Maximum Distance Separable code，MDS)建立了可靠性模型，但是并未針對所有非最大距離可分碼進(jìn)行研究，該方法不具通用性[20]。

綜上所述，當(dāng)前對存儲系統(tǒng)可靠性研究涉及了諸多方面，對特定的非最大距離可分碼與存儲系統(tǒng)可靠性分析也有相關(guān)研究。然而對非最大距離可分碼的數(shù)據(jù)失效若干塊后，剩余塊的可修復(fù)概率求解仍是尚未解決的問題，并且針對采用非最大距離可分碼的存儲系統(tǒng)也缺乏較為通用的可靠性模型。因此，筆者對采用非最大距離可分碼的存儲系統(tǒng)可靠性進(jìn)行了研究。與現(xiàn)有研究基于特定校驗碼以抽樣概率計算方法不同，從非最大距離可分碼的構(gòu)造矩陣入手，提出一種求解非最大距離可分碼丟失若干塊后的可修復(fù)概率計算方法，并提出了一種采用面向非最大距離可分碼存儲系統(tǒng)的通用可靠性模型，最后數(shù)值分析以局部修復(fù)碼為例驗證了模型的正確性，并且比較了不同因素對存儲系統(tǒng)可靠性的影響。

1 存儲系統(tǒng)可靠性模型

1.1 背景知識

分布式存儲系統(tǒng)由多個對象存儲設(shè)備 (Object-based Storage Device，OSD)組成。存儲系統(tǒng)對外提供的數(shù)據(jù)讀寫單元以對象為粒度，客戶端的對象X會在存儲系統(tǒng)內(nèi)部分割為d個數(shù)據(jù)塊，并且按照不同的糾刪碼規(guī)則生成p個校驗塊；對象X的數(shù)據(jù)塊和校驗塊被隨機分布到所有的存儲節(jié)點中，同一對象的數(shù)據(jù)塊和校驗塊不會在相同存儲節(jié)點存儲。

若采用多副本或最大距離可分碼存儲系統(tǒng)建模非最大距離可分碼存儲系統(tǒng)可靠性，其結(jié)果是不準(zhǔn)確的。因為多副本和糾刪碼中的最大距離可分碼的容錯能力是確定的，而非最大距離可分碼的容錯能力是具有一定概率的，以(6，2，2)局部修復(fù)碼為例說明，對象X被分割為6個數(shù)據(jù)塊x0，x1，x2，x3，x4，x5，并生成局部效驗塊px，py和全局校驗塊p0，p1，由于局部修復(fù)碼是非最大距離可分碼，它是無法容忍任意4個塊失效的，如圖1所示。

(a) 失效x0、x1、x3和x4節(jié)點

(b) 失效x0、x1、x2和px節(jié)點

圖1(a)和(b)所示分別表示(6，2，2)局部修復(fù)碼失效4個塊的2種不同情況，對于圖(a)來說，失效x0，x1，x3和x4節(jié)點，可以使用px，py和p0，p14個校驗塊修復(fù)對象X；對于圖(b)來說，失效x0，x1，x2和px節(jié)點以后，校驗塊py對于修復(fù)過程無任何意義，校驗塊p0和p1只能修復(fù)2個數(shù)據(jù)塊，因此對象X無法恢復(fù)，對于(6，2，2)局部修復(fù)碼中丟失任意4個塊，對象X只有87%的概率可以恢復(fù)[14]。

算法1非MDS碼可恢復(fù)概率求解算法。

輸入：

M：非MDS的m×n生成子矩陣。

lost：丟失的塊數(shù)(任意的數(shù)據(jù)塊和校驗塊)。

輸出：

P：可恢復(fù)概率值。

過程：

recovery=0；∥可恢復(fù)組合數(shù)

total=0；∥所有丟失塊的可能組合數(shù)

block=[i for i in range(m)]；

for(i=0；i++；i≤lost) ∥i表示丟失的校驗塊數(shù)

all_combin+=combinations(m，i)]

while(i

∥遍歷丟失的校驗塊數(shù)

parity=length(all_combin[i])

if(lost-parity = =0)：∥未丟失數(shù)據(jù)塊

recovery+=1；

total+=1；

else：

∥丟失數(shù)據(jù)塊的所有組合

data += combinations(lost - parity)；

for(j=0；j

matrix_A=M [all_combin[i]^block，：]；

matrix_B= matrix_A[：，data[j]]；

row，column=matrix_B。shape；

if( row =column)：

recovery+=1 if det(matrix_B)= =1 else 0

else( row>column)：

for sub_matrix in matrix_B：

if det(sub_matrix)= =1：

recovery+=1；

break；

total+=1；

p=recovery/total；

return P；∥遍歷求解可恢復(fù)的概率值。

針對最大距離可分碼和多副本存儲系統(tǒng)的可靠性模型，大都基于馬爾可夫理論，通常只考慮數(shù)據(jù)丟失的情況，不考慮其他諸如內(nèi)核升級、臨時性停電導(dǎo)致的數(shù)據(jù)臨時性無法訪問，模型中僅考慮硬盤的失效和修復(fù)。筆者所建立的模型也遵循此前提。

1.2 非最大距離可分碼可恢復(fù)概率求解算法

為了建立針對采用非最大距離可分碼的存儲系統(tǒng)的較為通用的可靠性理論模型，筆者提出了一種基于矩陣運算的求解任意非最大距離可分碼失效若干塊后可恢復(fù)概率求解算法。這里非最大距離可分碼指的是不滿足Singleton邊界條件的編碼方式的糾刪碼，如局部修復(fù)碼、低密度奇偶校驗碼和WEAVER碼等。糾刪碼的不同之處在于編碼和譯碼過程，編碼過程中將對象分割成多個數(shù)據(jù)塊，不同的糾刪碼生成特定的生成矩陣，對數(shù)據(jù)塊和生成矩陣進(jìn)行矩陣運算生成校驗塊，在可容忍的范圍內(nèi)丟失若干塊后，剩余的塊和生成矩陣逆運算能恢復(fù)出丟失的塊。

表1 模型中包含的變量和含義

1.3 模型描述

使用MTTDL平均數(shù)據(jù)丟失時間作為非最大距離可分碼存儲系統(tǒng)的可靠性評價指標(biāo)。首先定義了如表1中的變量和其含義，特別指出的是表1中k的含義是指非最大距離可分碼中失效任意k塊都能恢復(fù)的最大值。

非最大距離可分碼存儲系統(tǒng)馬爾可夫模型如圖2所示。

圖2 非最大距離可分碼存儲系統(tǒng)可靠性模型

首先計算非最大距離可分碼存儲系統(tǒng)狀態(tài)轉(zhuǎn)移圖中的各個狀態(tài)間的轉(zhuǎn)換速率，即狀態(tài)Si到狀態(tài)Si+1的失效速率，狀態(tài)Si到狀態(tài)Si-1的修復(fù)速率，狀態(tài)Si到Sstop吸收態(tài)的速率。

狀態(tài)Si到狀態(tài)Si+1的失效速率計算需要分為2個階段。第1個階段是失效k個對象存儲設(shè)備節(jié)點以內(nèi)的情況，包括狀態(tài)S0到狀態(tài)Sk的階段。因為對象的數(shù)據(jù)塊和校驗塊是隨機分布到所有對象存儲設(shè)備節(jié)點的，則失效節(jié)點數(shù)目小于k的情況下系統(tǒng)失效任何節(jié)點數(shù)目都不會造成數(shù)據(jù)丟失，狀態(tài)Si轉(zhuǎn)換到狀態(tài)Si+1的失效速率為r(n-i)。第2階段是失效節(jié)點數(shù)目大于k的情況，在狀態(tài)Sk到狀態(tài)Sp的階段，若失效i個節(jié)點后其下一個狀態(tài)則可能是Sstop狀態(tài)或Si+1狀態(tài)。

(1) 若狀態(tài)Si的下一狀態(tài)是Si+1，不發(fā)生數(shù)據(jù)丟失情況的失效速率：

(1)

(2) 若狀態(tài)Si的下一狀態(tài)是Sstop，則發(fā)生數(shù)據(jù)丟失情況的概率：

(2)

對象存儲系統(tǒng)平均每個存儲節(jié)點的存儲數(shù)據(jù)量為C/n，節(jié)點失效后數(shù)據(jù)的平均修復(fù)時間為C/nb，則狀態(tài)Si到狀態(tài)Si-1的修復(fù)速率為inb/C。

通過以上分析能夠得到非最大距離可分存儲系統(tǒng)馬爾可夫模型的狀態(tài)轉(zhuǎn)移矩陣Q，狀態(tài)轉(zhuǎn)移矩陣Q的元素表達(dá)式如下：

(3)

2 模型分析

非局部修復(fù)碼存儲系統(tǒng)可靠性影響因素眾多，筆者利用建立的可靠性模型量化不同因素對可靠性的影響。非局部修復(fù)存儲系統(tǒng)可靠性數(shù)值計算程序采用python語言實現(xiàn)。設(shè)單個硬盤容量為2 TB，數(shù)據(jù)修復(fù)帶寬只占系統(tǒng)總帶寬的一部分，假設(shè)系統(tǒng)分給對象存儲設(shè)備節(jié)點恢復(fù)的帶寬為30 MB/s，單存儲節(jié)點的平均失效時間為5年。首先比較了在相同配置下常見的RS碼(最大距離可分碼)和局部修復(fù)碼(非最大距離可分碼)對可靠性的影響。如圖3所示，比較(6，4)RS碼、(6，2，2)局部修復(fù)碼和(6，3，2)局部修復(fù)碼的可靠性，從圖中可以看出，在相同系統(tǒng)容量下(6，3，2)局部修復(fù)碼的可靠性最高，(6，4)RS碼次之，(6，2，2)局部修復(fù)碼最低。在系統(tǒng)容量較低時，采用不同配置的糾刪碼存儲系統(tǒng)MTTDL較為明顯，呈現(xiàn)數(shù)倍的差異；隨著存儲系統(tǒng)容量的增大，不同配置的糾刪碼存儲系統(tǒng)可靠性都隨之下降。(6，3，2)局部修復(fù)碼最低可容忍3個塊丟失，最高可容忍5個塊丟失，而(6，4)RS碼僅能容忍4個塊丟失，(6，2，2)局部修復(fù)碼最高可以容忍4個塊丟失。實驗仿真結(jié)果與理論分析較為一致，可以一定程度說明模型是符合真實情況的。

隨后量化對象存儲設(shè)備節(jié)點的可靠性對系統(tǒng)的影響。實驗計算分析針對PB級存儲系統(tǒng)，固定其他參數(shù)不變，僅改變硬盤的MTTDL，比較系統(tǒng)MTTDL變化趨勢，計算結(jié)果如圖4所示?？梢园l(fā)現(xiàn)，系統(tǒng)的平均數(shù)據(jù)丟失時間隨著存儲系統(tǒng)規(guī)模的增加而不斷降低，雖然采用了糾刪碼容錯，系統(tǒng)可以容忍一定數(shù)量的硬盤失效而不造成數(shù)據(jù)丟失，但是在相同存儲規(guī)模下，硬盤失效時間為5年的系統(tǒng)的可靠性更大。主要是因為當(dāng)對象存儲設(shè)備節(jié)點的可靠性較低時，很可能出現(xiàn)某些硬盤失效后系統(tǒng)進(jìn)行修復(fù)過程中又出現(xiàn)其他硬盤失效，頻繁失效造成的數(shù)據(jù)恢復(fù)需求超出系統(tǒng)的修復(fù)能力，因此系統(tǒng)的可靠性將會大大降低。

圖3 糾刪碼配置與存儲系統(tǒng)可靠性的關(guān)系

圖4 硬盤壽命與存儲系統(tǒng)可靠性的關(guān)系

存儲系統(tǒng)的網(wǎng)絡(luò)帶寬不僅僅影響系統(tǒng)的性能，也影響了節(jié)點失效后系統(tǒng)的修復(fù)過程，如圖5 所示。比較不同的修復(fù)帶寬對可靠性的影響，可以看出，修復(fù)帶寬為60 MB/s時系統(tǒng)的可靠性比修復(fù)帶寬為30 MB/s時更高，并且隨著存儲規(guī)模的增大而降低。主要是因為系統(tǒng)存儲節(jié)點失效后其修復(fù)時間受失效對象存儲設(shè)備節(jié)點數(shù)目、對象存儲設(shè)備節(jié)點容量和修復(fù)帶寬的影響，修復(fù)帶寬越大，修復(fù)的時間越短，在修復(fù)時間內(nèi)其他存儲節(jié)點發(fā)生失效的概率越低，因此數(shù)據(jù)丟失的概率越低，存儲系統(tǒng)更加可靠。

圖5 帶寬與存儲系統(tǒng)可靠性的關(guān)系

圖6 硬盤容量與存儲系統(tǒng)可靠性的關(guān)系

最后考察存儲系統(tǒng)可靠性與存儲節(jié)點容量的關(guān)系，如圖6所示。在相同存儲規(guī)模下，存儲節(jié)點容量越大，可靠性越高。因為系統(tǒng)存儲節(jié)點失效后其修復(fù)時間與節(jié)點容量成正比，容量越大，修復(fù)時間越長；而存儲容量越大，在相同存儲規(guī)模的條件下，其存儲節(jié)點數(shù)目也會相應(yīng)減少。因此可以得出在相同存儲規(guī)模的條件下，存儲節(jié)點數(shù)目對可靠性的影響比存儲節(jié)點容量對可靠性的影響更大。隨后在存儲設(shè)備節(jié)點數(shù)目相等的條件下，對具有不同存儲節(jié)點容量的存儲系統(tǒng)進(jìn)行比較，圖中存儲節(jié)點容量為1 TB時其存儲規(guī)模為0.2 PB，相對于的是存儲節(jié)點容量2 TB時存儲規(guī)模為0.4 TB。從圖中單硬盤容量2 TB的可靠性趨勢變化中可以看出，在存儲節(jié)點數(shù)相等的前提下，單硬盤容量2 TB組成的存儲系統(tǒng)比單硬盤容量1 TB組成的存儲系統(tǒng)可靠性更低。這也是與實際相契合的。

3 總 結(jié)

由于對大規(guī)模存儲系統(tǒng)的可靠性實測需要消耗數(shù)年的時間，開銷巨大，因此建立度量分布式存儲系統(tǒng)可靠性理論模型顯得尤為重要。面向大規(guī)模存儲系統(tǒng)，首先提出了通用的非最大距離可分碼失效若干塊后可恢復(fù)概率求解算法。隨后建立了可度量非最大距離可分碼存儲系統(tǒng)可靠性的理論模型。最后通過數(shù)值分析以局部修復(fù)碼為例驗證了模型的正確性，比較分析了存儲系統(tǒng)中不同糾刪碼配置參數(shù)、節(jié)點容量和節(jié)點失效時間、修復(fù)帶寬對系統(tǒng)可靠性的影響，為搭建真實的存儲系統(tǒng)提供了相應(yīng)的參考，具有一定的理論價值。