李 靜，羅金飛，李炳超

（1.中國民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300；2.南開大學(xué)計(jì)算機(jī)學(xué)院，天津 300350）

0 引言

雖然單個(gè)硬盤發(fā)生故障的概率比較小，但是隨著存儲(chǔ)系統(tǒng)規(guī)模的不斷增大，硬盤故障甚至是并發(fā)故障的發(fā)生頻率越來越高［1］。據(jù)統(tǒng)計(jì)，硬盤故障是數(shù)據(jù)中心最主要的故障源，在一個(gè)Petabyte 級(jí)別的文件系統(tǒng)中每天都會(huì)有硬盤故障的發(fā)生［2］。另外，作為硬盤的載體——服務(wù)器，也會(huì)因?yàn)橐恍┙M件，如網(wǎng)卡、內(nèi)存、CPU、主板和電源等的故障而崩潰，從而導(dǎo)致所有掛載在它上面的硬盤不可訪問［3］。硬盤故障會(huì)導(dǎo)致存儲(chǔ)系統(tǒng)服務(wù)性能的降級(jí)，甚至?xí)?dǎo)致用戶數(shù)據(jù)的丟失和服務(wù)的中斷，給企業(yè)和用戶帶來無法避免和估計(jì)的損失。

傳統(tǒng)的存儲(chǔ)系統(tǒng)普遍采用副本或糾刪碼機(jī)制保障數(shù)據(jù)的安全，硬盤故障發(fā)生之后，系統(tǒng)可利用其他可用硬盤上的冗余數(shù)據(jù)恢復(fù)故障數(shù)據(jù)，從而避免數(shù)據(jù)的丟失，這是一種典型的“被動(dòng)容錯(cuò)”機(jī)制。隨著硬件故障發(fā)生頻率的不斷增加，被動(dòng)容錯(cuò)機(jī)制只能通過不斷增加冗余來保證系統(tǒng)的高可靠性，這無疑增加了構(gòu)建和維護(hù)系統(tǒng)的成本。硬盤故障預(yù)測［4-9］通過對(duì)系統(tǒng)中硬盤健康狀態(tài)的實(shí)時(shí)監(jiān)測，在硬盤故障發(fā)生之前發(fā)出警報(bào)，提醒用戶遷移危險(xiǎn)數(shù)據(jù)，從而避免或減少硬盤故障帶來的損失，這是一種“主動(dòng)容錯(cuò)”的思想。目前已有很多存儲(chǔ)系統(tǒng)［5-6，10-11］采用了這種基于硬盤故障預(yù)測的主動(dòng)容錯(cuò)方式。

對(duì)主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性評(píng)價(jià)，可以用來評(píng)估不同預(yù)測模型、數(shù)據(jù)散布策略以及不同系統(tǒng)參數(shù)對(duì)系統(tǒng)可靠性的影響，有助于構(gòu)造出高可靠和可用性的存儲(chǔ)系統(tǒng)。然而，硬盤故障預(yù)測技術(shù)的引入令存儲(chǔ)系統(tǒng)產(chǎn)生了根本性變化——系統(tǒng)運(yùn)行由“正?！收闲迯?fù)”兩種狀態(tài)之間的轉(zhuǎn)換，變?yōu)椤罢！A(yù)警處理—故障修復(fù)”三個(gè)狀態(tài)之間的轉(zhuǎn)換，對(duì)主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性分析變得非常復(fù)雜，目前僅有少量研究關(guān)注此領(lǐng)域。

現(xiàn)有研究存在一些缺陷，不能準(zhǔn)確、細(xì)致地評(píng)價(jià)主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性水平：①忽略了節(jié)點(diǎn)故障對(duì)系統(tǒng)可靠性的影響。隨著系統(tǒng)規(guī)模的增大，節(jié)點(diǎn)故障的發(fā)生頻率越來越高，節(jié)點(diǎn)故障會(huì)導(dǎo)致所有掛載硬盤的失效，對(duì)系統(tǒng)可靠性的影響不容忽視。②沒有考慮數(shù)據(jù)散布方式對(duì)可靠性的影響。數(shù)據(jù)散布方式影響到系統(tǒng)在并發(fā)故障下的容錯(cuò)能力，對(duì)系統(tǒng)可靠性有重要影響。本文擬克服上述缺陷，研究主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性。

由于硬盤價(jià)格持續(xù)降低，以及良好的并行處理能力，副本冗余技術(shù)成為存儲(chǔ)系統(tǒng)普遍采用的容錯(cuò)機(jī)制［12-13］。在基于副本冗余機(jī)制的存儲(chǔ)系統(tǒng)中，一個(gè)節(jié)點(diǎn)只保存有一個(gè)副本，如果有硬盤發(fā)生故障，需要跨節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的重構(gòu)，會(huì)大量消耗網(wǎng)絡(luò)的帶寬，甚至在業(yè)務(wù)高峰時(shí)引起連鎖反應(yīng)，造成性能的抖動(dòng)。

本文作者在前期工作［14］中，針對(duì)采用RAID-5（Redundant Array of Inexpensive Disk）和RAID-6 機(jī)制的主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)，提出了兩個(gè)可靠性狀態(tài)轉(zhuǎn)換模型。本文擴(kuò)展此項(xiàng)工作到采用副本冗余機(jī)制的主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)，與前期工作［14］相比，本文主要新增了兩個(gè)創(chuàng)新點(diǎn)：①增加考慮節(jié)點(diǎn)故障和修復(fù)對(duì)系統(tǒng)可靠性的影響；②分析副本冗余機(jī)制下的系統(tǒng)可靠性水平。

具體來說，本文針對(duì)采用被動(dòng)/主動(dòng)容錯(cuò)二副本和三副本容錯(cuò)機(jī)制的存儲(chǔ)系統(tǒng)，提出四個(gè)可靠性狀態(tài)轉(zhuǎn)換模型，并據(jù)此設(shè)計(jì)了蒙特卡洛仿真算法模擬系統(tǒng)的運(yùn)行，統(tǒng)計(jì)存儲(chǔ)系統(tǒng)在一定運(yùn)行周期內(nèi)發(fā)生數(shù)據(jù)丟失的期望次數(shù)，從而量化評(píng)價(jià)主動(dòng)容錯(cuò)副本存儲(chǔ)系統(tǒng)的可靠性水平。本文采用韋布分布函數(shù)模擬硬盤故障和修復(fù)事件的時(shí)間分布，綜合評(píng)價(jià)了主動(dòng)容錯(cuò)機(jī)制、節(jié)點(diǎn)故障、節(jié)點(diǎn)故障修復(fù)、硬盤故障以及硬盤故障修復(fù)等因素對(duì)存儲(chǔ)系統(tǒng)可靠性的影響。利用本文提出的可靠性分析模型，系統(tǒng)管理者可以方便地比較不同冗余機(jī)制下的系統(tǒng)可靠性差異，定量評(píng)價(jià)硬盤故障預(yù)測模型對(duì)系統(tǒng)可靠性的提升效果，權(quán)衡比較不同系統(tǒng)參數(shù)對(duì)系統(tǒng)可靠性的影響，從而幫助系統(tǒng)管理者搭建出滿足特定可靠性需求的存儲(chǔ)系統(tǒng)。

1 背景知識(shí)

1.1 相關(guān)研究

可靠性一直是存儲(chǔ)系統(tǒng)相關(guān)研究領(lǐng)域重點(diǎn)關(guān)注的問題之一，該領(lǐng)域的研究者［2，15］通常基于硬盤故障服從指數(shù)分布的假設(shè)，使用Markov 模型構(gòu)建系統(tǒng)可靠性分析模型，研究大規(guī)模存儲(chǔ)系統(tǒng)的可靠性水平。然而，研究者通過大量實(shí)驗(yàn)證明［16-18］，相對(duì)于指數(shù)分布，Weibull分布函數(shù)能夠更好地模擬硬盤故障事件。Weibull函數(shù)可以模擬隨運(yùn)行時(shí)間而不斷升高、保持不變、或者降低的設(shè)備故障發(fā)生率，本文使用Weibull 分布函數(shù)模擬節(jié)點(diǎn)和硬盤故障事件。

對(duì)于副本存儲(chǔ)系統(tǒng)，有一些國內(nèi)外研究關(guān)注它們的可靠性。文獻(xiàn)［19］使用概率分析方法估計(jì)系統(tǒng)的可靠性，然而因?yàn)楹雎粤斯收现貥?gòu)時(shí)間而沒有真實(shí)反映系統(tǒng)的可靠性水平；Epstein 等［20］使用仿真和統(tǒng)計(jì)分析相結(jié)合的方法評(píng)估了分布式云存儲(chǔ)系統(tǒng)的可靠性，并關(guān)注網(wǎng)絡(luò)帶寬和并發(fā)故障對(duì)系統(tǒng)可靠性的影響；Wang 等［21］提出一個(gè)可靠性分析模型，通過合并副本丟失的概率來研究基于分塊散布的多副本系統(tǒng)的可靠性水平。

