馬瑋駿，王 強(qiáng)，何曉暉，馮 徑，馬 強(qiáng)

(解放軍理工大學(xué)，江蘇 南京 211101)

云存儲系統(tǒng)Master節(jié)點(diǎn)故障動態(tài)切換算法

馬瑋駿，王 強(qiáng)，何曉暉，馮 徑，馬 強(qiáng)

(解放軍理工大學(xué)，江蘇 南京 211101)

為了解決大規(guī)模云存儲系統(tǒng)中Master節(jié)點(diǎn)發(fā)生故障導(dǎo)致存儲服務(wù)不可用的問題，建立了面向云存儲系統(tǒng)管理節(jié)點(diǎn)發(fā)生故障時(shí)的故障影響分析模型。該模型以存儲服務(wù)可用性、數(shù)據(jù)可靠性和數(shù)據(jù)可用性為分析目標(biāo)，通過故障狀態(tài)、管理節(jié)點(diǎn)實(shí)時(shí)狀態(tài)以及管理節(jié)點(diǎn)故障的限制條件三個維度對故障影響進(jìn)行分析，為恢復(fù)故障提供了有效的方法依據(jù)。同時(shí)，基于故障影響分析模型，提出了一種基于消息的Master節(jié)點(diǎn)故障動態(tài)切換算法—DSA-M。該算法通過基于序號的優(yōu)先級策略實(shí)現(xiàn)了Master節(jié)點(diǎn)動態(tài)申請和切換，保證了云存儲服務(wù)的高可用性。測試結(jié)果表明，DSA-M算法能夠在Master節(jié)點(diǎn)發(fā)生故障時(shí)自動進(jìn)行Master節(jié)點(diǎn)的切換和接管，恢復(fù)云存儲服務(wù)的運(yùn)行；通過控制故障檢測周期，能夠使得DSA-M算法的性能保持在相對穩(wěn)定的區(qū)間內(nèi)，隨失效時(shí)刻的適應(yīng)性也比較強(qiáng)。

云存儲系統(tǒng)；Master節(jié)點(diǎn)；故障檢測；元數(shù)據(jù)；動態(tài)切換

1 概 述

大規(guī)模云存儲系統(tǒng)(Huge Cloud Storage System，HCSS)憑借規(guī)模大、覆蓋范圍廣、訪問量大、存儲數(shù)據(jù)量大等特點(diǎn)，逐步成為業(yè)界的研究熱點(diǎn)[1]，而如何保證云存儲系統(tǒng)的高可靠性、高可用性以及故障恢復(fù)問題一直是HCSS的重要研究方向。HCSS一般由一個Master節(jié)點(diǎn)，多個元數(shù)據(jù)管理節(jié)點(diǎn)和若干個存儲節(jié)點(diǎn)構(gòu)成，其中Master節(jié)點(diǎn)主要負(fù)責(zé)收集、檢測各個元數(shù)據(jù)管理節(jié)點(diǎn)的工作信息，掌握云存儲系統(tǒng)的全局運(yùn)行狀態(tài)。因此，當(dāng)Master節(jié)點(diǎn)出現(xiàn)故障時(shí)，如何保證云存儲服務(wù)的高可用性并盡快使其他元數(shù)據(jù)管理節(jié)點(diǎn)實(shí)現(xiàn)從普通管理節(jié)點(diǎn)至Master節(jié)點(diǎn)的無縫切換，是HCSS中需要解決的關(guān)鍵問題之一。

文獻(xiàn)[2]給出了一種提高云存儲系統(tǒng)可靠性的方法，并提出了多個云存儲管理節(jié)點(diǎn)相互協(xié)作提供存儲服務(wù)高可用和高可靠性的概念；文獻(xiàn)[3]研究了OpenStack類云存儲服務(wù)的同步瓶頸問題，并給出了一種輕量級的對象同步協(xié)議LightSync，減輕了同步負(fù)載；文獻(xiàn)[4]描述了GFS通過Master節(jié)點(diǎn)MASTER狀態(tài)、操作記錄、檢查點(diǎn)多機(jī)備份的方式確?？煽啃院凸收匣謴?fù)的相關(guān)方法；文獻(xiàn)[5]提出了一種基于糾刪碼的用于Hadoop平臺的高性價(jià)比的容錯策略，能夠使用較低的代價(jià)提供云存儲的高可靠性；文獻(xiàn)[6]提出了一種基于低密度奇偶校驗(yàn)碼的云存儲系統(tǒng)框架，其中使用了一種裁剪糾錯碼來提高云存儲系統(tǒng)的編碼和解碼性能；文獻(xiàn)[7]從資源分配角度建立了云存儲系統(tǒng)可靠性分析模型，并驗(yàn)證了模型的有效性；文獻(xiàn)[8]基于云存儲節(jié)點(diǎn)數(shù)據(jù)訪問頻率，提出一種副本備份算法，提高了數(shù)據(jù)的可靠性和云存儲訪問性能；文獻(xiàn)[9]針對云存儲系統(tǒng)的可靠性評價(jià)機(jī)制進(jìn)行研究，并給出了面向傳統(tǒng)被動容錯和新型主動容錯兩類云存儲系統(tǒng)的可靠性評價(jià)模型。為了提高云存儲服務(wù)的可用性和容災(zāi)性，近年來一些研究人員將P2P技術(shù)融合至云存儲架構(gòu)[10-12]。文獻(xiàn)[13]通過結(jié)合(n,k)-RS編碼和X編碼，為云存儲系統(tǒng)設(shè)計(jì)一類新的準(zhǔn)確修復(fù)編碼，在一個或兩個節(jié)點(diǎn)發(fā)生故障時(shí)，修復(fù)局部性以及修復(fù)帶寬上都具有顯著優(yōu)勢；文獻(xiàn)[14]利用數(shù)據(jù)拆分及編解碼的思想來解決云盤存儲數(shù)據(jù)的可靠性問題；文獻(xiàn)[15]采用雙活容災(zāi)存儲技術(shù)，構(gòu)建了一個真正意義上的雙活云計(jì)算數(shù)據(jù)中心；文獻(xiàn)[16]提出了云存儲系統(tǒng)故障自動化管理的策略框架、策略描述語言以及策略映射機(jī)制，提高了云存儲系統(tǒng)故障自動化管理的可實(shí)現(xiàn)性。

