劉鳳
摘? ?要:當(dāng)今時代,互聯(lián)網(wǎng)技術(shù)發(fā)展迅速,人們的社交需求日益增長,網(wǎng)絡(luò)爬蟲技術(shù)已被成熟地應(yīng)用于各大搜索引擎和檢索領(lǐng)域。文章針對分布式爬蟲系統(tǒng)中的任務(wù)分配問題,提出了具體的爬行任務(wù)分配算法。本算法建立了多維度計算機資源模型,采用優(yōu)先匹配啟發(fā)式算法進行爬行任務(wù)的靜態(tài)分配,通過求解目標(biāo)函數(shù),使整個系統(tǒng)的費用開銷最小化。實驗證明該算法能在滿足系統(tǒng)需求的前提下,當(dāng)系統(tǒng)需求確定時,使得總費用最小。
關(guān)鍵詞:資源分配;啟發(fā)式匹配;網(wǎng)絡(luò)爬蟲
當(dāng)今時代,互聯(lián)網(wǎng)快速發(fā)展,網(wǎng)絡(luò)爬蟲被應(yīng)用于各個搜索引擎和檢索領(lǐng)域[1]。隨著大數(shù)據(jù)時代的到來,分布式爬蟲技術(shù)被廣泛應(yīng)用于各個領(lǐng)域。分布式爬蟲技術(shù)中最重要的問題就是爬取任務(wù)的分配問題,這也是傳統(tǒng)分布式爬蟲能夠Spark改造的最關(guān)鍵問題。本團隊研究的重點是怎樣分割任務(wù)。通常來講,可以根據(jù)Web、區(qū)域或域名劃分,分割后將任務(wù)分配給相應(yīng)的爬蟲節(jié)點,基本沒有根據(jù)爬行節(jié)點自身屬性進行劃分的分配方法[2]。本研究提出的融合了多維度計算機資源模型和優(yōu)先匹配啟發(fā)式任務(wù)分配的算法,能夠根據(jù)計算機本身所擁有的資源(包括CPU、內(nèi)存等),進行建模,最終使得花費最小[3]。
1? ? 相關(guān)概念
任務(wù)分配指的是,當(dāng)系統(tǒng)處于初始化時,有多個爬蟲節(jié)點,并且有多個需要爬取的任務(wù),可以將任務(wù)分配到不同的爬蟲節(jié)點[4],重點是如何合理地分配任務(wù)和選擇適當(dāng)?shù)呐老x節(jié)點去執(zhí)行任務(wù),使得系統(tǒng)能夠在確保穩(wěn)定運行的同時達到高的執(zhí)行效率,也就是確保系統(tǒng)運行的時間和系統(tǒng)運行的費用竟達到最小值。可見,在分配爬行任務(wù)的整個過程里,本研究要考慮很多因素,包括計算機本身的配置、費用和占用的時間。所以,在分布式爬行過程中,任務(wù)的分配問題實際上是一種組合優(yōu)化,在實質(zhì)上和向量裝箱問題是一樣的[5]。
2? ? 算法的設(shè)計與實現(xiàn)
在分配爬行任務(wù)時,本研究采用優(yōu)先匹配啟發(fā)式算法。首先需要有一個準(zhǔn)則,本研究的目標(biāo)是選擇合適的爬蟲節(jié)點去完成任務(wù),使得系統(tǒng)在完成任務(wù)的過程中,整體的系統(tǒng)花費最小。本研究設(shè)計一種新的費用模型,能夠在分布式爬蟲任務(wù)分配過程中保證花費最?。ò–PU、內(nèi)存以及帶寬)。在系統(tǒng)實際運行時,不同時期的花費略有不同,本算法包含3種費用:
(1)預(yù)留費用。指的是在進行爬取之前預(yù)留相應(yīng)節(jié)點產(chǎn)生的花費[6]。
(2)使用費用。指的是系統(tǒng)在爬取數(shù)據(jù)時產(chǎn)生的費用。
(3)附加費用。指的是在系統(tǒng)預(yù)留的爬蟲節(jié)點不能完成任務(wù)時,本研究需要分配更多的爬蟲節(jié)點協(xié)助完成爬取,此時產(chǎn)生的新的費用。
可見,每個節(jié)點在執(zhí)行任務(wù)時產(chǎn)生的費用是由以上3種費用共同構(gòu)成的。本算法不考慮系統(tǒng)執(zhí)行的時間長短,只關(guān)心每臺計算機的CPU、內(nèi)存、帶寬的開銷,使得花費最小即可。
本研究設(shè)計了一種優(yōu)先匹配啟發(fā)式爬行任務(wù)分配算法,此方法在資源分配算法的基礎(chǔ)上進行了改進,不是從所有的節(jié)點隨意選擇一個或多個機器去執(zhí)行任務(wù),而是根據(jù)不同任務(wù)的規(guī)模,從正在工作的爬蟲節(jié)點中優(yōu)先尋找,如果正在工作的節(jié)點滿足需求,則不用啟用空閑節(jié)點,只有當(dāng)所有的正在工作的機器均不能達到任務(wù)要求時,才啟用空閑節(jié)點,從空閑節(jié)點中選擇合適的節(jié)點來完成任務(wù)。改進的算法可以減小節(jié)點的占用率,提高機器的利用率,從而減少系統(tǒng)的開銷,提高系統(tǒng)的負載能力,保證系統(tǒng)的穩(wěn)健性。
該算法的部分代碼如下:
(1)當(dāng)系統(tǒng)初始化時,從所有機器中隨意挑選一個節(jié)點分配任務(wù),一般選擇序列中的第一個節(jié)點。其他時候,首先從已經(jīng)占用的節(jié)點中選取一個節(jié)點,分配任務(wù)后,一般選擇序列中的第一個節(jié)點。
(2)判斷此爬蟲節(jié)點的多個資源量(CPU、內(nèi)存以及帶寬)能否滿足當(dāng)前任務(wù)的需求,如果資源足夠,則選擇該節(jié)點,分配任務(wù);如果不能滿足資源的要求,查找序列中下一個正在工作的節(jié)點,一直操作到尋找到滿足條件的節(jié)點為止,并將任務(wù)分配給它。
(3)如果已經(jīng)查遍所有正在工作的節(jié)點,并且節(jié)點的資源沒有辦法完成當(dāng)前任務(wù),這時在空閑的節(jié)點序列中選擇一個節(jié)點,將任務(wù)分配給它。分配任務(wù)前,要檢驗空閑節(jié)點的資源能否滿足任務(wù)需求,如果資源足夠,則選擇該節(jié)點,分配任務(wù);如果不能滿足資源的要求,查找序列中下一個空閑的節(jié)點,一直操作到尋找到滿足條件的節(jié)點為止,并將任務(wù)分配給它。
(4)重復(fù)步驟(1—3),直到完成所有任務(wù)序列中的任務(wù)為止,也有可能空閑爬蟲節(jié)點序列為空,此時只能等待。
3? ? 實驗結(jié)果與分析
通過利用Matlab軟件,本研究仿真了分布式爬蟲的任務(wù)分配算法,包括當(dāng)系統(tǒng)的需求確定時,執(zhí)行系統(tǒng)需要多少節(jié)點,需要分別使用和預(yù)留多少節(jié)點,以及這些節(jié)點數(shù)目和總的花費之間的關(guān)系。仿真試驗的結(jié)果如圖1所示。
假設(shè)整個系統(tǒng)運行的總節(jié)點數(shù)目是固定的,那么,預(yù)留的節(jié)點數(shù)目越多,預(yù)留的費用會逐漸增加,而使用費用會先上升,當(dāng)達到系統(tǒng)要求時,則不再變化。相反,附加費用會先下降,當(dāng)達到系統(tǒng)要求時,會下降至0。需要看的是總的費用=預(yù)留費用+使用費用+附加費用,總的費用先下降然后逐漸上升。所以,當(dāng)達到系統(tǒng)所需的機器總數(shù)時,得到最小花費點。
如果系統(tǒng)沒有預(yù)留工作節(jié)點,在系統(tǒng)執(zhí)行時,所有的節(jié)點都屬于附加,從圖中可以看到,由于附加價格實際高于預(yù)留價格和使用價格的總和,所以總花費會變多。如果預(yù)留的節(jié)點數(shù)目少于系統(tǒng)實際需求的節(jié)點數(shù)目,系統(tǒng)附加節(jié)點的附加費用也是一筆大的花銷。如果預(yù)留的節(jié)點數(shù)目大于系統(tǒng)實際需求的節(jié)點數(shù)目,顯然系統(tǒng)不再需要附加費用,而是在預(yù)留費用上花費更多。
圖1? 固定需求下各種費用關(guān)系
綜上所述,當(dāng)系統(tǒng)需求固定時,不能預(yù)留太多節(jié)點,否則就需要支付更多的預(yù)留費用;預(yù)留節(jié)點也不能太少,否則就需要支付額外的附加費用;只有當(dāng)預(yù)留節(jié)點數(shù)目等于需求節(jié)點數(shù)目時,總費用才能最小。這與現(xiàn)實生活一致,需要多少就留多少,這樣不會有額外的費用,總花費才能達到最少。
4? ? 結(jié)語
本算法建立了一種多維度計算機資源模型,在系統(tǒng)執(zhí)行爬蟲任務(wù)時,采用了優(yōu)先匹配啟發(fā)式算法,為各個節(jié)點分配任務(wù)。通過實驗,對目標(biāo)函數(shù)求解,求得目標(biāo)函數(shù)的最小值,從而保證系統(tǒng)的花費最小。實驗結(jié)果表明,該算法能在滿足系統(tǒng)需求的前提下,當(dāng)系統(tǒng)需求確定時,使得總費用最小。
[參考文獻]
[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é)報(英文版),2016(2):385-394.