近年來，有學(xué)者使用基于蒙特卡洛的仿真方法模擬存儲(chǔ)系統(tǒng)的運(yùn)行，進(jìn)而分析存儲(chǔ)系統(tǒng)的可靠性：Hall等［22］使用基于事件驅(qū)動(dòng)的仿真方法預(yù)測大型存儲(chǔ)系統(tǒng)設(shè)計(jì)和部署的可靠性；Zhang等［3］使用仿真方法分析了采用糾刪碼冗余機(jī)制的數(shù)據(jù)中心的可靠性水平，并比較了水平和垂直兩種數(shù)據(jù)散布方式對(duì)系統(tǒng)可靠性的影響。然而，前述工作都只是針對(duì)被動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)展開的可靠性研究。

對(duì)于主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)，目前只有少量研究關(guān)注它們的可靠性水平。Eckart等［23］設(shè)計(jì)了Markov可靠性模型分析主動(dòng)容錯(cuò)技術(shù)對(duì)單個(gè)硬盤、RAID-1 系統(tǒng)和RAID-5 系統(tǒng)平均數(shù)據(jù)丟失時(shí)間（Mean Time Between Data Loss，MTTDL）的影響；Li等［9，24］拓展了Eckart 等［23］的工作，為主動(dòng)容錯(cuò)RAID-6、二副本和三副本系統(tǒng)設(shè)計(jì)了Markov 可靠性分析模型。然而，這些工作都基于硬盤故障符合指數(shù)分布的假設(shè)，并沒有真實(shí)刻畫主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性水平。

李靜等［14，25］的后續(xù)工作中，采用更符合實(shí)際情況的韋布分布函數(shù)模擬硬盤故障事件，使用蒙特卡洛仿真方法和組合數(shù)學(xué)分析方法為主動(dòng)容錯(cuò)RAID-5、RAID-6、二副本和三副本系統(tǒng)設(shè)計(jì)了可靠性分析模型。然而，當(dāng)前現(xiàn)有的評(píng)價(jià)模型都沒有考慮節(jié)點(diǎn)故障對(duì)系統(tǒng)可靠性的影響，節(jié)點(diǎn)上的任何組件或軟件的故障都會(huì)導(dǎo)致節(jié)點(diǎn)故障，節(jié)點(diǎn)故障會(huì)引起所有掛載硬盤的集體失效，其發(fā)生頻率及對(duì)系統(tǒng)可靠性的影響不容忽視。本文擬面向被動(dòng)/主動(dòng)容錯(cuò)二副本和三副本存儲(chǔ)系統(tǒng)，綜合評(píng)價(jià)節(jié)點(diǎn)故障、硬盤故障對(duì)系統(tǒng)可靠性的影響。

1.2 系統(tǒng)框架

當(dāng)前存儲(chǔ)系統(tǒng)普遍采用分層的系統(tǒng)框架，如圖1 所示，機(jī)房中放置了多個(gè)機(jī)架，每個(gè)機(jī)架上放置了多個(gè)節(jié)點(diǎn)（存儲(chǔ)服務(wù)器），每個(gè)節(jié)點(diǎn)上配備了多塊硬盤以存儲(chǔ)業(yè)務(wù)數(shù)據(jù)。同一機(jī)架內(nèi)部的節(jié)點(diǎn)通過機(jī)架頂部的交換機(jī)進(jìn)行通信，不同機(jī)架的節(jié)點(diǎn)之間通過網(wǎng)絡(luò)核心交換機(jī)進(jìn)行通信。

圖1 存儲(chǔ)系統(tǒng)架構(gòu)Fig.1 Storage system architecture

在采用副本冗余機(jī)制的存儲(chǔ)系統(tǒng)中，用戶數(shù)據(jù)首先被分成很多數(shù)據(jù)塊（data chunks），然后每個(gè)數(shù)據(jù)塊都被復(fù)制一定數(shù)量的副本（二副本系統(tǒng)中有兩塊副本，三副本系統(tǒng)中有三塊副本），最后這些副本在系統(tǒng)的不同節(jié)點(diǎn)之間散布（而不是存放在同一個(gè)節(jié)點(diǎn)上），從而提高數(shù)據(jù)在節(jié)點(diǎn)故障時(shí)的存活概率。通常情況下，一個(gè)數(shù)據(jù)塊的副本首先被管理節(jié)點(diǎn)分配到某些存儲(chǔ)節(jié)點(diǎn)（存儲(chǔ)服務(wù)器）上，然后存儲(chǔ)節(jié)點(diǎn)再選擇一塊內(nèi)部硬盤存放其中一個(gè)副本。為了保障數(shù)據(jù)安全和系統(tǒng)可靠性，存儲(chǔ)系統(tǒng)一般會(huì)遵循兩個(gè)數(shù)據(jù)散布的原則：①一個(gè)節(jié)點(diǎn)至多只存放某個(gè)數(shù)據(jù)塊的一個(gè)副本；②一個(gè)數(shù)據(jù)塊的所有副本至少要被散布到兩個(gè)不同的機(jī)架上。

二副本系統(tǒng)：每個(gè)用戶數(shù)據(jù)都被復(fù)制兩次，這兩個(gè)數(shù)據(jù)副本必須存放在兩個(gè)不同的機(jī)架上。如果由節(jié)點(diǎn)故障或硬盤故障導(dǎo)致的數(shù)據(jù)損壞位于同一個(gè)機(jī)架上，這些故障不會(huì)導(dǎo)致系統(tǒng)發(fā)生數(shù)據(jù)丟失事件。

三副本系統(tǒng)：每個(gè)用戶數(shù)據(jù)都被復(fù)制了三份，這三個(gè)數(shù)據(jù)副本被散布到三個(gè)不同節(jié)點(diǎn)上，其中有兩個(gè)節(jié)點(diǎn)位于同一個(gè)機(jī)架上，另外一個(gè)節(jié)點(diǎn)位于其他機(jī)架上。這種數(shù)據(jù)散布方式有兩個(gè)優(yōu)點(diǎn)：①如果某個(gè)機(jī)架由于電源等設(shè)備的故障而失效，系統(tǒng)可以使用其他機(jī)架上的存活副本修復(fù)發(fā)生的故障，能夠提高數(shù)據(jù)的存活概率；②如果某個(gè)存儲(chǔ)節(jié)點(diǎn)發(fā)生了節(jié)點(diǎn)或硬盤故障，系統(tǒng)可以使用相同機(jī)架上的存活副本修復(fù)故障，這個(gè)操作使用的是機(jī)架內(nèi)部的網(wǎng)絡(luò)帶寬，不會(huì)對(duì)珍貴的機(jī)架之間的核心網(wǎng)絡(luò)通信產(chǎn)生影響。

1.3 故障模式

存儲(chǔ)系統(tǒng)主要存在三種類型的設(shè)備故障：①節(jié)點(diǎn)故障。由于服務(wù)器的網(wǎng)卡、內(nèi)存、CPU、主板和電源等組件的故障（或軟件故障）而導(dǎo)致的節(jié)點(diǎn)崩潰，使得該節(jié)點(diǎn)掛載的所有硬盤都無法訪問。②硬盤個(gè)體故障。由于磁頭損壞、芯片信息丟失、電路板問題等原因?qū)е碌挠脖P上所有數(shù)據(jù)都無法訪問。③硬盤潛在扇區(qū)錯(cuò)誤。一般是由介質(zhì)故障或磁頭劃傷等原因造成的硬盤部分二進(jìn)制位無法讀出。存儲(chǔ)系統(tǒng)后臺(tái)通常運(yùn)行著“硬盤清洗”進(jìn)程，周期性地檢測并修復(fù)硬盤潛在扇區(qū)錯(cuò)誤，文獻(xiàn)［25］中的圖10 顯示硬盤潛在扇區(qū)錯(cuò)誤對(duì)副本系統(tǒng)的可靠性影響不大，因此本文只關(guān)注前兩種類型的設(shè)備故障，即節(jié)點(diǎn)故障和硬盤個(gè)體故障。

設(shè)備故障根據(jù)其持續(xù)時(shí)間和危害程度可分為臨時(shí)故障和永久性故障兩類：①臨時(shí)故障。由網(wǎng)絡(luò)斷開、重啟或維護(hù)等原因造成的設(shè)備（節(jié)點(diǎn)或硬盤）暫時(shí)不可訪問，這種故障只需經(jīng)過多次嘗試，就可以恢復(fù)正常，不會(huì)造成系統(tǒng)的數(shù)據(jù)丟失，只對(duì)系統(tǒng)的可用性產(chǎn)生一定影響。②永久性故障。由于軟件故障、組件故障、磁道損壞等原因造成的設(shè)備永遠(yuǎn)不能被訪問，這種故障只能通過更換設(shè)備進(jìn)行恢復(fù)，不僅會(huì)降低系統(tǒng)的可用性，還可能會(huì)導(dǎo)致系統(tǒng)發(fā)生數(shù)據(jù)丟失，降低系統(tǒng)的可靠性。因?yàn)橹挥杏谰眯怨收蠒?huì)對(duì)系統(tǒng)的可靠性產(chǎn)生影響，所以本文只關(guān)注設(shè)備的永久性故障。

