分布式網頁內容安全監測系統任務調度方法

陳 超，李柏巖，劉曉強，馮珍妮

(東華大學 計算機科學與技術學院，上海 201620)

0 引言

近年來，隨著云計算技術的日益成熟，越來越越多的應用系統被以各種方式部署到云平臺。云服務器一般按實際使用資源來計費，可動態擴展和縮減，為充分利用購買的計算資源，節省計算成本，需要對應用系統的任務進行合理調度，使服務器負載均衡，并對應用系統隨著應用規模擴展對使用云資源的需求進行預測。

開放網絡環境下的分布式系統往往采用松耦合的面向服務的（Service-Oriented Architecture，SOA）架構，將復雜應用按照功能特點劃分為不同的服務，這些服務是一些粗粒度并且可以被調用的軟件實體，具有高可用性、擴展性和重用性特征。這樣的結構允許系統的組件按需部署。在大型系統中，隨著系統業務和用戶的不斷增加，系統的任務數量也會增多，分布式的任務處理架構在使系統提高并發性、可擴展性、容錯性的同時，也會產生因負載不均而導致的資源浪費問題。為保證系統的工作效率，最大限度地利用計算機資源，應用系統自身也需根據實際情況進行合理的任務調度。

任務調度是分布式系統的一個基本問題，而且一般形式下的任務調度是一個 NP完全問題（Non-deterministic Polynomial，NP），學者對此進行過大量的研究工作。參考文獻[1]使用改進蟻群算法對Storm任務調度進行優化，并通過實驗證明改進后的調度方法在算法效率上相比 Storm默認的輪詢調度算法得到了大幅的提高；參考文獻[2]采用隨機森林分類器將任務按照執行時長進行分類，再使用粒子群優化算法對問題進行優化，不僅均衡了計算節點的CPU和內存的利用率，還對任務完成時間進行了優化，減少了任務完成的總體時間；參考文獻[3]針對定時任務在未來一段時間內產生的負載，提出了靜態調度的可行性，并基于遺傳算法設計了一種適用于定時任務的負載均衡算法；參考文獻[4]針對蟻群算法在進行任務調度時，存在收斂速度慢，局部搜索能力差以及容易陷入局部最優等問題，結合了模擬退火算法，利用模擬退火算法較強的局部搜索能力，實現一種能有效減少任務完成時間以及保證資源負載均衡的任務調度算法；參考文獻[5]先用模糊 C均值聚類將任務分類，再用min-min算法進行任務調度，減少了任務完成時間；參考文獻[6]采用粒子群優化算法結合遺傳算法，實現了粒子群優化算法對離散問題的求解能力，并通過離散改進后的粒子群算法求解模糊柔性作業車間的多目標調度，在保留調度算法多樣性的同時，降低了算法后期陷入局部最優解的概率。

本文研究一個分布式網頁內容安全監測系統的任務調度優化問題，針對系統任務完成時間的實時性約束，提出了一種改進粒子群優化算法并結合遺傳算法解決了系統任務調度優化問題，并通過實驗證實所提出的調度策略有較好的負載均衡度及較短的優化完成時間。

1 網頁內容安全監測系統的任務調度問題

網頁內容安全監測系統是一個部署在云平臺上，為目標網站群提供實時安全監測服務的分布式應用系統。它定時掃描目標客戶網站，對網站中所有網頁進行分析，檢測網頁是否可用，是否被篡改，以及是否出現違規詞、敏感詞、敏感圖片等，并對網站出現的異常情況進行預警提示[7]。系統的監測分析任務如圖1所示，主要包括網站存活監測、網站爬蟲、網站解析、網頁變更監測、違規詞監測、違規圖片監測、敏感信息監測以及預警處理等。除了爬蟲任務要稍微提前外，系統中的每項任務基本上互不影響，獨立工作。

圖1 網頁內容安全監測系統任務調度示意圖Fig.1 Schematic diagram of task scheduling of web content security monitoring system

