摘  要：當(dāng)今，機(jī)群系統(tǒng)被廣泛地應(yīng)用于海量存儲(chǔ)系統(tǒng)。對(duì)數(shù)據(jù)有高可靠性要求的應(yīng)用，如何提高系統(tǒng)MTTF是人們研究的主要問題。本文提出了一個(gè)新的動(dòng)態(tài)備份策略，"并行數(shù)據(jù)備份策略"，通過詳細(xì)的理論分析，指出該策略可顯著地提高系統(tǒng)MTTF；還通過仿真實(shí)驗(yàn)，驗(yàn)證了其效果。
關(guān)鍵詞：海量存儲(chǔ);機(jī)群系統(tǒng);平均故障前時(shí)間

1 引言

在過去幾年里，機(jī)群系統(tǒng)被廣泛地應(yīng)用于海量存儲(chǔ)系統(tǒng)，比如，著名的Google文件系統(tǒng)就包含上千個(gè)基于linux的計(jì)算機(jī)。這樣做的好處有三個(gè)。第一，由于每個(gè)節(jié)點(diǎn)都是大批量生產(chǎn)的，整個(gè)系統(tǒng)的價(jià)格可以很低。第二，通過增減節(jié)點(diǎn)，系統(tǒng)可以簡(jiǎn)單地進(jìn)行擴(kuò)展。第三，通過在互相獨(dú)立的節(jié)點(diǎn)上備份數(shù)據(jù)，可以顯著地提高系統(tǒng)中數(shù)據(jù)的可靠性。

對(duì)存儲(chǔ)系統(tǒng)來說，系統(tǒng)的平均故障前時(shí)間（MTTF）是指系統(tǒng)中出現(xiàn)某個(gè)數(shù)據(jù)因所有的備份都丟失，而導(dǎo)致該數(shù)據(jù)無法挽回地丟失所需的平均時(shí)間。對(duì)于有較高數(shù)據(jù)可靠性要求的系統(tǒng)，系統(tǒng)的MTTF是衡量系統(tǒng)性能的一個(gè)重要指標(biāo)。提高系統(tǒng)MTTF的一個(gè)方法就是   提高數(shù)據(jù)的備份數(shù)。備份數(shù)的選擇需要綜合考慮，因?yàn)檫x擇過低的備份數(shù)，系統(tǒng)的MTTF不能滿足要求；而選擇過高的備份數(shù)，系統(tǒng)的存儲(chǔ)資源就被浪費(fèi)，特別是當(dāng)系統(tǒng)中包含大量數(shù)據(jù)的時(shí)候。另一個(gè)方面，考慮到機(jī)群系統(tǒng)中節(jié)點(diǎn)會(huì)不斷失效，因此還必須對(duì)備份數(shù)因節(jié)點(diǎn)失效而降低的數(shù)據(jù)進(jìn)行動(dòng)態(tài)備份，以提高系統(tǒng)MTTF。本文提出了一個(gè)新的動(dòng)態(tài)備份策略，"并行數(shù)據(jù)備份策略"，理論分析了其性能，并進(jìn)行了仿真實(shí)驗(yàn)。

2系統(tǒng)結(jié)構(gòu)和動(dòng)態(tài)備份策略                                 

整個(gè)系統(tǒng)的構(gòu)成情況如下。機(jī)群系統(tǒng)包含n個(gè)節(jié)點(diǎn)。系統(tǒng)中的所有對(duì)象狀態(tài)以狀態(tài)塊為單元進(jìn)行組織。系統(tǒng)中存儲(chǔ)的互不相同的狀態(tài)塊總數(shù)正比與節(jié)點(diǎn)總數(shù)。每個(gè)狀態(tài)塊有m個(gè)備份。同一個(gè)狀態(tài)塊的備份不能在一個(gè)節(jié)點(diǎn)上，以保證可靠性；一個(gè)節(jié)點(diǎn)可以同時(shí)存儲(chǔ)許多個(gè)狀態(tài)塊的備份。每個(gè)正常節(jié)點(diǎn)都會(huì)失效。

