卞強(qiáng) 劉永成 苗信凱 吳海強(qiáng)
(中國(guó)電子科技集團(tuán)公司第十五研究所 北京市 100083)
近年來(lái)隨著網(wǎng)絡(luò)應(yīng)用的不斷發(fā)展,越來(lái)越多的分布式應(yīng)用系統(tǒng)得到了大規(guī)模的應(yīng)用。每個(gè)節(jié)點(diǎn)既是客戶端也是服務(wù)端,在整個(gè)網(wǎng)絡(luò)范圍內(nèi)形成一個(gè)無(wú)中心的分布式應(yīng)用系統(tǒng)。這種系統(tǒng)帶來(lái)的最大的好處是,單個(gè)節(jié)點(diǎn)的失效不會(huì)對(duì)整個(gè)應(yīng)用造成致命的影響。然而,隨著系統(tǒng)規(guī)模的逐漸擴(kuò)大,各個(gè)節(jié)點(diǎn)組成的網(wǎng)絡(luò)拓?fù)渲饾u復(fù)雜起來(lái)。從某個(gè)節(jié)點(diǎn)的視角來(lái)看,很難在某個(gè)時(shí)刻實(shí)時(shí)掌握整個(gè)分布式系統(tǒng)的網(wǎng)絡(luò)拓?fù)?,從而?duì)該節(jié)點(diǎn)向其他節(jié)點(diǎn)的數(shù)據(jù)同步和其他通信造成困難。流言協(xié)議在分布式系統(tǒng)的各個(gè)方面的應(yīng)用都得到了研究,Tao Yu 等人[1]進(jìn)行了基于流言協(xié)議的分布式共識(shí)評(píng)估和控制的研究,提出了疊加共識(shí)策略的本地類龍伯格觀測(cè)器,驗(yàn)證了通過(guò)流言協(xié)議進(jìn)行分布式共識(shí)評(píng)估的可行性。Pengfei Ren 等人[2]研究了基于流言的分布式學(xué)習(xí)問(wèn)題,在隨機(jī)加入網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)間進(jìn)行數(shù)據(jù)隨機(jī)路由,最終在所有節(jié)點(diǎn)間形成構(gòu)建相同的理論學(xué)習(xí)模型,通過(guò)這項(xiàng)研究驗(yàn)證了基于流言協(xié)議的數(shù)據(jù)分發(fā)的穩(wěn)定性。Istvan Hegedus等人[3]對(duì)基于流言的機(jī)器學(xué)習(xí)和聯(lián)邦機(jī)器學(xué)習(xí)進(jìn)行了比較,經(jīng)過(guò)實(shí)際試驗(yàn)結(jié)果發(fā)現(xiàn),在實(shí)際的網(wǎng)絡(luò)環(huán)境中,在機(jī)器學(xué)習(xí)中通過(guò)流言進(jìn)行數(shù)據(jù)和策略的分發(fā)以及進(jìn)行學(xué)習(xí)結(jié)果的匯聚要比聯(lián)邦機(jī)器學(xué)習(xí)更有效,驗(yàn)證了流言協(xié)議在分布式環(huán)境下進(jìn)行數(shù)據(jù)分發(fā)和匯聚的有效性。Mauro Franceschelli 等人[4]在異構(gòu)隨機(jī)網(wǎng)絡(luò)中進(jìn)行了有質(zhì)量保證的任務(wù)分發(fā)研究,探討了在任務(wù)分發(fā)中的收斂特性,以及對(duì)各個(gè)節(jié)點(diǎn)組成的無(wú)向圖的邊選擇方法,以及最終的流言通信的終止。通過(guò)數(shù)值模擬驗(yàn)證了相關(guān)理論的正確性,整個(gè)通信過(guò)程都是在保證任務(wù)分發(fā)性能的前提下進(jìn)行的。
流言協(xié)議又稱流行病協(xié)議,是一種去中心化的分布式協(xié)議,用于實(shí)現(xiàn)分布式節(jié)點(diǎn)間的信息交換,一般用于大型的無(wú)中心化網(wǎng)絡(luò)環(huán)境中,并且假設(shè)網(wǎng)絡(luò)環(huán)境不太穩(wěn)定。流言協(xié)議是分布式系統(tǒng)中被廣泛使用的一種最終一致性協(xié)議,可以使用流言協(xié)議來(lái)實(shí)現(xiàn)分布式網(wǎng)絡(luò)中所有節(jié)點(diǎn)數(shù)據(jù)的一致性同步。流言協(xié)議最初是由施樂(lè)公司帕洛阿爾托研究中心的研究員Alan Demers 于1988年提出的[5]。最初用于分布式數(shù)據(jù)庫(kù)中各節(jié)點(diǎn)間進(jìn)行數(shù)據(jù)同步,后被廣泛用于數(shù)據(jù)庫(kù)復(fù)制、消息分發(fā)、大型集群的成員節(jié)點(diǎn)身份確認(rèn)、大型集群的節(jié)點(diǎn)故障探測(cè)等[6~8]。
對(duì)于具有N 個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò),流言協(xié)議發(fā)送消息的收斂時(shí)間為O(logN)。每個(gè)節(jié)點(diǎn)僅發(fā)送固定數(shù)量的消息,并且與網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目無(wú)關(guān),因此整個(gè)網(wǎng)絡(luò)的收斂時(shí)間不會(huì)隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增多而增大。在消息傳送過(guò)程中,發(fā)送節(jié)點(diǎn)不會(huì)等待被發(fā)送消息的應(yīng)答消息到達(dá)后才進(jìn)行其他工作,允許存在一定節(jié)點(diǎn)發(fā)送的失敗,但需要保證不小于扇出系數(shù)的發(fā)送成功量。在整個(gè)發(fā)送過(guò)程中,逐漸形成按照指數(shù)遞增的節(jié)點(diǎn)同時(shí)向外發(fā)送消息,因此系統(tǒng)可以輕松擴(kuò)展到數(shù)百萬(wàn)個(gè)節(jié)點(diǎn)。流言協(xié)議是去中心化的應(yīng)用層網(wǎng)絡(luò)協(xié)議,所有節(jié)點(diǎn)都是地位對(duì)等的,沒(méi)有特殊的節(jié)點(diǎn),網(wǎng)絡(luò)中任何節(jié)點(diǎn)的重啟或者宕機(jī)都不會(huì)影響流言協(xié)議的運(yùn)行,整個(gè)系統(tǒng)具有很要的健壯性。系統(tǒng)中任何一個(gè)節(jié)點(diǎn)都可以隨時(shí)加入或離開(kāi),從整個(gè)系統(tǒng)的角度來(lái)看這些節(jié)點(diǎn)的加入和離開(kāi)不會(huì)影響系統(tǒng)的整體服務(wù)質(zhì)量。在大規(guī)模分布式系統(tǒng)中,流言協(xié)議通過(guò)消息的指數(shù)級(jí)快速傳播,將新消息快速地發(fā)送到全局的每一個(gè)節(jié)點(diǎn),在有限的時(shí)間內(nèi)能夠做到所有節(jié)點(diǎn)都擁有最新的數(shù)據(jù)。為了避免整個(gè)系統(tǒng)的廣播風(fēng)暴,使消息傳播能夠最終停止,流言協(xié)議采用了SIR 模型[10],通過(guò)“已刪除”狀態(tài)來(lái)標(biāo)記已經(jīng)處理過(guò)的消息,當(dāng)節(jié)點(diǎn)收到的消息處于“已刪除”時(shí),該節(jié)點(diǎn)將不再傳播該消息。根據(jù) Ganesh 等人的研究[6]發(fā)現(xiàn),在一個(gè)擁有N 個(gè)節(jié)點(diǎn)的分布式網(wǎng)絡(luò)系統(tǒng)中進(jìn)行消息發(fā)送,若每個(gè)節(jié)點(diǎn)平均與logN+c個(gè)節(jié)點(diǎn)發(fā)送消息,那么原始消息發(fā)送至系統(tǒng)所有節(jié)點(diǎn)的概率將收斂至exp(-e-c)。這說(shuō)明如果每個(gè)節(jié)點(diǎn)對(duì)外散播流言消息的扇出系數(shù)大于logN,則系統(tǒng)中所有節(jié)點(diǎn)都能夠收到原始消息的概率趨近于1,反之則趨近于0。Ganesh 等人的研究成果從理論上找到了基于流言機(jī)制進(jìn)行消息隨機(jī)散播的可靠性條件。
覆蓋網(wǎng)是一個(gè)構(gòu)建在物理網(wǎng)絡(luò)之上的應(yīng)用層虛擬網(wǎng)絡(luò),Ranieri Baraglia 等人[11]通過(guò)覆蓋網(wǎng)構(gòu)建了內(nèi)容推薦系統(tǒng)。在覆蓋網(wǎng)中,各個(gè)節(jié)點(diǎn)是對(duì)等的,無(wú)中心的,隨時(shí)可以加入網(wǎng)絡(luò)和退出網(wǎng)絡(luò),其形態(tài)具有動(dòng)態(tài)性。為了掌握變化中的覆蓋網(wǎng)的形態(tài),需要一種分布式的穩(wěn)健的拓?fù)涔芾矸椒?。傳統(tǒng)的泛洪協(xié)議具有簡(jiǎn)單和可靠的特點(diǎn),但隨著網(wǎng)絡(luò)規(guī)模的增長(zhǎng)其收斂時(shí)間將會(huì)增大?;诹餮詤f(xié)議的拓?fù)涔芾矸椒ɡ昧餮缘奶攸c(diǎn)在覆蓋網(wǎng)中分發(fā)信息,其分發(fā)機(jī)制采用概率模型。每次進(jìn)行消息分發(fā)時(shí),按照扇出系數(shù)選擇部分節(jié)點(diǎn)進(jìn)行分發(fā),接收節(jié)點(diǎn)收到消息后,將其已知的部分網(wǎng)絡(luò)拓?fù)浒l(fā)送給發(fā)送節(jié)點(diǎn),同時(shí)又作為消息發(fā)送者繼續(xù)進(jìn)行消息分發(fā)。這樣,最終在每個(gè)節(jié)點(diǎn)形成一個(gè)動(dòng)態(tài)的全局網(wǎng)絡(luò)拓?fù)?。通過(guò)調(diào)整扇出系數(shù)和發(fā)送消息的時(shí)間間隔,實(shí)現(xiàn)對(duì)整個(gè)分布式系統(tǒng)穩(wěn)定性的提升。每個(gè)節(jié)點(diǎn)可以自由加入和退出覆蓋網(wǎng),在新節(jié)點(diǎn)加入覆蓋網(wǎng)時(shí),需要至少配置一個(gè)已知節(jié)點(diǎn),向已知節(jié)點(diǎn)發(fā)送上線消息。節(jié)點(diǎn)退出覆蓋網(wǎng)有兩種情形,一種是節(jié)點(diǎn)正常退出,在退出時(shí)向其他節(jié)點(diǎn)發(fā)送下線消息,這種情形的處理方式與節(jié)點(diǎn)上線類似;另外一種是異常退出,例如,機(jī)器宕機(jī)、服務(wù)奔潰或底層物理網(wǎng)絡(luò)產(chǎn)生故障,以下對(duì)整個(gè)通信過(guò)程進(jìn)行描述。
(1)新節(jié)點(diǎn)加入。新節(jié)點(diǎn)m 加入分布式網(wǎng)絡(luò)系統(tǒng)時(shí),節(jié)點(diǎn)m向系統(tǒng)中至少f(f 稱為扇出系數(shù))個(gè)節(jié)點(diǎn)(假設(shè)節(jié)點(diǎn)n)提交注冊(cè)請(qǐng)求消息msg_r(m)。節(jié)點(diǎn)n 收到節(jié)點(diǎn)m 的注冊(cè)請(qǐng)求消息msg_r(m)時(shí),首先將節(jié)點(diǎn)m 信息添加到自己的局部網(wǎng)絡(luò)視圖V(n)中,生成V(n+m),同時(shí)發(fā)送一個(gè)自己已知的局部視圖V(n)發(fā)送給節(jié)點(diǎn)m。然后將注冊(cè)申請(qǐng)的節(jié)點(diǎn)信息N(m)轉(zhuǎn)發(fā)給其本地視圖中的每一個(gè)成員,同時(shí)生成c(稱為扇出系數(shù))個(gè)注冊(cè)請(qǐng)求信息,并將其隨機(jī)轉(zhuǎn)發(fā)至本地網(wǎng)絡(luò)拓?fù)湟晥D中的c 個(gè)成員(n1,n2,…,nc)。c 是一個(gè)控制參數(shù),主要用來(lái)增強(qiáng)系統(tǒng)的容錯(cuò)性能,使新節(jié)點(diǎn)的信息能在系統(tǒng)中多個(gè)節(jié)點(diǎn)的局部視圖中存在。當(dāng)網(wǎng)絡(luò)系統(tǒng)中某個(gè)節(jié)點(diǎn)(n1,n2,…,nc)收到轉(zhuǎn)發(fā)來(lái)的注冊(cè)請(qǐng)求消息時(shí),它會(huì)以一定的概率p 接受這個(gè)注冊(cè)請(qǐng)求,概率p 的大小依賴于節(jié)點(diǎn)本地視圖的大小,然后將注冊(cè)消息隨機(jī)從本地視圖V(nc)中的選擇c 個(gè)成員進(jìn)行轉(zhuǎn)發(fā)。
(2)節(jié)點(diǎn)正常退出。當(dāng)網(wǎng)絡(luò)系統(tǒng)中某個(gè)節(jié)點(diǎn)m 需退出系統(tǒng)時(shí),則在退出前向系統(tǒng)中至少一個(gè)節(jié)點(diǎn)(假設(shè)節(jié)點(diǎn)n)發(fā)布一個(gè)節(jié)點(diǎn)注銷流言消息msg_o(m),消息msg_o(m)首先廣播至節(jié)點(diǎn)n 的局部視圖V(n)中的c 個(gè)節(jié)點(diǎn)(n1,n2,…,nc)。當(dāng)網(wǎng)絡(luò)系統(tǒng)中的節(jié)點(diǎn)(n1,n2,…,nc)收到注銷流言信息msg_o(m)時(shí),若節(jié)點(diǎn)的局部視圖V(nc)中包含有發(fā)送注銷消息的節(jié)點(diǎn)信息N(m),則首先在局部視圖V(nc)中將其刪除,生成V(nc-m)。隨后將此注銷消息msg_o(m)隨機(jī)散播給其局部視圖中的其他節(jié)點(diǎn);若節(jié)點(diǎn)的局部視圖V(nc) 中不包含節(jié)點(diǎn)信息N(m),那么僅進(jìn)行消息的散播。在沒(méi)有網(wǎng)絡(luò)節(jié)點(diǎn)失效及網(wǎng)絡(luò)鏈路故障的情況下經(jīng)過(guò)一定輪次后,系統(tǒng)中每個(gè)節(jié)點(diǎn)都收到該注銷消息,保證了分布式系統(tǒng)中節(jié)點(diǎn)視圖的一致性。相關(guān)研究[12]表明,當(dāng)70%以上的節(jié)點(diǎn)退出后依然可以保證系統(tǒng)的連接性。
(3)節(jié)點(diǎn)異常退出。因網(wǎng)絡(luò)故障或服務(wù)宕機(jī)等其他原因?qū)е鹿?jié)點(diǎn)m 退出分布式網(wǎng)絡(luò)系統(tǒng)時(shí),其他節(jié)點(diǎn)無(wú)法收到其注銷消息。這就需要每個(gè)節(jié)點(diǎn)對(duì)其已知的網(wǎng)絡(luò)拓?fù)溥M(jìn)行心跳探測(cè),設(shè)定探測(cè)周期為T,T 的大小取決于對(duì)網(wǎng)絡(luò)拓?fù)鋵?shí)時(shí)性的要求。當(dāng)某個(gè)節(jié)點(diǎn)n通過(guò)心跳探測(cè)發(fā)現(xiàn)其局部視圖V(n)中的節(jié)點(diǎn)m 異常時(shí),則向其他節(jié)點(diǎn)發(fā)布一個(gè)異常退出流言消息msg_q(nm),經(jīng)其他至少x 個(gè)節(jié)點(diǎn)確認(rèn)后,則刪除其本地視圖V(n)中的節(jié)點(diǎn)m,更新為V(n-m)。x的值需根據(jù)網(wǎng)絡(luò)質(zhì)量q 以及使用覆蓋網(wǎng)拓?fù)涞钠渌麘?yīng)用對(duì)于覆蓋網(wǎng)拓?fù)淇煽啃砸髍 來(lái)設(shè)定,即x=f(q,r)。
當(dāng)節(jié)點(diǎn)出現(xiàn)異常退出時(shí),可能服務(wù)本身出現(xiàn)了問(wèn)題,也有可能是網(wǎng)絡(luò)出現(xiàn)了問(wèn)題,此時(shí)需要防止整個(gè)網(wǎng)絡(luò)發(fā)生腦裂。在覆蓋網(wǎng)拓?fù)涞墓芾碇?,由于每個(gè)節(jié)點(diǎn)只存儲(chǔ)局部拓?fù)湟晥D,且后續(xù)的數(shù)據(jù)同步需要依賴覆蓋網(wǎng)拓?fù)溥M(jìn)行,既便發(fā)生暫時(shí)性的腦裂,后續(xù)的持續(xù)探測(cè)和隨機(jī)的流言分發(fā)機(jī)制會(huì)重新探測(cè)到發(fā)生腦裂的局部節(jié)點(diǎn)。
(4)廣播風(fēng)暴的避免。在流言消息的分發(fā)過(guò)程中,為了保證消息發(fā)送的可靠性和傳播的時(shí)效性,一般會(huì)選擇扇出系數(shù)f>1,此時(shí)發(fā)送消息的節(jié)點(diǎn)數(shù)量呈指數(shù)級(jí)增長(zhǎng)。為避免形成覆蓋網(wǎng)廣播風(fēng)暴,通過(guò)對(duì)接收到的流言消息進(jìn)行標(biāo)記來(lái)阻斷消息的重復(fù)發(fā)送。以節(jié)點(diǎn)a、b、c、d、e 為例,如圖3 所示,節(jié)點(diǎn)a 向節(jié)點(diǎn)b 發(fā)送了消息msg。
節(jié)點(diǎn)b、d 的本地視圖為V(b)={a,c,d,e},V(d)={a,b,c,e},
假定扇出系數(shù)f=3。節(jié)點(diǎn)b 收到消息msg 后,將消息分發(fā)給其本地視圖V(b)中的節(jié)點(diǎn)a、c、d,節(jié)點(diǎn)a 已將msg 標(biāo)記為重復(fù)消息,將不再繼續(xù)分發(fā)流言。節(jié)點(diǎn)d 繼續(xù)分發(fā)流言,將消息分發(fā)給其本地視圖V(d)的節(jié)點(diǎn)b、c、e,節(jié)點(diǎn)b、c 已將msg 標(biāo)記為重復(fù)消息,將不再分發(fā)流言。
(5)防止惡意節(jié)點(diǎn)的攻擊。在分布式網(wǎng)絡(luò)系統(tǒng)中,各個(gè)節(jié)點(diǎn)之間的連接是松散的,并且不存在中心節(jié)點(diǎn),這種結(jié)構(gòu)容易被惡意節(jié)點(diǎn)攻擊,造成覆蓋網(wǎng)拓?fù)涞膿p壞。Anubhava 等人采用基于概率的流言模型,通過(guò)在每個(gè)節(jié)點(diǎn)引入控制表以及能力分發(fā)指數(shù)來(lái)實(shí)現(xiàn)對(duì)惡意節(jié)點(diǎn)的探測(cè)和分析,通過(guò)仿真驗(yàn)證分析取得了較好的結(jié)果。在一些分布式異構(gòu)網(wǎng)絡(luò)中,組建覆蓋網(wǎng)的各個(gè)節(jié)點(diǎn)所處的底層鏈路的不同物理介質(zhì)的穩(wěn)定性存在差異,同時(shí)骨干網(wǎng)絡(luò)和支線網(wǎng)絡(luò)其穩(wěn)定性也存在差異。在這種情況下,可以采用Anubhava 等人的基于概率的流言模型,對(duì)每一個(gè)節(jié)點(diǎn)i 被新加入節(jié)點(diǎn)的連接概率Pi進(jìn)行有傾向性的控制,即:
其中ηi 為節(jié)點(diǎn)的能力分發(fā)指數(shù),ki 為節(jié)點(diǎn)所擁有可連通的鄰居節(jié)點(diǎn)的數(shù)量L(t)為其所有的鄰居節(jié)點(diǎn)??梢愿鶕?jù)不同節(jié)點(diǎn)的網(wǎng)絡(luò)類型對(duì)α 和β 進(jìn)行調(diào)整,實(shí)現(xiàn)對(duì)惡意節(jié)點(diǎn)攻擊的防止。
綜上所述,通過(guò)流言協(xié)議進(jìn)行分布式網(wǎng)絡(luò)覆蓋網(wǎng)的拓?fù)涔芾?,可以管理新?jié)點(diǎn)的加入、退出。通過(guò)引入SIR 模型,解決了流言分發(fā)的網(wǎng)絡(luò)風(fēng)暴,在流言模型中引入能力分發(fā)指數(shù)概率模型,解決惡意節(jié)點(diǎn)的探測(cè)和分析,保證不會(huì)因惡意節(jié)點(diǎn)的擾動(dòng)對(duì)整個(gè)覆蓋網(wǎng)拓?fù)湓斐捎绊?。本文中每個(gè)節(jié)點(diǎn)只存儲(chǔ)覆蓋網(wǎng)的部分拓?fù)湟晥D,符合實(shí)際應(yīng)用場(chǎng)景中對(duì)覆蓋網(wǎng)的要求,同時(shí)也減小了拓?fù)渚S護(hù)過(guò)程中所帶來(lái)的網(wǎng)絡(luò)開(kāi)銷。從流言協(xié)議的理論模型分析了流言傳播的收斂時(shí)間和分布式網(wǎng)絡(luò)規(guī)模之間的關(guān)系,從理論上驗(yàn)證了對(duì)多達(dá)上千個(gè)節(jié)點(diǎn)的分布式網(wǎng)絡(luò)中運(yùn)用流言協(xié)議的可行性,后續(xù)還需通過(guò)數(shù)值模擬定量分析在實(shí)際網(wǎng)絡(luò)中流言協(xié)議對(duì)拓?fù)涔芾淼目煽啃?,尤其是?dāng)某些節(jié)點(diǎn)頻繁上下線時(shí)。