可以看出，各類云存儲系統(tǒng)或多或少都采用了數(shù)據(jù)冗余來保證數(shù)據(jù)的可用性和可靠性，數(shù)據(jù)可靠性指數(shù)據(jù)能夠持久存儲并且不丟失的概率，數(shù)據(jù)可用性是指數(shù)據(jù)持續(xù)可用的概率。數(shù)據(jù)可靠性可以看作是靜態(tài)需求，而數(shù)據(jù)可用性則是動態(tài)需求。數(shù)據(jù)可靠性可以由數(shù)據(jù)冗余的方式提供保證，很明顯，數(shù)據(jù)可靠，卻不一定可用，如果存儲系統(tǒng)軟硬件出現(xiàn)故障，即便數(shù)據(jù)被可靠地存儲，卻不能被用戶使用。

因此，云存儲系統(tǒng)必須能通過有效的軟硬件動態(tài)恢復(fù)技術(shù)使系統(tǒng)發(fā)生故障時(shí)能夠自動恢復(fù)軟、硬件的正常運(yùn)行，盡可能地提供持續(xù)、正確的存儲服務(wù)，保證系統(tǒng)存儲服務(wù)的高可用性，這樣才能保證數(shù)據(jù)的高可用性。

為此，圍繞HCSS中Master節(jié)點(diǎn)故障失效時(shí)持續(xù)提供云存儲服務(wù)的問題，提出了HCSS管理節(jié)點(diǎn)(包括Master節(jié)點(diǎn)和元數(shù)據(jù)管理節(jié)點(diǎn))故障分析模型，并以該模型為基礎(chǔ)提出Master節(jié)點(diǎn)故障自我恢復(fù)的相關(guān)算法。

2 管理節(jié)點(diǎn)故障分析模型

HCSS管理節(jié)點(diǎn)主要負(fù)責(zé)為云存儲客戶端提供元數(shù)據(jù)服務(wù)，同時(shí)需要檢測各個存儲節(jié)點(diǎn)的工作狀態(tài)。通常HCSS中有多個管理節(jié)點(diǎn)，其中Master節(jié)點(diǎn)負(fù)責(zé)所有管理節(jié)點(diǎn)的故障檢測。使用故障管理對象、故障的限制條件和表現(xiàn)以及故障管理對象的狀態(tài)三個維度來表示HCSS中管理節(jié)點(diǎn)的故障分析模型。

設(shè)HCSS管理節(jié)點(diǎn)的故障狀態(tài)空間SCSSM={s1,s2,…,sn}；HCSS管理節(jié)點(diǎn)故障的限制條件和表現(xiàn)空間CCSSM={c1,c2,…,cm}；HCSS管理節(jié)點(diǎn)實(shí)時(shí)狀態(tài)空間RCSSM={r1,r2,…,rl}。在t時(shí)刻，存儲服務(wù)可用性為SA(t)；數(shù)據(jù)可靠性為DR(t)；數(shù)據(jù)可用性為AD(t)。

記故障發(fā)生時(shí)間為t1，故障狀態(tài)為sm，HCSS管理節(jié)點(diǎn)為oi，HCSS管理節(jié)點(diǎn)實(shí)時(shí)狀態(tài)為rj，HCSS管理節(jié)點(diǎn)故障的限制條件和表現(xiàn)為ck，故障持續(xù)時(shí)間為Δt，則故障sm對存儲服務(wù)可用性的影響記為：

Fsm→SA=fsm→SA(oi,rj,ck)∈[0,1]

(1)

設(shè)t2>t1，t2∈(t1,t1+Δt]，則t2時(shí)刻系統(tǒng)存儲服務(wù)可用性記為：

SA(t2)=SA(t1)(1-Fsm→SA)

(2)

式(1)中，fsm→SA表示故障sm對存儲服務(wù)可用性的影響函數(shù)，該函數(shù)的取值范圍為[0,1]，取0表示沒有影響，取1表示影響最大，使得系統(tǒng)存儲服務(wù)可用性為0，即無法提供存儲服務(wù)。