當(dāng)節(jié)點(diǎn)或硬盤故障發(fā)生之后，某些數(shù)據(jù)的部分（而非全部）副本會(huì)因此而丟失，為了維持系統(tǒng)數(shù)據(jù)冗余度的一致性，系統(tǒng)會(huì)啟動(dòng)一個(gè)重構(gòu)過程，利用其他存活副本修復(fù)（重構(gòu)）出丟失的副本。為了維持系統(tǒng)規(guī)模和全局的數(shù)據(jù)均衡，新設(shè)備替換故障設(shè)備加入系統(tǒng)并被散布上數(shù)據(jù)。在故障修復(fù)期間，如果又有其他設(shè)備（節(jié)點(diǎn)或硬盤）發(fā)生故障，一些數(shù)據(jù)塊可能會(huì)丟失更多的副本，直至不可恢復(fù)的數(shù)據(jù)丟失事件發(fā)生。如果數(shù)據(jù)塊的所有副本全部丟失，重構(gòu)過程已經(jīng)不能再重構(gòu)出這些由并發(fā)設(shè)備故障導(dǎo)致的損壞數(shù)據(jù)，本文研究認(rèn)為系統(tǒng)發(fā)生了數(shù)據(jù)丟失事件。

1.4 主動(dòng)容錯(cuò)技術(shù)

現(xiàn)代硬盤內(nèi)部基本上都實(shí)現(xiàn)了SMART（Self-Monitoring，Analysis and Reporting Technology），具有“自我監(jiān)測、分析和報(bào)告”功能，如果某些屬性的當(dāng)前值超過預(yù)先設(shè)定的閾值，硬盤會(huì)自動(dòng)發(fā)出警告信息，提醒用戶對(duì)硬盤采取措施，避免硬盤故障導(dǎo)致的數(shù)據(jù)丟失損失。但是，這種簡單閾值法的預(yù)報(bào)精度不高，不能滿足用戶對(duì)系統(tǒng)可靠性的需求。于是，國內(nèi)外研究者開始嘗試使用機(jī)器學(xué)習(xí)方法創(chuàng)建硬盤故障預(yù)測模型［4-9］，有一些方法，比如Li 等［4］的工作創(chuàng)建的基于決策樹的硬盤故障預(yù)測模型，取得了令人滿意的預(yù)測性能。

在主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)中，系統(tǒng)后臺(tái)運(yùn)行著一個(gè)硬盤故障預(yù)測模型，對(duì)工作中的硬盤進(jìn)行實(shí)時(shí)監(jiān)測，并周期性地輸出硬盤個(gè)體的“健康”情況，系統(tǒng)會(huì)對(duì)“健康”狀態(tài)差（即將發(fā)生故障）的硬盤啟動(dòng)預(yù)警修復(fù)過程，把危險(xiǎn)數(shù)據(jù)提前遷移到健康硬盤上。目前還沒有相關(guān)文獻(xiàn)研究節(jié)點(diǎn)故障預(yù)測，所以本文只關(guān)注基于硬盤故障預(yù)測的主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性。

2 系統(tǒng)狀態(tài)轉(zhuǎn)移模型

本章為被動(dòng)/主動(dòng)容錯(cuò)二副本和三副本系統(tǒng)提出了狀態(tài)轉(zhuǎn)移模型，分析系統(tǒng)在主動(dòng)容錯(cuò)機(jī)制、節(jié)點(diǎn)和硬盤故障以及故障修復(fù)等事件下的狀態(tài)轉(zhuǎn)換過程，為系統(tǒng)可靠性評(píng)價(jià)模型的設(shè)計(jì)提供依據(jù)。如果某個(gè)數(shù)據(jù)塊的所有副本都因?yàn)樵O(shè)備故障而發(fā)生了損壞（丟失），系統(tǒng)的修復(fù)過程已無法再重構(gòu)出該數(shù)據(jù)塊，本文研究認(rèn)為此時(shí)系統(tǒng)發(fā)生了數(shù)據(jù)丟失事件。

假設(shè)系統(tǒng)中包含r個(gè)機(jī)架，每個(gè)機(jī)架上放置了n個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)上配置了d塊硬盤，系統(tǒng)中共包含rn個(gè)節(jié)點(diǎn)和rnd塊硬盤。

2.1 被動(dòng)容錯(cuò)二副本系統(tǒng)

對(duì)于二副本存儲(chǔ)系統(tǒng)，根據(jù)副本系統(tǒng)數(shù)據(jù)的散布原則，用戶數(shù)據(jù)塊的兩個(gè)副本散布在位于不同機(jī)架的兩個(gè)硬盤上，稱這種位于不同機(jī)架上的兩個(gè)硬盤為一個(gè)“復(fù)制對(duì)”。對(duì)于系統(tǒng)中的一個(gè)硬盤D，其他機(jī)架上的任意一個(gè)硬盤都可以和D構(gòu)成一個(gè)“復(fù)制對(duì)”，共有(r-1)nd個(gè)包含D的“復(fù)制對(duì)”。假設(shè)系統(tǒng)中每個(gè)硬盤的容量為4 TB，每個(gè)數(shù)據(jù)塊的大小為1 MB，那么在完全均勻和隨機(jī)的散布下，只要(r-1)nd＜(4 TB/1 MB)，即系統(tǒng)包含的硬盤數(shù)量不超過4×106時(shí)，位于不同機(jī)架的任意兩個(gè)硬盤上都至少存儲(chǔ)了一個(gè)數(shù)據(jù)塊的兩個(gè)副本。因此，如果系統(tǒng)中的兩個(gè)機(jī)架同時(shí)出現(xiàn)了設(shè)備（節(jié)點(diǎn)或硬盤）故障，這些并發(fā)故障就會(huì)導(dǎo)致系統(tǒng)發(fā)生數(shù)據(jù)丟失事件。

圖2 的狀態(tài)轉(zhuǎn)換模型描述了被動(dòng)容錯(cuò)二副本系統(tǒng)在設(shè)備故障和故障修復(fù)等事件影響下的狀態(tài)轉(zhuǎn)換邏輯，系統(tǒng)共有三種主要狀態(tài)：狀態(tài)1 表示系統(tǒng)處于完全健康的狀態(tài)，所有設(shè)備都在正常運(yùn)行，沒有任何設(shè)備出現(xiàn)故障；狀態(tài)2 表示系統(tǒng)處于降級(jí)模式，某一個(gè)機(jī)架由于硬盤或節(jié)點(diǎn)故障出現(xiàn)了數(shù)據(jù)損壞，其他機(jī)架上并沒有出現(xiàn)設(shè)備故障，系統(tǒng)不會(huì)發(fā)生數(shù)據(jù)丟失，只是可用性受到一定影響；狀態(tài)3 表示系統(tǒng)進(jìn)入數(shù)據(jù)丟失模式，此時(shí)系統(tǒng)發(fā)生了永久性數(shù)據(jù)丟失事件，無法再為用戶繼續(xù)提供服務(wù)。

圖2 被動(dòng)容錯(cuò)二副本系統(tǒng)狀態(tài)轉(zhuǎn)換模型Fig.2 State transition model for 2-way replication system with passive fault tolerance

系統(tǒng)開始運(yùn)行時(shí)處于狀態(tài)1，如果某個(gè)機(jī)架上發(fā)生了設(shè)備（硬件或節(jié)點(diǎn)）故障事件，系統(tǒng)進(jìn)入狀態(tài)2（降級(jí)模式），由于所有數(shù)據(jù)塊的副本都存放在兩個(gè)不同機(jī)架上，所以此時(shí)系統(tǒng)不會(huì)發(fā)生數(shù)據(jù)丟失事件。

系統(tǒng)進(jìn)入狀態(tài)2 之后，會(huì)立刻啟動(dòng)故障重構(gòu)過程，利用其他設(shè)備上的存活副本重新構(gòu)造故障導(dǎo)致的損壞數(shù)據(jù)，此時(shí)系統(tǒng)有兩種狀態(tài)轉(zhuǎn)移可能：①如果所有故障都被及時(shí)修復(fù)完成，全部數(shù)據(jù)塊均恢復(fù)至擁有兩個(gè)副本的正常狀態(tài)，系統(tǒng)轉(zhuǎn)入狀態(tài)1；②在現(xiàn)有的故障設(shè)備修復(fù)完成之前，其他機(jī)架上又發(fā)生了硬盤或節(jié)點(diǎn)故障，導(dǎo)致系統(tǒng)中至少一個(gè)數(shù)據(jù)塊的全部副本都發(fā)生了損壞，數(shù)據(jù)丟失事件發(fā)生，系統(tǒng)進(jìn)入狀態(tài)3。

系統(tǒng)進(jìn)入狀態(tài)3 之后，無法再繼續(xù)為用戶提供正常服務(wù)，不能再向其他狀態(tài)轉(zhuǎn)換。

2.2 被動(dòng)容錯(cuò)三副本系統(tǒng)

