云環(huán)境下基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)研究

王清雲(yún) 邵清

摘 要：云計(jì)算環(huán)境下信息處理會(huì)產(chǎn)生海量而又至關(guān)重要的中間數(shù)據(jù)，服務(wù)器如果失效會(huì)導(dǎo)致中間數(shù)據(jù)丟失。可靠性保障能力不足不僅是云計(jì)算應(yīng)用推廣的主要障礙，而且還促使云計(jì)算環(huán)境下的容錯(cuò)技術(shù)研究成為一個(gè)亟待解決的問(wèn)題。針對(duì)目前云計(jì)算環(huán)境下容錯(cuò)效率低、計(jì)算資源浪費(fèi)等問(wèn)題，提出基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)，利用任務(wù)重新提交、檢查點(diǎn)技術(shù)和資源執(zhí)行歷史記錄等方法，減少任務(wù)執(zhí)行和處理時(shí)間，提高云計(jì)算成功率。實(shí)驗(yàn)結(jié)果表明，該技術(shù)改進(jìn)了任務(wù)重新提交、檢查點(diǎn)和擴(kuò)展信息素更新公式，在任務(wù)分配和重新提交過(guò)程中，明顯縮短了任務(wù)平均執(zhí)行時(shí)間，提高了執(zhí)行成功率。

關(guān)鍵詞：云計(jì)算;容錯(cuò)算法;蟻群算法;檢查點(diǎn)技術(shù)

DOI：10. 11907/rjdk. 181553

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）001-0073-04

Abstract： In the process of information processing in the cloud computing environment， massive and crucial intermediate data will be generated. If the server fails， it will lead to the loss of intermediate data. The lack of reliability guarantee capability will not only become a major obstacle to the promotion and application of cloud computing， but also induce the research of fault-tolerant technology in the cloud computing environment to become a problem demanding prompt solution. To solve the problems of low error efficiency and waste of computing resources in cloud computing environment， this paper proposes a dynamic fault tolerance technology based on ant colony algorithm， using tasks to resubmit new resources， checkpoint technology and resource execution history records to reduce tasks. Execution and processing time improve the success rate of the cloud computing environment. Experimental results show that the proposed algorithm improves task resubmission， checkpoints， and extended pheromone update formulas. In task allocation and resubmission， the average execution time of tasks is significantly shortened and the task execution success rate is improved.

0 引言

云計(jì)算是一個(gè)熱門研究方向，許多企業(yè)都相繼開發(fā)出自己的云端系統(tǒng)進(jìn)行運(yùn)算與研究。然而，只要是計(jì)算機(jī)就會(huì)發(fā)生錯(cuò)誤[1]。在云計(jì)算中由于資源的高度動(dòng)態(tài)性和異構(gòu)性，使云計(jì)算平臺(tái)較傳統(tǒng)計(jì)算平臺(tái)出錯(cuò)幾率更高[2]。為減少發(fā)生錯(cuò)誤所造成的損失，需要容錯(cuò)機(jī)制保證系統(tǒng)在故障情況下也能持續(xù)運(yùn)行[3]。容錯(cuò)包括故障檢測(cè)或識(shí)別、故障預(yù)測(cè)和故障恢復(fù)3個(gè)策略。故障檢測(cè)或識(shí)別通常用于檢測(cè)故障類型，然后用最合適的方案進(jìn)行故障診斷。故障預(yù)測(cè)側(cè)重于根據(jù)歷史數(shù)據(jù)預(yù)測(cè)故障發(fā)生的概率，并應(yīng)用合適的調(diào)度策略降低故障概率。故障恢復(fù)常用技術(shù)有作業(yè)復(fù)制和檢查點(diǎn)[4]。作業(yè)復(fù)制的優(yōu)點(diǎn)是不需要重新計(jì)算，因?yàn)槊總€(gè)作業(yè)都會(huì)同時(shí)分配給不同資源的多個(gè)副本，如果其中一個(gè)失敗，其它作業(yè)副本仍然可以處理[5]。但是，這種技術(shù)不是很有效，因?yàn)樽鳂I(yè)的副本單獨(dú)執(zhí)行可能會(huì)占用作業(yè)隊(duì)列。檢查點(diǎn)是另一種技術(shù)，它要求將運(yùn)行任務(wù)的狀態(tài)存儲(chǔ)在一個(gè)已定義的檢查點(diǎn)上。如果作業(yè)執(zhí)行失敗，則從最后一次保存的狀態(tài)重新啟動(dòng)任務(wù)執(zhí)行而不是從頭開始，這樣可極大地節(jié)省任務(wù)執(zhí)行時(shí)間。

