陳 超，李柏巖，劉曉強(qiáng)，馮珍妮

(東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，上海 201620)

0 引言

近年來(lái)，隨著云計(jì)算技術(shù)的日益成熟，越來(lái)越越多的應(yīng)用系統(tǒng)被以各種方式部署到云平臺(tái)。云服務(wù)器一般按實(shí)際使用資源來(lái)計(jì)費(fèi)，可動(dòng)態(tài)擴(kuò)展和縮減，為充分利用購(gòu)買(mǎi)的計(jì)算資源，節(jié)省計(jì)算成本，需要對(duì)應(yīng)用系統(tǒng)的任務(wù)進(jìn)行合理調(diào)度，使服務(wù)器負(fù)載均衡，并對(duì)應(yīng)用系統(tǒng)隨著應(yīng)用規(guī)模擴(kuò)展對(duì)使用云資源的需求進(jìn)行預(yù)測(cè)。

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

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

本文研究一個(gè)分布式網(wǎng)頁(yè)內(nèi)容安全監(jiān)測(cè)系統(tǒng)的任務(wù)調(diào)度優(yōu)化問(wèn)題，針對(duì)系統(tǒng)任務(wù)完成時(shí)間的實(shí)時(shí)性約束，提出了一種改進(jìn)粒子群優(yōu)化算法并結(jié)合遺傳算法解決了系統(tǒng)任務(wù)調(diào)度優(yōu)化問(wèn)題，并通過(guò)實(shí)驗(yàn)證實(shí)所提出的調(diào)度策略有較好的負(fù)載均衡度及較短的優(yōu)化完成時(shí)間。

1 網(wǎng)頁(yè)內(nèi)容安全監(jiān)測(cè)系統(tǒng)的任務(wù)調(diào)度問(wèn)題

網(wǎng)頁(yè)內(nèi)容安全監(jiān)測(cè)系統(tǒng)是一個(gè)部署在云平臺(tái)上，為目標(biāo)網(wǎng)站群提供實(shí)時(shí)安全監(jiān)測(cè)服務(wù)的分布式應(yīng)用系統(tǒng)。它定時(shí)掃描目標(biāo)客戶網(wǎng)站，對(duì)網(wǎng)站中所有網(wǎng)頁(yè)進(jìn)行分析，檢測(cè)網(wǎng)頁(yè)是否可用，是否被篡改，以及是否出現(xiàn)違規(guī)詞、敏感詞、敏感圖片等，并對(duì)網(wǎng)站出現(xiàn)的異常情況進(jìn)行預(yù)警提示[7]。系統(tǒng)的監(jiān)測(cè)分析任務(wù)如圖1所示，主要包括網(wǎng)站存活監(jiān)測(cè)、網(wǎng)站爬蟲(chóng)、網(wǎng)站解析、網(wǎng)頁(yè)變更監(jiān)測(cè)、違規(guī)詞監(jiān)測(cè)、違規(guī)圖片監(jiān)測(cè)、敏感信息監(jiān)測(cè)以及預(yù)警處理等。除了爬蟲(chóng)任務(wù)要稍微提前外，系統(tǒng)中的每項(xiàng)任務(wù)基本上互不影響，獨(dú)立工作。

圖1 網(wǎng)頁(yè)內(nèi)容安全監(jiān)測(cè)系統(tǒng)任務(wù)調(diào)度示意圖Fig.1 Schematic diagram of task scheduling of web content security monitoring system

網(wǎng)頁(yè)內(nèi)容安全監(jiān)測(cè)系統(tǒng)的幾乎所有的監(jiān)測(cè)任務(wù)都是定時(shí)觸發(fā)的，任務(wù)的啟動(dòng)頻率由客戶自行選擇。由于客戶較多，而且每個(gè)客戶一般有多個(gè)網(wǎng)站需要監(jiān)測(cè)，因此系統(tǒng)同時(shí)監(jiān)測(cè)的目標(biāo)網(wǎng)站數(shù)量很大，網(wǎng)頁(yè)數(shù)量十分龐大。隨著監(jiān)測(cè)網(wǎng)站數(shù)量的增加，系統(tǒng)并發(fā)運(yùn)行的任務(wù)數(shù)會(huì)急劇增長(zhǎng)。為了能夠在第一時(shí)間發(fā)現(xiàn)網(wǎng)站的問(wèn)題，及時(shí)進(jìn)行處理，監(jiān)測(cè)系統(tǒng)必須在限定時(shí)間內(nèi)完成每個(gè)網(wǎng)站的監(jiān)測(cè)任務(wù)，對(duì)發(fā)現(xiàn)的問(wèn)題及時(shí)進(jìn)行報(bào)告。因此，對(duì)系統(tǒng)進(jìn)行合理的任務(wù)調(diào)度，不同的任務(wù)負(fù)載均衡地分配到現(xiàn)有的服務(wù)器，保障現(xiàn)有資源能夠被充分利用。