對(duì)于三副本存儲(chǔ)系統(tǒng)，每個(gè)數(shù)據(jù)塊都擁有三個(gè)副本，分別存放在三個(gè)不同的硬盤上，其中兩個(gè)硬盤位于某個(gè)機(jī)架的兩個(gè)不同節(jié)點(diǎn)上，第三個(gè)硬盤位于另外一個(gè)機(jī)架上，本文稱這樣的組合為一個(gè)“副本集合”。對(duì)于系統(tǒng)中的任意硬盤D，有兩種構(gòu)成“副本集合”的方式：從D所在機(jī)架的其他節(jié)點(diǎn)上選取一個(gè)硬盤，再從其他機(jī)架選取另一個(gè)硬盤，可以組成(n-1)d×(r-1)nd個(gè)“副本集合”；從其他機(jī)架的不同節(jié)點(diǎn)上選取兩個(gè)硬盤，可以組成個(gè)“副本集合”。合并兩種方式，對(duì)于系統(tǒng)中的任意一個(gè)硬盤，總共包含在1)n(n-1)d2個(gè)“副本集合”中。假設(shè)硬盤容量為4 TB，數(shù)據(jù)塊大小為1 MB，那么對(duì)于(r=900，n=10，d=4)的三副本系統(tǒng)（硬盤數(shù)量為36 000），任意一個(gè)“副本集合”的硬盤上都至少保存有一個(gè)數(shù)據(jù)塊的所有副本（單個(gè)硬盤上的數(shù)據(jù)塊數(shù)量多于它所在的“副本集合”個(gè)數(shù)）。

因此，對(duì)于系統(tǒng)規(guī)模不超過36 000 塊硬盤的三副本系統(tǒng)發(fā)生數(shù)據(jù)丟失事件的條件是：至少兩個(gè)機(jī)架發(fā)生了設(shè)備（硬盤或節(jié)點(diǎn)）故障，其中一個(gè)機(jī)架至少有兩個(gè)節(jié)點(diǎn)發(fā)生數(shù)據(jù)損壞，這些故障設(shè)備構(gòu)成了一個(gè)（或多個(gè)）“副本集合”，導(dǎo)致某個(gè)（或某些）數(shù)據(jù)塊的全部副本都被損壞。如果硬盤上的數(shù)據(jù)塊數(shù)量（用c表示每個(gè)硬盤上的數(shù)據(jù)塊數(shù)量）少于它所在的“副本集合”個(gè)數(shù)（用rep表示包含給定硬盤的“副本集合”數(shù)量），當(dāng)一個(gè)“副本集合”的三個(gè)硬盤同時(shí)發(fā)生故障時(shí)，系統(tǒng)以的概率發(fā)生數(shù)據(jù)丟失。

圖3 狀態(tài)轉(zhuǎn)換模型描述了被動(dòng)容錯(cuò)三副本存儲(chǔ)系統(tǒng)在設(shè)備（硬盤或節(jié)點(diǎn)）故障和故障修復(fù)等事件下的狀態(tài)轉(zhuǎn)換邏輯，其中，模型共包含五種主要狀態(tài)：狀態(tài)1 是完全健康狀態(tài)，系統(tǒng)中的所有設(shè)備都在正常運(yùn)行；狀態(tài)2 是降級(jí)模式，系統(tǒng)中的某一個(gè)機(jī)架上出現(xiàn)了設(shè)備故障；狀態(tài)3 也是降級(jí)模式，至少兩個(gè)機(jī)架上都有一個(gè)節(jié)點(diǎn)出現(xiàn)了數(shù)據(jù)損壞，系統(tǒng)處于故障邊緣；狀態(tài)4 也為降級(jí)模式，某一個(gè)機(jī)架上的至少兩個(gè)節(jié)點(diǎn)上都有數(shù)據(jù)損壞，系統(tǒng)處于故障邊緣；狀態(tài)5 是數(shù)據(jù)丟失狀態(tài)，此時(shí)已有數(shù)據(jù)塊發(fā)生了永久性丟失，系統(tǒng)不能再提供正常服務(wù)。

系統(tǒng)開始運(yùn)行時(shí)處于狀態(tài)1，系統(tǒng)中所有數(shù)據(jù)都處于具有三個(gè)副本的正常狀態(tài)，如果某個(gè)硬盤或節(jié)點(diǎn)發(fā)生故障，系統(tǒng)轉(zhuǎn)入狀態(tài)2。

系統(tǒng)進(jìn)入狀態(tài)2 之后，會(huì)馬上啟動(dòng)故障修復(fù)進(jìn)程重構(gòu)損壞的數(shù)據(jù)，此時(shí)有三種狀態(tài)轉(zhuǎn)移可能：①如果故障可以被及時(shí)修復(fù)完成，系統(tǒng)返回到狀態(tài)1；②在第一個(gè)故障修復(fù)完成之前，其他機(jī)架上又有硬盤或節(jié)點(diǎn)故障發(fā)生，系統(tǒng)轉(zhuǎn)入狀態(tài)3；③在第一個(gè)故障修復(fù)完成之前，損壞機(jī)架上的其他節(jié)點(diǎn)又發(fā)生了設(shè)備（節(jié)點(diǎn)或硬盤）故障，系統(tǒng)轉(zhuǎn)入狀態(tài)4。

系統(tǒng)處于狀態(tài)3 時(shí)，由于每個(gè)機(jī)架上最多只有一個(gè)節(jié)點(diǎn)發(fā)生損壞，這些故障設(shè)備沒有構(gòu)成“副本集合”，不會(huì)導(dǎo)致數(shù)據(jù)丟失，系統(tǒng)會(huì)針對(duì)新發(fā)生的故障再啟動(dòng)一個(gè)修復(fù)進(jìn)程，有兩種狀態(tài)轉(zhuǎn)移可能：①如果某個(gè)（或其他）機(jī)架上的故障全部修復(fù)完成，只剩一個(gè)機(jī)架上有損壞數(shù)據(jù)，系統(tǒng)返回狀態(tài)2；②如果在兩個(gè)機(jī)架上的故障修復(fù)完成之前，損壞機(jī)架上又有其他節(jié)點(diǎn)（或其他節(jié)點(diǎn)上的硬盤）發(fā)生了故障，這些故障設(shè)備構(gòu)成了一個(gè)或多個(gè)“副本集合”，系統(tǒng)發(fā)生數(shù)據(jù)丟失事件，進(jìn)入狀態(tài)5。

系統(tǒng)處于狀態(tài)4 時(shí)，系統(tǒng)中只有一個(gè)機(jī)架發(fā)生損壞，故障設(shè)備沒有構(gòu)成“副本集合”，不會(huì)導(dǎo)致數(shù)據(jù)丟失，系統(tǒng)會(huì)立即再啟動(dòng)一個(gè)修復(fù)過程重構(gòu)損壞數(shù)據(jù)，會(huì)有兩種狀態(tài)轉(zhuǎn)移可能：①如果某個(gè)（或某些）故障修復(fù)完成，機(jī)架上只剩一個(gè)節(jié)點(diǎn)有數(shù)據(jù)損壞，系統(tǒng)返回狀態(tài)2；②如果在兩個(gè)不同節(jié)點(diǎn)（或不同節(jié)點(diǎn)上的硬盤）故障修復(fù)完成之前，又有其他機(jī)架上發(fā)生節(jié)點(diǎn)（或硬盤）故障，這些故障設(shè)備構(gòu)成了“副本集合”，造成數(shù)據(jù)丟失，系統(tǒng)轉(zhuǎn)入狀態(tài)5。

系統(tǒng)進(jìn)入狀態(tài)5 之后，無法再繼續(xù)為用戶提供正常服務(wù)，不能再向其他狀態(tài)轉(zhuǎn)換。

2.3 主動(dòng)容錯(cuò)二副本系統(tǒng)

由于預(yù)測性能（不能達(dá)到100%的預(yù)測準(zhǔn)確率）和預(yù)警修復(fù)能力（不能及時(shí)處理完所有的預(yù)警）的限制，主動(dòng)容錯(cuò)機(jī)制并不能完全避免硬盤故障的發(fā)生，再加上存在節(jié)點(diǎn)故障的風(fēng)險(xiǎn)，存儲(chǔ)系統(tǒng)還需要采取一定的被動(dòng)容錯(cuò)機(jī)制以保證系統(tǒng)的可靠性，所以主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的狀態(tài)轉(zhuǎn)換邏輯比較復(fù)雜。圖4 描述了采用二副本冗余機(jī)制的主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)在硬盤故障預(yù)警、硬盤故障、節(jié)點(diǎn)故障，以及預(yù)警處理和故障修復(fù)等事件下的狀態(tài)轉(zhuǎn)換邏輯。其中：“發(fā)生預(yù)警”表示系統(tǒng)中有硬盤被故障預(yù)測模型檢測出即將發(fā)生故障，“預(yù)警處理”表示系統(tǒng)對(duì)預(yù)警硬盤采取的備份遷移操作。

圖4 主動(dòng)容錯(cuò)二副本系統(tǒng)狀態(tài)轉(zhuǎn)換模型Fig.4 State transition model for 2-way replication system with proactive fault tolerance

