分布式系統(tǒng)大數(shù)據(jù)分層調(diào)度算法

王 瑋，田 兵，劉 蔭，蘇 琦，周 偉

（國(guó)網(wǎng)山東省電力公司信息通信公司，山東 濟(jì)南 250001）

分布式系統(tǒng)大數(shù)據(jù)分層調(diào)度算法

王 瑋，田 兵，劉 蔭，蘇 琦，周 偉

（國(guó)網(wǎng)山東省電力公司信息通信公司，山東 濟(jì)南 250001）

互聯(lián)網(wǎng)時(shí)代數(shù)據(jù)量激增，數(shù)據(jù)的抓取調(diào)度已成為有效采集關(guān)鍵信息的重點(diǎn)問(wèn)題。提出一種分布式系統(tǒng)的大數(shù)據(jù)分層調(diào)度算法，該算法依據(jù)數(shù)據(jù)集的維度特征屬性，利用凝聚層次聚類對(duì)數(shù)據(jù)集進(jìn)行分層處理，結(jié)合小型Hadoop分布式系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)集分層調(diào)度。該算法為互聯(lián)網(wǎng)時(shí)代下大數(shù)據(jù)的快速采集調(diào)度問(wèn)題提出了一種新的解決思路。

分布式系統(tǒng)；凝聚層次聚類；分層調(diào)度

0 引言

隨著全球進(jìn)入互聯(lián)網(wǎng)時(shí)代，數(shù)據(jù)的抓取調(diào)度成為關(guān)鍵信息有效采集的重點(diǎn)問(wèn)題［1-3］。與此同時(shí)，計(jì)算機(jī)受物理器件性能的限制，僅依靠CPU主頻的提升并不能降低數(shù)據(jù)庫(kù)的調(diào)度處理壓力，使用快速有效的算法成為目前大數(shù)據(jù)挖掘的主流［4-5］。本文主要研究大數(shù)據(jù)挖掘分層調(diào)度處理算法，在抓取數(shù)據(jù)集的維度特征信息后，通過(guò)凝聚層次聚類對(duì)數(shù)據(jù)集進(jìn)行分層處理，結(jié)合小型Hadoop分布式系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)集分層調(diào)度，實(shí)現(xiàn)一種自配置的Hadoop分布式數(shù)據(jù)調(diào)度算法。

1 算法基本思想

1.1 Hadoop分布式系統(tǒng)

選用基于Hadoop的篩選過(guò)濾系統(tǒng)來(lái)實(shí)現(xiàn)大數(shù)據(jù)的分布式并行計(jì)算處理。Hadoop采用主從式架構(gòu)，由一臺(tái)Master主控節(jié)點(diǎn)、多個(gè)Slave節(jié)點(diǎn)和計(jì)算節(jié)點(diǎn)組成，由控制節(jié)點(diǎn)對(duì)數(shù)據(jù)庫(kù)進(jìn)行數(shù)據(jù)特征歸列后分發(fā)到各個(gè)計(jì)算節(jié)點(diǎn)進(jìn)行處理。Master節(jié)點(diǎn)同時(shí)還負(fù)責(zé)對(duì)Slave服務(wù)器的各種服務(wù)載荷進(jìn)行調(diào)度管理和評(píng)估，以使得Slave服務(wù)器能夠合理高效的分配與利用計(jì)算節(jié)點(diǎn)的資源［6］。其基本結(jié)構(gòu)如圖1所示。

圖1 Hadoop主從式基本結(jié)構(gòu)

1.2 凝聚層次聚類算法

