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

王清雲(yún) 邵清

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

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

DOI：10. 11907/rjdk. 181553

中圖分類號：TP312文獻標識碼：A文章編號：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 引言

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

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

1 系統(tǒng)建模

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

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

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

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

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

2.1 算法描述

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

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

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

2.2 算法流程

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

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

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

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

3 實驗結(jié)果

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

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

4 結(jié)語

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

參考文獻：

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

[2] 廖福蓉，王成良，陳蜀宇. 基于任務(wù)備份的云計算容錯調(diào)度算法[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)中基于主/副版本的實時容錯調(diào)度綜述[J]. 計算機應(yīng)用研究，2012，29（11）：4017-4022.

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

[7] 馬俊濤，陳業(yè)恩，胡國杰，等. 云計算環(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時隙分配對業(yè)務(wù)時延性能的影響分析[J]. 電子學(xué)報，2009，37（10）：2277-2283.

[10] 王吉，包衛(wèi)東，朱曉敏. 虛擬化云平臺中實時任務(wù)容錯調(diào)度算法研究[J]. 通信學(xué)報，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] 查英華， 楊靜麗. 改進蟻群算法在云計算任務(wù)調(diào)度中的應(yīng)用[J]. 計算機工程與設(shè)計， 2013， 34（5）：1716-1719.

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