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

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

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

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

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

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

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

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

1 概 述

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

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

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

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

為此，圍繞HCSS中Master節(jié)點(diǎn)故障失效時(shí)持續(xù)提供云存儲(chǔ)服務(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é)為云存儲(chǔ)客戶端提供元數(shù)據(jù)服務(wù)，同時(shí)需要檢測(cè)各個(gè)存儲(chǔ)節(jié)點(diǎn)的工作狀態(tài)。通常HCSS中有多個(gè)管理節(jié)點(diǎn)，其中Master節(jié)點(diǎn)負(fù)責(zé)所有管理節(jié)點(diǎn)的故障檢測(cè)。使用故障管理對(duì)象、故障的限制條件和表現(xiàn)以及故障管理對(duì)象的狀態(tài)三個(gè)維度來表示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í)刻，存儲(chǔ)服務(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對(duì)存儲(chǔ)服務(wù)可用性的影響記為：

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

(1)

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

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

(2)

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

同理，設(shè)fsm→DR和fsm→AD分別表示故障sm對(duì)系統(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)

為了討論簡(jiǎn)便，下面對(duì)影響函數(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)表示將故障影響簡(jiǎn)化為0和1兩種取值，0表示沒有影響，1表示有影響，這種簡(jiǎn)化對(duì)于界定故障的檢測(cè)范圍、恢復(fù)范圍以及恢復(fù)時(shí)效是很有意義的。對(duì)于故障影響為0的故障，可以檢測(cè)但不一定要及時(shí)恢復(fù)；對(duì)于故障影響為1的故障，是必須要進(jìn)行檢測(cè)和及時(shí)恢復(fù)的。

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

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

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

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

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

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

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

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

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

3.1.1 超時(shí)判定策略

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

(8)

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

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

3.1.2 優(yōu)先級(jí)策略

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

TD=(SNj-1)×MDT

(9)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第12行表示如果hj收到某個(gè)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)被重置，則它不會(huì)再處理任何MAIN_AFFIRMATIVE或者M(jìn)AIN_NEGATIVE消息。

第13行表示hj收到來自hi的申請(qǐng)消息MAIN_REQUEST，第14～18行表示對(duì)消息中hi的序號(hào)SNi進(jìn)行判斷，如果SNi≤SNj，表示hi滿足申請(qǐng)條件(優(yōu)先級(jí)條件)，hj便使用同意申請(qǐng)消息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不滿足申請(qǐng)條件(優(yōu)先級(jí)條件)，hj便使用不同意申請(qǐng)消息MAIN_NEGATIVE響應(yīng)hi。

第19～21行表示hj收到來自Master節(jié)點(diǎn)的故障檢測(cè)消息，則立即響應(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)不同意申請(qǐng)消息MAIN_NEGATIVE。

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

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

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

(3)Master節(jié)點(diǎn)申請(qǐng)和接管對(duì)于每個(gè)節(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)過一個(gè)故障檢測(cè)周期加上網(wǎng)絡(luò)時(shí)延的時(shí)間，即可完成接管，不論網(wǎng)絡(luò)條件如何，都能自動(dòng)進(jìn)行恢復(fù)，保證故障檢測(cè)的有效性。

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

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

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

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

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

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

(10)

(11)

(12)

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

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

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

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

Twait=n×MDT

(13)

(14)

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

(15)

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

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

(16)

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

5 結(jié)束語

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

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

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

[2] 馬瑋駿,吳海佳,劉 鵬.MassCloud云存儲(chǔ)系統(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] 趙 暢. 云存儲(chǔ)系統(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再生碼:一類適用于云存儲(chǔ)的準(zhǔn)確修復(fù)編碼[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(8):241-244.

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

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

[16] 馬瑋駿,王 強(qiáng),何曉暉,等.一種基于策略的云存儲(chǔ)系統(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

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

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

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