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

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

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

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

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

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

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

0 引言

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

1 算法基本思想

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

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

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

1.2 凝聚層次聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 應(yīng)用分析

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

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

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

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

4 結(jié)語

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

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

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

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

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

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

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

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

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

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

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

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

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

［13］陳吉榮，樂嘉錦.基于MapReduce的Hadoop大表導(dǎo)入編程模型［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），女，高級工程師，從事電力信息系統(tǒng)建設(shè)和運維工作；田 兵（1965），男，高級工程師，從事電力信息系統(tǒng)規(guī)劃和設(shè)計工作；劉 蔭（1985），男，工程師，從事電力信息系統(tǒng)運維工作；蘇 琦（1981），男，經(jīng)濟師，從事電力信息系統(tǒng)建設(shè)工作；周 偉（1984），男，工程師，從事電力信息系統(tǒng)建設(shè)工作。