云環(huán)境下基于Agent協(xié)商的宿主機(jī)容錯(cuò)策略

張凱旋 顧春華 萬 峰

(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237)

云環(huán)境下基于Agent協(xié)商的宿主機(jī)容錯(cuò)策略

張凱旋 顧春華 萬 峰

(華東理工大學(xué)信息科學(xué)與工程學(xué)院 上海 200237)

云計(jì)算平臺(tái)中大量使用了廉價(jià)的設(shè)備，使得宿主機(jī)出現(xiàn)故障概率大大增加。針對(duì)因宿主機(jī)故障而導(dǎo)致的虛擬機(jī)實(shí)例失效問題，提出一種宿主機(jī)容錯(cuò)策略。通過對(duì)宿主機(jī)集群分組和對(duì)宿主機(jī)進(jìn)行Agent建模，在每個(gè)小組內(nèi)利用Agent協(xié)商來快速重建虛擬機(jī)實(shí)例。仿真實(shí)驗(yàn)表明，所提出的策略能夠自動(dòng)重建失效的虛擬機(jī)實(shí)例，提出的容錯(cuò)策略在耗時(shí)上小于其他策略。

云環(huán)境 宿主機(jī) Agent協(xié)商 容錯(cuò)

0 引 言

隨著互聯(lián)網(wǎng)和云計(jì)算的不斷發(fā)展，云計(jì)算平臺(tái)作為基礎(chǔ)服務(wù)變得越來越流行?，F(xiàn)在的云計(jì)算平臺(tái)，其底層是基于虛擬化技術(shù)實(shí)現(xiàn)的[1]。云計(jì)算平臺(tái)最典型的實(shí)現(xiàn)是在大量的的物理機(jī)構(gòu)成的集群上運(yùn)行虛擬機(jī)，通過虛擬機(jī)向用戶提供服務(wù)。在云計(jì)算平臺(tái)中，稱這種物理機(jī)為宿主機(jī)，虛擬機(jī)為客戶機(jī)或者實(shí)例。

作為衡量云計(jì)算平臺(tái)服務(wù)質(zhì)量的重要標(biāo)準(zhǔn)，云計(jì)算平臺(tái)的高可用性越來越得到重視[2]。云計(jì)算平臺(tái)的高可用性是指虛擬機(jī)實(shí)例正常運(yùn)行的時(shí)間占虛擬機(jī)實(shí)例總時(shí)間的百分比。云計(jì)算平臺(tái)的最大優(yōu)勢是大量使用了廉價(jià)的標(biāo)準(zhǔn)計(jì)算機(jī)，而這種普通的計(jì)算機(jī)和專用服務(wù)器相比，出現(xiàn)故障的概率則大大增加。當(dāng)宿主機(jī)出現(xiàn)故障，宿主機(jī)上運(yùn)行的虛擬機(jī)實(shí)例便會(huì)失效，從而造成租用該虛擬機(jī)實(shí)例的用戶服務(wù)中斷。當(dāng)宿主機(jī)出現(xiàn)斷電、硬件損壞等故障時(shí)，對(duì)宿主機(jī)上運(yùn)行的虛擬機(jī)進(jìn)行恢復(fù)重建才能恢復(fù)云計(jì)算平臺(tái)的服務(wù)。因此，云計(jì)算平臺(tái)需要有一定的容錯(cuò)能力，才能保證云計(jì)算服務(wù)的高可用性。

1 相關(guān)研究

云計(jì)算平臺(tái)的出現(xiàn)的錯(cuò)誤分布在三個(gè)層面：應(yīng)用層、虛擬機(jī)層和宿主機(jī)層[3]。其中應(yīng)用層面，是指應(yīng)用程序在運(yùn)行過程中出現(xiàn)的錯(cuò)誤，例如Web服務(wù)器數(shù)據(jù)庫服務(wù)故障。虛擬機(jī)層面是指某一些虛擬機(jī)出現(xiàn)故障，如虛擬機(jī)網(wǎng)絡(luò)中斷等。而宿主機(jī)層面的錯(cuò)誤是指宿主機(jī)出現(xiàn)硬件故障。在應(yīng)用層容錯(cuò)方面，傳統(tǒng)的容錯(cuò)方案能夠滿足需求，如通過Web服務(wù)器集群和反向代理技術(shù)實(shí)現(xiàn)對(duì)Web服務(wù)器的容錯(cuò)。因此，目前在云計(jì)算平臺(tái)的容錯(cuò)方面研究的重點(diǎn)在于虛擬機(jī)層面的容錯(cuò)和宿主機(jī)層面的容錯(cuò)，而本文研究的是宿主機(jī)層面的容錯(cuò)策略。

