四模冗余拜占庭容錯(cuò)計(jì)算機(jī)可靠性分析*

肖愛(ài)斌，胡明明，任憲朝，李 森，楊 樑

(1.北京控制工程研究所，北京100190;2.北京空間科技信息研究所，北京100190;3.中國(guó)空間技術(shù)研究院，北京100094)

0 引 言

工業(yè)界往往采用最小的硬件冗余來(lái)提高可靠性，只能容忍少數(shù)的幾種故障模式;國(guó)防應(yīng)用研究領(lǐng)域，尤其是載人航天器一般采用足夠的硬件冗余來(lái)提高系統(tǒng)可靠性，具備容忍所有故障模式的能力.

星載控制計(jì)算機(jī)是衛(wèi)星的關(guān)鍵部件，其可靠性直接關(guān)系到衛(wèi)星能否正常運(yùn)行和完成預(yù)定任務(wù).為了保證計(jì)算機(jī)能在惡劣太空輻射環(huán)境中長(zhǎng)期可靠工作，需要對(duì)其進(jìn)行專(zhuān)門(mén)的加固和冗余容錯(cuò)設(shè)計(jì).對(duì)于載人航天器，由于涉及到乘員的安全性，控制計(jì)算機(jī)在完善單機(jī)設(shè)計(jì)外，通過(guò)精巧的冗余設(shè)計(jì)來(lái)增強(qiáng)整個(gè)計(jì)算機(jī)系統(tǒng)的容忍故障的能力尤為必要.學(xué)術(shù)界和防御研究機(jī)構(gòu)建議，對(duì)于載人航天器這樣有關(guān)鍵安全性需求的設(shè)備或系統(tǒng)可以使用足夠硬件冗余來(lái)滿(mǎn)足容忍任意故障模式的需求.容忍任意故障模式稱(chēng)作拜占庭恢復(fù)(Byzantine resilience)[1].由于拜占庭恢復(fù)系統(tǒng)通過(guò)硬件冗余來(lái)屏蔽隱藏的未知故障引起的模塊或單機(jī)失效，因此具有極高的可靠性，使得星載計(jì)算機(jī)在關(guān)鍵安全、可靠性方面的指標(biāo)能得到有效保障.

本文采用馬爾可夫鏈分析拜占庭容錯(cuò)模型的可靠性，為四模冗余拜占庭容錯(cuò)計(jì)算機(jī)設(shè)計(jì)提供參考.

1 拜占庭容錯(cuò)計(jì)算機(jī)模型

在容錯(cuò)計(jì)算機(jī)里多機(jī)間通信是實(shí)現(xiàn)容錯(cuò)的瓶頸，為盡可能減少開(kāi)銷(xiāo)，需要采用硬件實(shí)現(xiàn)多機(jī)間的通信.采用額外硬件——網(wǎng)絡(luò)單元(NE，network element)來(lái)連接冗余多機(jī).NE實(shí)現(xiàn)冗余多機(jī)間同步、數(shù)據(jù)通信和數(shù)據(jù)表決等容錯(cuò)相關(guān)功能，而處理器負(fù)責(zé)執(zhí)行應(yīng)用程序、調(diào)度和重構(gòu)等復(fù)雜任務(wù).使用這種體系結(jié)構(gòu)就是為了解決上述3個(gè)問(wèn)題:①通過(guò)獨(dú)立的硬件實(shí)現(xiàn)并維持多機(jī)間的數(shù)據(jù)一致性，避免主處理器進(jìn)行頻繁的數(shù)據(jù)通信和數(shù)據(jù)表決等任務(wù)，減輕主處理器的容錯(cuò)開(kāi)銷(xiāo);②提供多機(jī)實(shí)現(xiàn)的靈活性，使得支持異構(gòu)處理器、操作系統(tǒng)和應(yīng)用軟件的多機(jī)成為可能;③層次化的容錯(cuò)策略可以使應(yīng)用軟件盡可能少的與容錯(cuò)策略實(shí)現(xiàn)的細(xì)節(jié)耦合[2].