層次聚類算法用于實(shí)現(xiàn)大數(shù)據(jù)集合的多層次歸類。具體又可分為凝聚和分裂兩種方案［7］。凝聚層次聚類由下而上進(jìn)行操作，它先選取集合內(nèi)的元素作為子簇，再將其合并，最終累積為更大的簇，這個(gè)過(guò)程持續(xù)到所有的元素都包括在一個(gè)簇內(nèi)，或者運(yùn)行到其他的終結(jié)條件再結(jié)束。分裂層次聚類則采用由下而上進(jìn)行操作的方式，與凝聚的層次聚類相反，該算法先在集合內(nèi)規(guī)劃好所有的元素，再將其定義為一個(gè)一個(gè)小簇，逐步細(xì)化，這樣的過(guò)程持續(xù)到集合內(nèi)的子簇自成一簇，或者運(yùn)行到其他的終結(jié)條件再結(jié)束［8］。選取最小距離的凝聚型層次聚類算法，算法流程如圖2所示。

圖2 最小距離的凝聚層次聚類算法流程

2 數(shù)據(jù)的分層調(diào)度

2.1 基于小型Hadoop集群的數(shù)據(jù)分層提取

利用層次聚類的方法進(jìn)行數(shù)據(jù)分層主要用于同一數(shù)據(jù)庫(kù)出現(xiàn)頻率較高、而在其他數(shù)據(jù)庫(kù)中很少出現(xiàn)的數(shù)據(jù)，這些數(shù)據(jù)具有很好的類別區(qū)分能力且適合用來(lái)分類［9］，可有效應(yīng)用于數(shù)據(jù)信息挖掘?；谛⌒虷adoop集群的數(shù)據(jù)分層提取，主要工作是根據(jù)數(shù)據(jù)集的多維度特征結(jié)構(gòu)對(duì)數(shù)據(jù)進(jìn)行分類［10］，并從中提取出關(guān)鍵信息完成數(shù)據(jù)的篩選。由于數(shù)據(jù)信息的提取是實(shí)現(xiàn)數(shù)據(jù)分類調(diào)度工作的基礎(chǔ)，因此在提取數(shù)據(jù)集的維度信息要求盡量做到不重不漏。與此同時(shí)，隨著數(shù)據(jù)的不斷存入，數(shù)據(jù)的分層會(huì)隨著時(shí)間改變，離現(xiàn)在越久的聚類分層，變化的可能性越大，很久以前的分層對(duì)于構(gòu)建層次聚類模型來(lái)說(shuō)意義不大，因此需要考慮數(shù)據(jù)量分層相對(duì)時(shí)間的衰減。選用MySQL數(shù)據(jù)庫(kù)存儲(chǔ)發(fā)生時(shí)間戳與上一周期存儲(chǔ)的秒數(shù)差與一個(gè)周期的總秒數(shù)的比值，作為一個(gè)線性衰減要素加入到算法中。

數(shù)據(jù)集調(diào)度功能的偽代碼實(shí)現(xiàn)如下。

2.2 數(shù)據(jù)的分層調(diào)度處理

基于Hadoop的數(shù)據(jù)分層調(diào)度處理分為兩個(gè)過(guò)程［11］：Map過(guò)程和Reduce過(guò)程。在Map過(guò)程之前，可將凝聚層次聚類規(guī)則作為預(yù)處理操作：即根據(jù)初始MySQL數(shù)據(jù)庫(kù)提取數(shù)據(jù)集分層信息，以鍵值的形式保存。Map函數(shù)根據(jù)list_data加載相應(yīng)的數(shù)據(jù)集維度列表，利用事先定義好的特征規(guī)則，提取其中的分層數(shù)據(jù)，并完成MySQL數(shù)據(jù)庫(kù)信息的遍歷，提取出來(lái)的信息以的格式輸出［12］。Reduce函數(shù)主要工作是接受Map函數(shù)的輸入，對(duì)輸出格式進(jìn)行調(diào)整并依據(jù)凝聚層次聚類匹配規(guī)則完成數(shù)據(jù)的處理與歸類，最終得到結(jié)果輸出文件［13］，相同鍵值的輸入會(huì)由同一個(gè)Reduce函數(shù)處理。