在宿主機(jī)層的容錯(cuò)方面，Wang等提出了一種主備份的容錯(cuò)調(diào)度策略用于對(duì)宿主機(jī)的錯(cuò)誤容忍[4]。這種策略使用了主從宿主機(jī)結(jié)構(gòu)，當(dāng)宿主機(jī)出現(xiàn)故障，啟用備用的宿主機(jī)，這種策略需要設(shè)置多個(gè)宿主機(jī)作為備份宿主機(jī)，對(duì)宿主機(jī)資源浪費(fèi)比較嚴(yán)重。Nogueira等將宿主機(jī)故障問題描述為一個(gè)拜占庭故障模型[5]，提出了一種副本組的策略，使得對(duì)于有2m+1個(gè)宿主機(jī)集群，最多可以容忍m個(gè)宿主機(jī)出現(xiàn)錯(cuò)誤。這種策略改進(jìn)了傳統(tǒng)的拜占庭故障模型，提高了容忍錯(cuò)誤的數(shù)量。但是，由于它的決策在全局中進(jìn)行迭代，當(dāng)集群規(guī)模比較大的時(shí)候，這種策略在效率上會(huì)變得很慢。

很多云計(jì)算廠商將宿主機(jī)的錯(cuò)誤當(dāng)作虛擬機(jī)錯(cuò)誤來處理[6-7]，其做法是，通過實(shí)時(shí)監(jiān)測所有的虛擬機(jī)，并對(duì)虛擬機(jī)進(jìn)行周期性快照。監(jiān)控程序一旦檢測到虛擬機(jī)出現(xiàn)問題，則從最近的一次快照重新新建一個(gè)虛擬機(jī)取代失效的虛擬機(jī)。這種策略由于要定期做快照，保存快照增大了存儲(chǔ)資源的開銷。

在宿主機(jī)容錯(cuò)方面存在著資源開銷大、效率低的問題。針對(duì)這些問題，本文提出了一種基于Agent協(xié)商的宿主機(jī)容錯(cuò)策略，在不額外使用宿主機(jī)的前提下，能夠快速自動(dòng)重建因宿主機(jī)故障而失效的虛擬機(jī)，提高了云計(jì)算平臺(tái)的容錯(cuò)性。下文將介紹這種基于多Agent協(xié)商的容錯(cuò)策略。

2 多Agent容錯(cuò)模型

把宿主機(jī)看作Agent，利用Agent的自治性、協(xié)商來處理Agent故障[8]。

2.1 系統(tǒng)架構(gòu)

在云計(jì)算平臺(tái)中，宿主機(jī)的數(shù)量成千上萬，因此Agent的數(shù)量也成千上萬。如果把整個(gè)集群中的Agent視為一個(gè)多Agent系統(tǒng)，則對(duì)于規(guī)模較大的多Agent系統(tǒng)，其用于通信的系統(tǒng)開銷也很大，并且Agent之間的協(xié)商時(shí)間開銷也很大。為了避免因多Agent系統(tǒng)規(guī)模太大造成的策略的收斂速度慢的問題，把集群中宿主機(jī)劃分成規(guī)模較小的組，每個(gè)組內(nèi)有5到10個(gè)宿主機(jī)。每個(gè)組內(nèi)的宿主機(jī)構(gòu)成了規(guī)模較小的多Agent系統(tǒng)，組內(nèi)的Agent之間通過交互來互相彼此狀態(tài)信息。當(dāng)某個(gè)宿主機(jī)出現(xiàn)故障時(shí)，即Agent失效時(shí)，同一個(gè)組內(nèi)的其他活動(dòng)的Agent通過協(xié)作來處理失效Agent上正在運(yùn)行的任務(wù)，即重建失效的虛擬機(jī)。由于故障處理策略作用在組內(nèi)，從而加快了決策的收斂速度。圖1是多Agent系統(tǒng)的分組模型，其中Agent在邏輯上被分到一個(gè)個(gè)的組內(nèi)。

圖1 多Agent的分組模型

同一個(gè)組內(nèi)的Agent構(gòu)成了一個(gè)規(guī)模較小的多Agent系統(tǒng)，它們形成了一種聯(lián)盟。它們之間通過周期性的信息更新，來獲取組內(nèi)成員Agent的任務(wù)信息和狀態(tài)信息。假設(shè)某時(shí)刻t某個(gè)Agent失效，則其他Agent檢測到該Agent失效后，由于失效Agent的狀態(tài)信息和任務(wù)信息在其他Agent上留有副本，因此，其余Agent通過協(xié)商來共同處理失效Agent正在處理的任務(wù)。如圖2所示。

圖2 組內(nèi)Agent通過協(xié)商處理任務(wù)

2.2 Agent結(jié)構(gòu)