同理，設(shè)fsm→DR和fsm→AD分別表示故障sm對系統(tǒng)數(shù)據(jù)可靠性和數(shù)據(jù)可用性的影響函數(shù)，則t2時(shí)刻系統(tǒng)數(shù)據(jù)可靠性記為：

DR(t2)=DR(t1)(1-Fsm→DR)

(3)

t2時(shí)刻系統(tǒng)數(shù)據(jù)可用性記為：

AD(t2)=AD(t1)(1-Fsm→AD)

(4)

為了討論簡便，下面對影響函數(shù)進(jìn)行二值化：

Fsm→SA=fsm→SA(oi,rj,ck)∈{0,1}

(5)

Fsm→DR=fsm→DR(oi,rj,ck)∈{0,1}

(6)

Fsm→AD=fsm→AD(oi,rj,ck)∈{0,1}

(7)

式(5)～(7)表示將故障影響簡化為0和1兩種取值，0表示沒有影響，1表示有影響，這種簡化對于界定故障的檢測范圍、恢復(fù)范圍以及恢復(fù)時(shí)效是很有意義的。對于故障影響為0的故障，可以檢測但不一定要及時(shí)恢復(fù)；對于故障影響為1的故障，是必須要進(jìn)行檢測和及時(shí)恢復(fù)的。

表1給出了HCSS管理節(jié)點(diǎn)在崩潰故障情況下的故障分析。其中，崩潰故障指節(jié)點(diǎn)宕機(jī)、掉電或系統(tǒng)崩潰等，對HCSS管理節(jié)點(diǎn)上存儲的元數(shù)據(jù)隨節(jié)點(diǎn)崩潰的丟失情況不做任何假設(shè)。

通過表1可以看出，與Master節(jié)點(diǎn)緊密相關(guān)的是r5狀態(tài)，首先影響的是系統(tǒng)的存儲服務(wù)可用性以及數(shù)據(jù)可用性，Master節(jié)點(diǎn)崩潰會導(dǎo)致其他HCSS管理節(jié)點(diǎn)無法獲取全局的狀態(tài)信息，這必然會影響元數(shù)據(jù)管理工作，因此系統(tǒng)數(shù)據(jù)可靠性也會受到影響。

表1 HCSS管理節(jié)點(diǎn)崩潰故障影響分析

對于Master節(jié)點(diǎn)故障時(shí)的存儲服務(wù)可用性自恢復(fù)，關(guān)鍵在于故障恢復(fù)軟件能否在Master節(jié)點(diǎn)發(fā)生故障時(shí)，在r5狀態(tài)下，使多個HCSS管理節(jié)點(diǎn)能迅速完成Master節(jié)點(diǎn)申請和接管，否則Master節(jié)點(diǎn)故障將導(dǎo)致系統(tǒng)的存儲服務(wù)可用性、數(shù)據(jù)可用性都受到影響，也會影響系統(tǒng)的數(shù)據(jù)可靠性。

3 基于消息的Master節(jié)點(diǎn)故障動態(tài)切換算法

從故障影響分析模型的分析結(jié)果可以看出，由于同一時(shí)刻HCSS管理節(jié)點(diǎn)集合中只有一個節(jié)點(diǎn)作為Master節(jié)點(diǎn)，當(dāng)Master節(jié)點(diǎn)出現(xiàn)故障，必須由其他HCSS管理節(jié)點(diǎn)動態(tài)接管Master節(jié)點(diǎn)的所有職能。

因此，提出了一種基于消息的Master節(jié)點(diǎn)動態(tài)切換算法(Dynamic Switching Algorithm for Master，DSA-M)。通過基于序號的優(yōu)先級策略實(shí)現(xiàn)了Master節(jié)點(diǎn)失效時(shí)的Master節(jié)點(diǎn)動態(tài)申請及負(fù)載接管，保證了系統(tǒng)的存儲服務(wù)高可用性。

3.1DSA-M算法設(shè)計(jì)

DSA-M算法的核心思想是：如果某個HCSS管理節(jié)點(diǎn)hj超過一定的時(shí)間沒有收到Master節(jié)點(diǎn)hm的檢測消息，就認(rèn)為hm失效(崩潰)，便開始申請為Master節(jié)點(diǎn)，如果所有其他節(jié)點(diǎn)都同意hj作為Master節(jié)點(diǎn)，hj便接管故障檢測工作。

3.1.1 超時(shí)判定策略

算法中有兩個超時(shí)時(shí)限，第一個是每個HCSS管理節(jié)點(diǎn)hj判斷故障檢測Master節(jié)點(diǎn)hm失效的超時(shí)時(shí)限，該超時(shí)通過式(8)進(jìn)行計(jì)算:

(8)

如果hj發(fā)現(xiàn)超過Tme仍然沒有收到hm的檢測消息，則認(rèn)為hm出現(xiàn)故障；Tme的選擇需要謹(jǐn)慎，因?yàn)槿绻x擇得過小，則會產(chǎn)生誤判，造成頻繁而沒有必要的申請消息；如果選擇得過大，則會造成長時(shí)間HCSS管理節(jié)點(diǎn)集合中沒有Master節(jié)點(diǎn)，HCSS管理節(jié)點(diǎn)的故障信息以及狀態(tài)信息不能及時(shí)更新。如果出現(xiàn)誤判，則Master節(jié)點(diǎn)返回不同意消息。