根據(jù)拜占庭恢復(fù)的理論需求，采用的拜占庭恢復(fù)容錯(cuò)計(jì)算機(jī)的結(jié)構(gòu)方案[2]為:4個(gè)故障包容區(qū)域(FCR，fault containment region)，每個(gè)包含一個(gè)處理單元(PE)和一個(gè)NE，其中PE是執(zhí)行應(yīng)用程序、調(diào)度和重構(gòu)任務(wù)的單板計(jì)算機(jī)，NE是實(shí)現(xiàn)同步、數(shù)據(jù)傳遞和數(shù)據(jù)表決等容錯(cuò)相關(guān)功能的硬件，4個(gè)NE通過(guò)完全連接提供1-拜占庭故障恢復(fù)，如圖1所示.

圖1 拜占庭容錯(cuò)系統(tǒng)模型Fig.1 Byzantine fault tolerantmodel

此系統(tǒng)中每個(gè)處理器都連接自己的傳感器組，通過(guò)兩輪輸入一致交換使得系統(tǒng)中所有處理器都獲得此傳感器組的值(解決輸入一致問(wèn)題);每個(gè)處理器都連接執(zhí)行機(jī)構(gòu)，通過(guò)仲裁算法確定某個(gè)無(wú)故障處理器當(dāng)班控制輸出(解決輸出沖突).

2 可靠性分析

本節(jié)采用馬爾可夫鏈分析拜占庭容錯(cuò)模型的可靠性.系統(tǒng)失效概率記為Psysloss，可靠性定義為1-Psysloss.系統(tǒng)失效概率又可分為停機(jī)失效概率Pshutdown和不安全失效概率Punsafe，其中停機(jī)失效定義為系統(tǒng)檢測(cè)到故障的主動(dòng)停機(jī)狀態(tài)，而不安全失效定義為系統(tǒng)發(fā)生故障未被檢測(cè)的不安全狀態(tài).對(duì)于空間應(yīng)用的星載計(jì)算機(jī)來(lái)說(shuō)，Psysloss是Pshutdown與Punsafe的總和，由于傳統(tǒng)的容錯(cuò)方法通過(guò)冗余備份能夠很好地解決系統(tǒng)停機(jī)失效的問(wèn)題，因此本節(jié)的可靠性分析著重于拜占庭容錯(cuò)對(duì)改善系統(tǒng)不安全失效的概率上.PE和NE的失效概率分別記為λPE和λNE，根據(jù)文獻(xiàn)[3]λPE的典型數(shù)值取10-4h-1;由于NE比PE簡(jiǎn)單，因此NE的失效概率要低，根據(jù)文獻(xiàn)[4]λNE的值取1.4×10-5h-1.PE和NE的故障恢復(fù)率(故障恢復(fù)時(shí)間的倒數(shù))分別記為uPE和uNE，為簡(jiǎn)便起見(jiàn)，uPE和uNE的值都取103h-1[5].參數(shù)fc指故障能夠被系統(tǒng)檢測(cè)到的概率，稱(chēng)之為故障檢測(cè)率.對(duì)于單機(jī)系統(tǒng)，可以采用自測(cè)試、超時(shí)、重試和滾回等操作來(lái)恢復(fù)故障，其故障檢測(cè)率fc通常在0.8到0.95之間，這里取0.8來(lái)分析.本文的方案滿(mǎn)足1-拜占庭恢復(fù)條件[2]，因此，對(duì)于單個(gè)故障可以達(dá)到100%的檢測(cè)率，即fc=1.ft指當(dāng)發(fā)生故障時(shí)，瞬時(shí)故障所占的比率，這里取0.5.

2.1 單機(jī)系統(tǒng)可靠性分析