按問題求解能力劃分，Agent分為三種類型[9]，即反應(yīng)型Agent，能響應(yīng)環(huán)境的變化或來自其他Agent的消息；慎思型Agent，能夠針對(duì)意圖和信念進(jìn)行推理，建立行為計(jì)劃，并執(zhí)行這些計(jì)劃；社會(huì)型Agent，除具有慎思型Agent的能力外，還具有關(guān)于其他主體的明確模型[10]。本文的Agent代表了宿主機(jī)，則CPU利用率、內(nèi)存利用率等是Agent本身能夠感知的信息，且這些信息隨著外部環(huán)境如負(fù)載的變化而變化。Agent除了能感知自身的信息之外，還通過其他Agent交互獲取其它Agent的狀態(tài)、任務(wù)信息，例如運(yùn)行的虛擬機(jī)實(shí)例的個(gè)數(shù)、類型、虛擬機(jī)的配置信息等。慎思型的Agent其會(huì)維護(hù)一個(gè)內(nèi)部可識(shí)別的世界模型，該模型描述了自身可感知的信息和外界環(huán)境信息。而當(dāng)環(huán)境發(fā)生變化，Agent根據(jù)預(yù)設(shè)的目標(biāo)作出不同的反應(yīng)。本文的Agent需要維護(hù)自身和其他Agent的狀態(tài)，當(dāng)外部環(huán)境改變即發(fā)現(xiàn)有Agent失效，就會(huì)做出反應(yīng)。因此，慎思型Agent的結(jié)構(gòu)最適合構(gòu)造本文的Agent。如圖3所示。

圖3 慎思型Agent的結(jié)構(gòu)

2.3 Agent世界模型

Agent的世界模型(WM，World Model)是Agent內(nèi)部可識(shí)別的狀態(tài)，是對(duì)外部環(huán)境和自身信息經(jīng)過加工、推理而建立的世界狀態(tài)[10]。Agent通過與其他Agent交互來獲取外部環(huán)境信息，通過自身的感知來獲取自身信息。虛擬化軟件啟動(dòng)虛擬機(jī)的流程如下：虛擬機(jī)化軟件根據(jù)用戶指定的虛擬機(jī)配額生成一個(gè)xml文件，該文件描述了虛擬機(jī)的配置情況。接下來，虛擬機(jī)化軟件會(huì)根據(jù)上面生成的xml文件啟動(dòng)虛擬機(jī)。虛擬機(jī)化軟件則根據(jù)鏡像文件和配置文件在計(jì)算節(jié)點(diǎn)啟動(dòng)虛擬機(jī)。通過分析虛擬化軟件啟動(dòng)虛擬機(jī)的流程可知，啟動(dòng)一個(gè)虛擬機(jī)所必需的輸入條件是基礎(chǔ)鏡像和配置文件。其中基礎(chǔ)鏡像是虛擬機(jī)操作系統(tǒng)的鏡像，配置文件指定了虛擬機(jī)的核數(shù)、內(nèi)存大小、硬盤大小、網(wǎng)卡設(shè)備等信息。用戶在虛擬機(jī)的過程中，會(huì)產(chǎn)生用戶數(shù)據(jù)，如用戶存放的文件等。一般地，用戶數(shù)據(jù)會(huì)單獨(dú)保存在云硬盤上，而云硬盤由塊服務(wù)提供，通過遠(yuǎn)程掛載的方式掛載在虛擬機(jī)上。

Agent的世界模型由Agent自身周期性的進(jìn)行更新。世界模型的信息按照信息變化的頻率可以劃分為靜態(tài)信息和動(dòng)態(tài)信息。靜態(tài)數(shù)據(jù)是指Agent在初始化后，不經(jīng)常改變的數(shù)據(jù)，如CPU核數(shù)、內(nèi)存總大小、鏡像文件、虛擬機(jī)配置文件等。動(dòng)態(tài)信息是指在Agent正?；顒?dòng)時(shí)，會(huì)時(shí)刻發(fā)生改變的數(shù)據(jù)，如CPU利用率、內(nèi)存利用率、組內(nèi)其他Agent運(yùn)行的虛擬機(jī)信息和緩存的鏡像信息等。靜態(tài)信息的更新周期較長，相反的，動(dòng)態(tài)信息的更新周期則要短。Agent的世界模型用一個(gè)二元組表示，其中StaticInfo表示靜態(tài)信息，DynamicInfo表示動(dòng)態(tài)信息。

WM=

(1)

為了簡化描述，靜態(tài)信息用一個(gè)三元組表示。其中CPUtotle表示總的CPU核數(shù)，MEMORYtotle表示總的內(nèi)存總大小，Disktotle表示總的硬盤總?cè)萘俊?/p>

StaticInfo=

(2)

動(dòng)態(tài)信息用一個(gè)五元組表示，分別表示宿主機(jī)的CPU剩余核數(shù)、內(nèi)存剩余大小、硬盤剩余容量、所運(yùn)行的虛擬機(jī)信息、緩存的鏡像信息、Agent所在的分組信息。

DynamicInfo=

(3)