針對(duì)云計(jì)算容錯(cuò)技術(shù)，國(guó)內(nèi)外學(xué)者進(jìn)行了相應(yīng)研究，提出了許多算法：文獻(xiàn)[6]提出了周期任務(wù)模型的容錯(cuò)調(diào)度算法，但是該模型要求所有任務(wù)的周期完全相同，文獻(xiàn)[7] 研究了動(dòng)態(tài)實(shí)時(shí)調(diào)度算法與速率單調(diào)算法。文獻(xiàn)[8]討論帶固定優(yōu)先級(jí)實(shí)時(shí)調(diào)度算法，這些算法均沒有考慮系統(tǒng)的容錯(cuò)問(wèn)題。文獻(xiàn)[9]針對(duì)當(dāng)前計(jì)算機(jī)系統(tǒng)計(jì)算和存儲(chǔ)資源豐富但并行文件系統(tǒng)寫帶寬提高相對(duì)滯后的特點(diǎn)，提出了基于內(nèi)存緩存的異步檢查點(diǎn)容錯(cuò)技術(shù)。文獻(xiàn)[10]提出了一種主備份的容錯(cuò)調(diào)度策略用于對(duì)宿主機(jī)的錯(cuò)誤容忍，其使用主從宿主機(jī)結(jié)構(gòu)，需要設(shè)置多個(gè)宿主機(jī)作為備份宿主機(jī)，對(duì)宿主機(jī)資源浪費(fèi)比較嚴(yán)重。文獻(xiàn)[11]提出了增強(qiáng)型蟻群優(yōu)化算法（Enhanced Ant Colony Optimization， EACO），根據(jù)任務(wù)和資源數(shù)量引入動(dòng)態(tài)蒸發(fā)速率確定信息素蒸發(fā)速率，確保每個(gè)資源處理的任務(wù)數(shù)量很多時(shí)蒸發(fā)率很小，否則蒸發(fā)率會(huì)很高，實(shí)驗(yàn)結(jié)果表明控制蒸發(fā)率可有效平衡所有資源的負(fù)載。文獻(xiàn)[12]提出了基于信任的蟻群優(yōu)化調(diào)度算法（Trust-based Ant Colony Optimization，TACO），旨在盡量減少作業(yè)完成時(shí)間，平衡所有可用資源的工作量，同時(shí)引入面向資源的信任機(jī)制處理資源故障問(wèn)題。文獻(xiàn)[13]通過(guò)ACS算法和有向無(wú)環(huán)圖（DAG）方法相結(jié)合，提出了一種新的云計(jì)算故障管理算法，該算法可提供有效的資源分配但沒有恢復(fù)操作。文獻(xiàn)[14]提出基于遺傳算法（Genetic Algorithm，GA）的混合蟻群優(yōu)化算法，以克服元啟發(fā)式算法不受控制的性質(zhì)，但會(huì)降低云計(jì)算分配性能。文獻(xiàn)[15]提出在云計(jì)算中使用檢查點(diǎn)的容錯(cuò)蟻群優(yōu)化算法（Fault Tolerance ACO，F(xiàn)TACO），有效利用云計(jì)算中的動(dòng)態(tài)資源解決故障和負(fù)載平衡問(wèn)題。文獻(xiàn)[16]提出了使用蟻群優(yōu)化算法進(jìn)行云計(jì)算的容錯(cuò)作業(yè)調(diào)度以滿足服務(wù)質(zhì)量需求，該服務(wù)使用資源失敗率和基于檢查點(diǎn)的回滾恢復(fù)策略。在任務(wù)執(zhí)行期間，故障索引管理器將不斷與檢查點(diǎn)處理程序交互以記錄資源故障率，每發(fā)生一次故障，都將應(yīng)用回滾恢復(fù)技術(shù)以節(jié)省執(zhí)行時(shí)間，該算法減少了任務(wù)總執(zhí)行時(shí)間，提高了吞吐量和平均周轉(zhuǎn)時(shí)間。

