王清雲(yún) 邵清

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

關鍵詞：云計算;容錯算法;蟻群算法;檢查點技術

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

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

1 系統(tǒng)建模

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

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

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

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

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

2.1 算法描述

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

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

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

2.2 算法流程

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

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

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

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

3 實驗結果

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

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

4 結語

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

參考文獻：

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

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

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

[7] 馬俊濤，陳業(yè)恩，胡國杰，等. 云計算環(huán)境下基于遺傳算法的任務調度技術研究[J]. 軟件導刊，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è)務時延性能的影響分析[J]. 電子學報，2009，37（10）：2277-2283.

[10] 王吉，包衛(wèi)東，朱曉敏. 虛擬化云平臺中實時任務容錯調度算法研究[J]. 通信學報，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]. 計算機工程與設計， 2013， 34（5）：1716-1719.

（責任編輯：杜能鋼）