所運(yùn)行的虛擬機(jī)信息是Agent上所有運(yùn)行的虛擬機(jī)的摘要信息，每一個(gè)虛擬機(jī)的摘要信息為虛擬機(jī)的id和鏡像id。虛擬機(jī)的id是由虛擬化軟件在啟動(dòng)虛擬機(jī)虛擬機(jī)時(shí)分配的一個(gè)唯一的id，Agent用虛擬機(jī)的id作為該虛擬機(jī)配置文件的文件名保存到自身的文件系統(tǒng)中。

(4)

(5)

分組信息用一個(gè)三元組表示，其中MemberList是Agent所在組的其他Agent的集合。IsMaster表示Agent自身是不是管理Agent。

GroupInfo=

(6)

成員列表MemberList用一個(gè)二元組集合表示，其中Agentm表示組內(nèi)第m個(gè)成員，Addressm表示Agentm的通信地址。

MemberList={|m∈[0,n]}

(7)

Agent在初始化后，從分組信息中獲知和它同一個(gè)組的其他Agent的通信地址，接下來Agent會(huì)周期性的更新自己的世界狀態(tài)。為了在啟動(dòng)虛擬機(jī)時(shí)，節(jié)省鏡像從鏡像服務(wù)器傳輸?shù)紸gent的時(shí)間，Agent主動(dòng)的將從已經(jīng)緩存的鏡像文件平均的分發(fā)到組內(nèi)其他Agent。因此，針對(duì)鏡像文件，Agent采取的更新策略是主動(dòng)的將自己的鏡像文件平均的推到組內(nèi)其他Agent上。而鏡像的描述信息以及其他摘要信息的更新采用拉的模式。

3 改進(jìn)的合同網(wǎng)協(xié)商模型

Agent周期性地更新自身世界模型時(shí)，如果存在無響應(yīng)的Agent，則認(rèn)為該Agent失效了。當(dāng)檢測到Agent失效時(shí)，同一組內(nèi)的其他活動(dòng)的Agent就會(huì)通過協(xié)商來協(xié)助失效Agent重建正在運(yùn)行的虛擬機(jī)。Agent協(xié)商中經(jīng)典的協(xié)調(diào)策略是由RandallDevis等提出的合同網(wǎng)協(xié)議，合同網(wǎng)協(xié)議是為了解決Agent之間的任務(wù)分配而進(jìn)行的一種合約協(xié)商過程[10]。

3.1Agent的協(xié)商過程

合同網(wǎng)協(xié)議中的Agent有兩種類型[11]，一種是管理Agent(MA，MasterAgent)，另一種是執(zhí)行Agent(EA，ExecuteAgent)。MA是協(xié)商過程的組織者，EA是執(zhí)行任務(wù)的工作Agent。MA組織協(xié)商的過程如下：①M(fèi)A向所有的EA發(fā)布任務(wù)；②EA收到任務(wù)信息后，根據(jù)任務(wù)要求和自己的能力，計(jì)算自己能夠完成的任務(wù)，并提交標(biāo)書給MA進(jìn)行競標(biāo)；③MA選擇一個(gè)或多個(gè)EA進(jìn)行作為最終的中標(biāo)者，并與競標(biāo)者簽訂問題求解合同；④MA負(fù)責(zé)監(jiān)視整個(gè)任務(wù)的執(zhí)行，EA將求解的結(jié)果提交給MA；⑤MA整合最終的處理結(jié)果。

3.2MA的選舉

傳統(tǒng)的合同網(wǎng)模型會(huì)指定某個(gè)Agent充當(dāng)一種角色，而實(shí)際上每個(gè)Agent都有可能失效，如果MA自身失效，則會(huì)導(dǎo)致Agent之間因缺少組織者而無法協(xié)商。為了避免這個(gè)問題，本文的MA由所有Agent選舉產(chǎn)生，并且Agent可以充當(dāng)多個(gè)角色，即Agent可以同時(shí)具備兩個(gè)角色。初始化時(shí)，每一個(gè)Agent都是EA，第一個(gè)檢測到存在失效的Agent，首先將失效Agent和當(dāng)時(shí)的時(shí)間戳記錄下來，然后將帶時(shí)間戳的失效消息告知到組內(nèi)其他Agent，并選舉自己為MA。當(dāng)收到超過一半的Agent同意后則，把自己標(biāo)記為Agent。如圖4所示。

圖4 Group內(nèi)的不同角色的Agent