第二個超時(shí)時(shí)限是每個HCSS管理節(jié)點(diǎn)hj在發(fā)出Master節(jié)點(diǎn)申請消息后，期望別的HCSS管理節(jié)點(diǎn)回執(zhí)的超時(shí)時(shí)限，該超時(shí)記為MDT，取MDT為當(dāng)前網(wǎng)絡(luò)往返時(shí)延的最大值。這樣取值的目的一方面在于避免由于個別被申請節(jié)點(diǎn)的時(shí)延較大而遺漏確認(rèn)消息，另一方面在于減少多個節(jié)點(diǎn)同時(shí)申請Master節(jié)點(diǎn)的可能性，從而減少網(wǎng)絡(luò)通信量。

3.1.2 優(yōu)先級策略

為了減少通信量，避免多個節(jié)點(diǎn)同時(shí)申請，為每個節(jié)點(diǎn)設(shè)定申請的優(yōu)先級。按照優(yōu)先級，當(dāng)某個節(jié)點(diǎn)申請成功后，其他節(jié)點(diǎn)無需再申請。優(yōu)先級采用hj在云存儲管理節(jié)點(diǎn)集合SCSSMN中的序號SNj進(jìn)行定義，排在前面的節(jié)點(diǎn)申請優(yōu)先級高，hj通過式(9)計(jì)算自己在懷疑Master節(jié)點(diǎn)失效后開始Master節(jié)點(diǎn)申請的等待時(shí)延：

TD=(SNj-1)×MDT

(9)

可以看出，排序越靠后的節(jié)點(diǎn)，需要等待的時(shí)間就越長。這里需要注意一個問題，序號的規(guī)定和發(fā)布是基于序號的優(yōu)先級策略中的核心環(huán)節(jié)，如果序號固定，那必然存在申請不公平的現(xiàn)象，排序靠后的節(jié)點(diǎn)可能始終無法獲得申請的機(jī)會。因此，算法中的序號主要通過Master節(jié)點(diǎn)進(jìn)行生成和發(fā)布，而不是固定的，Master節(jié)點(diǎn)只需每次檢測時(shí)更新序號的排列(可以采用隨機(jī)排列)，便能使各個節(jié)點(diǎn)的優(yōu)先級發(fā)生實(shí)時(shí)變化，因此Master節(jié)點(diǎn)通過序號的公平分配，即可解決申請過程中的不公平問題。

3.1.3 節(jié)點(diǎn)失效處理策略

(1)申請過程中被申請節(jié)點(diǎn)失效：申請過程中，如果某個被申請節(jié)點(diǎn)失效，則無法響應(yīng)申請節(jié)點(diǎn)的申請消息，此時(shí)申請節(jié)點(diǎn)可以通過超時(shí)機(jī)制進(jìn)行處理，一旦某個被申請節(jié)點(diǎn)超時(shí)，申請節(jié)點(diǎn)便跳過該節(jié)點(diǎn)，強(qiáng)制實(shí)行接管，這樣在第一個故障檢測周期內(nèi)，就能夠檢測出該失效節(jié)點(diǎn)。

(2)申請過程中被申請節(jié)點(diǎn)超時(shí)(但沒有失效)：申請過程中，如果某個被申請節(jié)點(diǎn)由于網(wǎng)絡(luò)或者過載等原因超時(shí)，申請節(jié)點(diǎn)便跳過該節(jié)點(diǎn)，強(qiáng)制實(shí)行接管，這樣在第一個檢測周期內(nèi)，就能夠檢測出該節(jié)點(diǎn)的實(shí)時(shí)狀態(tài)，對于被申請節(jié)點(diǎn)，一旦收到檢測消息，便進(jìn)行響應(yīng)，并更新Master節(jié)點(diǎn)。

