一種改進(jìn)的多維計(jì)算資源任務(wù)分配算法研究

劉鳳

摘? ?要：當(dāng)今時(shí)代，互聯(lián)網(wǎng)技術(shù)發(fā)展迅速，人們的社交需求日益增長(zhǎng)，網(wǎng)絡(luò)爬蟲技術(shù)已被成熟地應(yīng)用于各大搜索引擎和檢索領(lǐng)域。文章針對(duì)分布式爬蟲系統(tǒng)中的任務(wù)分配問題，提出了具體的爬行任務(wù)分配算法。本算法建立了多維度計(jì)算機(jī)資源模型，采用優(yōu)先匹配啟發(fā)式算法進(jìn)行爬行任務(wù)的靜態(tài)分配，通過求解目標(biāo)函數(shù)，使整個(gè)系統(tǒng)的費(fèi)用開銷最小化。實(shí)驗(yàn)證明該算法能在滿足系統(tǒng)需求的前提下，當(dāng)系統(tǒng)需求確定時(shí)，使得總費(fèi)用最小。

關(guān)鍵詞：資源分配;啟發(fā)式匹配;網(wǎng)絡(luò)爬蟲

當(dāng)今時(shí)代，互聯(lián)網(wǎng)快速發(fā)展，網(wǎng)絡(luò)爬蟲被應(yīng)用于各個(gè)搜索引擎和檢索領(lǐng)域[1]。隨著大數(shù)據(jù)時(shí)代的到來，分布式爬蟲技術(shù)被廣泛應(yīng)用于各個(gè)領(lǐng)域。分布式爬蟲技術(shù)中最重要的問題就是爬取任務(wù)的分配問題，這也是傳統(tǒng)分布式爬蟲能夠Spark改造的最關(guān)鍵問題。本團(tuán)隊(duì)研究的重點(diǎn)是怎樣分割任務(wù)。通常來講，可以根據(jù)Web、區(qū)域或域名劃分，分割后將任務(wù)分配給相應(yīng)的爬蟲節(jié)點(diǎn)，基本沒有根據(jù)爬行節(jié)點(diǎn)自身屬性進(jìn)行劃分的分配方法[2]。本研究提出的融合了多維度計(jì)算機(jī)資源模型和優(yōu)先匹配啟發(fā)式任務(wù)分配的算法，能夠根據(jù)計(jì)算機(jī)本身所擁有的資源（包括CPU、內(nèi)存等），進(jìn)行建模，最終使得花費(fèi)最小[3]。

1? ? 相關(guān)概念

任務(wù)分配指的是，當(dāng)系統(tǒng)處于初始化時(shí)，有多個(gè)爬蟲節(jié)點(diǎn)，并且有多個(gè)需要爬取的任務(wù)，可以將任務(wù)分配到不同的爬蟲節(jié)點(diǎn)[4]，重點(diǎn)是如何合理地分配任務(wù)和選擇適當(dāng)?shù)呐老x節(jié)點(diǎn)去執(zhí)行任務(wù)，使得系統(tǒng)能夠在確保穩(wěn)定運(yùn)行的同時(shí)達(dá)到高的執(zhí)行效率，也就是確保系統(tǒng)運(yùn)行的時(shí)間和系統(tǒng)運(yùn)行的費(fèi)用竟達(dá)到最小值。可見，在分配爬行任務(wù)的整個(gè)過程里，本研究要考慮很多因素，包括計(jì)算機(jī)本身的配置、費(fèi)用和占用的時(shí)間。所以，在分布式爬行過程中，任務(wù)的分配問題實(shí)際上是一種組合優(yōu)化，在實(shí)質(zhì)上和向量裝箱問題是一樣的[5]。

2? ? 算法的設(shè)計(jì)與實(shí)現(xiàn)

在分配爬行任務(wù)時(shí)，本研究采用優(yōu)先匹配啟發(fā)式算法。首先需要有一個(gè)準(zhǔn)則，本研究的目標(biāo)是選擇合適的爬蟲節(jié)點(diǎn)去完成任務(wù)，使得系統(tǒng)在完成任務(wù)的過程中，整體的系統(tǒng)花費(fèi)最小。本研究設(shè)計(jì)一種新的費(fèi)用模型，能夠在分布式爬蟲任務(wù)分配過程中保證花費(fèi)最小（包括CPU、內(nèi)存以及帶寬）。在系統(tǒng)實(shí)際運(yùn)行時(shí)，不同時(shí)期的花費(fèi)略有不同，本算法包含3種費(fèi)用：