主動(dòng)容錯(cuò)二副本系統(tǒng)有6 個(gè)主要狀態(tài)節(jié)點(diǎn)：狀態(tài)1，所有設(shè)備都在健康正常運(yùn)行，沒有發(fā)生任何預(yù)警和故障；狀態(tài)2，某個(gè)機(jī)架上的硬盤被預(yù)測出即將發(fā)生故障；狀態(tài)3，某個(gè)機(jī)架上發(fā)生了設(shè)備（節(jié)點(diǎn)或硬盤）故障；狀態(tài)4，多個(gè)機(jī)架出現(xiàn)了硬盤故障預(yù)警；狀態(tài)5，某個(gè)機(jī)架上發(fā)生了設(shè)備故障，同時(shí)其他機(jī)架的硬盤被檢測出存在潛在故障；狀態(tài)6，某個(gè)（或某些）數(shù)據(jù)塊的所有副本都發(fā)生了損壞，系統(tǒng)發(fā)生了數(shù)據(jù)丟失事件。系統(tǒng)存在下述幾種狀態(tài)轉(zhuǎn)換情況：

1）系統(tǒng)開始運(yùn)行時(shí)處于狀態(tài)1，系統(tǒng)中的所有設(shè)備都在健康運(yùn)行，此時(shí)系統(tǒng)有兩種狀態(tài)轉(zhuǎn)移可能：①如果預(yù)測模型發(fā)出預(yù)警，某個(gè)機(jī)架上的硬盤被檢測出即將發(fā)生故障，系統(tǒng)轉(zhuǎn)入狀態(tài)2；②如果某個(gè)機(jī)架上發(fā)生了設(shè)備故障，系統(tǒng)轉(zhuǎn)入狀態(tài)3。

2）系統(tǒng)出現(xiàn)故障預(yù)警進(jìn)入狀態(tài)2 之后，會(huì)立即啟動(dòng)預(yù)警處理進(jìn)程，把預(yù)警硬盤上的數(shù)據(jù)遷移備份到其他健康硬盤上。從狀態(tài)2 出發(fā)，系統(tǒng)有四種狀態(tài)轉(zhuǎn)移可能：①預(yù)警處理過程及時(shí)完成，在預(yù)警硬盤真正發(fā)生故障之前就把危險(xiǎn)數(shù)據(jù)遷移到了其他健康硬盤上，系統(tǒng)返回到健康狀態(tài)1；②預(yù)警處理完成之前，預(yù)警硬盤發(fā)生了故障，造成部分?jǐn)?shù)據(jù)損壞，或預(yù)警機(jī)架上其他設(shè)備（節(jié)點(diǎn)或硬盤）發(fā)生了故障，系統(tǒng)進(jìn)入狀態(tài)3；③當(dāng)前預(yù)警處理完成之前，其他機(jī)架也出現(xiàn)故障預(yù)警，系統(tǒng)進(jìn)入狀態(tài)4；④在預(yù)警處理完成之前，其他機(jī)架發(fā)生了設(shè)備故障，系統(tǒng)進(jìn)入狀態(tài)5。

3）系統(tǒng)進(jìn)入狀態(tài)3 之后，立即啟動(dòng)故障修復(fù)進(jìn)程，利用其他健康盤上的存活副本對(duì)損壞的數(shù)據(jù)進(jìn)行重構(gòu)。從狀態(tài)3 出發(fā)，系統(tǒng)有三種狀態(tài)轉(zhuǎn)移可能：①故障修復(fù)完成，系統(tǒng)中的所有數(shù)據(jù)塊都恢復(fù)至擁有兩個(gè)副本，所有設(shè)備都在健康運(yùn)行，系統(tǒng)返回狀態(tài)1；②故障修復(fù)完成之前，其他機(jī)架出現(xiàn)故障預(yù)警，系統(tǒng)進(jìn)入狀態(tài)5；③故障修復(fù)完成之前，其他機(jī)架發(fā)生設(shè)備故障，導(dǎo)致系統(tǒng)中至少有一個(gè)數(shù)據(jù)塊的所有副本全部損壞，系統(tǒng)進(jìn)入狀態(tài)6。

4）系統(tǒng)處于狀態(tài)4 時(shí)，系統(tǒng)中運(yùn)行著多個(gè)預(yù)警處理進(jìn)程，對(duì)危險(xiǎn)數(shù)據(jù)進(jìn)行備份。從狀態(tài)4 出發(fā)，系統(tǒng)有兩種狀態(tài)轉(zhuǎn)移可能：①某些預(yù)警處理進(jìn)程成功完成，系統(tǒng)中只剩下一個(gè)機(jī)架上有危險(xiǎn)數(shù)據(jù)沒有備份完，系統(tǒng)返回到狀態(tài)2；②某個(gè)預(yù)警硬盤在備份完成之前發(fā)生了故障，預(yù)警處理失敗，或者其他設(shè)備又發(fā)生了故障，系統(tǒng)進(jìn)入狀態(tài)5。

5）系統(tǒng)處于狀態(tài)5 時(shí)，系統(tǒng)中同時(shí)運(yùn)行著故障修復(fù)進(jìn)程和預(yù)警處理進(jìn)程，對(duì)故障設(shè)備進(jìn)行修復(fù)并備份危險(xiǎn)數(shù)據(jù)。從狀態(tài)5 出發(fā)，系統(tǒng)有三種狀態(tài)轉(zhuǎn)移可能：①故障修復(fù)過程完成，通過其他存活副本將損壞的數(shù)據(jù)重構(gòu)完成，系統(tǒng)返回到狀態(tài)4；②預(yù)警處理過程完成，消除了預(yù)警硬盤發(fā)生故障的危險(xiǎn)，系統(tǒng)返回到狀態(tài)3；③在預(yù)警處理過程完成之前，預(yù)警硬盤就發(fā)生了故障，或者其他（與故障機(jī)架不同的）機(jī)架又發(fā)生了設(shè)備故障，這些并發(fā)的故障造成了數(shù)據(jù)丟失，系統(tǒng)進(jìn)入狀態(tài)6。

6）系統(tǒng)進(jìn)入狀態(tài)6 之后，因?yàn)橛袛?shù)據(jù)發(fā)生了永久性丟失，系統(tǒng)已無法再為用戶提供服務(wù)，所以不能再向其他狀態(tài)轉(zhuǎn)移。

2.4 主動(dòng)容錯(cuò)三副本系統(tǒng)

主動(dòng)容錯(cuò)三副本系統(tǒng)的可靠性狀態(tài)轉(zhuǎn)換邏輯非常復(fù)雜，無法完整地顯示在一個(gè)邏輯圖中，另外，主動(dòng)容錯(cuò)三副本系統(tǒng)的狀態(tài)轉(zhuǎn)換邏輯與上述二副本系統(tǒng)的轉(zhuǎn)換邏輯類似，所以，本文僅把發(fā)生數(shù)據(jù)丟失過程中的關(guān)鍵狀態(tài)節(jié)點(diǎn)列出，如圖5所示。

圖5 主動(dòng)容錯(cuò)三副本系統(tǒng)狀態(tài)轉(zhuǎn)換模型Fig.5 State transition model for 3-way replication system with proactive fault tolerance

狀態(tài)1表示系統(tǒng)處于完全健康運(yùn)行狀態(tài)；狀態(tài)2表示系統(tǒng)中出現(xiàn)了部分設(shè)備故障及（或）硬盤故障預(yù)警，這些故障設(shè)備還沒有對(duì)系統(tǒng)的可靠性造成威脅，此時(shí)系統(tǒng)進(jìn)入降級(jí)模式，啟動(dòng)故障修復(fù)及（或）預(yù)警處理進(jìn)程，對(duì)故障及（或）預(yù)警硬盤進(jìn)行修復(fù)。

在兩種情況下，系統(tǒng)會(huì)進(jìn)入狀態(tài)3：①兩個(gè)機(jī)架上都有一個(gè)節(jié)點(diǎn)由于設(shè)備故障出現(xiàn)數(shù)據(jù)損壞；②某個(gè)機(jī)架上的兩個(gè)節(jié)點(diǎn)都出現(xiàn)了數(shù)據(jù)損壞。此時(shí)系統(tǒng)進(jìn)入瀕臨數(shù)據(jù)丟失的狀態(tài)，只要某些特定位置的設(shè)備發(fā)生故障，系統(tǒng)就會(huì)發(fā)生數(shù)據(jù)丟失事件：①如果兩個(gè)損壞機(jī)架上再有一個(gè)節(jié)點(diǎn)出現(xiàn)數(shù)據(jù)損壞；②其他機(jī)架上的某個(gè)節(jié)點(diǎn)出現(xiàn)數(shù)據(jù)損壞。這樣，系統(tǒng)中的這些并發(fā)故障設(shè)備構(gòu)成了一個(gè)或多個(gè)“副本集合”，導(dǎo)致數(shù)據(jù)丟失事件的發(fā)生。

3 仿真程序

根據(jù)上述提出的系統(tǒng)可靠性狀態(tài)轉(zhuǎn)換邏輯，本文設(shè)計(jì)了蒙特卡洛仿真算法，模擬主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的運(yùn)行，并評(píng)價(jià)系統(tǒng)在一定運(yùn)行周期內(nèi)（比如，10 a）發(fā)生數(shù)據(jù)丟失的期望次數(shù)。