在出現(xiàn)一個(gè)節(jié)點(diǎn)失效后，系統(tǒng)的動(dòng)態(tài)備份策略為：1）為失效節(jié)點(diǎn)上的每個(gè)狀態(tài)塊，選擇一對(duì)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，源節(jié)點(diǎn)包含該狀態(tài)塊，目標(biāo)節(jié)點(diǎn)不包含；2）讓這些狀態(tài)塊，同時(shí)在各對(duì)應(yīng)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間開始轉(zhuǎn)移，直至轉(zhuǎn)移完畢。其中，各狀態(tài)塊的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的選擇應(yīng)盡可能互不重合，以使盡可能多的狀態(tài)塊轉(zhuǎn)移可并發(fā)進(jìn)行。另外，這個(gè)備份策略也意味著每個(gè)狀態(tài)塊的備份可存儲(chǔ)于任一節(jié)點(diǎn)上。下面，通過建立數(shù)學(xué)模型，理論估計(jì)該動(dòng)態(tài)備份策略下的系統(tǒng)MTTF。

3理論分析

考慮用Markov過程來描述這個(gè)模型。為此，做如下假設(shè)。節(jié)點(diǎn)的失效速率服從指數(shù)分布，均值為l。由于系統(tǒng)中節(jié)點(diǎn)數(shù)目巨大，所以在一個(gè)節(jié)點(diǎn)失效后，其上的狀態(tài)塊完全可以找到互不重復(fù)的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，狀態(tài)塊轉(zhuǎn)移可以并發(fā)進(jìn)行，可設(shè)轉(zhuǎn)移速率服從指數(shù)分布，均值為lb。另外，考慮到系統(tǒng)中的節(jié)點(diǎn)數(shù)目巨大，可以認(rèn)為系統(tǒng)在出現(xiàn)某狀態(tài)塊無法挽回丟失時(shí)，系統(tǒng)中正常工作的節(jié)點(diǎn)數(shù)依然維持在較高水平，與起始時(shí)的節(jié)點(diǎn)數(shù)n在同一個(gè)數(shù)量級(jí)。因此，可近似認(rèn)為系統(tǒng)中節(jié)點(diǎn)數(shù)始終為n。于是，取有幾個(gè)失效節(jié)點(diǎn)上的狀態(tài)塊正在進(jìn)行轉(zhuǎn)移為研究對(duì)象，可得狀態(tài)轉(zhuǎn)移圖如圖1。其中，m為每個(gè)狀態(tài)塊的原備份數(shù)；ai表示當(dāng)一個(gè)有n個(gè)節(jié)點(diǎn)的系統(tǒng)中有（i-1）個(gè)失效節(jié)點(diǎn)上的狀態(tài)塊正在進(jìn)行轉(zhuǎn)移時(shí)無狀態(tài)塊丟失，而再失效一個(gè)節(jié)點(diǎn)發(fā)生一狀態(tài)塊丟失的概率；狀態(tài)i‘（i>=m）表示系統(tǒng)中出現(xiàn)某狀態(tài)塊無法挽回地丟失。

圖1 系統(tǒng)的狀態(tài)轉(zhuǎn)移過程

因此，目標(biāo)就化為系統(tǒng)進(jìn)入狀態(tài)i‘的均值時(shí)間。這個(gè)系統(tǒng)可以近似看成一個(gè)狀態(tài)數(shù)為無窮的一維生滅過程。要求解進(jìn)入狀態(tài)i‘的瞬態(tài)概率，將涉及解一個(gè)含無窮多等式的微分方程組，這是很復(fù)雜的。但根據(jù)以往求一維生滅過程的穩(wěn)態(tài)解的經(jīng)驗(yàn)知道，  。因此，如果ln-1/mn很小，那隨著n的增加，Pn將急速下降。于是，當(dāng)n增加到一定值時(shí)，可以忽略其后的狀態(tài)。對(duì)一個(gè)典型的含1000個(gè)節(jié)點(diǎn)的機(jī)群系統(tǒng)，若節(jié)點(diǎn)的MTTF為一天，則系統(tǒng)中出現(xiàn)某節(jié)點(diǎn)失效的速率約為0.011/秒；而一個(gè)狀態(tài)塊的平均轉(zhuǎn)移時(shí)間可以在10秒鐘左右，即，轉(zhuǎn)移速率為0.1/秒；這兩個(gè)速率之比約為0.1。因此，可以忽略系統(tǒng)中n>=m的狀態(tài)，而把系統(tǒng)進(jìn)入狀態(tài)m‘的均值時(shí)間作為系統(tǒng)的MTTF。