2 監(jiān)測(cè)系統(tǒng)的任務(wù)調(diào)度解決方案

2.1 監(jiān)測(cè)任務(wù)整合

由于監(jiān)測(cè)系統(tǒng)的核心任務(wù)都是周期性定時(shí)觸發(fā)的，在運(yùn)行環(huán)境和監(jiān)測(cè)目標(biāo)不變的情況下，產(chǎn)生的任務(wù)數(shù)量與執(zhí)行時(shí)間基本穩(wěn)定。為減少開(kāi)銷(xiāo)，本文采用靜態(tài)調(diào)度策略對(duì)系統(tǒng)中的任務(wù)進(jìn)行調(diào)度。為了掌握任務(wù)的基本信息，本文首先對(duì)各種任務(wù)的資源占用情況進(jìn)行了多次測(cè)量，并計(jì)算出各任務(wù)平均用時(shí)，如表1所示。其中，違規(guī)詞監(jiān)測(cè)、違規(guī)詞監(jiān)測(cè)、敏感詞監(jiān)測(cè)、網(wǎng)站爬蟲(chóng)以及網(wǎng)頁(yè)變更監(jiān)測(cè)是針對(duì)網(wǎng)站所有頁(yè)面，故處理時(shí)間為處理每個(gè)頁(yè)面所需的平均時(shí)間，網(wǎng)站存活檢測(cè)和網(wǎng)站信息獲取只針對(duì)主頁(yè)。測(cè)量在多個(gè)相同參數(shù)配置的租用服務(wù)器上進(jìn)行，得到相近的結(jié)果。

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

對(duì)于監(jiān)測(cè)系統(tǒng)中的每個(gè)目標(biāo)網(wǎng)站，系統(tǒng)每次檢測(cè)都會(huì)產(chǎn)生7個(gè)任務(wù)（見(jiàn)表1）。由于要監(jiān)測(cè)網(wǎng)站數(shù)量龐大，每日要監(jiān)測(cè)多次，所以產(chǎn)生的任務(wù)數(shù)量十分巨大，調(diào)度算法進(jìn)行優(yōu)化時(shí)所需的計(jì)算量也會(huì)很大。為此，本文將一段時(shí)間內(nèi)的同一種類(lèi)任務(wù)合并，不但能簡(jiǎn)化調(diào)度的難度，還能減少調(diào)度的次數(shù)。這里之所以能進(jìn)行“歸并”是因?yàn)橥环N任務(wù)即便針對(duì)不同網(wǎng)站，其所需的計(jì)算資源也大致相同，歸并之后可以將它們看成一個(gè)任務(wù)在時(shí)間上的拉長(zhǎng)。

對(duì)每類(lèi)業(yè)務(wù)做“歸并”，將同類(lèi)任務(wù)按時(shí)間段分段歸并，稱(chēng)為“歸并任務(wù)”，記為 Task。第 j個(gè)歸并任務(wù)taskj用向量表示為：

2.2 監(jiān)測(cè)任務(wù)調(diào)度

2.2.1 監(jiān)測(cè)任務(wù)調(diào)度定義

任務(wù)調(diào)度就是將系統(tǒng)任務(wù)集里的任務(wù)以某種策略合理地分配到各分布式計(jì)算節(jié)點(diǎn)上進(jìn)行處理，并以任務(wù)資源利用率、可靠性和負(fù)載均衡等指標(biāo)作為調(diào)度目標(biāo)[8]。本調(diào)度問(wèn)題有以下具體約束：

①每臺(tái)服務(wù)器所有并發(fā)Task所需 CPU資源總和不大于服務(wù)器CPU資源上限。

②每臺(tái)服務(wù)器所有并Task所需內(nèi)存資源總和不大于服務(wù)器內(nèi)存資源上限。

③每臺(tái)服務(wù)器所有Task完成時(shí)間不大于Φ。

對(duì)于系統(tǒng)中的m個(gè)Task，其調(diào)度向量可表示為：

D=[s1,s2,…,sm]