在這個(gè)過程中，為了避免多個(gè)Agent競爭MA，規(guī)定每個(gè)Agent在一次失效中只能投一次票。Agent投票之前，Agent分兩種情況來決定是否選舉自己為MA:① 如果它還沒有檢測到有失效Agent，就收到失效通知信息，說明自己不是第一個(gè)發(fā)現(xiàn)存在失效Agent。那么它將發(fā)送一個(gè)探測包給失效Agent，來確認(rèn)Agent是否真的失效。確認(rèn)后，則發(fā)送確認(rèn)信息給發(fā)布失效通知的Agent，并且同意其成為MA；② 如果它自己也探測到有失效Agent并且自己沒來得及發(fā)出通告，則它就不再發(fā)出通告，避免多個(gè)Agent爭奪MA，接下來它按照①的方式繼續(xù)處理。Agent在發(fā)出選舉自己為在收到超過半數(shù)的投票后，把自己標(biāo)記為MA，并告知其他Agent自己成為MA。

3.3 任務(wù)模型

當(dāng)MA選舉成功后，由MA生成和發(fā)布任務(wù)。由前面的分析可知，該任務(wù)就是重建失效Agent上所運(yùn)行的n個(gè)虛擬機(jī)。根據(jù)重建虛擬機(jī)所需的必要條件，任務(wù)的內(nèi)容可以用一個(gè)待重建的虛擬機(jī)列表來表示。由于每個(gè)Agent的世界模型中都能保存了組內(nèi)其他任意一個(gè)Agent運(yùn)行虛擬機(jī)的摘要信息。因此，當(dāng)故障出現(xiàn)時(shí)，其他活動(dòng)Agent都可能具備失效Agent的完整信息。由于每個(gè)Agent更新世界狀態(tài)并不是同步的，所以并不能保證每個(gè)Agent在某一時(shí)刻對(duì)同一個(gè)對(duì)象的認(rèn)知和描述都是一樣的。為了獲得失效Agent在失效的時(shí)刻最準(zhǔn)確的信息，MA需要向所有活動(dòng)EA詢問誰的信息是最新的。EA將自己最近一次更新世界狀態(tài)的時(shí)間戳發(fā)送給MA，MA對(duì)比所有EA發(fā)來的時(shí)間戳，就能確定最準(zhǔn)確的信息在哪里。MA確定了最準(zhǔn)確的信息之后制作任務(wù)清單，任務(wù)清單用一個(gè)二元組表示:

Task=

(8)

其中Agentadd表示失效的Agent的地址，InfoAgentadd描述了要失效的Agent在失效時(shí)的最準(zhǔn)確的狀態(tài)信息所在的Agent地址。

3.4MA組織協(xié)商

MA在制作完任務(wù)清單后，將清單發(fā)送給所有的EA。EA收到MA發(fā)來的任務(wù)清單后，根據(jù)任務(wù)清單中的描述，從指定的Agent那里獲得失效Agent失效時(shí)的虛擬機(jī)信息VMInfo。EA按照約定的存儲(chǔ)方式，根據(jù)VMInfo提供的信息可以推算出要恢復(fù)的虛擬機(jī)所需的鏡像以及配置文件。

EA獲取到虛擬機(jī)的信息后，根據(jù)自身當(dāng)前的負(fù)載和已經(jīng)保存的信息來評(píng)估自己恢復(fù)每一個(gè)VM所耗費(fèi)的時(shí)間，并制作標(biāo)書發(fā)送給MA，標(biāo)書用一個(gè)五元組表示，它描述了該Agent能夠?qū)χ亟恳粋€(gè)VM所耗費(fèi)的時(shí)間:

VMBid=

(9)

其中Agentadd表示該Agent的地址，VMid表示VM的id，Tschedule表示啟動(dòng)這個(gè)虛擬機(jī)的調(diào)度耗時(shí)，TtransImage表示傳輸鏡像耗時(shí)，Tlaunch表示加載虛擬機(jī)耗時(shí)。

MA根據(jù)每個(gè)EA的提交的標(biāo)書，求出最優(yōu)的解。為了提高云計(jì)算服務(wù)的高可用性，就要盡量縮短恢復(fù)故障的時(shí)間，即MA求解的目標(biāo)是使得在最短的時(shí)間內(nèi)完成任務(wù)。從單個(gè)Agent來看，重建一個(gè)虛擬機(jī)的耗時(shí)包括三個(gè)方面:一是調(diào)度耗時(shí)，二是鏡像傳輸耗時(shí)，三是啟動(dòng)耗時(shí)。其中一包含了控制器轉(zhuǎn)發(fā)請(qǐng)求時(shí)間和選擇合適的宿主機(jī)時(shí)間。這部分耗時(shí)對(duì)于Agent協(xié)商這種模型是不需要控制轉(zhuǎn)發(fā)，也不需要去遍歷所有的宿主機(jī)節(jié)點(diǎn)。針對(duì)第二點(diǎn)，Agent協(xié)商模型中每個(gè)Agent都會(huì)緩存其他Agent的信息，這其中包含啟動(dòng)鏡像的配置文件和鏡像文件，因此傳生成配置文件的時(shí)間為0，啟動(dòng)已經(jīng)緩存過鏡像的虛擬機(jī)鏡像傳輸?shù)暮臅r(shí)為0。針對(duì)第三點(diǎn)，通過實(shí)踐可知，大多數(shù)的虛擬機(jī)化技術(shù)啟動(dòng)一個(gè)虛擬機(jī)的耗時(shí)很少且恒定。雖然Agent協(xié)商模型會(huì)帶來額外的協(xié)商時(shí)間開銷，但是由于組內(nèi)的Agent數(shù)目有限，且合同網(wǎng)協(xié)議處理一個(gè)任務(wù)是一次協(xié)商，而不是多次協(xié)商。因此，Agent協(xié)商耗時(shí)相對(duì)于其節(jié)約的調(diào)度耗時(shí)和鏡像傳輸耗時(shí)要小得多，因此通過理論分析，Agent協(xié)商模型能減小故障恢復(fù)的時(shí)間。