(3)申請過程中申請節(jié)點(diǎn)失效：申請過程中，如果申請節(jié)點(diǎn)失效，則存在兩種情況。第一種是申請進(jìn)行了一半，此時(shí)必定有部分被申請節(jié)點(diǎn)無法收到申請消息，假設(shè)沒有收到申請消息的第一個節(jié)點(diǎn)是hj，則一旦到達(dá)時(shí)間TD，hj會由于沒收到申請消息而發(fā)出Master節(jié)點(diǎn)申請，因此其他節(jié)點(diǎn)最多等待TD即可收到申請消息。這里注意申請節(jié)點(diǎn)發(fā)送消息的順序，應(yīng)該與SN的順序相反，這樣，每次申請節(jié)點(diǎn)失效后，下一個申請節(jié)點(diǎn)可以在最短的時(shí)間內(nèi)發(fā)出申請。例如：假設(shè)排序后的節(jié)點(diǎn)按SN順序?yàn)閔1,h2,…,hl，申請節(jié)點(diǎn)為h1，被申請節(jié)點(diǎn)總數(shù)為l-1，則h1發(fā)送申請消息的順序?yàn)閔l-1,hl-2,…,h2，h1如果在發(fā)送完給hk(2j則SNi>SNj，因此其余節(jié)點(diǎn)能在最短的時(shí)間內(nèi)獲得申請消息。

另一種情況是所有被申請節(jié)點(diǎn)都收到了申請消息后，申請節(jié)點(diǎn)失效，在這種情況下，由于各個節(jié)點(diǎn)都承認(rèn)了申請節(jié)點(diǎn)為Master節(jié)點(diǎn)，因此可以按照針對Master節(jié)點(diǎn)的超時(shí)機(jī)制進(jìn)行處理，超時(shí)時(shí)限可以按照式(8)進(jìn)行設(shè)定。由于排序越靠后的節(jié)點(diǎn)越先得到申請消息，因此如果靠后的節(jié)點(diǎn)由于超時(shí)設(shè)置太小而超時(shí)的話，則會發(fā)起申請，但是該申請消息不會被其他節(jié)點(diǎn)所接受，于是申請節(jié)點(diǎn)會繼續(xù)等待下一個超時(shí)周期。

3.2DSA-M算法描述

DSA-M的算法描述如下所示：

算法1：DSA-M算法。

1:ON no MAIN_DETECT message from MainNode forTme=

2:SCSSMN←SCSSMN-hm;SNj←Sequence Number ofhjinSCSSMN;

3:ON no MAIN_REQUEST message from any Node forTD=(SNj-1)×MDT then

4:SendRequest(hm,MAIN_REQUEST);

5:fori=SNldown to SN1do //hi∈SCSSMN={h1,h2,…,hl}

6:ifi<>SNjthen SendRequest(hi,MAIN_REQUEST);

7:SetTimer;

8:ON ReceiveFromCSSMN(hi,MAIN_AFFIRMATIVE) then OK_COUNT++;

9:if(OK_COUNT=SCSSMN.Count-1)or(Timer>MDT) then

10:SetMainNode(hi);

11:StartDetect;

12:ON ReceiveFromCSSMN(hi,MAIN_NEGATIVE) then ResetToStep4;

13:ON ReceiveFromCSSMN(hi,MAIN_REQUEST) then

14:ifSNi≤SNjthen

15:SendResponse(hi,MAIN_AFFIRMATIVE);

16:SetMainNode(hi);

17:ResetToStep1;

18:else SendResponse(hi,MAIN_NEGATIVE);

19:ON receive MAIN_DETECT message from MasterNodehithen

20:SendResponse(hi,MAIN_DETECT_RESPONSE);

21:ResetToStep1;

22:ON receive MAIN_REQUEST message from other Node then//hm

23:SendResponse(hi,MAIN_NEGATIVE);

算法1中假設(shè)當(dāng)前Master節(jié)點(diǎn)為hm，當(dāng)前HCSS管理節(jié)點(diǎn)為hj。算法將管理節(jié)點(diǎn)之間的消息分為五類，分別是：

(1)MAIN_DETECTMaster：節(jié)點(diǎn)對其余HCSS管理節(jié)點(diǎn)的故障檢測消息；

(2)MAIN_DETECT_RESPONSE：HCSS管理節(jié)點(diǎn)對故障檢測的響應(yīng)消息；

(3)MAIN_REQUEST：某個HCSS管理節(jié)點(diǎn)申請成為Master節(jié)點(diǎn)的申請消息；

(4)MAIN_AFFIRMATIVE：某個被申請節(jié)點(diǎn)同意申請節(jié)點(diǎn)的Master節(jié)點(diǎn)申請消息；

(5)MAIN_NEGATIVE：某個被申請節(jié)點(diǎn)不同意申請節(jié)點(diǎn)的Master節(jié)點(diǎn)申請消息。

第1行表示一旦任意一個HCSS管理節(jié)點(diǎn)hj(非Master節(jié)點(diǎn))超過Tme都沒有收到來自Master節(jié)點(diǎn)hm的消息，則啟動2～21行的算法任務(wù)。

第2行表示在SCSSMN中去除hm進(jìn)行重新排序，得到每個節(jié)點(diǎn)的SN。

第3～12行表示hj超過TD仍然未收到來自其他HCSS管理節(jié)點(diǎn)的申請消息MAIN_REQUEST，而執(zhí)行的算法任務(wù)。

第4行表示首先給hm發(fā)送申請消息MAIN_REQUEST，防止對Master節(jié)點(diǎn)的誤判造成系統(tǒng)中存在多個Master節(jié)點(diǎn)的情況。

第5～6行表示hj按照SN倒排的順序?qū)ζ渌鸋CSS管理節(jié)點(diǎn)發(fā)出申請消息MAIN_REQUEST。

第7行表示發(fā)送完消息即設(shè)定一個定時(shí)器，用于檢測對申請消息響應(yīng)的超時(shí)。