其中sj(j=1,2,…,m)為服務(wù)器編號(hào)。如D=[1，3，1，2]表示為task1分配給服務(wù)器1，task2分配給服務(wù)器 3，task3分配給服務(wù)器 1，task4分配給服務(wù)器 2。有了任務(wù)調(diào)度向量，下面定義評(píng)價(jià)指標(biāo)，建立調(diào)度優(yōu)劣的評(píng)價(jià)標(biāo)準(zhǔn)。

定義2.n臺(tái)服務(wù)器機(jī)組的平均資源利用率：

定義3.服務(wù)器機(jī)組的負(fù)載均衡度：

當(dāng) LD越大時(shí)，服務(wù)器機(jī)組的負(fù)載均衡度越高，調(diào)度策略越優(yōu)秀。

2.2.2 監(jiān)測(cè)任務(wù)調(diào)度算法

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

由式（4）及（5）可知PSO算法可用于求解連續(xù)優(yōu)化問(wèn)題，而本文調(diào)度問(wèn)題明顯是一離散優(yōu)化問(wèn)題，需對(duì)算法進(jìn)行離散化改進(jìn)，使其能夠解決離散型問(wèn)題。

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

離散PSO算法更新過(guò)程如下：

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

輸出：全部迭代完成后的全局最優(yōu)位置gg

2.3 算法步驟

本文任務(wù)調(diào)度算法的具體步驟如下：

①進(jìn)行任務(wù)“歸并”，得到任務(wù)集合。

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

③初始化N個(gè)粒子位置xi，粒子速度v，計(jì)算每個(gè)粒子對(duì)應(yīng)的適應(yīng)值，更新個(gè)體歷史最優(yōu)位置以及全局最優(yōu)位置。

④根據(jù)粒子群更新算法更新每個(gè)粒子的位置與速度，重新計(jì)算每個(gè)粒子對(duì)應(yīng)的適應(yīng)值，更新個(gè)體歷史最優(yōu)位置以及全局最優(yōu)位置。

⑤達(dá)到最大迭代次數(shù)，返回全局最優(yōu)位置，否則回到步驟④。

⑥對(duì)得到的最優(yōu)位置進(jìn)行評(píng)價(jià)，符合約束，輸出調(diào)度策略，否則，服務(wù)器數(shù)量+1，返回步驟③。

3 實(shí)驗(yàn)與分析

3.1 任務(wù)調(diào)度算法實(shí)驗(yàn)

本文通過(guò)開(kāi)源仿真平臺(tái)Cloudsim進(jìn)行仿真實(shí)驗(yàn)，對(duì)比了 GA算法以及蟻群（Ant Colony Optimization，ACO）算法，就任務(wù)調(diào)度算法完成時(shí)間，調(diào)度策略的負(fù)載均衡度兩方面，分析了三種任務(wù)調(diào)度算法的優(yōu)劣。PSO-GA算法、GA算法、ACO算法的相關(guān)參數(shù)設(shè)置分別如表2、表3以及表4所示。

表2 PSO-GA 相關(guān)參數(shù)Tab.2 PSO-GA related parameters

表3 GA 相關(guān)參數(shù)Tab.3 GA related parameters

表4 ACO 相關(guān)參數(shù)Tab.4 ACO related parameters

實(shí)驗(yàn)中設(shè)定的任務(wù)數(shù)從20個(gè)逐漸遞增到160個(gè)，每種情況實(shí)驗(yàn)20次，取測(cè)試結(jié)果的平均值。基于PSO-GA算法，GA算法以及ACO算法對(duì)任務(wù)調(diào)度優(yōu)化完成所需時(shí)間以及任務(wù)調(diào)度負(fù)載均衡度分別如圖2，圖3所示。

圖2 任務(wù)調(diào)度所需時(shí)間Fig.2 Time required for task scheduling

圖3 任務(wù)調(diào)度負(fù)載均衡度Fig.3 Task scheduling load balance

從圖2可知，三種算法中，GA算法所需計(jì)算時(shí)間最多，本文算法和 ACO算法則相差不多，GA算法所需時(shí)間遠(yuǎn)超其他兩者因在實(shí)現(xiàn)時(shí)，該算法有對(duì)基因DNA有編碼和解碼過(guò)程，增加了計(jì)算量。三種算法所需時(shí)間大體與任務(wù)數(shù)量成正比。

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

3.2 服務(wù)器需求分析

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

圖4 監(jiān)測(cè)網(wǎng)站數(shù)與服務(wù)器數(shù)關(guān)系圖Fig.4 The relationship between the number of monitored websites and the number of servers

4 總結(jié)

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