網頁內容安全監測系統的幾乎所有的監測任務都是定時觸發的，任務的啟動頻率由客戶自行選擇。由于客戶較多，而且每個客戶一般有多個網站需要監測，因此系統同時監測的目標網站數量很大，網頁數量十分龐大。隨著監測網站數量的增加，系統并發運行的任務數會急劇增長。為了能夠在第一時間發現網站的問題，及時進行處理，監測系統必須在限定時間內完成每個網站的監測任務，對發現的問題及時進行報告。因此，對系統進行合理的任務調度，不同的任務負載均衡地分配到現有的服務器，保障現有資源能夠被充分利用。

2 監測系統的任務調度解決方案

2.1 監測任務整合

由于監測系統的核心任務都是周期性定時觸發的，在運行環境和監測目標不變的情況下，產生的任務數量與執行時間基本穩定。為減少開銷，本文采用靜態調度策略對系統中的任務進行調度。為了掌握任務的基本信息，本文首先對各種任務的資源占用情況進行了多次測量，并計算出各任務平均用時，如表1所示。其中，違規詞監測、違規詞監測、敏感詞監測、網站爬蟲以及網頁變更監測是針對網站所有頁面，故處理時間為處理每個頁面所需的平均時間，網站存活檢測和網站信息獲取只針對主頁。測量在多個相同參數配置的租用服務器上進行，得到相近的結果。

表1 任務平均資源消耗表Tab.1 Task average resource consumption table

對于監測系統中的每個目標網站，系統每次檢測都會產生7個任務（見表1）。由于要監測網站數量龐大，每日要監測多次，所以產生的任務數量十分巨大，調度算法進行優化時所需的計算量也會很大。為此，本文將一段時間內的同一種類任務合并，不但能簡化調度的難度，還能減少調度的次數。這里之所以能進行“歸并”是因為同一種任務即便針對不同網站，其所需的計算資源也大致相同，歸并之后可以將它們看成一個任務在時間上的拉長。

對每類業務做“歸并”，將同類任務按時間段分段歸并，稱為“歸并任務”，記為 Task。第 j個歸并任務taskj用向量表示為：

2.2 監測任務調度

2.2.1 監測任務調度定義

任務調度就是將系統任務集里的任務以某種策略合理地分配到各分布式計算節點上進行處理，并以任務資源利用率、可靠性和負載均衡等指標作為調度目標[8]。本調度問題有以下具體約束：

①每臺服務器所有并發Task所需 CPU資源總和不大于服務器CPU資源上限。

②每臺服務器所有并Task所需內存資源總和不大于服務器內存資源上限。

③每臺服務器所有Task完成時間不大于Φ。

對于系統中的m個Task，其調度向量可表示為：

D=[s1,s2,…,sm]

其中sj(j=1,2,…,m)為服務器編號。如D=[1，3，1，2]表示為task1分配給服務器1，task2分配給服務器 3，task3分配給服務器 1，task4分配給服務器 2。有了任務調度向量，下面定義評價指標，建立調度優劣的評價標準。

定義2.n臺服務器機組的平均資源利用率：

定義3.服務器機組的負載均衡度：

當 LD越大時，服務器機組的負載均衡度越高，調度策略越優秀。

2.2.2 監測任務調度算法

粒子群優化算法（Particle Swarm Optimization，PSO）是一種優化計算的技術[9-11]，它通過模擬鳥群合作尋找食物的過程，快速地搜索最優解，常用來優化調度策略。PSO算法參數簡單、收斂速度快。算法隨機生成初始化粒子群，粒子有兩個屬性：速度和位置，每個粒子代表了一種解的可能并對應一個適應值。在搜尋過程中每個粒子有著個體最優化位置，粒子群有全局最優位置，每個粒子根據個體最優位置和全局最優位置更新自己的速度和位置。其更新公式如下：

由式（4）及（5）可知PSO算法可用于求解連續優化問題，而本文調度問題明顯是一離散優化問題，需對算法進行離散化改進，使其能夠解決離散型問題。

本文的調度算法是為求解調度向量 D，由于廣義的PSO算法并不合適解決離散問題，故將遺傳（Genetic Algorithm，GA）算法中的交叉和變異操作引入PSO算法來重構其速度和位置的更新算法[12-14]，不但能解決不適合應用于離散優化的問題，同時利用GA算法提高了算法迭代到后期的多樣性[15]。改進離散PSO算法如下所示：

離散PSO算法更新過程如下：

輸入：迭代次數G，參數c1,c2，粒子群數N