1 系統(tǒng)建模

蟻群優(yōu)化算法是一種生物啟發(fā)式算法，為求解優(yōu)化問(wèn)題和設(shè)計(jì)元啟發(fā)式算法提供一個(gè)自適應(yīng)概念[17]。蟻群優(yōu)化算法在處理調(diào)度和負(fù)載均衡時(shí)非常有效，且在查找最佳路徑過(guò)程中出現(xiàn)故障時(shí)可構(gòu)建替代路徑，圖1為蟻群在查找最佳路徑期間出現(xiàn)故障最終找到替代路徑的例證[18]。

流程如下：①通過(guò)蟻群1建立最優(yōu)資源a的路徑路線;②資源a執(zhí)行任務(wù)失敗，重新調(diào)用提交流程;③通過(guò)蟻群1建立替代資源b的新路徑，并完成任務(wù)的提交和處理;④從不同來(lái)源的蟻群2選擇由前一個(gè)蟻群1構(gòu)造的最優(yōu)路徑分配下一個(gè)任務(wù)。

本文受蟻群尋找最適合資源的最佳路徑概念啟發(fā)，基于此概念進(jìn)一步擴(kuò)展，提出基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)（Dynamic ACS-based Fault Tolerance， DAFT），使蟻群能夠在重新提交任務(wù)過(guò)程中執(zhí)行資源研究，以確保任何執(zhí)行失敗的任務(wù)都被完全處理。此外，進(jìn)一步改進(jìn)信息素更新技術(shù)，作為一種懲罰失敗的資源機(jī)制，使其不那么有吸引力以最終減少失敗的可能性，并根據(jù)資源適當(dāng)控制任務(wù)分配。

基于蟻群算法的動(dòng)態(tài)容錯(cuò)算法對(duì)每個(gè)任務(wù)都會(huì)生成一個(gè)蟻群，根據(jù)信息素值選擇執(zhí)行資源。初始化的信息素值首先被啟動(dòng)，以確定所有資源的狀態(tài)，然后提交隊(duì)列中的第一個(gè)任務(wù)。資源的選擇是基于信息素初始計(jì)算或信息素更新過(guò)程的信息素值的量。在執(zhí)行過(guò)程中，每個(gè)任務(wù)被分成幾個(gè)檢查點(diǎn)，這些檢查點(diǎn)將按順序處理以保持輸出的真實(shí)性。如果任務(wù)執(zhí)行成功，蟻群會(huì)更新全局信息素再執(zhí)行后增加的信息素;但是，如果在執(zhí)行過(guò)程中出現(xiàn)任何故障，最后一個(gè)檢查點(diǎn)將重新提交給另一個(gè)合適的資源，并且會(huì)更新本地信息素，此外每個(gè)成功的檢查點(diǎn)還將更新本地信息素。最后，資源將與更新的信息素一起發(fā)布，用于下一個(gè)任務(wù)分配。利用重新提交的新資源、檢查點(diǎn)技術(shù)和資源執(zhí)行歷史記錄的方法，減少任務(wù)執(zhí)行和處理時(shí)間，提高云計(jì)算環(huán)境的成功率。

2 基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)

2.1 算法描述

在初始任務(wù)期間，每個(gè)資源應(yīng)具有預(yù)定義的參數(shù)，例如處理器速度、當(dāng)前負(fù)載和帶寬以及處理元素的數(shù)量，所有這些參數(shù)將用來(lái)計(jì)算初始的信息素值，[PVij] 用于每個(gè)資源[i]和任務(wù)[j]的組合。 初始信息素值由公式（1）給出。

假定所有資源都是相互關(guān)聯(lián)的，這意味著如果任務(wù)來(lái)自特定資源，那么它就可以分配給所有可用的資源。[PVmatrix] 中的每一行都列出了資源[i]的可能任務(wù)列表，任務(wù)[j]的可能資源列表。

每列中最大的信息素值被蟻群視為最適合的資源，并且該任務(wù)分配給選定索引所引用的資源進(jìn)行處理。 一旦任務(wù)被分配，相應(yīng)[PVmatrix]中的信息素值將根據(jù)公式（3）更新全局信息素，以減少分配給當(dāng)前資源的信息素量，使它變得對(duì)下一個(gè)蟻群不具有吸引力，讓其探索其它資源。