傳統(tǒng)單機(jī)系統(tǒng)的馬爾可夫模型如圖2所示，共包括以下4種狀態(tài):狀態(tài)1，零故障狀態(tài);狀態(tài)2，檢測(cè)故障的重試或滾回狀態(tài);狀態(tài)3，發(fā)生永久故障的停機(jī)失效狀態(tài);狀態(tài)4，未檢測(cè)故障的不安全失效狀態(tài).當(dāng)系統(tǒng)檢測(cè)到故障時(shí)進(jìn)入狀態(tài)2，如果發(fā)生的是瞬時(shí)故障，系統(tǒng)通過(guò)重試或滾回操作可以恢復(fù)故障返回狀態(tài)1;如果發(fā)生的是永久故障，系統(tǒng)將進(jìn)入狀態(tài)3.當(dāng)系統(tǒng)發(fā)生故障而沒(méi)有被檢測(cè)到時(shí)，系統(tǒng)進(jìn)入狀態(tài)4.圖3是單機(jī)系統(tǒng)在fc=0.8時(shí)停機(jī)失效Pshutdown和不安全失效Punsafe的概率.

圖2 單機(jī)系統(tǒng)馬爾可夫鏈Fig.2 Markov chain for simplex system

單機(jī)系統(tǒng)在工作10h后Psysloss為其中為這不滿(mǎn)足文獻(xiàn)[1]中的10h運(yùn)行的需求.

2.2 本文模型可靠性分析

由于本文拜占庭容錯(cuò)模型的馬爾可夫鏈取決于所采用的容錯(cuò)方案，下面根據(jù)不同的容錯(cuò)方案分析第1節(jié)拜占庭容錯(cuò)系統(tǒng)模型的可靠性.

方案1.系統(tǒng)一直工作在拜占庭恢復(fù)模式，當(dāng)出現(xiàn)第一個(gè)NE永久故障(不滿(mǎn)足拜占庭恢復(fù)條件)時(shí)系統(tǒng)安全停機(jī).由于本文的系統(tǒng)模型是拜占庭恢復(fù)結(jié)構(gòu)，當(dāng)出現(xiàn)任意單個(gè)故障，系統(tǒng)都能夠容忍，也就是說(shuō)fc等于1.方案1的馬爾可夫鏈如圖4所示，其中包括兩組工作狀態(tài):停機(jī)失效以及不安全失效狀態(tài).第一組工作狀態(tài)包括狀態(tài)1、2、3和5.狀態(tài)1是初始零故障狀態(tài)，當(dāng)PE故障時(shí)，系統(tǒng)轉(zhuǎn)換到狀態(tài)2(PE故障恢復(fù)狀態(tài))，相應(yīng)的，任意單個(gè)NE故障時(shí)，將使系統(tǒng)從狀態(tài)1轉(zhuǎn)換到狀態(tài)3(NE故障恢復(fù)狀態(tài)).如果上面發(fā)生的是瞬時(shí)故障，系統(tǒng)將返回狀態(tài)1;如果在狀態(tài)2或3發(fā)生第二個(gè)故障，系統(tǒng)將轉(zhuǎn)換到狀態(tài)10(不安全系統(tǒng)失效狀態(tài))，但當(dāng)發(fā)生的這兩個(gè)故障是一個(gè)FCR內(nèi)的PE和NE時(shí)系統(tǒng)轉(zhuǎn)移到狀態(tài)5.狀態(tài)5同時(shí)存在PE和NE故障，此時(shí)將首先恢復(fù)NE故障.在狀態(tài)3和狀態(tài)5時(shí)，如果發(fā)生的是NE永久故障，將導(dǎo)致系統(tǒng)轉(zhuǎn)換到狀態(tài)11(停機(jī)失效狀態(tài))，因?yàn)镹E故障意味著相應(yīng)的FCR故障，此時(shí)無(wú)故障FCR不滿(mǎn)足最少拜占庭恢復(fù)的基數(shù)需求.在狀態(tài)5，重構(gòu)一個(gè)瞬時(shí)NE故障將返回狀態(tài)2.如果狀態(tài)2的PE是永久故障，系統(tǒng)將進(jìn)入狀態(tài)4.