仿真算法模擬了6 個(gè)事件：①節(jié)點(diǎn)故障事件，潛在存在于每個(gè)服務(wù)器節(jié)點(diǎn)上，發(fā)生時(shí)間根據(jù)節(jié)點(diǎn)故障的時(shí)間分布函數(shù)隨機(jī)生成；②節(jié)點(diǎn)故障修復(fù)完成事件，在節(jié)點(diǎn)故障修復(fù)進(jìn)程完成時(shí)觸發(fā)，修復(fù)過程的處理時(shí)間根據(jù)節(jié)點(diǎn)故障修復(fù)的時(shí)間分布函數(shù)隨機(jī)生成；③硬盤故障事件，潛在存在于每個(gè)硬盤上，發(fā)生時(shí)間根據(jù)硬盤故障的時(shí)間分布函數(shù)隨機(jī)生成；④硬盤故障修復(fù)完成事件，在硬盤故障修復(fù)進(jìn)程完成時(shí)觸發(fā)，修復(fù)過程的處理時(shí)間根據(jù)硬盤故障修復(fù)的時(shí)間分布函數(shù)隨機(jī)生成；⑤硬盤故障預(yù)警事件，在故障預(yù)測模型檢測到系統(tǒng)中有即將發(fā)生的硬盤故障時(shí)觸發(fā)，發(fā)生時(shí)間根據(jù)硬盤故障的發(fā)生時(shí)間和故障預(yù)測模型的性能指標(biāo)——提前預(yù)測時(shí)間（Time In Advance，TIA）生成；⑥硬盤故障預(yù)警處理完成事件，在預(yù)警硬盤上的數(shù)據(jù)全部遷移備份完成時(shí)觸發(fā)，預(yù)警處理過程的時(shí)間根據(jù)硬盤故障預(yù)警處理的時(shí)間分布函數(shù)生成。

事件⑤和事件⑥模擬主動(dòng)容錯(cuò)機(jī)制在系統(tǒng)中的運(yùn)行，事件⑤發(fā)生之后，系統(tǒng)立即啟動(dòng)預(yù)警處理進(jìn)程，把危險(xiǎn)硬盤上的數(shù)據(jù)遷移備份到其他健康硬盤上。事件①或③發(fā)生時(shí)，算法根據(jù)系統(tǒng)的冗余機(jī)制檢測是否發(fā)生數(shù)據(jù)丟失事件：a）如果沒有發(fā)生數(shù)據(jù)丟失，系統(tǒng)立即啟動(dòng)故障修復(fù)進(jìn)程，利用其他健康設(shè)備上的存活數(shù)據(jù)重構(gòu)故障數(shù)據(jù)；b）如果發(fā)生了數(shù)據(jù)丟失，為了維持系統(tǒng)規(guī)模，系統(tǒng)添加新的設(shè)備和數(shù)據(jù)，并為新設(shè)備生成未來的潛在故障事件。事件②、④或⑥發(fā)生時(shí)，表示故障或預(yù)警已經(jīng)被修復(fù)完成，系統(tǒng)中加入新的設(shè)備替換故障（或危險(xiǎn)）設(shè)備，并為新設(shè)備生成未來的潛在故障事件。

仿真算法維護(hù)了一個(gè)最小堆，用以保存當(dāng)前還沒有發(fā)生的未來事件，這些事件根據(jù)發(fā)生時(shí)間的先后順序插入最小堆，最小堆頂部的事件為最先要發(fā)生的事件。系統(tǒng)中事件的發(fā)生時(shí)間不斷累積，直到超過預(yù)設(shè)的運(yùn)行周期，仿真程序的一次運(yùn)行結(jié)束，統(tǒng)計(jì)系統(tǒng)運(yùn)行期間數(shù)據(jù)丟失的發(fā)生次數(shù)作為仿真結(jié)果。程序開始時(shí)，根據(jù)節(jié)點(diǎn)故障和硬盤故障的時(shí)間分布函數(shù)，分別為系統(tǒng)中的每個(gè)節(jié)點(diǎn)和硬盤生成一個(gè)未來的故障事件，并且根據(jù)硬盤故障預(yù)測模型的預(yù)測準(zhǔn)確率（Failure Detection Rate，F(xiàn)DR）為潛在的硬盤故障生成預(yù)警事件，這些事件都根據(jù)發(fā)生時(shí)間的先后順序插入最小堆。程序運(yùn)行期間，最小堆頂部的事件被彈出，模擬該事件的發(fā)生，系統(tǒng)根據(jù)發(fā)生事件的類型作出相應(yīng)操作。

4 實(shí)驗(yàn)和結(jié)果分析

本章呈現(xiàn)了仿真程序的實(shí)驗(yàn)結(jié)果，并分析了主動(dòng)容錯(cuò)機(jī)制和不同系統(tǒng)參數(shù)對(duì)系統(tǒng)可靠性的影響。

4.1 實(shí)驗(yàn)準(zhǔn)備

1）系統(tǒng)規(guī)模：對(duì)于用戶來說，主要關(guān)心不同存儲(chǔ)系統(tǒng)在相同用戶數(shù)據(jù)容量下的可靠性差異，所以考慮如下的系統(tǒng)規(guī)模：對(duì)于二副本存儲(chǔ)系統(tǒng)，系統(tǒng)共包含200 個(gè)機(jī)架，每個(gè)機(jī)架上部署了10個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)掛載了4個(gè)硬盤，假設(shè)硬盤的容量是4 TB，系統(tǒng)總共可以存儲(chǔ)16 000 TB的用戶數(shù)據(jù)；對(duì)于三副本系統(tǒng)，系統(tǒng)包含300 個(gè)機(jī)架，每個(gè)機(jī)架上部署了10 個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)掛載了4 個(gè)硬盤，假設(shè)硬盤的容量是4 TB，系統(tǒng)也可以存儲(chǔ)16 000 TB的用戶數(shù)據(jù)。

2）硬盤故障和故障修復(fù)：很多前人的研究都假設(shè)硬盤故障時(shí)間服從指數(shù)分布，這個(gè)假設(shè)被Schroeder 等［16］推翻了，他們發(fā)現(xiàn)韋布分布函數(shù)能夠很好地模擬硬盤故障的發(fā)生。

硬盤發(fā)生故障之后，系統(tǒng)啟動(dòng)故障重構(gòu)過程，利用其他存活硬盤上的副本恢復(fù)損壞的數(shù)據(jù)，并把重構(gòu)出的數(shù)據(jù)散布到系統(tǒng)其他健康硬盤上，同時(shí)增加新硬盤到系統(tǒng)，維持系統(tǒng)規(guī)模。通過對(duì)大量領(lǐng)域數(shù)據(jù)的分析，Elerath 等［18］發(fā)現(xiàn)韋布分布函數(shù)可以很好地?cái)M合硬盤故障和故障修復(fù)過程的時(shí)間分布，因此，本文使用韋布分布函數(shù)模擬硬盤故障和硬盤故障修復(fù)事件在云存儲(chǔ)系統(tǒng)中的發(fā)生。Elerath等［18］從大量領(lǐng)域數(shù)據(jù)中分析得出三種型號(hào)硬盤的故障和修復(fù)過程的韋布分布參數(shù)，本文選擇文獻(xiàn)［18］表3 中A 型號(hào)SATA 硬盤的故障和修復(fù)過程的參數(shù)，詳細(xì)信息見表1。

3）節(jié)點(diǎn)故障和故障修復(fù)：文獻(xiàn)［13］報(bào)道稱在Yahoo！集群中每個(gè)月大約有0.8%的節(jié)點(diǎn)會(huì)發(fā)生（永久或臨時(shí)）故障，相對(duì)臨時(shí)節(jié)點(diǎn)故障，永久性節(jié)點(diǎn)故障發(fā)生的頻率小很多，因此，本文使用0.8%的年平均故障率（平均故障時(shí)間為(24 ×30 × 12)/0.8%=1 080 000 h），模擬生成副本系統(tǒng)中永久性節(jié)點(diǎn)故障。本文使用形狀參數(shù)為1、生命特征參數(shù)為1 080 000的韋布分布函數(shù)模擬節(jié)點(diǎn)故障。形狀參數(shù)為1 時(shí)，韋布分布函數(shù)退化為指數(shù)分布。

節(jié)點(diǎn)故障發(fā)生之后，節(jié)點(diǎn)上掛載的所有硬盤都將不能被訪問，系統(tǒng)會(huì)對(duì)每個(gè)掉線的硬盤啟動(dòng)一個(gè)重構(gòu)過程，利用其他存活硬盤上的副本恢復(fù)損壞的數(shù)據(jù)，為了維持系統(tǒng)規(guī)模，系統(tǒng)管理員會(huì)添加新的節(jié)點(diǎn)到系統(tǒng)，并會(huì)向新的設(shè)備上遷移數(shù)據(jù)以實(shí)現(xiàn)系統(tǒng)的負(fù)載均衡。故障設(shè)備上的數(shù)據(jù)總量除以可用修復(fù)帶寬，得到重構(gòu)過程的運(yùn)行時(shí)間，假設(shè)系統(tǒng)為每個(gè)故障（包括節(jié)點(diǎn)故障和硬盤故障）修復(fù)事件分配的帶寬一致，節(jié)點(diǎn)故障的修復(fù)時(shí)間為硬盤故障修復(fù)時(shí)間的4倍（每個(gè)節(jié)點(diǎn)上掛載4塊硬盤）。