第8行表示hj發(fā)出申請消息后收到了某個HCSS管理節(jié)點(diǎn)hi的同意消息MAIN_AFFIRMATIVE，此時(shí)hj將計(jì)數(shù)器加1，用于統(tǒng)計(jì)收到的同意消息數(shù)；第9～11行表示如果hj收到的同意消息數(shù)等于被申請節(jié)點(diǎn)數(shù)，或者等待同意申請消息超時(shí)，便置自己為Master節(jié)點(diǎn)，同時(shí)開始故障檢測。

第12行表示如果hj收到某個HCSS管理節(jié)點(diǎn)hi的不同意消息MAIN_NEGATIVE，則hj重置本地定時(shí)器，恢復(fù)到第4步的初始狀態(tài)，即剛發(fā)現(xiàn)hm失效的狀態(tài)，繼續(xù)等待TD，ResetToStep4函數(shù)負(fù)責(zé)狀態(tài)的重置工作。需要注意的是，一旦hj的狀態(tài)被重置，則它不會再處理任何MAIN_AFFIRMATIVE或者M(jìn)AIN_NEGATIVE消息。

第13行表示hj收到來自hi的申請消息MAIN_REQUEST，第14～18行表示對消息中hi的序號SNi進(jìn)行判斷，如果SNi≤SNj，表示hi滿足申請條件(優(yōu)先級條件)，hj便使用同意申請消息MAIN_AFFIRMATIVE響應(yīng)hi，同時(shí)置hi為Master節(jié)點(diǎn)，重置自身的狀態(tài)到發(fā)現(xiàn)Master節(jié)點(diǎn)超時(shí)時(shí)的狀態(tài)，進(jìn)入正常的運(yùn)行流程，ResetToStep1函數(shù)負(fù)責(zé)重置處理；如果SNi>SNj，則表示hi不滿足申請條件(優(yōu)先級條件)，hj便使用不同意申請消息MAIN_NEGATIVE響應(yīng)hi。

第19～21行表示hj收到來自Master節(jié)點(diǎn)的故障檢測消息，則立即響應(yīng)MAIN_DETECT_RESPONSE消息，并重置自身的狀態(tài)到發(fā)現(xiàn)Master節(jié)點(diǎn)超時(shí)時(shí)的狀態(tài)，進(jìn)入正常的運(yùn)行流程。

第22～23行是Master節(jié)點(diǎn)hm算法，這里表示如果由于網(wǎng)絡(luò)狀態(tài)不穩(wěn)定或者h(yuǎn)m過載，造成hj的誤判，則hm響應(yīng)不同意申請消息MAIN_NEGATIVE。

該算法的優(yōu)點(diǎn)在于：

(1)無需實(shí)時(shí)獲取各個HCSS管理節(jié)點(diǎn)的狀態(tài)，由于Master節(jié)點(diǎn)失效，狀態(tài)檢測結(jié)果可能會不一致，采用序號的方式進(jìn)行Master節(jié)點(diǎn)申請計(jì)算工作，能夠在HCSS管理節(jié)點(diǎn)狀態(tài)不一致的情況下完成申請，并正確運(yùn)行；

(2)采用序號的方式進(jìn)行申請優(yōu)先級計(jì)算，避免了不必要和過多的申請消息，申請過程中任何HCSS管理節(jié)點(diǎn)失效，算法依然能夠保證正確性；

(3)Master節(jié)點(diǎn)申請和接管對于每個節(jié)點(diǎn)只需1次往返消息交互，消息代價(jià)很小，復(fù)雜度為O(N)，N為HCSS管理節(jié)點(diǎn)數(shù)；

(4)可擴(kuò)展性好，當(dāng)HCSS管理節(jié)點(diǎn)增多，增加的消息量為常數(shù)，與節(jié)點(diǎn)數(shù)目無關(guān)；

(5)正常情況下，Master節(jié)點(diǎn)失效后，經(jīng)過一個故障檢測周期加上網(wǎng)絡(luò)時(shí)延的時(shí)間，即可完成接管，不論網(wǎng)絡(luò)條件如何，都能自動進(jìn)行恢復(fù)，保證故障檢測的有效性。

因此，DSA-M算法在Master節(jié)點(diǎn)處于狀態(tài)hj并出現(xiàn)故障的情況下，保證了系統(tǒng)的數(shù)據(jù)可靠性。

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

實(shí)驗(yàn)采用5個HCSS管理節(jié)點(diǎn)，其中5號節(jié)點(diǎn)作為初始Master節(jié)點(diǎn)，在5個節(jié)點(diǎn)上運(yùn)行DSA-M算法，測試當(dāng)Master節(jié)點(diǎn)失效時(shí)，其他HCSS管理節(jié)點(diǎn)申請Master節(jié)點(diǎn)的性能。

測試中，故障檢測超時(shí)取800 ms和200 ms，故障檢測周期為1 000 ms，初始故障檢測Master節(jié)點(diǎn)編號為5，故障檢測Master節(jié)點(diǎn)申請回執(zhí)超時(shí)為100 ms，測試進(jìn)行100次。