狀態(tài)4時(shí)系統(tǒng)進(jìn)入第二組工作狀態(tài)(狀態(tài)4、6、7、8和9)，此時(shí)系統(tǒng)包含3個(gè)工作PE和4個(gè)工作NE，系統(tǒng)仍然滿(mǎn)足1-拜占庭恢復(fù)條件，因此仍然能夠容忍任意單個(gè)故障.其中3個(gè)處理器提供故障屏蔽能力，4個(gè)NE滿(mǎn)足1-拜占庭恢復(fù)的基數(shù)、互連和同步需求.因此，狀態(tài)4是降級(jí)拜占庭恢復(fù)結(jié)構(gòu)的初始狀態(tài).

在狀態(tài)4，PE故障將轉(zhuǎn)換到狀態(tài)6，如果發(fā)生的是瞬時(shí)故障，系統(tǒng)將返回狀態(tài)4;如果是永久故障，系統(tǒng)將進(jìn)入停機(jī)失效狀態(tài).如果在狀態(tài)6時(shí)又發(fā)生一個(gè)部件故障將使得系統(tǒng)進(jìn)入不安全失效狀態(tài).同樣，如果發(fā)生的是PE/NE故障對(duì)，使得系統(tǒng)進(jìn)入狀態(tài)9.在狀態(tài)4，如果帶有工作PE的NE故障將進(jìn)入狀態(tài)8，如果發(fā)生的是瞬時(shí)故障，系統(tǒng)返回狀態(tài)4，否則進(jìn)入停機(jī)狀態(tài).在狀態(tài)8，如果又發(fā)生故障，系統(tǒng)進(jìn)入不安全失效狀態(tài).同樣，PE/NE對(duì)失效時(shí)進(jìn)入狀態(tài)9.在狀態(tài)4時(shí)，如果不含PE的NE故障，系統(tǒng)將進(jìn)入狀態(tài)7，狀態(tài)7和狀態(tài)8不同的是它不能進(jìn)入狀態(tài)9(PE/NE故障狀態(tài)).狀態(tài)9和狀態(tài)5一樣，系統(tǒng)首先恢復(fù)NE，如果成功恢復(fù)則進(jìn)入狀態(tài)6，否則進(jìn)入狀態(tài)11.此方案中，如圖5所示.

從圖5中可以看出，Punsafe比Pshutdown低5個(gè)數(shù)量級(jí)，因此Psysloss基本等于Pshutdown的值.在10h運(yùn)行后，這比單模系統(tǒng)的Pshutdown還高，這是因?yàn)橄到y(tǒng)的4個(gè)FCR中有一個(gè)FCR故障的概率比單模系統(tǒng)FCR故障的概率要高.但如果系統(tǒng)仍有冗余備份資源，通過(guò)對(duì)故障機(jī)的替換繼續(xù)工作在拜占庭恢復(fù)模式，可以使系統(tǒng)停機(jī)失效的概率即Pshutdown的值接近于0，此時(shí)系統(tǒng)失效的概率基本等于不安全失效的概率即

圖4 方案1的馬爾可夫鏈Fig.4 Markov chains for redundancy scheme 1

圖5 方案1的 P shutdown和 P unsafe概率Fig.5 P shutdown and P unsafe for redundancy scheme 1

方案2.當(dāng)出現(xiàn)第一個(gè)NE永久故障時(shí)系統(tǒng)降級(jí)為單模系統(tǒng)繼續(xù)工作.在圖4的基礎(chǔ)上將狀態(tài)11替換為圖6的4個(gè)狀態(tài)，即可得到此方案的馬爾可夫鏈，其中如圖7所示.10h運(yùn)行后，h-1，這比方案1要低好幾個(gè)數(shù)量級(jí)，但是比方案1要高一個(gè)數(shù)量級(jí)，這是因?yàn)榉桨?允許系統(tǒng)在非拜占庭恢復(fù)模式工作，這降低了Pshutdown，同時(shí)增加了Punsafe.

圖6 方案2增加的馬爾可夫鏈Fig.6 Additive Markov chains for redundancy scheme 2