4）硬盤故障預(yù)警和預(yù)警處理：當(dāng)前已經(jīng)有大量工作在研究硬盤故障預(yù)測模型，Li 等［4］的工作中提出的基于決策樹的硬盤故障預(yù)測模型，可以達(dá)到95%的預(yù)測準(zhǔn)確率和近360 h的提前預(yù)測時(shí)間。本文設(shè)置硬盤故障預(yù)測模型的預(yù)測準(zhǔn)確率FDR為80%，平均提前預(yù)警時(shí)間TIA為320 h，即在硬盤故障發(fā)生前平均320 h觸發(fā)預(yù)警事件。當(dāng)設(shè)置FDR=0，主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)退化為被動(dòng)容錯(cuò)系統(tǒng)。

硬盤故障預(yù)警事件發(fā)生之后，系統(tǒng)會(huì)立即啟動(dòng)預(yù)警處理過程，把預(yù)警硬盤上的危險(xiǎn)數(shù)據(jù)提前備份到其他健康的硬盤上。假設(shè)系統(tǒng)為預(yù)警處理分配與故障修復(fù)一致的帶寬，預(yù)警處理的完成時(shí)間與硬盤故障修復(fù)的時(shí)間相同，本文研究使用上述硬盤故障修復(fù)參數(shù)設(shè)置預(yù)警處理完成事件。

表1 列出了本文實(shí)驗(yàn)的主要參數(shù)設(shè)置，如果沒有特殊說明，本文仿真實(shí)驗(yàn)?zāi)J(rèn)使用如表1 的參數(shù)值。其中，符號(hào)r表示系統(tǒng)內(nèi)機(jī)架的數(shù)量，n表示每個(gè)機(jī)架上的節(jié)點(diǎn)數(shù)量，d表示每個(gè)節(jié)點(diǎn)上硬盤的數(shù)量。韋布分布函數(shù)W（α，β，γ），形狀參數(shù)用α表示，生命特征參數(shù)用β表示，位置參數(shù)用γ表示，當(dāng)α=1時(shí)，韋布分布函數(shù)退化為指數(shù)分布。被動(dòng)容錯(cuò)系統(tǒng)的參數(shù)FDR設(shè)置為0。

表1 實(shí)驗(yàn)參數(shù)設(shè)置Tab.1 Experimental parameter setting

對(duì)每組參數(shù)，仿真程序迭代運(yùn)行100 次，最后統(tǒng)計(jì)所有迭代運(yùn)行結(jié)果的平均值作為本組參數(shù)的實(shí)驗(yàn)結(jié)果。

4.2 模型比較

Li 等［25］針對(duì)主動(dòng)容錯(cuò)RAID 系統(tǒng)和副本系統(tǒng)設(shè)計(jì)了數(shù)學(xué)模型和蒙特卡洛仿真模型，評(píng)價(jià)系統(tǒng)在硬盤故障和潛在扇區(qū)錯(cuò)誤（不包含節(jié)點(diǎn)故障）等事件下的可靠性水平。為了驗(yàn)證節(jié)點(diǎn)故障對(duì)副本存儲(chǔ)系統(tǒng)可靠性的影響，本文選用Li 等［25］的蒙特卡洛仿真模型與本文模型做實(shí)驗(yàn)對(duì)比。對(duì)于沒有考慮節(jié)點(diǎn)故障的舊蒙特卡洛仿真模型，除了表1 中的參數(shù)設(shè)置外，使用文獻(xiàn)［18］的表3中硬盤A的潛在扇區(qū)錯(cuò)誤和磁盤清洗參數(shù)。

圖6 呈現(xiàn)了本文所提的新評(píng)價(jià)模型和文獻(xiàn)［25］中的舊仿真模型，對(duì)被動(dòng)/主動(dòng)容錯(cuò)二副本和三副本系統(tǒng)可靠性的評(píng)價(jià)結(jié)果。

圖6 節(jié)點(diǎn)故障對(duì)副本系統(tǒng)可靠性的影響Fig.6 Impact of node failure on reliability of replication systems

“被動(dòng)二副本”“被動(dòng)三副本”“主動(dòng)二副本”和“主動(dòng)三副本”線段上的結(jié)果由不包含節(jié)點(diǎn)故障的舊仿真模型［24］評(píng)價(jià)得出，“被動(dòng)二副本+節(jié)點(diǎn)故障”“被動(dòng)三副本+節(jié)點(diǎn)故障”“主動(dòng)二副本+節(jié)點(diǎn)故障”和“主動(dòng)三副本+節(jié)點(diǎn)故障”線段上的結(jié)果由本文提出的可靠性分析模型評(píng)價(jià)得出。

從圖6 可看出：①隨著運(yùn)行周期的增長，副本存儲(chǔ)系統(tǒng)的可靠性在不斷降低（數(shù)據(jù)丟失次數(shù)在增加），相對(duì)于被動(dòng)容錯(cuò)系統(tǒng)，主動(dòng)容錯(cuò)副本存儲(chǔ)系統(tǒng)的可靠性水平的降低速度緩慢一些；②節(jié)點(diǎn)故障對(duì)副本存儲(chǔ)系統(tǒng)的可靠性有很大影響，尤其是在主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)中，因?yàn)橹鲃?dòng)容錯(cuò)機(jī)制可以消除部分硬盤故障的危害，節(jié)點(diǎn)故障對(duì)系統(tǒng)可靠性的影響更為突出（二副本系統(tǒng)的數(shù)據(jù)丟失概率增大2 倍左右，三副本系統(tǒng)的數(shù)據(jù)丟失概率增大6 倍左右）。本實(shí)驗(yàn)結(jié)果表明，在研究存儲(chǔ)系統(tǒng)可靠性時(shí)，不能忽略節(jié)點(diǎn)故障對(duì)系統(tǒng)可靠性的影響。

4.3 敏感性分析

利用本文提出的可靠性分析模型，系統(tǒng)管理者可以方便地了解主動(dòng)容錯(cuò)機(jī)制以及其他系統(tǒng)參數(shù)對(duì)系統(tǒng)全局可靠性的影響，有利于構(gòu)建和維護(hù)具有高可靠性的存儲(chǔ)系統(tǒng)。實(shí)驗(yàn)將演示如何使用本文提出的可靠性分析模型評(píng)價(jià)不同系統(tǒng)參數(shù)對(duì)系統(tǒng)全局可靠性的影響。

4.3.1 節(jié)點(diǎn)故障的敏感性

本節(jié)實(shí)驗(yàn)分析了隨著節(jié)點(diǎn)年故障率的變化，存儲(chǔ)系統(tǒng)可靠性的變化情況。本實(shí)驗(yàn)設(shè)置節(jié)點(diǎn)的年故障率分別為0.4%、0.6%、0.8%、1.0%、1.2%、1.4%和1.6%，其他參數(shù)使用表1中的設(shè)置，結(jié)果如圖7所示。

圖7 存儲(chǔ)系統(tǒng)在不同節(jié)點(diǎn)故障率下的可靠性Fig.7 Reliability of storage systems under different node failure rates

從圖7 可看出：①隨著節(jié)點(diǎn)故障發(fā)生頻率的增大，四個(gè)系統(tǒng)的可靠性都存在降低的趨勢（數(shù)據(jù)丟失次數(shù)增加）；②相對(duì)于被動(dòng)容錯(cuò)系統(tǒng)，主動(dòng)容錯(cuò)系統(tǒng)可靠性受節(jié)點(diǎn)故障率的影響更大，主要原因是主動(dòng)容錯(cuò)機(jī)制消除了大部分（80%）硬盤故障的危害，節(jié)點(diǎn)故障對(duì)數(shù)據(jù)丟失事件的“貢獻(xiàn)”（影響）更為突出；③相對(duì)于二副本系統(tǒng)，三副本系統(tǒng)的可靠性對(duì)節(jié)點(diǎn)故障率敏感性更大，主要是因?yàn)槿北鞠到y(tǒng)需要更多的并發(fā)設(shè)備故障導(dǎo)致數(shù)據(jù)丟失，所以受節(jié)點(diǎn)故障率的影響更大。

4.3.2 硬盤故障的敏感性

本節(jié)實(shí)驗(yàn)分析隨著硬盤故障頻率的變化，存儲(chǔ)系統(tǒng)可靠性的變化情況。本實(shí)驗(yàn)通過調(diào)整硬盤故障分布函數(shù)的β參數(shù)（特征壽命）改變硬盤的故障時(shí)間，如圖8所示。

圖8 存儲(chǔ)系統(tǒng)在不同硬盤特征壽命下的可靠性Fig.8 Reliability of storage systems under different characteristic lives of disk

從圖8 可看出：①隨著硬盤個(gè)體可靠性的增強(qiáng)（生命特征時(shí)間的增長），四個(gè)系統(tǒng)的可靠性水平都得到了提升；②相對(duì)于二副本系統(tǒng)，三副本系統(tǒng)受硬盤故障時(shí)間的影響更大，主要是因?yàn)槿北鞠到y(tǒng)需要更多的并發(fā)硬盤故障導(dǎo)致數(shù)據(jù)丟失事件的發(fā)生；③即使采用故障頻率高兩倍的硬盤（特征壽命為原來的50%），主動(dòng)容錯(cuò)系統(tǒng)（FDR=80%）也可以達(dá)到與被動(dòng)容錯(cuò)系統(tǒng)相近或更高的可靠性水平，驗(yàn)證了主動(dòng)容錯(cuò)機(jī)制對(duì)系統(tǒng)可靠性提升的效果。