[!--empirenews.page--]

下面，以m=3為例，求系統(tǒng)進(jìn)入狀態(tài)m‘的均值時(shí)間E3(T)。由一維生滅過程的瞬態(tài)分析，可得以下方程組。其中，Pi(t)表示在t時(shí)刻系統(tǒng)處于狀態(tài)i的概率。

這是一個(gè)四元常系數(shù)線性微分方程組，可通過消元法消為一元線性微分方程，解之，然后可以求出其他各元的解。再根據(jù)邊界條件，可以求出各解中的系數(shù)。系統(tǒng)的邊界條件為

   。 。

而E3(T)可表示為：

。。

為了求出E3(T)的具體值，還必須求出a3的值。限于篇幅，不加證明的給出如下求am的定理。

定理：如果一個(gè)擁有n個(gè)節(jié)點(diǎn)的機(jī)群系統(tǒng)，含kn個(gè)互不相同的數(shù)據(jù)塊，每個(gè)數(shù)據(jù)塊都有m個(gè)備份，每個(gè)備份隨機(jī)地分布于機(jī)群系統(tǒng)中不同的節(jié)點(diǎn)上，那么當(dāng)系統(tǒng)中出現(xiàn)有s-1個(gè)節(jié)點(diǎn)失效的時(shí)候，無數(shù)據(jù)塊丟失；而當(dāng)系統(tǒng)中出現(xiàn)有s個(gè)節(jié)點(diǎn)失效的時(shí)候，系統(tǒng)中出現(xiàn)某個(gè)數(shù)據(jù)塊無法挽回地丟失的概率為， 其中， 并且s>=1。

根據(jù)此定理，求出當(dāng)n=1000, m=3, k=100時(shí)a3=0.0006。

根據(jù)以上推導(dǎo)，可求出E3(T)在不同條件下的值，得到在n=1000, l=1/(24*3600) (/秒)的配置下，當(dāng)lb=0.1(/秒)時(shí)，E3(T)=319天；當(dāng)lb=0.05(/秒)時(shí)，E3(T)=86天；當(dāng)lb=0.01(/秒)時(shí)，E3(T)=2天。類似地，可求出m=2時(shí)系統(tǒng)進(jìn)入狀態(tài)m‘的均值時(shí)間E2(T)，得到在n=1000, l=1/(24*3600) (/秒)的配置下，當(dāng)lb=0.1(/秒)時(shí)，E2(T)=1.3小時(shí)；當(dāng)lb=0.05(/秒)時(shí)，E2(T)=0.73小時(shí)；當(dāng)lb=0.01(/秒)時(shí)，E2(T)=0.27小時(shí)。

分析以上數(shù)據(jù)可以得到兩個(gè)結(jié)論。第一，三個(gè)備份的系統(tǒng)比兩個(gè)備份的，能顯著地提升系統(tǒng)的MTTF。在通常配置下，三個(gè)備份的系統(tǒng)的MTTF可達(dá)幾十天；而兩個(gè)備份的系統(tǒng)的MTTF只能在1小時(shí)左右。第二，數(shù)據(jù)塊的轉(zhuǎn)移時(shí)間顯著地影響系統(tǒng)的MTTF，轉(zhuǎn)移時(shí)間越短，系統(tǒng)的MTTF越長(zhǎng)。

4仿真實(shí)驗(yàn)

