任海鵬,汪學(xué)文,方繼才
安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系,安徽蕪湖,241002
面向分布式流處理系統(tǒng)的故障檢測及容錯策略
任海鵬,汪學(xué)文,方繼才
安徽機(jī)電職業(yè)技術(shù)學(xué)院信息工程系,安徽蕪湖,241002
為解決智能手機(jī)主要依靠的客戶端-服務(wù)器計算模式所面臨的蜂窩網(wǎng)絡(luò)瓶頸問題,提出將智能手機(jī)作為分布式計算平臺,直接在手機(jī)上處理感應(yīng)數(shù)據(jù)的方法,設(shè)計一種可以直接在智能手機(jī)上運行的分布式流處理系統(tǒng)MobiStreams。研究在智能手機(jī)上部署DSPS系統(tǒng)所面臨的故障檢測及容錯策略問題,利用部署在美國的一項SignalGuru手機(jī)應(yīng)用進(jìn)行性能評估。仿真結(jié)果表明:從服務(wù)器平臺遷移到智能手機(jī)平臺有效解決了蜂窩網(wǎng)絡(luò)的瓶頸問題。與傳統(tǒng)基于服務(wù)器的DSPSs相比,吞吐量提升0.78~42.6倍,延時降低10%~94.8%。
智能手機(jī);分布式數(shù)據(jù)流處理系統(tǒng);故障檢測;容錯策略;吞吐量;延時
目前大多數(shù)智能手機(jī)[1-2]都配有主頻達(dá)1.5~2.0GHz的四核CPU,比如三星的Galaxy S4、聯(lián)想的K860i和華為的Ascend P6,此外,八核智能手機(jī)已經(jīng)面市。然而,當(dāng)前系統(tǒng)和應(yīng)用往往僅把手機(jī)當(dāng)作數(shù)據(jù)采集工具,將手機(jī)的感知數(shù)據(jù)通過蜂窩網(wǎng)絡(luò)發(fā)送給服務(wù)器進(jìn)行處理[3-4]。由于蜂窩網(wǎng)絡(luò)速度慢、開銷大等缺陷,所以這些系統(tǒng)在采用蜂窩網(wǎng)絡(luò)后存在諸多容錯問題[5-7]。當(dāng)前用于智能手機(jī)端的實時數(shù)據(jù)分析計算模式為分布式流處理系統(tǒng)(Distributed Stream Processing Systems, DSPSs),如IBM的InfoSphere Streams[8],Yahoo的S4[9]和Streambase[10]。這些DSPSs的核心硬件平臺往往是可靠性較高的服務(wù)器集群。
當(dāng)DSPSs從服務(wù)器集群轉(zhuǎn)移到與ad-hoc WiFi相連的智能手機(jī)上時,在容錯方面帶來了巨大挑戰(zhàn)。電量有限、移動性和可靠性有限的無線網(wǎng)絡(luò),均有可能導(dǎo)致智能手機(jī)出現(xiàn)故障?,F(xiàn)有的這些容錯方案均針對服務(wù)器,在智能手機(jī)上性能有限,原因如下:一是智能手機(jī)平臺的故障模型與之前研究時的假設(shè)有很大不同,之前研究假設(shè)即使發(fā)生小規(guī)模(往往是單節(jié)點)故障也足以滿足大多數(shù)實際應(yīng)用的要求。對智能手機(jī)平臺,往往會有多個手機(jī)同時故障,如多個手機(jī)用戶同時離開通信區(qū)域,或者WiFi連接中斷。二是以前的容錯方案要求通過網(wǎng)絡(luò)發(fā)送大量附加數(shù)據(jù),給DSPS應(yīng)用的性能帶來了巨大開銷,而智能手機(jī)平臺的手機(jī)到手機(jī)ad-hoc WiFi網(wǎng)絡(luò)帶寬有限。因此,將當(dāng)前的容錯方案簡單地用于智能手機(jī)平臺將會降低系統(tǒng)性能。為此,本文提出將智能手機(jī)作為分布式計算平臺,直接在手機(jī)上處理感應(yīng)數(shù)據(jù),以避免客戶端-服務(wù)器計算模式的缺點。設(shè)計可直接在智能手機(jī)上運行的DSPS系統(tǒng)MobiStreams。
MobiStreams的設(shè)計受到交通領(lǐng)域中SignalGuru手機(jī)應(yīng)用的啟發(fā),SignalGuru可以預(yù)測交叉路口紅綠燈的轉(zhuǎn)換時間,并向司機(jī)建議最優(yōu)行駛速度以便到達(dá)路口時亮綠燈。車輛通過這種方式可以在通過路口時一路通行,從而降低耗油量。SignalGuru利用了擋風(fēng)玻璃上安裝的智能手機(jī),當(dāng)手機(jī)靠近交叉路口時抓拍路口圖片,然后通過ad-hoc WiFi網(wǎng)絡(luò)與附近的手機(jī)共享圖片,并一起學(xué)習(xí)信號轉(zhuǎn)換模式。SignalGuru的核心是通過顏色(紅、黃、綠)濾波、形態(tài)(圓圈,箭頭)濾波、和運動濾波(交通燈總是在路邊)從圖片中檢測出交通信號的圖像處理算法。然后,利用支持向量機(jī)訓(xùn)練和預(yù)測轉(zhuǎn)換模式。路口車輛上的智能手機(jī)運行DSPS系統(tǒng)時就是執(zhí)行上述步驟。預(yù)測結(jié)果發(fā)送給道路上的下個路口,以便司機(jī)提前知道交通信號轉(zhuǎn)換時間。DSPS系統(tǒng)在每個路口的運行方式見圖1。攝像頭數(shù)據(jù)發(fā)送給S1,每個元組包含一個圖片。先前路口的數(shù)據(jù)發(fā)送給S0,每個元組包含預(yù)測的交通信號轉(zhuǎn)換時間。這些時間將被廣播給所有附近智能手機(jī)。
圖1 SignalGuru應(yīng)用示例
圖1 SignalGuru應(yīng)用中每個交叉口的DSPS系統(tǒng),具有同一顏色的操作程序位于同一節(jié)點上。其中,S0:上一路口的數(shù)據(jù),S1:智能手機(jī)攝像頭數(shù)據(jù),C:顏色濾波器,A:形態(tài)濾波器,M:運動濾波器,V:投票濾波器,G:組群,P:SVM預(yù)測,K:匯點(到下一路口)。在多個路口執(zhí)行計算任務(wù),DSPS系統(tǒng)運行于每個區(qū)域的智能手機(jī)上。不同區(qū)域的DSPS系統(tǒng)互相接力,即一個區(qū)域中DSPS系統(tǒng)的結(jié)果傳遞給下個區(qū)域的DSPS系統(tǒng),提高了應(yīng)用的覆蓋范圍。這個應(yīng)用的結(jié)構(gòu)促使我們設(shè)計MobiStreams。
MobiStreams系統(tǒng)的設(shè)計采用雙層架構(gòu),如圖2所示。其中,MobiStreams系統(tǒng)的高層架構(gòu)可用一個有向非周期圖來表示。圖中的每個節(jié)點表示一個區(qū)域,箭頭表示區(qū)域間的網(wǎng)絡(luò)連接和數(shù)據(jù)流方向。MobiStreams的低層架構(gòu)主要是每個區(qū)域的微結(jié)構(gòu),區(qū)域內(nèi)通過ad-hoc WiFi相連的智能手機(jī)可認(rèn)為是一個集群,每個智能手機(jī)就是集群中的一個節(jié)點,在每個區(qū)域的集群上運行DSPS。除了區(qū)域和智能手機(jī)外,MobiStreams系統(tǒng)還需要一個控制器,一種可通過蜂窩網(wǎng)絡(luò)與區(qū)域內(nèi)所有智能手機(jī)連接的服務(wù)器節(jié)點。
3.1 智能手機(jī)故障檢測
MobiStreams周期性地檢測每個區(qū)域的DSPS狀態(tài),采用一種新的檢測點策略,通過信標(biāo)來協(xié)調(diào)多個智能手機(jī)的行為,當(dāng)智能手機(jī)在區(qū)域內(nèi)發(fā)生突然故障,系統(tǒng)依靠控制器來ping每個區(qū)域內(nèi)的源節(jié)點。若源節(jié)點在預(yù)定時間內(nèi)無回復(fù),則認(rèn)為發(fā)生故障。每個區(qū)域內(nèi)的計算節(jié)點和匯點由它們的上游相鄰節(jié)點監(jiān)測,若一個節(jié)點發(fā)現(xiàn)其下游相鄰節(jié)點故障,則通過網(wǎng)絡(luò)迅速向控制器匯報。除了下游相鄰節(jié)點的故障外,節(jié)點也可非常活躍地將自己的故障匯報給控制器,如當(dāng)其電池電量較低時的匯報。
圖2 MobiStreams雙層架構(gòu)
3.2 低可靠性無線網(wǎng)絡(luò)的檢測
在檢測期間,節(jié)點的狀態(tài)及區(qū)域的輸入數(shù)據(jù)必須存儲在輸出節(jié)點上,即使節(jié)點故障也可保證檢測的穩(wěn)定性?;诜?wù)器的DSPS系統(tǒng)是在可靠性高、速度快的以太網(wǎng)上進(jìn)行檢測,但本文中檢測點的保存必須依托于可靠性低、速度慢、帶寬窄的ad-hoc WiFi網(wǎng)絡(luò)。MobiStreams通過基于高可靠性和低可靠性數(shù)據(jù)傳輸?shù)亩嚯A段廣播策略解決這一問題。
前幾個階段采用UDP協(xié)議。節(jié)點的檢測數(shù)據(jù)分為多個1KB數(shù)據(jù)塊(最后一個數(shù)據(jù)塊低于1KB)。節(jié)點發(fā)送的每個UDP報文包含一個數(shù)據(jù)塊,及表示運行于節(jié)點上的操作程序ID的數(shù)據(jù)塊描述符,該檢測點的版本以及該數(shù)據(jù)塊的序號。數(shù)據(jù)塊描述符很小,因此報文尺寸仍然為1KB左右。之所以采取小規(guī)模報文,是因為大規(guī)模UDP報文在進(jìn)行報文分割時容易受到有損網(wǎng)絡(luò)的影響。在接收器端,每個節(jié)點記錄接收到的報文,根據(jù)UDP的數(shù)據(jù)報屬性,UDP協(xié)議維持報文間的邊界,只要有部分報文未被接收到,則整個報文就被丟棄。所有報文廣播完畢后,發(fā)送方詢問接收節(jié)點哪些報文被接收到,每個接收方返回一個位圖,每一位表示相應(yīng)消息被丟失(0)還是接收到(1)。位圖中的位數(shù)因此等于發(fā)送方廣播的消息數(shù)量。根據(jù)所有接收方的位圖,發(fā)送方可以推斷廣播期間被丟失的消息(未被任何接收方接收到的消息)。發(fā)送方然后再次廣播丟失消息,重復(fù)上述廣播和詢問過程,直到成本超過收益,成本和收益的概念從發(fā)送或接收到的字節(jié)數(shù)量角度定義。
圖3詳細(xì)描述了MobiStreams的多階段廣播過程。區(qū)域內(nèi)有4個節(jié)點。發(fā)送節(jié)點的檢測點數(shù)據(jù)規(guī)模為8MB (8192個消息)。
圖3 包括4個智能手機(jī)的區(qū)域的UDP廣播
在時刻1,發(fā)送方向節(jié)點A, B和C廣播所有消息M1,…,M8192。在時刻2,發(fā)送方結(jié)束對接收方的廣播和詢問過程。節(jié)點A只接收到前3個消息,因此返回首部只有3個1的位圖。節(jié)點B接收到所有偶數(shù)消息,因此返回0和1交叉的位圖。節(jié)點C接收到所有奇數(shù)消息,因此返回1和0交叉的位圖。每個位圖的規(guī)模為1KB。發(fā)送方可利用這些位圖進(jìn)行一些計算。(1)發(fā)送方對所有位圖進(jìn)行AND操作,獲得只包含0的位圖,換句話說,每個消息至少有一個接收器未接收到。(2)發(fā)送方計算接收方接收到的字節(jié)數(shù)量。節(jié)點A, B和C接收到的字節(jié)數(shù)量分別為3KB, 4096KB和4096KB。因此,總數(shù)為8195KB。(3)發(fā)送方評估廣播增益,將其計算為廣播之前和之后接收到的字節(jié)數(shù)量。在廣播之前,接收到的字節(jié)數(shù)量為0。因此,廣播增益為8195KB個接收字節(jié)。(4)接收方計算廣播成本。它已經(jīng)發(fā)送了8192個消息,接收到3個位圖消息,總成本是通過網(wǎng)絡(luò)傳輸8195KB個消息。因為成本(8195KB)小于等于增益(8195KB),所以發(fā)送方開始在時刻3進(jìn)行第2次廣播。
根據(jù)時刻2的ANDed位圖,每個消息必須被重發(fā)。然后,發(fā)送方再次廣播所有消息。在時刻4,發(fā)送方完成第2次廣播,獲得返回的位圖。節(jié)點A和B接收到所有消息,因此它們返回全由1組成的位圖。節(jié)點C在第2次廣播時未接收到任何消息。其返回位圖與上次相同。發(fā)送方利用這些位圖進(jìn)行相同的計算步驟。ANDed位圖為1010..,表示所有偶數(shù)消息必須重傳。接收到的字?jǐn)?shù)總數(shù)量為20480KB。第2次廣播的增益為新接收到12285KB個消息,成本為通過網(wǎng)絡(luò)傳輸8195KB個消息。因為成本(8195KB)不大于增益(12285KB),所以發(fā)送方在時刻5開始第3次廣播。根據(jù)時刻4時的ANDed位圖,只有偶數(shù)消息M2,M4,…,M8192被重傳。在時刻6,節(jié)點C返回一個位圖,表示它已經(jīng)接收到除了M2的所有消息。根據(jù)相同的算法步驟,第3次廣播的增益為4095KB,成本為4099KB。因此,發(fā)送方最終終止UDP廣播。
UDP廣播無法保證每個節(jié)點接收到所有的檢測點數(shù)據(jù)。因此,引入基于可靠TCP協(xié)議的額外步驟。在該步驟中,區(qū)域內(nèi)的所有節(jié)點組織為一個樹。發(fā)送方也是樹中的一個節(jié)點。首先從發(fā)送方開始向根節(jié)點傳輸數(shù)據(jù),然后從根節(jié)點向葉節(jié)點傳輸。由控制器創(chuàng)建樹結(jié)構(gòu),只當(dāng)手機(jī)故障、進(jìn)入或離開區(qū)域時樹結(jié)構(gòu)才會變化。
3.3 機(jī)動性檢測
本文迄今假設(shè)智能手機(jī)在區(qū)域內(nèi)靜止不動,即手機(jī)進(jìn)入?yún)^(qū)域后不會離開。下面進(jìn)一步考慮智能手機(jī)移動情景。如圖4所示,計算節(jié)點(節(jié)點D)離開區(qū)域。當(dāng)D不在區(qū)域內(nèi)時,節(jié)點D、B和E間的距離較大,它們之間的WiFi連接中斷。然后,這些節(jié)點切換到緊急模式,采用蜂窩網(wǎng)絡(luò)來發(fā)送元組,如圖4時刻2所示。節(jié)點D、B和E向控制器匯報緊急模式。根據(jù)節(jié)點D的GPS,控制器知道節(jié)點D正在離開。然后,控制器選擇區(qū)域內(nèi)的另一節(jié)點替換節(jié)點D。此時,控制器選擇節(jié)點F,命令D在時刻3通過蜂窩網(wǎng)絡(luò)將其狀態(tài)發(fā)送給F。一旦節(jié)點F的狀態(tài)與D相同,控制器命令節(jié)點B、F和E來在時刻4重建WiFi連接。此后,該區(qū)域的DSPS系統(tǒng)返回正常模式,繼續(xù)處理元組。離開區(qū)域的節(jié)點將在控制器處注銷。這里有一種特殊情況需要特別介紹。在時刻2處,如果節(jié)點D的GPS匯報節(jié)點D仍在區(qū)域內(nèi),則有兩種可能:(1)由于受到干擾,WiFi連接中斷,而不是節(jié)點離開;或者(2)GPS不準(zhǔn)確。控制器因此命令節(jié)點D、B和E暫時重建WiFi連接。如果它們在幾次嘗試后無法成功,則認(rèn)為節(jié)點D確實離開了區(qū)域。
圖4 智能手機(jī)離開時觸發(fā)的行為
如果多個節(jié)點同時離開區(qū)域,則DSPS的結(jié)構(gòu)仍可保持在緊急模式,但是節(jié)點間的部分網(wǎng)絡(luò)連接將依靠蜂窩網(wǎng)絡(luò)。該區(qū)域的DSPS可繼續(xù)工作,但性能將會下降,一直持續(xù)到控制器替換了離開節(jié)點。如果部分節(jié)點離開之后區(qū)域內(nèi)沒有足夠多的剩余節(jié)點,則控制器停止該區(qū)域的計算任務(wù),連接該區(qū)域的上游和下游相鄰節(jié)點(繞過該區(qū)域)。如果源節(jié)點或匯點離開區(qū)域,則控制器選擇區(qū)域內(nèi)的另一節(jié)點來替換它。因為源節(jié)點和匯點為無狀態(tài)節(jié)點,所以沒有必要將其狀態(tài)從離開節(jié)點狀態(tài)轉(zhuǎn)換為新選擇節(jié)點狀態(tài)。然而,控制器必須命令新選擇的節(jié)點相應(yīng)地重建跨區(qū)域連接。如果有空閑節(jié)點離開(GPS檢測出來),則它向控制器注銷自己(unregister),刪除上面存儲的所有檢測點數(shù)據(jù)。
將MobiStreams作為iOS頂層的中間件加以部署,同時將預(yù)測交叉路口紅綠燈的轉(zhuǎn)換時間應(yīng)用作為DSPS系統(tǒng)進(jìn)行部署。
4.1 MobiStreams和基于服務(wù)器的DSPS
表1給出了比較結(jié)果。一個手機(jī)故障表明有個手機(jī)停止工作,手機(jī)離開表示一個手機(jī)離開區(qū)域,且離開手機(jī)的狀態(tài)必須傳輸給區(qū)域內(nèi)的另一個手機(jī)。
其中MobiStreams1為容錯功能關(guān)閉,MobiStreams2 為容錯功能開啟且手機(jī)每5分鐘離開其區(qū)域,MobiStreams3為容錯功能開啟且手機(jī)每5分鐘故障。在這些場景中,MobiStreams的性能均優(yōu)于基于服務(wù)器的DSPS。
表1 Mobistreams與基于服務(wù)器的DSPS比較
4.2 不同算法的性能比較
為了驗證MobiStreams的優(yōu)越性,本文定義如下容錯算法并與其做比較:(1)不支持容錯的baseline算法(base);(2)活躍備用算法(rep-2);(3)本地檢測點算法(local);(4)分布式檢測算法(dist-n)。
為了評估恢復(fù)開銷,在場景中引入手機(jī)故障和離開事件。圖5(BCP汽車容量預(yù)測和Signal Guru預(yù)測交叉路口紅綠燈的轉(zhuǎn)換時間)給出了在一個檢測周期內(nèi)有n個節(jié)點故障或離開時相關(guān)應(yīng)用的性能。圖5中的延時和吞吐量包括應(yīng)用的停機(jī)時間和恢復(fù)時間。在該圖中有三大發(fā)現(xiàn)。首先,無論多少個節(jié)點故障,MobiStreams總是能夠恢復(fù)DSPS中的所有節(jié)點。因此,當(dāng)故障節(jié)點數(shù)量上升時,故障恢復(fù)開銷恒定??梢钥闯觯琈obiStreams的性能曲線(ms-8手機(jī)故障)為一條水平線。其次,dist-n的性能曲線只有n+1個點,因為它只能處理n個節(jié)點故障。rep-2的曲線只包含兩個點,因為它只能處理單節(jié)點故障。rep-2和dist-n的性能遠(yuǎn)低于MobiStreams,當(dāng)n變大時,dist-n的性能下降。在SignalGuru中,dist-3的曲線只包含1個點,因為它無法在5分鐘內(nèi)恢復(fù)系統(tǒng)。最后,MobiStreams的節(jié)點離開開銷低于rep-2和dist-n的故障恢復(fù)開銷,且在大部分情況下低于MobiStreams的故障恢復(fù)開銷。這在預(yù)料之中。節(jié)點故障比節(jié)點離開復(fù)雜,因為故障會觸發(fā)恢復(fù)和補(bǔ)救,而節(jié)點離開只需要狀態(tài)傳輸。然而,當(dāng)同時離開的手機(jī)數(shù)量較大時(圖5第2個子圖),MobiStreams的離開開銷可能超過故障恢復(fù)開銷。筆者認(rèn)為這是因為狀態(tài)傳輸需要使用蜂窩網(wǎng)絡(luò)通信,當(dāng)許多手機(jī)同時使用蜂窩網(wǎng)絡(luò)時,網(wǎng)絡(luò)便會影響總體性能。因為先前的容錯算法無法處理節(jié)點離開事件(它們的設(shè)計著眼于服務(wù)器),所以只對MobiStreams進(jìn)行節(jié)點離開實驗。
圖5 在一個檢測周期內(nèi)發(fā)生一次n個節(jié)點故障或離開時的相對吞吐量和延時
針對在智能手機(jī)上部署DSPS系統(tǒng)時面臨的智能手機(jī)故障、低可靠性無線網(wǎng)絡(luò)、智能手機(jī)移動情境等挑戰(zhàn),提出一種容錯的分布式流處理系統(tǒng),該系統(tǒng)緩解了蜂窩網(wǎng)絡(luò)的壓力。最后的仿真實驗驗證了該系統(tǒng)的有效性和性能的優(yōu)越性。下一步工作的重點是對不同場景下的智能手機(jī)數(shù)據(jù)傳輸可靠性問題進(jìn)行分析,進(jìn)一步提升智能手機(jī)的應(yīng)用性能。
[1]諶國風(fēng),孔俊俊,郭耀,等.一種智能手機(jī)上下文信息獲取的代價模型及其應(yīng)用[J].計算機(jī)科學(xué),2014,41(11):132-136
[2]谷瓊,李杰,龔雄興.基于Android智能手機(jī)的隱私管理系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機(jī)應(yīng)用與軟件,2014,31(1):260-263
[3]薛建彬,何鳳婕.基于業(yè)務(wù)量感知的蜂窩網(wǎng)絡(luò)中繼站協(xié)作控制機(jī)制[J].蘭州理工大學(xué)學(xué)報,2014,40(4):105-109
[4]林啟中,張冬梅,許魁,等.蜂窩網(wǎng)絡(luò)中M2M通信上行接入資源分配[J].應(yīng)用科學(xué)學(xué)報,2015,33(2):129-141
[5]朱近康,許莉.綠色蜂窩網(wǎng)絡(luò)的頻譜效率與能效函數(shù)[J].通信學(xué)報,2013,34(1):1-7
[6]王飛,許魁,徐友云,等.大數(shù)據(jù)無線通信面臨的幾點挑戰(zhàn)與對策[J].電子技術(shù)應(yīng)用,2015,41(3):12-16
[7]楊亞讓,趙越.OFDMA多跳中繼蜂窩網(wǎng)絡(luò)的干擾協(xié)調(diào)策略[J].鐵道學(xué)報,2015,37(1):44-50
[8]Nabi Z,Wagle R,Bouillet E.The best of two worlds:Integrating IBM InfoSphere Streams with Apache YARN[C]//2014 IEEE International Conference on Big Data.Beijing China: IEEE Press,2014:47-51
[9]Xhafa Fatos,Naranjo Victor,Caballe Santi.Processing and Analytics of Big Data Streams with Yahoo! S4[C]//2015 IEEE 29th International Conference on Advanced Information Networking and Applications.Gwangju Korea:IEEE Press,2015:263-270
[10]Botan I,Younggoo Cho,Derakhshan R,et al.A demonstration of the MaxStream federated stream processing system[C]//2010 IEEE 26th International Conference on Data Engineering.California USA:IEEE Press,2010:1093-1096
(責(zé)任編輯:汪材印)
10.3969/j.issn.1673-2006.2015.11.028
2015-08-21
安徽省質(zhì)量工程教學(xué)團(tuán)隊項目“計算機(jī)網(wǎng)絡(luò)技術(shù)專業(yè)教學(xué)團(tuán)隊”(2014jxtd099)。
任海鵬(1979-),安徽蕪湖人,碩士,講師,主要研究方向:數(shù)據(jù)通信與無線網(wǎng)絡(luò).
TP393
A
1673-2006(2015)11-0107-05