云環境下基于蟻群算法的動態容錯技術研究

　　引言

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

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

 　1 系統建模

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

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

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

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

　　2 基于蟻群算法的動態容錯技術

　　2.1 算法描述

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

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

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

　　2.2 算法流程

　　圖2為daft算法流程，實現步驟如下：

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

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

　　（3）任務狀態。任務完成時，終止執行。

　　3 實驗結果

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

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

　　4 結語

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