分布式系統大數據分層調度算法

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

（國網山東省電力公司信息通信公司，山東 濟南 250001）

分布式系統大數據分層調度算法

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

（國網山東省電力公司信息通信公司，山東 濟南 250001）

互聯網時代數據量激增，數據的抓取調度已成為有效采集關鍵信息的重點問題。提出一種分布式系統的大數據分層調度算法，該算法依據數據集的維度特征屬性，利用凝聚層次聚類對數據集進行分層處理，結合小型Hadoop分布式系統實現數據集分層調度。該算法為互聯網時代下大數據的快速采集調度問題提出了一種新的解決思路。

分布式系統；凝聚層次聚類；分層調度

0 引言

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

1 算法基本思想

1.1 Hadoop分布式系統

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

圖1 Hadoop主從式基本結構

1.2 凝聚層次聚類算法

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

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

2 數據的分層調度

2.1 基于小型Hadoop集群的數據分層提取

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

數據集調度功能的偽代碼實現如下。

2.2 數據的分層調度處理

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

數據的分層調度處理過程如下：

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

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

Step.3：從數據信息列表中取出數據子集，加載數據集內容；

Step.4：根據凝聚層次聚類匹配規則完成抽取調度，并寫入輸出文件；

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

Step.6：若列表為空則數據的調度工作完成，否則重復進行第3步操作。

3 應用分析

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

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

表1 Hadoop集群服務器硬件配置

表2 Hadoop分布式與單機的調度數據集數量比較

4 結語

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

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

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

［3］王元卓，靳小龍，程學旗.網絡大數據：現狀與展望［J］.計算機學報，2013，36（6）：1 125-1 138.

［4］申彥，朱玉全.CMP上基于數據集劃分的K-means多核優化算法［J］.智能系統學報，2015，10（4）：607-614.

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

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

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

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

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

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

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

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

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