數(shù)據(jù)的分層調(diào)度處理過(guò)程如下：

Step.1：加載模板文件，初始化凝聚層次聚類模板類，獲取初始數(shù)據(jù)信息分層；

Step.2：根據(jù)層次聚類分配準(zhǔn)則，對(duì)加載的初始數(shù)據(jù)信息分層進(jìn)行子集提取操作，提取出的子集依次加入數(shù)據(jù)集的維度隊(duì)列中，同時(shí)寫(xiě)入列表文件；

Step.3：從數(shù)據(jù)信息列表中取出數(shù)據(jù)子集，加載數(shù)據(jù)集內(nèi)容；

Step.4：根據(jù)凝聚層次聚類匹配規(guī)則完成抽取調(diào)度，并寫(xiě)入輸出文件；

Step.5：判斷列表是否加載完成維度隊(duì)列中的全部特征。如全部加載完畢，則該類分層下的數(shù)據(jù)集分層工作完成，否則繼續(xù)加載下一個(gè)維度特征，重復(fù)進(jìn)行第4步操作；

Step.6：若列表為空則數(shù)據(jù)的調(diào)度工作完成，否則重復(fù)進(jìn)行第3步操作。

3 應(yīng)用分析

選取一套MVC模式的應(yīng)用系統(tǒng)，用于對(duì)本文提出的算法效果進(jìn)行測(cè)試驗(yàn)證，分別在單機(jī)和分布式的環(huán)境下進(jìn)行了3 h的數(shù)據(jù)調(diào)度測(cè)試。其中分布式環(huán)境選用了兩臺(tái)PC服務(wù)器分別作為Master節(jié)點(diǎn)和Slave節(jié)點(diǎn)組建Hadoop集群，服務(wù)器配置如表1所示，測(cè)試比較結(jié)果如表2所示。

通過(guò)對(duì)表2測(cè)試結(jié)果的分析可以看出，分布式集群中單個(gè)節(jié)點(diǎn)的效率同單機(jī)節(jié)點(diǎn)相比略低，這是由于分布式環(huán)境中存在網(wǎng)絡(luò)帶寬等瓶頸因素，同時(shí)分布式系統(tǒng)還需承擔(dān)作業(yè)調(diào)度、系統(tǒng)IO等額外開(kāi)銷導(dǎo)致的。但是兩個(gè)節(jié)點(diǎn)的總體運(yùn)行效率比單機(jī)提高了約59.58%，隨計(jì)算節(jié)點(diǎn)的增加運(yùn)行效率還可進(jìn)一步提高，這也是分布式計(jì)算的優(yōu)勢(shì)。

表1 Hadoop集群服務(wù)器硬件配置

表2 Hadoop分布式與單機(jī)的調(diào)度數(shù)據(jù)集數(shù)量比較

4 結(jié)語(yǔ)

設(shè)計(jì)并實(shí)現(xiàn)了一種分布式系統(tǒng)的大數(shù)據(jù)分層調(diào)度算法，算法依據(jù)數(shù)據(jù)集的維度特征屬性，利用凝聚層次聚類對(duì)數(shù)據(jù)集進(jìn)行分層處理，結(jié)合小型Hadoop分布式系統(tǒng)實(shí)現(xiàn)數(shù)據(jù)集分層調(diào)度。通過(guò)在MVC模式系統(tǒng)中對(duì)算法的實(shí)際測(cè)試驗(yàn)證，雙節(jié)點(diǎn)集群的總體運(yùn)行效率比單機(jī)提高了約59.58%，且隨計(jì)算節(jié)點(diǎn)的增加運(yùn)行效率還可進(jìn)一步提高。

［1］賀瑤，王文慶，薛飛.基于云計(jì)算的海量數(shù)據(jù)挖掘研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（2）：69-72.

［2］胡文瑜，孫志揮，吳英杰.數(shù)據(jù)挖掘取樣方法研究［J］.計(jì)算機(jī)研究與發(fā)展，2011，48（1）：45-54.