（1）預(yù)留費(fèi)用。指的是在進(jìn)行爬取之前預(yù)留相應(yīng)節(jié)點(diǎn)產(chǎn)生的花費(fèi)[6]。

（2）使用費(fèi)用。指的是系統(tǒng)在爬取數(shù)據(jù)時(shí)產(chǎn)生的費(fèi)用。

（3）附加費(fèi)用。指的是在系統(tǒng)預(yù)留的爬蟲節(jié)點(diǎn)不能完成任務(wù)時(shí)，本研究需要分配更多的爬蟲節(jié)點(diǎn)協(xié)助完成爬取，此時(shí)產(chǎn)生的新的費(fèi)用。

可見，每個(gè)節(jié)點(diǎn)在執(zhí)行任務(wù)時(shí)產(chǎn)生的費(fèi)用是由以上3種費(fèi)用共同構(gòu)成的。本算法不考慮系統(tǒng)執(zhí)行的時(shí)間長(zhǎng)短，只關(guān)心每臺(tái)計(jì)算機(jī)的CPU、內(nèi)存、帶寬的開銷，使得花費(fèi)最小即可。

本研究設(shè)計(jì)了一種優(yōu)先匹配啟發(fā)式爬行任務(wù)分配算法，此方法在資源分配算法的基礎(chǔ)上進(jìn)行了改進(jìn)，不是從所有的節(jié)點(diǎn)隨意選擇一個(gè)或多個(gè)機(jī)器去執(zhí)行任務(wù)，而是根據(jù)不同任務(wù)的規(guī)模，從正在工作的爬蟲節(jié)點(diǎn)中優(yōu)先尋找，如果正在工作的節(jié)點(diǎn)滿足需求，則不用啟用空閑節(jié)點(diǎn)，只有當(dāng)所有的正在工作的機(jī)器均不能達(dá)到任務(wù)要求時(shí)，才啟用空閑節(jié)點(diǎn)，從空閑節(jié)點(diǎn)中選擇合適的節(jié)點(diǎn)來完成任務(wù)。改進(jìn)的算法可以減小節(jié)點(diǎn)的占用率，提高機(jī)器的利用率，從而減少系統(tǒng)的開銷，提高系統(tǒng)的負(fù)載能力，保證系統(tǒng)的穩(wěn)健性。

該算法的部分代碼如下：

（1）當(dāng)系統(tǒng)初始化時(shí)，從所有機(jī)器中隨意挑選一個(gè)節(jié)點(diǎn)分配任務(wù)，一般選擇序列中的第一個(gè)節(jié)點(diǎn)。其他時(shí)候，首先從已經(jīng)占用的節(jié)點(diǎn)中選取一個(gè)節(jié)點(diǎn)，分配任務(wù)后，一般選擇序列中的第一個(gè)節(jié)點(diǎn)。

（2）判斷此爬蟲節(jié)點(diǎn)的多個(gè)資源量（CPU、內(nèi)存以及帶寬）能否滿足當(dāng)前任務(wù)的需求，如果資源足夠，則選擇該節(jié)點(diǎn)，分配任務(wù);如果不能滿足資源的要求，查找序列中下一個(gè)正在工作的節(jié)點(diǎn)，一直操作到尋找到滿足條件的節(jié)點(diǎn)為止，并將任務(wù)分配給它。

（3）如果已經(jīng)查遍所有正在工作的節(jié)點(diǎn)，并且節(jié)點(diǎn)的資源沒有辦法完成當(dāng)前任務(wù)，這時(shí)在空閑的節(jié)點(diǎn)序列中選擇一個(gè)節(jié)點(diǎn)，將任務(wù)分配給它。分配任務(wù)前，要檢驗(yàn)空閑節(jié)點(diǎn)的資源能否滿足任務(wù)需求，如果資源足夠，則選擇該節(jié)點(diǎn)，分配任務(wù);如果不能滿足資源的要求，查找序列中下一個(gè)空閑的節(jié)點(diǎn)，一直操作到尋找到滿足條件的節(jié)點(diǎn)為止，并將任務(wù)分配給它。

（4）重復(fù)步驟（1—3），直到完成所有任務(wù)序列中的任務(wù)為止，也有可能空閑爬蟲節(jié)點(diǎn)序列為空，此時(shí)只能等待。

3? ? 實(shí)驗(yàn)結(jié)果與分析

通過利用Matlab軟件，本研究仿真了分布式爬蟲的任務(wù)分配算法，包括當(dāng)系統(tǒng)的需求確定時(shí)，執(zhí)行系統(tǒng)需要多少節(jié)點(diǎn)，需要分別使用和預(yù)留多少節(jié)點(diǎn)，以及這些節(jié)點(diǎn)數(shù)目和總的花費(fèi)之間的關(guān)系。仿真試驗(yàn)的結(jié)果如圖1所示。