下面，通過仿真實(shí)驗(yàn)來驗(yàn)證上面的結(jié)論。仿真實(shí)驗(yàn)中的主要參數(shù)和限制條件如下。狀態(tài)塊總數(shù)與節(jié)點(diǎn)總數(shù)之比為rchunk=100，節(jié)點(diǎn)失效速率l=1/（24小時(shí)），節(jié)點(diǎn)恢復(fù)速率m=1/（24小時(shí)）。在進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的選擇策略：源節(jié)點(diǎn)，必須包含該狀態(tài)塊的備份，同時(shí)其上正在進(jìn)行拷貝的狀態(tài)塊數(shù)目必須最??；目標(biāo)節(jié)點(diǎn)，從所有不含該狀態(tài)塊的備份的節(jié)點(diǎn)中隨機(jī)選取，同時(shí)其上所存儲(chǔ)的狀態(tài)塊數(shù)目不能超過平均值的tcap=1.3。為保證狀態(tài)塊拷貝不影響系統(tǒng)的正常服務(wù)，人為限制正在進(jìn)行拷貝的節(jié)點(diǎn)數(shù)目不超過機(jī)群系統(tǒng)中節(jié)點(diǎn)總數(shù)的tratio=40%。為了同樣的目的，人為限制狀態(tài)塊拷貝只占用網(wǎng)絡(luò)帶寬的一半；若有多個(gè)狀態(tài)塊在向外輸出，則它們分享帶寬。網(wǎng)絡(luò)帶寬為100Mb/s，一個(gè)狀態(tài)塊大小為64M。為了使新加入的節(jié)點(diǎn)不在短時(shí)間里收到大量的新備份，人為限制每個(gè)節(jié)點(diǎn)正在進(jìn)行拷貝的狀態(tài)塊數(shù)目不超過tcopy=1。實(shí)驗(yàn)結(jié)果，如圖2所表示。這些限制條件均來自實(shí)際系統(tǒng)。

圖2不同備份數(shù)下的系統(tǒng)MTTF        [!--empirenews.page--]

從圖上可以很明顯地看到三個(gè)特點(diǎn)。第一，在相同節(jié)點(diǎn)數(shù)目下，備份數(shù)越多，系統(tǒng)的MTTF越大，這是所預(yù)期的。第二，當(dāng)節(jié)點(diǎn)數(shù)目達(dá)到1000的時(shí)候，在2個(gè)備份的情況下，系統(tǒng)MTTF小于1小時(shí)；在3個(gè)備份的情況下，系統(tǒng)MTTF仍能保持在400小時(shí)（約為16天）左右。這些值與前面的理論分析基本一致，數(shù)值都在相同的數(shù)量級(jí)。第三，當(dāng)備份數(shù)只有1或2個(gè)的時(shí)候，隨著節(jié)點(diǎn)數(shù)的增加，系統(tǒng)MTTF顯著下降；而當(dāng)備份數(shù)是3個(gè)的時(shí)候，隨著節(jié)點(diǎn)數(shù)的增加，系統(tǒng)MTTF基本保持不變。這個(gè)現(xiàn)象可以解釋如下。首先，當(dāng)備份數(shù)只有1或2個(gè)的時(shí)候，系統(tǒng)MTTF隨著節(jié)點(diǎn)數(shù)的增加而下降的原因是：當(dāng)節(jié)點(diǎn)數(shù)增多時(shí)，系統(tǒng)中出現(xiàn)節(jié)點(diǎn)失效的可能性就增大。比如，對(duì)于一個(gè)包含1000個(gè)節(jié)點(diǎn)的機(jī)群系統(tǒng)，若每個(gè)節(jié)點(diǎn)的失效速率為l，則系統(tǒng)中出現(xiàn)節(jié)點(diǎn)失效的速率為1000l。在這樣高的失效速率下，很容易發(fā)生包含同一個(gè)狀態(tài)塊備份的兩個(gè)節(jié)點(diǎn)（當(dāng)備份數(shù)為2時(shí)）幾乎同時(shí)失效。另外，隨節(jié)點(diǎn)數(shù)的增多，狀態(tài)塊的數(shù)目也成倍增加，這也增加了系統(tǒng)中出現(xiàn)某狀態(tài)塊丟失的可能性。其次，當(dāng)備份數(shù)有3個(gè)的時(shí)候，系統(tǒng)MTTF隨著節(jié)點(diǎn)數(shù)的增加能保持穩(wěn)定的原因是：當(dāng)節(jié)點(diǎn)數(shù)增多時(shí)，雖然系統(tǒng)中出現(xiàn)某個(gè)節(jié)點(diǎn)失效的可能性增大，會(huì)降低系統(tǒng)MTTF，但另一個(gè)能起到相反的作用因素顯著表現(xiàn)出來。這個(gè)因素就是通過并發(fā)拷貝操作，大大降低對(duì)象狀態(tài)轉(zhuǎn)移時(shí)間。舉個(gè)例子。假設(shè)一個(gè)機(jī)群系統(tǒng)有1000個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)存儲(chǔ)著100個(gè)狀態(tài)塊，每個(gè)狀態(tài)塊大小為64M。當(dāng)一個(gè)節(jié)點(diǎn)失效后，系統(tǒng)就會(huì)為其上的100個(gè)狀態(tài)塊尋找一對(duì)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移。正常情況下，在100Mb/s的網(wǎng)絡(luò)里，若只使用一半帶寬的話，轉(zhuǎn)移一個(gè)狀態(tài)塊需要（64MB*8b/B*2）/(100Mb/s)，即，近似為10秒。那么，轉(zhuǎn)移100個(gè)狀態(tài)塊需要1000秒左右，即，近似為15分鐘，這是很長(zhǎng)的一段時(shí)間。但考慮到系統(tǒng)中有1000個(gè)節(jié)點(diǎn)，很容易找到這樣100對(duì)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，它們沒有任何兩個(gè)節(jié)點(diǎn)是相同的。在這種情況下，拷貝操作完全可以并發(fā)進(jìn)行，100個(gè)狀態(tài)塊可在10秒內(nèi)拷貝完畢，這是很短的一段時(shí)間。