而另一方面，要重建的虛擬機(jī)可能不止一個(gè)，MA在分配任務(wù)時(shí)，讓EA盡可能并行地去處理任務(wù)，從而縮短任務(wù)處理的時(shí)間。在啟動(dòng)虛擬機(jī)時(shí)，鏡像傳輸是最耗時(shí)的一個(gè)環(huán)節(jié)，因此首先將虛擬機(jī)分配給那些不需要傳輸鏡像的Agent。如果任務(wù)沒有分配完成，再將剩下的虛擬機(jī)平均地分配到每個(gè)Agent上，算法保證了每個(gè)EA獲取到任務(wù)量是相等的，下面給出該算法的偽代碼。

算法1 任務(wù)分配算法

輸入數(shù)據(jù)：標(biāo)書列表BidList，要重建的虛擬機(jī)列表VMList。

結(jié)果：任務(wù)分配結(jié)果Result。

0 int Average= VMList.size() / BidList.size();

//每個(gè)Agent平均獲得的任務(wù)數(shù)目

1 /*首先嘗試將任務(wù)分配給不需要傳輸鏡像的Agent*/

1 for ( vmi:VMList ){

2 for ( bidj:BidList ){

3 currentAgent = bidj.agent();

//當(dāng)前報(bào)價(jià)的Agent

4 if( bidj.T_transImage = = 0 )

//已經(jīng)緩存該鏡像

5 if( currentAgent.acceptVm < Average)

//小于平均值

6 Result.add(vmi,currentAgent);

//將vmi分配給currentAgent

7 currentAgent.acceptVm += 1;

8 break;

9 else

//當(dāng)前Agent已經(jīng)獲得的任務(wù)書達(dá)到期望值

10 continue;

//嘗試分配給下一個(gè)Agent

11 }

12 }

13 /*一輪分配后，如果還存在未分配的任務(wù)，則平均分配給每個(gè)Agent*/

14 if( Result.size() < VMList.size() ){

15 List UnallocateVMList;

//沒有分配出去的VM

16 for( bidj:BidList ){

17 currentAgent = bidj.agent();

18 while(currentAgent.acceptVm < Average){

19 vm = UnallocateVMList.take();//分配一個(gè)VM

20 Result.add(vm,currentAgent);

21 currentAgent.acceptVm += 1;

22 }

23 }

24 }

該任務(wù)分配算法，使得整個(gè)任務(wù)平均分?jǐn)傇诿總€(gè)EA上，并且盡可能優(yōu)先考慮最優(yōu)分配。最后MA將計(jì)算出來的最終中標(biāo)結(jié)果發(fā)送個(gè)每一個(gè)EA，中標(biāo)結(jié)果中包含了整個(gè)中標(biāo)結(jié)果。EA收到中標(biāo)結(jié)果后，向MA發(fā)送一個(gè)確認(rèn)回復(fù)，表示接收任務(wù)，即簽訂了合同，并開始執(zhí)行任務(wù)。EA執(zhí)行任務(wù)結(jié)束后將執(zhí)行結(jié)果發(fā)送給MA。MA確定協(xié)商結(jié)果后，將去掉自己的MA角色，并告知其他Agent，任務(wù)處理結(jié)束，系統(tǒng)恢復(fù)正常。

4 仿真實(shí)驗(yàn)

FIPA是Agent領(lǐng)域制定Agent之間互操作標(biāo)準(zhǔn)的國際組織[12]，本文采用JADE進(jìn)行仿真實(shí)驗(yàn)室。JADE是一個(gè)完全由Java語言實(shí)現(xiàn)的Agent開發(fā)框架，它通過中間件的方式實(shí)現(xiàn)符合FIPA規(guī)范的多Agent系統(tǒng)，并支持通過一組圖形工具支持調(diào)試和部署[13]。

4.1 實(shí)驗(yàn)設(shè)計(jì)