假設(shè)整個(gè)系統(tǒng)運(yùn)行的總節(jié)點(diǎn)數(shù)目是固定的，那么，預(yù)留的節(jié)點(diǎn)數(shù)目越多，預(yù)留的費(fèi)用會(huì)逐漸增加，而使用費(fèi)用會(huì)先上升，當(dāng)達(dá)到系統(tǒng)要求時(shí)，則不再變化。相反，附加費(fèi)用會(huì)先下降，當(dāng)達(dá)到系統(tǒng)要求時(shí)，會(huì)下降至0。需要看的是總的費(fèi)用=預(yù)留費(fèi)用+使用費(fèi)用+附加費(fèi)用，總的費(fèi)用先下降然后逐漸上升。所以，當(dāng)達(dá)到系統(tǒng)所需的機(jī)器總數(shù)時(shí)，得到最小花費(fèi)點(diǎn)。

如果系統(tǒng)沒有預(yù)留工作節(jié)點(diǎn)，在系統(tǒng)執(zhí)行時(shí)，所有的節(jié)點(diǎn)都屬于附加，從圖中可以看到，由于附加價(jià)格實(shí)際高于預(yù)留價(jià)格和使用價(jià)格的總和，所以總花費(fèi)會(huì)變多。如果預(yù)留的節(jié)點(diǎn)數(shù)目少于系統(tǒng)實(shí)際需求的節(jié)點(diǎn)數(shù)目，系統(tǒng)附加節(jié)點(diǎn)的附加費(fèi)用也是一筆大的花銷。如果預(yù)留的節(jié)點(diǎn)數(shù)目大于系統(tǒng)實(shí)際需求的節(jié)點(diǎn)數(shù)目，顯然系統(tǒng)不再需要附加費(fèi)用，而是在預(yù)留費(fèi)用上花費(fèi)更多。

圖1? 固定需求下各種費(fèi)用關(guān)系

綜上所述，當(dāng)系統(tǒng)需求固定時(shí)，不能預(yù)留太多節(jié)點(diǎn)，否則就需要支付更多的預(yù)留費(fèi)用;預(yù)留節(jié)點(diǎn)也不能太少，否則就需要支付額外的附加費(fèi)用;只有當(dāng)預(yù)留節(jié)點(diǎn)數(shù)目等于需求節(jié)點(diǎn)數(shù)目時(shí)，總費(fèi)用才能最小。這與現(xiàn)實(shí)生活一致，需要多少就留多少，這樣不會(huì)有額外的費(fèi)用，總花費(fèi)才能達(dá)到最少。

4? ? 結(jié)語(yǔ)

本算法建立了一種多維度計(jì)算機(jī)資源模型，在系統(tǒng)執(zhí)行爬蟲任務(wù)時(shí)，采用了優(yōu)先匹配啟發(fā)式算法，為各個(gè)節(jié)點(diǎn)分配任務(wù)。通過實(shí)驗(yàn)，對(duì)目標(biāo)函數(shù)求解，求得目標(biāo)函數(shù)的最小值，從而保證系統(tǒng)的花費(fèi)最小。實(shí)驗(yàn)結(jié)果表明，該算法能在滿足系統(tǒng)需求的前提下，當(dāng)系統(tǒng)需求確定時(shí)，使得總費(fèi)用最小。

[參考文獻(xiàn)]

[1]JADIDI O，ZOLFAGHARI S，CAVALIERI S.A new normalized goal programming model for multi-objective problems： a case of supplier selection and order allocation[J].International Journal of Production Economics，2014（1）：158-165.

[2]CHOUDHARY D，SHANKAR R.A goal programming model for joint decision making of inventory lot-size， supplier selection and carrier selection[J].Computers & Industrial Engineering，2014（1）：1-9.

[3]JADIDI O，CAVALIERI S，ZOLFAGHARI S.An Improved multi-choice goal programming approach for supplier selection problems[J].Applied Mathematical Modelling，2014（14）：4213-4222.

[4]LUO J，LAN C E.Determination of weighting matrices of a linear quadratic regulator[J].Journal of Guidance Control & Dynamics，2015（6）：1462-1463.

[5]EJSMONT W.A characterization of the normal distribution by the independence of a pair of random vectors[J].Statistics & Probability Letters，2016（114）：1-5.

[6]QUN Y.Laws of the iterated logarithm for ρ-mixing random variables with normal distribution[J].應(yīng)用數(shù)學(xué)學(xué)報(bào)（英文版），2016（2）：385-394.