測試過程中，使HCSS管理節(jié)點(diǎn)5(故障檢測Master節(jié)點(diǎn))停止響應(yīng)任何請求(模擬崩潰故障，即失效)，Master節(jié)點(diǎn)失效的時(shí)刻是隨機(jī)的，記錄Master節(jié)點(diǎn)失效的時(shí)刻t1與其他HCSS管理節(jié)點(diǎn)申請Master節(jié)點(diǎn)成功的時(shí)刻t2之差：Δt=t2-t1(申請時(shí)間)，用于衡量Master節(jié)點(diǎn)失效狀態(tài)下其余節(jié)點(diǎn)申請Master節(jié)點(diǎn)的性能。

測試結(jié)果如圖1所示。

(10)

(11)

(12)

為了體現(xiàn)測試的全面性，考察當(dāng)多個節(jié)點(diǎn)失效時(shí)Master節(jié)點(diǎn)申請的性能，失效節(jié)點(diǎn)組合按照(5)、(5，1)、(5，1，2)，(5，1，2，3)四種，每一種組合內(nèi)的節(jié)點(diǎn)都是同時(shí)失效，由DSA-M算法描述可知，申請的優(yōu)先級是以節(jié)點(diǎn)序號計(jì)算，只要排序靠前的節(jié)點(diǎn)沒有失效，排序靠后的節(jié)點(diǎn)將無法完成申請，因此以上四種組合使得每個節(jié)點(diǎn)(1，2，3，4)都有機(jī)會申請Master節(jié)點(diǎn)，是最有代表性的一種組合。

此外，由圖1的分析可知，申請時(shí)間的變化依賴于Master節(jié)點(diǎn)失效時(shí)刻在故障檢測周期內(nèi)的分布，因此為了討論方便，假設(shè)Master節(jié)點(diǎn)失效時(shí)刻按照間隔100 ms的規(guī)律均勻變化，考察一個檢測周期內(nèi)HCSS管理節(jié)點(diǎn)申請Master節(jié)點(diǎn)時(shí)間與失效節(jié)點(diǎn)組合之間的關(guān)系，如圖2所示。

圖2 多個節(jié)點(diǎn)失效時(shí)申請Master節(jié)點(diǎn)成功時(shí)間(失效時(shí)刻均勻分布)

從圖2可以看出，節(jié)點(diǎn)失效的不同組合所對應(yīng)的Master節(jié)點(diǎn)申請時(shí)間并不相同，這種差異主要來自于Master節(jié)點(diǎn)申請優(yōu)先級的控制。由DSA-M算法描述可知，每個節(jié)點(diǎn)發(fā)現(xiàn)Master節(jié)點(diǎn)失效后，將延遲時(shí)間TD發(fā)送Master節(jié)點(diǎn)申請消息，因此排序越靠后的節(jié)點(diǎn)發(fā)起申請的延遲就越大，而延遲的時(shí)間和節(jié)點(diǎn)的序號以及最大往返時(shí)延(MDT)相關(guān)，測試中MDT=100 ms。圖2中Master節(jié)點(diǎn)失效后，可以申請成為Master節(jié)點(diǎn)的HCSS管理節(jié)點(diǎn)有4個，因此當(dāng)前n個節(jié)點(diǎn)都失效時(shí)，最大等待時(shí)延Twait(申請開始時(shí)間)和申請完成時(shí)間Tfinish分別為：

Twait=n×MDT

(13)

(14)

式(14)因?yàn)橛卸鄠€節(jié)點(diǎn)失效，必然有節(jié)點(diǎn)會響應(yīng)申請消息超時(shí)，因此會多一個超時(shí)時(shí)間MDT，這也是圖2中多于1個節(jié)點(diǎn)失效時(shí)的申請時(shí)間要比只有Master節(jié)點(diǎn)失效時(shí)的申請時(shí)間普遍多100 ms左右的原因。因此在多個節(jié)點(diǎn)失效的情況下，申請時(shí)間可以使用式(15)計(jì)算。

(15)

其中，n表示從1號節(jié)點(diǎn)開始，連續(xù)失效的節(jié)點(diǎn)個數(shù)。

因此在多個節(jié)點(diǎn)失效的情況下，申請時(shí)間的變化范圍為：

(16)

可以看出，通過控制故障檢測周期T，便能夠使得DSA-M算法的性能保持在相對穩(wěn)定的區(qū)間內(nèi)，隨失效時(shí)刻的適應(yīng)性也比較強(qiáng)。

5 結(jié)束語

存儲服務(wù)可用性是衡量云存儲系統(tǒng)好壞的重要指標(biāo)之一，當(dāng)云存儲系統(tǒng)中管理節(jié)點(diǎn)出現(xiàn)故障時(shí)，如何快速恢復(fù)系統(tǒng)運(yùn)行，確保存儲服務(wù)的可用性是HCSS需要解決的關(guān)鍵問題之一。針對HCSS中Master節(jié)點(diǎn)失效導(dǎo)致存儲服務(wù)不可用的問題，建立了HCSS中管理節(jié)點(diǎn)故障影響分析模型，根據(jù)模型分析結(jié)果，提出了DSA-M算法。當(dāng)Master節(jié)點(diǎn)發(fā)生故障時(shí)，以多個HCSS管理節(jié)點(diǎn)之間并行工作為基礎(chǔ)，通過基于序號的優(yōu)先級策略實(shí)現(xiàn)了Master節(jié)點(diǎn)的動態(tài)申請和切換，保證了云存儲服務(wù)的高可用性。

