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

1 引言

在過(guò)去幾年里，機(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à)格可以很低。第二，通過(guò)增減節(jié)點(diǎn)，系統(tǒng)可以簡(jiǎn)單地進(jìn)行擴(kuò)展。第三，通過(guò)在互相獨(dú)立的節(jié)點(diǎn)上備份數(shù)據(jù)，可以顯著地提高系統(tǒng)中數(shù)據(jù)的可靠性。

對(duì)存儲(chǔ)系統(tǒng)來(lái)說(shuō)，系統(tǒng)的平均故障前時(shí)間（MTTF）是指系統(tǒng)中出現(xiàn)某個(gè)數(shù)據(jù)因所有的備份都丟失，而導(dǎo)致該數(shù)據(jù)無(wú)法挽回地丟失所需的平均時(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擇過(guò)低的備份數(shù)，系統(tǒng)的MTTF不能滿(mǎn)足要求；而選擇過(guò)高的備份數(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)之間開(kāi)始轉(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)上。下面，通過(guò)建立數(shù)學(xué)模型，理論估計(jì)該動(dòng)態(tài)備份策略下的系統(tǒng)MTTF。

3理論分析

考慮用Markov過(guò)程來(lái)描述這個(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)塊無(wú)法挽回丟失時(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í)無(wú)狀態(tài)塊丟失，而再失效一個(gè)節(jié)點(diǎn)發(fā)生一狀態(tài)塊丟失的概率；狀態(tài)i'（i>=m）表示系統(tǒng)中出現(xiàn)某狀態(tài)塊無(wú)法挽回地丟失。

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

因此，目標(biāo)就化為系統(tǒng)進(jìn)入狀態(tài)i'的均值時(shí)間。這個(gè)系統(tǒng)可以近似看成一個(gè)狀態(tài)數(shù)為無(wú)窮的一維生滅過(guò)程。要求解進(jìn)入狀態(tài)i'的瞬態(tài)概率，將涉及解一個(gè)含無(wú)窮多等式的微分方程組，這是很復(fù)雜的。但根據(jù)以往求一維生滅過(guò)程的穩(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。