海量存儲機(jī)群系統(tǒng)中提高系統(tǒng)MTTF的設(shè)計(jì)和分析

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

1 引言

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

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

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

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

在出現(xiàn)一個節(jié)點(diǎn)失效后，系統(tǒng)的動態(tài)備份策略為：1）為失效節(jié)點(diǎn)上的每個狀態(tài)塊，選擇一對源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，源節(jié)點(diǎn)包含該狀態(tài)塊，目標(biāo)節(jié)點(diǎn)不包含；2）讓這些狀態(tài)塊，同時在各對應(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)行。另外，這個備份策略也意味著每個狀態(tài)塊的備份可存儲于任一節(jié)點(diǎn)上。下面，通過建立數(shù)學(xué)模型，理論估計(jì)該動態(tài)備份策略下的系統(tǒng)MTTF。

3理論分析

考慮用Markov過程來描述這個模型。為此，做如下假設(shè)。節(jié)點(diǎn)的失效速率服從指數(shù)分布，均值為l。由于系統(tǒng)中節(jié)點(diǎn)數(shù)目巨大，所以在一個節(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)塊無法挽回丟失時，系統(tǒng)中正常工作的節(jié)點(diǎn)數(shù)依然維持在較高水平，與起始時的節(jié)點(diǎn)數(shù)n在同一個數(shù)量級。因此，可近似認(rèn)為系統(tǒng)中節(jié)點(diǎn)數(shù)始終為n。于是，取有幾個失效節(jié)點(diǎn)上的狀態(tài)塊正在進(jìn)行轉(zhuǎn)移為研究對象，可得狀態(tài)轉(zhuǎn)移圖如圖1。其中，m為每個狀態(tài)塊的原備份數(shù)；ai表示當(dāng)一個有n個節(jié)點(diǎn)的系統(tǒng)中有（i-1）個失效節(jié)點(diǎn)上的狀態(tài)塊正在進(jìn)行轉(zhuǎn)移時無狀態(tài)塊丟失，而再失效一個節(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'的均值時間。這個系統(tǒng)可以近似看成一個狀態(tài)數(shù)為無窮的一維生滅過程。要求解進(jìn)入狀態(tài)i'的瞬態(tài)概率，將涉及解一個含無窮多等式的微分方程組，這是很復(fù)雜的。但根據(jù)以往求一維生滅過程的穩(wěn)態(tài)解的經(jīng)驗(yàn)知道，  。因此，如果ln-1/mn很小，那隨著n的增加，Pn將急速下降。于是，當(dāng)n增加到一定值時，可以忽略其后的狀態(tài)。對一個典型的含1000個節(jié)點(diǎn)的機(jī)群系統(tǒng)，若節(jié)點(diǎn)的MTTF為一天，則系統(tǒng)中出現(xiàn)某節(jié)點(diǎn)失效的速率約為0.011/秒；而一個狀態(tài)塊的平均轉(zhuǎn)移時間可以在10秒鐘左右，即，轉(zhuǎn)移速率為0.1/秒；這兩個速率之比約為0.1。因此，可以忽略系統(tǒng)中n>=m的狀態(tài)，而把系統(tǒng)進(jìn)入狀態(tài)m'的均值時間作為系統(tǒng)的MTTF。

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

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

   。 。

而E3(T)可表示為：

。。

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

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

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

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

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

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小時），節(jié)點(diǎn)恢復(fù)速率m=1/（24小時）。在進(jìn)行狀態(tài)轉(zhuǎn)移時，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的選擇策略：源節(jié)點(diǎn)，必須包含該狀態(tài)塊的備份，同時其上正在進(jìn)行拷貝的狀態(tài)塊數(shù)目必須最小；目標(biāo)節(jié)點(diǎn)，從所有不含該狀態(tài)塊的備份的節(jié)點(diǎn)中隨機(jī)選取，同時其上所存儲的狀態(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ò)帶寬的一半；若有多個狀態(tài)塊在向外輸出，則它們分享帶寬。網(wǎng)絡(luò)帶寬為100Mb/s，一個狀態(tài)塊大小為64M。為了使新加入的節(jié)點(diǎn)不在短時間里收到大量的新備份，人為限制每個節(jié)點(diǎn)正在進(jìn)行拷貝的狀態(tài)塊數(shù)目不超過tcopy=1。實(shí)驗(yàn)結(jié)果，如圖2所表示。這些限制條件均來自實(shí)際系統(tǒng)。

圖2不同備份數(shù)下的系統(tǒng)MTTF       

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

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

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

5 結(jié)論

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

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

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