測試結(jié)果表明，DSA-M算法能夠在Master節(jié)點(diǎn)發(fā)生故障時(shí)自動進(jìn)行Master節(jié)點(diǎn)切換和接管，恢復(fù)云存儲服務(wù)的運(yùn)行。通過控制故障檢測周期，能夠使DSA-M算法的性能保持在相對穩(wěn)定的區(qū)間內(nèi)，隨失效時(shí)刻的適應(yīng)性也比較強(qiáng)。

[1] 劉 鵬.云計(jì)算[M].第3版.北京:電子工業(yè)出版社,2015.

[2] 馬瑋駿,吳海佳,劉 鵬.MassCloud云存儲系統(tǒng)構(gòu)架及可靠性機(jī)制[J].河海大學(xué)學(xué)報(bào):自然科學(xué)版,2011,39(3):348-354.

[3] Chekam T T,Zhai E,Li Z,et al.On the synchronization bottleneck of OpenStack swift-like cloud storage systems[C]//IEEE international conference on computer communications.San Francisco:IEEE,2016:135-144.

[4] Kamath A,Jaiswal A,Dive K.From idea to reality:Google file system[J].International Journal of Computer Applications,2014,103(9):8-10.

[5] Wu C H,Hsu P.Cost-effective and reliable cloud storage for big data[C]//ASE big data & social informatics 2015.New York:ACM,2015.

[6] Wei Y,Yong W F.A cost-effective and reliable cloud storage[C]//2014 IEEE 7th international conference on cloud computing.Anchorage:IEEE,2014:938-939.

[7] Faragardi H R,Shojaee R,Tabani H,et al.An analytical model to evaluate reliability of cloud computing systems in the presence of QoS requirements[C]//International conference on computer and information science.Niigata,Japan:[s.n.],2013:315-321.

[8] Joolahluk J,Wen Y F.Reliable and available data replication planning for cloud storage[C]//IEEE international conference on advanced information networking and applications.Barcelona,Spain:IEEE,2013:772-779.

[9] 趙 暢. 云存儲系統(tǒng)可靠性分析[D].天津：南開大學(xué),2014.

[10] Song J,Deng J H.NOVA:a P2P-cloud VoD system for IPTV with collaborative pre-deployment module based on recommendation scheme[C]//International conference on materials science and information technology.Nanjing,China:[s.n.],2013:1566-1570.

[11] Chakareski J.Cost and profit driven cloud-P2P interaction[J].Peer-to-Peer Networking and Applications,2015,8(2):244-259.

[12] Babaolu O,Marzolla M,Trambrini M.Design and implementation of a P2P cloud system[C]//Proceedings of the ACM symposium on applied computing.Trento,Italy:ACM,2012:412-417.

[13] 李小兵,許胤龍,林一施,等.X再生碼:一類適用于云存儲的準(zhǔn)確修復(fù)編碼[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(8):241-244.

[14] 王 帥,常朝穩(wěn),王禹同,等.面向多云盤的N+i模式的編碼冗余存儲機(jī)制[J].小型微型計(jì)算機(jī)系統(tǒng),2016,37(2):236-240.

[15] 吳禮樂.基于雙活容災(zāi)存儲技術(shù)的云計(jì)算數(shù)據(jù)中心的設(shè)計(jì)及應(yīng)用[J].電子設(shè)計(jì)工程,2015,23(6):190-192.

[16] 馬瑋駿,王 強(qiáng),何曉暉,等.一種基于策略的云存儲系統(tǒng)故障管理方法[J].軟件工程,2016,19(6):4-7.

Dynamic Switching Algorithm for Master Node in Huge Cloud Storage System

MA Wei-jun，WANG Qiang，HE Xiao-hui，F(xiàn)ENG Jing，MA Qiang

(PLA University of Science and Technology,Nanjing 211101,China)

In order to solve the unavailable problem of storage service on account of the Master node fault in huge cloud storage system,an analysis model for fault effect of management node has been constructed,which takes storage service availability,data reliability and data availability as the analysis target.Three-dimensional element has been employed in the analysis model such as fault status,real-time status and restrictive condition so as to provide an effective method for fault recovery.Based on the analysis model,a dynamic switching algorithm for master node based on message called DSA-M has been presented,in which it implements the dynamic application and switching of Master node by PRI policy based on sequence number and ensures the high availability.Test results show that DSA-M has provided management nodes auto switching and taken over while master node is breakdown and high storage service availability.The performance of DRA-M also can be stable in relative region by reasonable control of fault detection cycle and DRA-M also has strong adaptability for crush moment.

cloud storage system;Master node;fault detection;metadata;dynamic switching

2016-05-09

：2016-08-10 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間

時(shí)間：2017-07-05

國家自然科學(xué)基金資助項(xiàng)目(61371119)

馬瑋駿(1980-)，男，講師，博士，研究方向?yàn)榫W(wǎng)絡(luò)管理、網(wǎng)格計(jì)算、分布式存儲。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170705.1649.006.html

TP301.6

:A

:1673-629X(2017)09-0085-07

10.3969/j.issn.1673-629X.2017.09.019