縮短拷貝時(shí)間的最大好處是，在拷貝期間發(fā)生新節(jié)點(diǎn)失效的可能性減小，進(jìn)而這樣就可以減小某個(gè)狀態(tài)塊丟失的可能性。為了證明降低拷貝時(shí)間的作用，考慮如下對(duì)比實(shí)驗(yàn)。對(duì)于備份數(shù)為2和3的那兩組實(shí)驗(yàn)，將原先的tratio的限制舍棄不用，而限制系統(tǒng)中正在進(jìn)行拷貝的節(jié)點(diǎn)數(shù)目的上限為10個(gè)。如果實(shí)驗(yàn)的結(jié)果表明，隨節(jié)點(diǎn)數(shù)的增加，系統(tǒng)MTTF顯著降低，那么就證明了降低拷貝時(shí)間對(duì)提高系統(tǒng)MTTF的作用。圖3顯示的是得到的實(shí)驗(yàn)結(jié)果。作為對(duì)比，把沒有該限制的原實(shí)驗(yàn)結(jié)果也畫在圖上，用虛線表示。實(shí)驗(yàn)的結(jié)果正如所預(yù)料的，在兩種實(shí)驗(yàn)情況下，系統(tǒng)MTTF都隨節(jié)點(diǎn)數(shù)增加，而顯著降低。特別地，當(dāng)節(jié)點(diǎn)數(shù)為1000時(shí)，在備份數(shù)為2的情況下，系統(tǒng)MTTF遠(yuǎn)低于1小時(shí)；在備份數(shù)為3的情況下，系統(tǒng)MTTF只有2小時(shí)左右。這些性能數(shù)據(jù)，都比原先沒有該限制的實(shí)驗(yàn)，要低得多。

圖3有并發(fā)限制與無并發(fā)限制的比較

5 結(jié)論

本文提出了一個(gè)新的動(dòng)態(tài)備份策略，"并行數(shù)據(jù)備份策略"。研究表明，該策略可顯著地提高系統(tǒng)的MTTF。特別地，當(dāng)系統(tǒng)節(jié)點(diǎn)數(shù)目達(dá)到1000的時(shí)候，在3個(gè)備份的情況下，系統(tǒng)MTTF仍能保持在幾十天的數(shù)量級(jí)。并且指出該策略的有效性主要來源于通過并發(fā)拷貝操作，大大降低了對(duì)象狀態(tài)的轉(zhuǎn)移時(shí)間。

本文創(chuàng)新點(diǎn)

本文提出了一個(gè)新的動(dòng)態(tài)備份策略，"并行數(shù)據(jù)備份策略"。通過詳細(xì)的理論分析和仿真實(shí)驗(yàn)，指出該策略可以在系統(tǒng)中當(dāng)節(jié)點(diǎn)數(shù)達(dá)到成百上千時(shí)顯著地提高系統(tǒng)的MTTF。該策略若使用在海量存儲(chǔ)系統(tǒng)中，可以顯著地提高數(shù)據(jù)的可靠性。