2.2 算法流程

圖2為DAFT算法流程，實(shí)現(xiàn)步驟如下：

（1）初始化。配置所有參數(shù)，根據(jù)公式（1）計(jì)算每個(gè)資源的初始化信息素值，為每項(xiàng)任務(wù)生成一個(gè)單獨(dú)的蟻群，在第一次迭代中確定具有最高初始信息素的資源。

（2）開始循環(huán)。根據(jù)蟻群優(yōu)化算法思想確定最適合的資源，然后發(fā)出任務(wù)提交信號(hào)，通過(guò)公式（3）更新全局信息素的值，確實(shí)任務(wù)是否完成。如果任務(wù)完成則結(jié)束，否則繼續(xù)判斷任務(wù)執(zhí)行狀態(tài)。如果任務(wù)執(zhí)行成功就保存檢查點(diǎn)，增加成功計(jì)數(shù)，并根據(jù)公式（1）-公式（5）更新局部信息素值。如果任務(wù)執(zhí)行失敗，則檢索最后一個(gè)檢查點(diǎn)，重新提交，增加失敗計(jì)數(shù)，并根據(jù)公式（5）更新局部信息素，重復(fù)步驟（2）操作。

（3）任務(wù)狀態(tài)。任務(wù)完成時(shí)，終止執(zhí)行。

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證本文的DAFT算法性能，定義平均成功率為70%（0.7），誤差范圍用標(biāo)準(zhǔn)偏差±0%（0.0）～±30%（0.3）表示。使用具有標(biāo)準(zhǔn)偏差的偽隨機(jī)算法分配成功率，在初始化過(guò)程中定義每個(gè)單獨(dú)資源范圍。每種資源具有不同的成功率，且這些信息在資源分配期間不被蟻群知道。為確保實(shí)驗(yàn)的可靠性，每個(gè)資源都設(shè)置為具有相同的處理能力，參數(shù)如表1所示。

在云計(jì)算環(huán)境中，除了處理能力之外，每個(gè)可用資源都具有不同的適應(yīng)性。在這種情況下，可使用最小和最大適應(yīng)值形成適應(yīng)范圍。實(shí)驗(yàn)結(jié)果表明，啟發(fā)式能夠改善任務(wù)分配過(guò)程并最終提高云計(jì)算環(huán)境性能。隨著執(zhí)行深入，成功和失敗的次數(shù)被記錄并最終影響資源信息素值的蒸發(fā)。可根據(jù)資源適應(yīng)度動(dòng)態(tài)分配任務(wù)，如資源的成功率為0%，則分配給它的任務(wù)量最少。另一方面，如果資源的成功率非常高，則會(huì)分配最多的任務(wù)。除了在調(diào)度或重新提交過(guò)程中考慮資源適應(yīng)性以外，檢查點(diǎn)還允許從最后保存的狀態(tài)重新提交失敗的任務(wù)，這大大減少了處理時(shí)間，因?yàn)槿蝿?wù)不需要從頭開始。

4 結(jié)語(yǔ)

為了提高云計(jì)算容錯(cuò)性能，本文提出在云環(huán)境下基于蟻群算法的動(dòng)態(tài)容錯(cuò)技術(shù)，利用檢查點(diǎn)回滾技術(shù)消除從一開始就重新啟動(dòng)任務(wù)，減少了任務(wù)總執(zhí)行時(shí)間，提高了吞吐量和平均周轉(zhuǎn)時(shí)間。在資源分配期間，根據(jù)其適合度通過(guò)蟻群算法的啟發(fā)式能力選擇最佳資源，不但減少了每個(gè)任務(wù)的處理時(shí)間，還提高了云計(jì)算環(huán)境的成功率。與TACO算法和FTACO算法進(jìn)行比較，仿真結(jié)果表明，本文方法在容錯(cuò)性上明顯優(yōu)于TACO算法和FTACO算法，最大限度提高了云環(huán)境下的容錯(cuò)性能。但是，在任務(wù)調(diào)度過(guò)程中，保存檢查點(diǎn)的數(shù)量太多會(huì)加大數(shù)據(jù)量計(jì)算，因此如何控制保存檢查點(diǎn)數(shù)量是后續(xù)研究目標(biāo)。

參考文獻(xiàn)：