輸出：全部迭代完成后的全局最優位置gg

2.3 算法步驟

本文任務調度算法的具體步驟如下：

①進行任務“歸并”，得到任務集合。

②設置PSO算法所需參數：迭代次數G，參數c1,c2，粒子群個數N，服務器數量（即PSO算法位置邊界）。

③初始化N個粒子位置xi，粒子速度v，計算每個粒子對應的適應值，更新個體歷史最優位置以及全局最優位置。

④根據粒子群更新算法更新每個粒子的位置與速度，重新計算每個粒子對應的適應值，更新個體歷史最優位置以及全局最優位置。

⑤達到最大迭代次數，返回全局最優位置，否則回到步驟④。

⑥對得到的最優位置進行評價，符合約束，輸出調度策略，否則，服務器數量+1，返回步驟③。

3 實驗與分析

3.1 任務調度算法實驗

本文通過開源仿真平臺Cloudsim進行仿真實驗，對比了 GA算法以及蟻群（Ant Colony Optimization，ACO）算法，就任務調度算法完成時間，調度策略的負載均衡度兩方面，分析了三種任務調度算法的優劣。PSO-GA算法、GA算法、ACO算法的相關參數設置分別如表2、表3以及表4所示。

表2 PSO-GA 相關參數Tab.2 PSO-GA related parameters

表3 GA 相關參數Tab.3 GA related parameters

表4 ACO 相關參數Tab.4 ACO related parameters

實驗中設定的任務數從20個逐漸遞增到160個，每種情況實驗20次，取測試結果的平均值。基于PSO-GA算法，GA算法以及ACO算法對任務調度優化完成所需時間以及任務調度負載均衡度分別如圖2，圖3所示。

圖2 任務調度所需時間Fig.2 Time required for task scheduling

圖3 任務調度負載均衡度Fig.3 Task scheduling load balance

從圖2可知，三種算法中，GA算法所需計算時間最多，本文算法和 ACO算法則相差不多，GA算法所需時間遠超其他兩者因在實現時，該算法有對基因DNA有編碼和解碼過程，增加了計算量。三種算法所需時間大體與任務數量成正比。

從圖3可知，隨著任務數從20個逐步增加到160個，三種算法的負載均衡度波動最大不超過0.15，其中ACO算法結果最不理想，而本文離散改進的PSO算法最優，最大波動僅為0.02。在有限的迭代次數中，本文提出算法相較于其他兩種算法有著更為優秀的收斂速度以及尋優能力。

3.2 服務器需求分析

本文網頁內容安全監測系統的業務針對的是用戶指定的某個網站，然而不同的網站所包含的網頁數量各不相同，系統運行時需對每個頁面進行監測，這也導致了同樣的業務對不同網站所消耗的計算資源截然不同。對國內三十余所211高校的主站進行3層爬取所獲取的網頁數量進行統計，將數據進行ks檢驗，計算出其D值為0.16，P值為 0.33，故而可知高校網站的網頁數量服從均值131.59，標準差44.21的正態分布。結合表1的任務平均資源消耗表和本文提出的算法，根據正態分布規律模擬出網站情況。觀察在網站數不斷增加時，所需服務器數量的變化，記錄每次服務器增加時網站數量的臨界點。網站數量與所需服務器的關系如下圖4所示。從圖中可知，本網頁內容安全監測系統，大約每增加495個監測網站，就需增加一臺服務器以滿足系統監測的實時性要求。

圖4 監測網站數與服務器數關系圖Fig.4 The relationship between the number of monitored websites and the number of servers

4 總結

本文為了使大規模分布式網頁內容安全監測系統能夠充分利用現有資源，高效穩定地運行，提出了一種可行調度方案，即采用粒子群優化算法結合遺傳算法，在綜合考慮系統負載均衡和任務完成時間的實時性約束后進行系統任務調度優化。通過實驗對比了傳統的遺傳算法以及蟻群算法，實驗表明改進的粒子群優化算法的執行時間短，調度方案負載均衡度更高。本文的任務調度策略現已應用到系統當中，并在實際工作中取得了良好的效果，但本方案尚有不足之處有待改進：其任務調度對象針對的是系統的定時任務，而實際情況中系統還有一些非定時任務，最后得到的調度策略只是近似最優解。