以O(shè)penStack云計(jì)算架構(gòu)作為實(shí)驗(yàn)的參考架構(gòu)，OpenStack是一個(gè)由NASA和Rackspace合作并發(fā)起的開源云計(jì)算管理平臺(tái)[14]。OpenStack啟動(dòng)虛擬機(jī)的流程為：控制節(jié)點(diǎn)接收請(qǐng)求，啟用調(diào)度器，調(diào)度器根據(jù)各個(gè)宿主機(jī)的負(fù)載和資源使用情況，在所有的宿主機(jī)集群中選擇合適的宿主機(jī)，并將任務(wù)發(fā)送給計(jì)算節(jié)點(diǎn)的計(jì)算服務(wù)。計(jì)算節(jié)點(diǎn)首先從鏡像服務(wù)器請(qǐng)求鏡像，再調(diào)用底層虛擬機(jī)化軟件啟動(dòng)虛擬機(jī)。

為了便于仿真實(shí)驗(yàn)，定義一些預(yù)設(shè)前置條件：① 宿主機(jī)是同構(gòu)的且物理資源是足夠大的；② 網(wǎng)絡(luò)傳輸?shù)淖畲笏俣葹?000 MB/s，且傳輸鏡像時(shí)以網(wǎng)絡(luò)最大速度傳輸；③ 設(shè)定5種規(guī)格的鏡像文件；④ 以鏡像的最低配置要求啟動(dòng)虛擬機(jī)；⑤ 假設(shè)Agent失效時(shí)，Agent之間已經(jīng)完成了數(shù)據(jù)的同步。如表1所示。

表1 預(yù)設(shè)的鏡像文件列表

現(xiàn)有的調(diào)度策略都是全局類調(diào)度策略，因此設(shè)計(jì)兩個(gè)實(shí)驗(yàn)做對(duì)比:全局調(diào)度類的策略和本文基于組內(nèi)Agent協(xié)商的策略。兩個(gè)實(shí)驗(yàn)啟動(dòng)虛擬機(jī)流程都是模擬OpenStack啟動(dòng)虛擬機(jī)的流程，兩個(gè)實(shí)驗(yàn)假設(shè)都是一個(gè)宿主機(jī)出現(xiàn)故障，針對(duì)兩個(gè)實(shí)驗(yàn)分別構(gòu)造20組實(shí)驗(yàn)，故障宿主機(jī)上運(yùn)行的虛擬機(jī)個(gè)數(shù)從1到20個(gè)。當(dāng)虛擬機(jī)個(gè)數(shù)小于等于鏡像種類時(shí)虛擬機(jī)使用不同的鏡像，當(dāng)虛擬機(jī)個(gè)數(shù)大于鏡像種類時(shí)，隨機(jī)選擇一個(gè)鏡像。本文策略的實(shí)驗(yàn)構(gòu)造一個(gè)Agent Group，當(dāng)Agent之間完成數(shù)據(jù)同步后，通過JADE的GUI界面隨機(jī)殺死一個(gè)Agent，輸出中間的協(xié)商過程，并統(tǒng)計(jì)協(xié)商耗時(shí)、重建虛擬機(jī)耗時(shí)等。

4.2 結(jié)果分析

1) Agent協(xié)商效率分析

本文使用CNP作為協(xié)商的協(xié)議，由于本文改進(jìn)了傳統(tǒng)的CNP協(xié)議，增加了管理Agent選舉的過程，使得整個(gè)協(xié)商過程的耗時(shí)會(huì)增加。為了減少選舉管理Agent的耗時(shí)，本文通過規(guī)定每個(gè)Agent在一次選舉中只能投一次票、投票前的分析等原則使得選舉在一輪即可得到結(jié)果。實(shí)驗(yàn)表明，選舉過程對(duì)協(xié)商過程的協(xié)商效率影響很小，只有在參與協(xié)商的Agent數(shù)目非常多的時(shí)候才會(huì)有明顯的影響。實(shí)際上，參與協(xié)商的Agent處于同一個(gè)組內(nèi)，而每個(gè)組的Agent數(shù)量又是比較小的。所以，增加了選舉過程的CNP協(xié)議在效率上是可以接受的。如圖5所示。

圖5 改進(jìn)的CNP協(xié)商和經(jīng)典的耗時(shí)對(duì)比

2) 恢復(fù)故障的耗時(shí)分析

從實(shí)驗(yàn)結(jié)果可以看出，隨著虛擬機(jī)個(gè)數(shù)的增加，兩種策略的耗時(shí)都在增加，但在一定的范圍內(nèi)本文策略的耗時(shí)是小于全局調(diào)度策略的耗時(shí)。如圖6所示。

圖6 重建虛擬機(jī)耗時(shí)隨著失效Agent運(yùn)行的虛擬機(jī)個(gè)數(shù)的變化曲線