[1] 梁健. 基于云平臺(tái)的虛擬機(jī)容錯(cuò)技術(shù)概述[J]. 青年時(shí)代， 2016（12）：109-110.

[2] 廖福蓉，王成良，陳蜀宇. 基于任務(wù)備份的云計(jì)算容錯(cuò)調(diào)度算法[J]. 計(jì)算機(jī)工程，2012， 38（24）：17-20.

[3] PAWGASAME？W，SA-AD W. Self-organized TDMA protocol for tactical data links[M]. Linkoping： Linkoping University，2011.

[4] ALTAMEEM T. Fault tolerance techniques in grid computing systems[J]. Comp. Sci. Inform，2013（4）：858-862.

[5] 陳晗鳴，羅威，李明輝. 分布式系統(tǒng)中基于主/副版本的實(shí)時(shí)容錯(cuò)調(diào)度綜述[J]. 計(jì)算機(jī)應(yīng)用研究，2012，29（11）：4017-4022.

[6] 秦嘯，韓宗芬，龐麗萍. 基于異構(gòu)分布式系統(tǒng)的實(shí)時(shí)容錯(cuò)調(diào)度算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2002，25（1）：49-56.

[7] 馬俊濤，陳業(yè)恩，胡國(guó)杰，等. 云計(jì)算環(huán)境下基于遺傳算法的任務(wù)調(diào)度技術(shù)研究[J]. 軟件導(dǎo)刊，2016，15（1）：51-53.

[8] SAMAL A K，MALL R，TRIPATHY C. Fault tolerant scheduling of hard real-time tasks on multiprocessor system using a hybrid genetic algorithm[J]. Swarm & Evolutionary Computation，2014（14）：92-105.

[9] 秦勇，張軍，張濤. TDMA時(shí)隙分配對(duì)業(yè)務(wù)時(shí)延性能的影響分析[J]. 電子學(xué)報(bào)，2009，37（10）：2277-2283.

[10] 王吉，包衛(wèi)東，朱曉敏. 虛擬化云平臺(tái)中實(shí)時(shí)任務(wù)容錯(cuò)調(diào)度算法研究[J]. 通信學(xué)報(bào)，2014，35（10）：171-180.

[11] KU-MAHAMUD K R，DIN A M，NASIR H J A. Enhancement of ant colony optimization for grid load balancing[J]. European Journal of Scientific Research， 2011（5）：1541-1560.

[12] HUANG W， DENG Z， WEN P. Trust-based ant colony optimization for grid resource scheduling[C]. Third International Conference on Genetic and Evolutionary Computing，IEEE Computer Society， 2009：288-292.

[13] MODIRI V， ANALOUI M， JABBEHDARI S. Fault tolerance in grid using ant colony optimization and directed acyclic graph[J]. Grid Comp， 2011（2）：14-26.

[14] MANDLOI S， GUPTA H. Adaptive job scheduling for computational grid based on ant colony optimization with genetic parameter selection[J]. International Journal of Advanced Computer Research， 2013， 3（9）：64-69.

[15] PRASHAR T，NANCY N，KUMAR D. Fault tolerant ACO using checkpoint in grid computing[J]. International Journal of Computer Applications， 2014， 98（10）：44-49.

[16] IDRIS H， EZUGWU A E， JUNAIDU S B， et al. An improved ant colony optimization algorithm with fault tolerance for job scheduling in grid computing systems[J]. Plos One， 2017， 12（5）：177-576.

[17] DORIGO M， BIRATTARI M， STUTZLE T. Ant colony optimization[J]. IEEE Computational Intelligence Magazine，2007，1（4）：28-39.

[18] FERDAUS M H， MURSHED M， CALHEIROS R N， et al. Virtual machine consolidation in cloud data centers using ACO metaheuristic[C]. European Conference on Parallel Processing. Springer International Publishing， 2014：306-317.

[19] BUYYA R， RANJAN R， CALHEIROS R N. Modeling and simulation of scalable cloud computing environments and the cloudSim toolkit： challenges and opportunities[C]. International Conference on High PERFORMANCE Computing & Simulation，IEEE， 2009：1-11.

[20] 查英華， 楊靜麗. 改進(jìn)蟻群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用[J]. 計(jì)算機(jī)工程與設(shè)計(jì)， 2013， 34（5）：1716-1719.

（責(zé)任編輯：杜能鋼）