［3］王元卓，靳小龍，程學(xué)旗.網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與展望［J］.計(jì)算機(jī)學(xué)報(bào)，2013，36（6）：1 125-1 138.

［4］申彥，朱玉全.CMP上基于數(shù)據(jù)集劃分的K-means多核優(yōu)化算法［J］.智能系統(tǒng)學(xué)報(bào)，2015，10（4）：607-614.

［5］張繼福，李永紅，秦嘯，等.基于MapReduce與相關(guān)子空間的局部離群數(shù)據(jù)挖掘算法［J］.軟件學(xué)報(bào)，2015，26（5）：1 079-1 095.

［6］傅巍瑋，李仁發(fā)，劉鈺峰，等.基于Solr的分布式實(shí)時(shí)搜索模型研究與實(shí)現(xiàn)［J］.電信科學(xué)，2011，27（11）：51-56.

［7］李春忠，徐宗本，喬琛.帶信息反饋的凝聚層次聚類算法［J］.中國(guó)科學(xué)：信息科學(xué)，2012，42（6）：730-742.

［8］張愛(ài)琦，左萬(wàn)利，王英，等.基于多個(gè)領(lǐng)域本體的文本層次被定義聚類方法［J］.計(jì)算機(jī)科學(xué)，2010，37（3）：199-204.

［9］余長(zhǎng)俊，張燃.云環(huán)境下基于Canopy聚類的FCM算法研究［J］.計(jì)算機(jī)科學(xué)，2014，41（z2）：316-319.

［10］李昌，陳金花.基于最大熵功率譜估計(jì)的Hadoop高速數(shù)據(jù)訪問(wèn)［J］.科技通報(bào)，2014，30（8）：59-61.

［11］唐珊珊，朱躍龍，朱凱.基于Map／Reduce的外殼片段立方體并行計(jì)算方法［J］.計(jì)算機(jī)工程與應(yīng)用.2015，51（22）：124-129.

［12］李瑞霞，劉仁金，周先存.基于哈希表的MapReduce算法優(yōu)化［J］.山東大學(xué)學(xué)報(bào)（理學(xué)版），2015，50（7）：66-70.

［13］陳吉榮，樂(lè)嘉錦.基于MapReduce的Hadoop大表導(dǎo)入編程模型［J］.計(jì)算機(jī)應(yīng)用，2013，33（9）：2 486-2 489.

Hierarchical Scheduling A lgorithm of Large Data for Distributed System s

WANGWei，TIAN Bing，LIU Yin，SU Qi，ZHOUWei
（Information&Communication Company，State Grid Shandong Electric Power Company，Jinan 250001，China）

Capturing and scheduling of the key data from the vast information has become the focus of the information acquisition under the background of information explosion in the internet era.This paper proposes a hierarchical scheduling algorithm of big data for distributed system.Based on the dimension feature of the data sets，this algorithm realizes the processing of data sets by hierarchical clustering and the hierarchical scheduling through Hadoop distributed system.This algorithm presents a new solution to the problem of rapid acquisition and scheduling of big data in the Internetera.

Distributed Systems；agglomerative hierarchical clustering；hierarchical scheduling

TP311.1

A

1007－9904（2017）06－0045－04

2017－03－16

王 瑋（1970），女，高級(jí)工程師，從事電力信息系統(tǒng)建設(shè)和運(yùn)維工作；田 兵（1965），男，高級(jí)工程師，從事電力信息系統(tǒng)規(guī)劃和設(shè)計(jì)工作；劉 蔭（1985），男，工程師，從事電力信息系統(tǒng)運(yùn)維工作；蘇 琦（1981），男，經(jīng)濟(jì)師，從事電力信息系統(tǒng)建設(shè)工作；周 偉（1984），男，工程師，從事電力信息系統(tǒng)建設(shè)工作。