4.3.3 修復(fù)帶寬的敏感性

存儲(chǔ)設(shè)備（節(jié)點(diǎn)或硬盤）發(fā)生故障之后，系統(tǒng)會(huì)啟動(dòng)故障修復(fù)過程重新構(gòu)造受損的數(shù)據(jù)塊，為了維持用戶正常服務(wù)的質(zhì)量，系統(tǒng)只會(huì)將一部分的可用帶寬分配給故障修復(fù)過程，修復(fù)帶寬的多少?zèng)Q定了故障修復(fù)時(shí)間的長短。故障修復(fù)時(shí)間越長，在故障修復(fù)期間再次發(fā)生設(shè)備故障的概率就越大，系統(tǒng)發(fā)生數(shù)據(jù)丟失的危險(xiǎn)也就越大。

為了驗(yàn)證修復(fù)帶寬對(duì)系統(tǒng)可靠性的影響，本實(shí)驗(yàn)通過調(diào)節(jié)故障修復(fù)分布函數(shù)的β參數(shù)改變硬盤故障和節(jié)點(diǎn)故障的修復(fù)時(shí)間，實(shí)驗(yàn)比較了存儲(chǔ)系統(tǒng)在不同故障修復(fù)時(shí)間下的可靠性水平，結(jié)果如圖9 所示。本文假設(shè)系統(tǒng)為所有故障修復(fù)過程分配一樣的修復(fù)帶寬，所以節(jié)點(diǎn)故障修復(fù)的時(shí)間是硬盤故障修復(fù)時(shí)間的4倍（每個(gè)節(jié)點(diǎn)上掛載4塊硬盤）。

圖9 存儲(chǔ)系統(tǒng)在不同故障修復(fù)時(shí)間下的可靠性Fig.9 Reliability of storage systems under different failure repair time

從圖9 可看出：①正如上述分析所示，隨著重構(gòu)時(shí)間的增長，四個(gè)系統(tǒng)的可靠性都呈現(xiàn)出不同程度的降低趨勢；②相對(duì)于二副本系統(tǒng)，三副本存儲(chǔ)系統(tǒng)只有在更多的設(shè)備故障下才會(huì)發(fā)生數(shù)據(jù)丟失，所以對(duì)重構(gòu)時(shí)間具有更強(qiáng)的敏感性；③即使將修復(fù)帶寬降低66%，主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)也可以達(dá)到或超越傳統(tǒng)被動(dòng)容錯(cuò)系統(tǒng)的可靠性水平，這表明在主動(dòng)容錯(cuò)機(jī)制的幫助下，存儲(chǔ)系統(tǒng)可以節(jié)省對(duì)網(wǎng)絡(luò)資源的消耗。

4.3.4 故障預(yù)測準(zhǔn)確率的敏感性

為了定量評(píng)價(jià)主動(dòng)容錯(cuò)機(jī)制對(duì)存儲(chǔ)系統(tǒng)可靠性的提升效果，本實(shí)驗(yàn)比較了存儲(chǔ)系統(tǒng)在不同故障預(yù)測準(zhǔn)確率下的可靠性水平。實(shí)驗(yàn)結(jié)果如圖10所示。

圖10 存儲(chǔ)系統(tǒng)在不同故障檢測率下的可靠性Fig.10 Reliability of storage systems under different failure detection rates

從圖10 中可以清楚地看出：①故障預(yù)測模型的準(zhǔn)確率越高，主動(dòng)容錯(cuò)機(jī)制可以消除越多的潛在硬盤故障，存儲(chǔ)系統(tǒng)的可靠性越強(qiáng)；②對(duì)于二副本系統(tǒng)，當(dāng)故障預(yù)測模型的準(zhǔn)確率達(dá)到50%時(shí)，系統(tǒng)的可靠性提升了1 倍（數(shù)據(jù)丟失數(shù)量降低了50%）；③對(duì)于三副本系統(tǒng)，當(dāng)準(zhǔn)確率達(dá)到50%時(shí)，系統(tǒng)的數(shù)據(jù)丟失次數(shù)減少了75%（可靠性提升了3 倍），這表明與二副本系統(tǒng)相比，三副本系統(tǒng)對(duì)預(yù)測模型性能更敏感；④當(dāng)FDR=100%時(shí)，主動(dòng)容錯(cuò)機(jī)制幾乎可以消除所有的潛在硬盤故障（取決于TIA），系統(tǒng)的數(shù)據(jù)丟失只會(huì)由節(jié)點(diǎn)故障所導(dǎo)致，二副本存儲(chǔ)系統(tǒng)的數(shù)據(jù)丟失量降低近95%，三副本存儲(chǔ)系統(tǒng)的數(shù)據(jù)丟失量降低了97%。

4.3.5 系統(tǒng)規(guī)模的敏感性

本節(jié)實(shí)驗(yàn)分析了隨著系統(tǒng)有效存儲(chǔ)容量的變化，存儲(chǔ)系統(tǒng)可靠性的變化情況。假設(shè)每個(gè)硬盤的容量都是4 TB，通過調(diào)整系統(tǒng)內(nèi)機(jī)架的數(shù)量，從而改變系統(tǒng)的存儲(chǔ)容量，比如，設(shè)置二副本系統(tǒng)的機(jī)架數(shù)r=300，三副本系統(tǒng)的機(jī)架數(shù)r=450，使得四個(gè)系統(tǒng)中的有效存儲(chǔ)容量都是24 000 TB。結(jié)果如圖11所示。

圖11 存儲(chǔ)系統(tǒng)在不同存儲(chǔ)容量下的可靠性Fig.11 Reliability of storage systems under different storage capacities

從圖11 中可以看出：隨著系統(tǒng)有效容量的增大，四個(gè)存儲(chǔ)系統(tǒng)的可靠性呈現(xiàn)出了相近的降低趨勢：系統(tǒng)有效規(guī)模每增大一倍，存儲(chǔ)系統(tǒng)的數(shù)據(jù)丟失數(shù)量將增加近兩倍。系統(tǒng)容量的擴(kuò)大，需要增加存儲(chǔ)設(shè)備（包括節(jié)點(diǎn)服務(wù)器和硬盤），在相同容錯(cuò)能力下，可能發(fā)生故障的設(shè)備增多了，導(dǎo)致系統(tǒng)發(fā)生更多的數(shù)據(jù)丟失事件。

5 結(jié)語

本文針對(duì)采用副本冗余機(jī)制的存儲(chǔ)系統(tǒng)提出了系統(tǒng)可靠性轉(zhuǎn)移模型，分析了在主動(dòng)容錯(cuò)機(jī)制、節(jié)點(diǎn)故障、硬盤故障以及故障修復(fù)事件下的系統(tǒng)狀態(tài)轉(zhuǎn)換邏輯，并根據(jù)這些狀態(tài)轉(zhuǎn)換邏輯、采用蒙特卡洛仿真算法構(gòu)建了存儲(chǔ)系統(tǒng)的可靠性分析模型，評(píng)估系統(tǒng)在一定運(yùn)行周期內(nèi)發(fā)生數(shù)據(jù)丟失的期望次數(shù)。本文采用更接近實(shí)際的韋布分布函數(shù)模擬硬盤故障和故障修復(fù)事件的時(shí)間分布，定量評(píng)價(jià)了主動(dòng)容錯(cuò)機(jī)制、節(jié)點(diǎn)故障、節(jié)點(diǎn)故障修復(fù)、硬盤故障、硬盤故障修復(fù)對(duì)副本系統(tǒng)可靠性的影響。

另外，本文利用仿真程序驗(yàn)證了節(jié)點(diǎn)故障對(duì)云存儲(chǔ)系統(tǒng)可靠性的影響，并分析了主動(dòng)容錯(cuò)機(jī)制和其他系統(tǒng)參數(shù)對(duì)系統(tǒng)可靠性的影響。利用本文提出的可靠性分析模型，系統(tǒng)管理者在構(gòu)建或維護(hù)系統(tǒng)時(shí)，可以靈活方便地評(píng)估不同系統(tǒng)參數(shù)對(duì)系統(tǒng)可用性和可靠性的影響，從而有助于高可靠存儲(chǔ)系統(tǒng)的搭建和維護(hù)。

本文研究使用Weibull分布函數(shù)模擬故障修復(fù)的時(shí)間，沒有細(xì)致考慮副本數(shù)據(jù)塊的分發(fā)方式以及故障恢復(fù)機(jī)制對(duì)修復(fù)時(shí)間的影響。在未來的研究中，本文作者計(jì)劃根據(jù)副本數(shù)據(jù)塊在系統(tǒng)中的散布方式、可用的網(wǎng)絡(luò)修復(fù)帶寬以及并發(fā)的故障數(shù)量計(jì)算故障修復(fù)的時(shí)間，更真實(shí)準(zhǔn)確地評(píng)價(jià)主動(dòng)容錯(cuò)存儲(chǔ)系統(tǒng)的可靠性。