方案3.當(dāng)出現(xiàn)第一個(gè)NE永久故障時(shí)系統(tǒng)降級(jí)為三模系統(tǒng)繼續(xù)工作，當(dāng)出現(xiàn)第二個(gè)NE永久故障時(shí)系統(tǒng)安全停機(jī).在圖4的基礎(chǔ)上，將狀態(tài)11替換為圖8的8個(gè)狀態(tài)，即可得到此方案的馬爾可夫鏈.圖8中狀態(tài)11是3個(gè)FCR工作狀態(tài)，從圖4的狀態(tài)3、5、7中而來(lái).這里的狀態(tài)13、14和圖4中的狀態(tài)2、3相似，所不同的是，三模系統(tǒng)是非拜占庭恢復(fù)結(jié)構(gòu)，當(dāng)系統(tǒng)發(fā)生拜占庭故障時(shí)系統(tǒng)不能檢測(cè).因此在狀態(tài)11時(shí)，如果發(fā)生檢測(cè)到的NE故障，系統(tǒng)進(jìn)入狀態(tài)13(NE故障恢復(fù)狀態(tài));否則，如果發(fā)生未檢測(cè)的拜占庭故障，系統(tǒng)將進(jìn)入狀態(tài)18.同樣，如果發(fā)生檢測(cè)的PE故障，系統(tǒng)進(jìn)入狀態(tài)14，否則，系統(tǒng)進(jìn)入狀態(tài)18.圖8中狀態(tài)12是4個(gè)NE和兩個(gè)PE工作狀態(tài)，這是從圖4的狀態(tài)6進(jìn)入的，也不滿(mǎn)足拜占庭恢復(fù)條件.

圖7 方案2的 P shutdown和 P unsafe概率Fig.7 P shutdown and P unsafe for redundancy scheme 2

圖8 方案3增加的馬爾可夫鏈Fig.8 Additive Markov chains for redundancy scheme 3

不同容錯(cuò)方案在工作10h的可靠性分析總結(jié)如表1所示.

表1 可靠性分析總結(jié)Tab.1 Reliability analysis summary h-1

3 結(jié) 論

通過(guò)本文分析可以看出，工作在拜占庭恢復(fù)模式下系統(tǒng)具有最小的不安全失效概率.如果系統(tǒng)有額外備份資源可用，通過(guò)對(duì)故障機(jī)的替換，系統(tǒng)就不會(huì)發(fā)生停機(jī)失效，因此系統(tǒng)的失效概率等于不安全失效的概率，所以系統(tǒng)一直工作在拜占庭恢復(fù)模式可以獲得最高的可靠性.如果系統(tǒng)沒(méi)有額外的備份資源，通過(guò)降級(jí)工作在非拜占庭恢復(fù)模式下，這可以降低系統(tǒng)停機(jī)失效的概率，同時(shí)增加系統(tǒng)的不安全失效概率，當(dāng)兩者的和最小時(shí)系統(tǒng)獲得最高可靠性.因此，系統(tǒng)采用何種方案降級(jí)工作取決于系統(tǒng)Pshutdown和Punsafe之間的關(guān)系.

圖9 方案3的 P shutdown和 P unsafe概率Fig.9 P shutdown and P unsafe for redundancy scheme 3

[1]LALA JH，HARPER R E.Architectural principles for safety-critical real-time applications[C]//Proceedings of the IEEE.Cambridge:IEEE，1994:25-40.

[2]XIAO A B，YANG M F，LIU B.Design and validation of Byzantine fault tolerance for on-board computer[J].Aerospace Control and Application， 2008，34(4):17-22.

[3]WENSLEY J.SIFT:the design and analysis of a fault tolerant computer for aircraft control[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1240-1255.

[4]HARPER R.Critical issues in ultra-reliable parallel processing[D].Cambridge:Massachusetts Institute of Technology，1987.

[5]HOPKINS A L，SMITH T B，LALA J H.FTMP-A highly reliable fault-tolerant multiprocessor for aircraft[C]//Proceedings of the IEEE.Cambridge:IEEE，1978:1221-1239.