這是因?yàn)锳gent已經(jīng)緩存了數(shù)據(jù)，在重建虛擬機(jī)時(shí)候，不需要傳輸鏡像和重新生成虛擬機(jī)的配置文件，并且任務(wù)分配算法又保證了每個(gè)Agent的任務(wù)是相同的，因此極大提高了處理任務(wù)的并行度。全局調(diào)度的算法在失效Agent運(yùn)行的虛擬機(jī)個(gè)數(shù)達(dá)到鏡像種類個(gè)數(shù)相等的時(shí)候，由于OpenStack在短時(shí)間內(nèi)會(huì)緩存鏡像，所以會(huì)存在一個(gè)拐點(diǎn)。在實(shí)際的云計(jì)算環(huán)境中，一個(gè)宿主機(jī)上運(yùn)行的虛擬機(jī)實(shí)例個(gè)數(shù)是有限個(gè)的且數(shù)目在幾十個(gè)之內(nèi)。因此，本文的策略在實(shí)際的環(huán)境中是有效的。

5 結(jié) 語

從仿真實(shí)驗(yàn)可以得出，提出的基于Agent協(xié)商的容錯(cuò)策略是可行的。它具備以下的優(yōu)點(diǎn)：① 不額外增加宿主機(jī),減小了資源浪費(fèi)；② 容錯(cuò)機(jī)制作用在Agent組內(nèi)，策略收斂速度較全局調(diào)度策略快。

[1] 林利, 石文昌. 構(gòu)建云計(jì)算平臺(tái)的開源軟件綜述[J]. 計(jì)算機(jī)科學(xué), 2012, 39(11):1-7,28.

[2] 陳康, 鄭緯民. 云計(jì)算：系統(tǒng)實(shí)例與研究現(xiàn)狀[J]. 軟件學(xué)報(bào), 2009, 20(5):1337-1348.

[3] Tchana A, Broto L, Hagimont D. Approaches to cloud computing fault tolerance[C]//Computer, Information and Telecommunication Systems (CITS), 2012 International Conference on. IEEE, 2012:1-6.

[4] Wang J, Zhu X, Bao W. Real-Time Fault-Tolerant Scheduling Based on Primary-Backup Approach in Virtualized Clouds[C]// High Performance Computing and Communications & 2013 IEEE International Conference on Embedded and Ubiquitous Computing (HPCC_EUC), 2013 IEEE 10th International Conference on. IEEE, 2013:1127-1134.

[5] Nogueira R, Araujo F, Barbosa R. CloudBFT: Elastic Byzantine Fault Tolerance[C]//2014 IEEE 20th Pacific Rim International Symposium on Dependable Computing (PRDC). IEEE Computer Society, 2014:180-189.

[6] Microsoft. Windows azure: Microsoft's cloud services platform[EB/OL]. http://www.microsoft.com/windowsazure/.

[7] Bakshi K. Cisco cloud computing-data center strategy, architecture, and solutions point of view white paper for U.S. public sector[EB/OL]. http://www.cisco.com/web/strategy/docs/gov/CiscoCloudComputing WP.pdf.

[8] 黃楠, 劉斌. 多Agent技術(shù)綜述[J]. 微處理機(jī), 2010, 31(2):1-4.

[9] 黃關(guān)山, 徐冬梅. Agent的理論與結(jié)構(gòu)模型分析[J]. 微型機(jī)與應(yīng)用, 2004(2):6.

[10] 徐燕妮. 基于合同網(wǎng)協(xié)議的多Agent協(xié)作技術(shù)研究[D]. 青島：山東科技大學(xué), 2006.

[11] 宋海剛, 陳學(xué)廣. FIPA合同網(wǎng)協(xié)議的一種改進(jìn)方案[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2004, 32(7):31-33.

[12] FIPA. Welcome to FIPA[OL]. http://www.fipa.org/.

[13] JADE. Introduction to Jade[EB/OL]. http://jade.tilab.com/documentation/tutorials-guides/introduction-to-jade/.

[14] OpenStack. Document for Mitaka[EB/OL]. http://docs.openstack.org.

FAULT TOLERANCE STRATEGY BASED ON AGENT NEGOTIATION IN A CLOUD ENVIRONMENT

Zhang Kaixuan Gu Chunhua Wan Feng

(CollegeofInformationScienceandEngineering,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

In the cloud computing platform,a large number of low-cost devices are used,which greatly increases the failure probability of host computers.To deal the problem of virtual machine instance failure caused by host failure,a kind of fault tolerant strategy of host is proposed.The virtual machines are rebuilt in each group using Agent negotiation by clustering,grouping and Agent modeling the host computers.The simulation experiment shows that the proposed method is able to rebuild the disabled virtual machine instances automatically,and take less time than other strategies.

Cloud Host Agent negotiation Fault tolerance

2015-10-12。張凱旋，碩士生，主研領(lǐng)域：云計(jì)算方向。顧春華，教授。萬峰，高工。

TP3

A

10.3969/j.issn.1000-386x.2017.01.005