王 瑋，蘇 琦，劉 蔭，周 偉，于展鵬，穆 林

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

一種基于小型Hadoop集群的數(shù)據(jù)分層調(diào)度處理算法研究

王 瑋，蘇 琦，劉 蔭，周 偉，于展鵬，穆 林

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

針對當前抓取調(diào)度數(shù)據(jù)量巨大且計算復雜耗時長的問題，根據(jù)數(shù)據(jù)集的維度特征屬性，通過凝聚層次聚類的方式對數(shù)據(jù)進行分層處理，并將其運用到小型Hadoop分布式系統(tǒng)中，通過服務器Master來對一般數(shù)據(jù)庫MySQL數(shù)據(jù)庫進行維護與待分層，并對其中的數(shù)據(jù)特征進行歸列，再按照流程傳遞到不同的Slave服務器使得處理好工作得以進行。Map過程之前將凝聚層次聚類規(guī)則作為預處理操作，完成數(shù)據(jù)模板文件的編寫。選取MVC模式應用到實驗模擬測試中：小型Hadoop分布式系統(tǒng)Master節(jié)點和Slave節(jié)點的運行效率比單機爬蟲的效率高了近65%。

Hadoop分布式；凝聚層次聚類；Master服務器；Slave服務器；分層調(diào)度

隨著全球進入互聯(lián)網(wǎng)時代，數(shù)據(jù)獲取技術的不斷發(fā)展帶來數(shù)據(jù)量不斷激增，數(shù)據(jù)的抓取調(diào)度成為關鍵信息有效采集的重點問題[1-3]。與此同時，計算機受物理器件性能的限制，為了滿足數(shù)據(jù)處理的要求，MySQL數(shù)據(jù)庫面對的調(diào)度處理的要求也在逐漸提高[4]，僅依靠CPU主頻的提升并不能快速的處理大數(shù)據(jù)帶來的壓力，快速有效的算法成為目前數(shù)據(jù)挖掘的主流[5-6]。本研究致力于數(shù)據(jù)挖掘分層調(diào)度處理，抓取的目標為各數(shù)據(jù)集的維度特征信息，最終設計并實現(xiàn)一種自配置的Hadoop分布式數(shù)據(jù)調(diào)度算法。因此，為了完成數(shù)據(jù)集分層調(diào)度功能的設計與實現(xiàn)，本系統(tǒng)主要包括兩大基本模塊：數(shù)據(jù)集的分層模塊和調(diào)度模塊。采用凝聚層次聚類對數(shù)據(jù)集進行分層處理，結(jié)合小型Hadoop分布式系統(tǒng)實現(xiàn)數(shù)據(jù)集分層調(diào)度。

1 算法基本思想

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

為了實現(xiàn)數(shù)據(jù)的分布式處理，通過選取Hadoop的分布式篩選過濾系統(tǒng)來實現(xiàn)數(shù)據(jù)的處理工作。Hadoop是一個主從式（Master-Slave）的分布處理框架[7]，整個系統(tǒng)的核心節(jié)點在于，與主從式的結(jié)構(gòu)相比較，在分布式系統(tǒng)通過服務器Master來對一般數(shù)據(jù)庫MySQL數(shù)據(jù)庫進行維護與待分層，并對其中的數(shù)據(jù)特征進行歸列，再按照流程傳遞到不同的Slave服務器使得處理好工作得以進行[8]。Master服務器不僅僅要對數(shù)據(jù)庫進行維護與待分層以及調(diào)度處理的工作，還需要對Slave服務器的各種載荷進行管理和評估，以使得Slave服務器的資源合理高效的分配與利用起來[9]。其基本結(jié)構(gòu)如圖1所示。

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

1.2 凝聚層次聚類算法

凝聚層次聚類的算法能夠?qū)Υ髷?shù)據(jù)集合進行層次的歸類，直到某種條件滿足為止。具體又可分為凝聚和分裂兩種方案[10]。凝聚層次聚類由下而上進行操作，它先選取集合內(nèi)得元素作為子簇，再將其合并，最終累積為更大的簇，這個過程持續(xù)到所有的元素都包括在一個簇內(nèi)，或者運行到其他的終結(jié)條件再結(jié)束。一般的層次聚類方法在集合間的簇與簇之間對于相似度的定義是各不相同的；還存在一種與凝聚的層次聚類相反的分裂層次聚類，它處理的準則是由下而上進行操作，它先在集合內(nèi)規(guī)劃好所有的元素，再將其定義為一個一個小簇，逐步細化，這樣的過程持續(xù)到集合內(nèi)的子簇自成一簇，或者運行到其他的終結(jié)條件再結(jié)束[11]。本文選取最小距離的凝聚型層次聚類算法。算法流程如圖2所示。

圖2 凝聚層次聚類算法流程

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

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

利用Hadoop平臺對分布式的數(shù)據(jù)進行分層，主要功能是根據(jù)數(shù)據(jù)集的多維度特征結(jié)構(gòu)[12]，對數(shù)據(jù)進行分類并從數(shù)據(jù)中提取出關鍵的信息完成數(shù)據(jù)的篩選，其中數(shù)據(jù)信息的提取是為數(shù)據(jù)分類調(diào)度工作做準備的，所以最終的目的在于完整提取MySQL數(shù)據(jù)庫中所有數(shù)據(jù)集的維度信息，并且要求盡量做到不重不漏。利用層次聚類的方法進行數(shù)據(jù)分層主要在于使用在同一數(shù)據(jù)庫出現(xiàn)頻率較高的數(shù)據(jù)，即出現(xiàn)率較高的數(shù)據(jù)，并且在其他數(shù)據(jù)庫中很少出現(xiàn)，則認為此數(shù)據(jù)具有很好的類別區(qū)分能力且適合用來分類[13]。將其應用到數(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)度處理分為兩個過程[14]：Map過程和Reduce過程。在Map過程之前，本系統(tǒng)將凝聚層次聚類規(guī)則作為預處理操作：即根據(jù)初始MySQL數(shù)據(jù)庫提取數(shù)據(jù)集分層信息，以鍵值對＜type，list_url＞的形式保存。這個過程比較簡單，代碼實現(xiàn)也不算復雜，因此，本系統(tǒng)采用單機預處理的方式實現(xiàn)就可以了[15]。Map函數(shù)輸入＜type，list_url＞格式的數(shù)據(jù)，根據(jù)list_data加載相應的數(shù)據(jù)集維度列表頁面，根據(jù)事先定義好的數(shù)據(jù)集維度列表鏈接的特征規(guī)則，提取數(shù)據(jù)集維度列表中的分層數(shù)據(jù)，并且根據(jù)pageNum遍歷所有MySQL數(shù)據(jù)庫信息，提取出來的信息以＜type_id，data＞的格式輸出[16]。Reduce函數(shù)接受Map函數(shù)的輸入，相同key值的輸入會由同一個Reduce函數(shù)處理，Reduce函數(shù)主要的工作是對輸出格式進行調(diào)整，并依據(jù)Hadoop的準則完成數(shù)據(jù)的處理與歸類，最終得到結(jié)果輸出文件[17]。數(shù)據(jù)的分層調(diào)度處理過程為：

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

Step.2：由初始data信息分層，根據(jù)層次聚類分配準則，在上一步加載的data信息分層進行數(shù)據(jù)信息化的提取操作，并將提取出來的數(shù)據(jù)子集依次放入數(shù)據(jù)集的維度隊列中，同時寫入列表文件list.txt；

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

Step.4：在data信息列表頁面，并根據(jù)凝聚層次聚類匹配規(guī)則，完成抽取調(diào)度，并計入詳情文件data.txt；

Step.5：判斷列表是否加載到最后一個維度特征，如果是的話，則該類分層下的data數(shù)據(jù)集分層工作完成。否則，加載data列表的下一個維度特征，進行第4步操作；

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

3 案例分析

為了提高系統(tǒng)的可用性，通過選取MVC的模式應用到本研究的算法設計中，其中MVC分層和各層的主要功能如下：

Model層：主要就是對應凝聚層次聚類模板類Template，該類包含了Template文件的所有參數(shù)信息，與XML文件內(nèi)容相對應，也是前后臺程序交互的主要部分。

View層：用于前端頁面的數(shù)據(jù)展示和數(shù)據(jù)交互，用JSP實現(xiàn)，頁面布局和樣式選用了bootstrap開源組件，其柵格布局使得控件大小和布局能夠自適應屏幕，頁面風格簡潔大方。頁面響應采用jQuery控制，為了增強用戶體驗，大量采用了ajax技術，使得頁面能夠提供豐富的功能，用戶的可操作性更強。

Controller層：將View層和Model層相連接，主要的業(yè)務邏輯，主要包括對凝聚層次聚類模板類Template文件的增刪查改操作，同時提供對后臺程序的控制功能（比如：啟動和停止程序）。各層之間的數(shù)據(jù)交互如圖3所示。

圖3 MVC模式

為了方便對系統(tǒng)的運行表現(xiàn)進行評測，本文選用了兩臺PC服務器，組建Hadoop分布式集群，選擇其中一臺設備作為Master節(jié)點，另一臺作為Slave節(jié)點，服務器配置如表1所示。

表1 硬件配置

為了完成系統(tǒng)性能分析與比較，本研究分別在單機和分布式的環(huán)境下進行了4個小時左右的數(shù)據(jù)調(diào)度測試，比較結(jié)果如表2所示。

從表2中可以看出，單節(jié)點得到的結(jié)果比較理想，數(shù)據(jù)信息調(diào)度效率較高。分布式測試中，單個節(jié)點的效率同單機節(jié)點相比下降了一些，但是這個性能下降是必然的，而且在正常的范圍之內(nèi)，網(wǎng)絡帶寬成了數(shù)據(jù)調(diào)度的主要瓶頸，而且小型Hadoop分布式分層條件下，系統(tǒng)還要承擔作業(yè)調(diào)度、系統(tǒng)IO、數(shù)據(jù)備份等額外開銷，所以單個節(jié)點的數(shù)據(jù)信息調(diào)度效率反而降低了，但是總體來看，分布式系統(tǒng)兩個節(jié)點的運行效率比單機爬蟲的效率高了近65%，這也是分布式計算的優(yōu)勢

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

4 結(jié) 論

文中設計并實現(xiàn)了一種基于小型Hadoop分布式的數(shù)據(jù)分層調(diào)度系統(tǒng)，解決了大數(shù)據(jù)背景下，MySQL數(shù)據(jù)庫信息的快速采集調(diào)度問題。依據(jù)數(shù)據(jù)集的維度特征屬性，利用凝聚層次聚類算法完成數(shù)據(jù)模板文件的編寫，實現(xiàn)了數(shù)據(jù)集在Master節(jié)點服務器的分層功能，保證了小型Hadoop分布式系統(tǒng)具有良好的可擴展性。本研究的算法設計采用MVC的設計模式，結(jié)果表明，小型Hadoop分布式系統(tǒng)的Master節(jié)點和Slave節(jié)點的運行效率比單機爬蟲的效率高了近65%，使得本系統(tǒng)具有很強的擴展性和靈活性，可以根據(jù)實際業(yè)務需求動態(tài)調(diào)整節(jié)點數(shù)量。

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

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

[3]王元卓，靳小龍，程學旗.網(wǎng)絡大數(shù)據(jù):現(xiàn)狀與展望[J].計算機學報，2013，36（6）:1125-1138.

[4]張偉麗，江春華，魏勁超.MySQL復制技術的研究及應用[J].計算機科學，2012，39（3）:168-170.

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

[6]張繼福，李永紅，秦嘯，等.基于MapReduce與相關子空間的局部離群數(shù)據(jù)挖掘算法 [J].軟件學報，2015，26（5）:1079-1095.

[7]陳文波，張秀娟，李林，等.基于Hadoop的分布式日志分析系統(tǒng)，廣西大學學報：自然科學版，2011，36（1）:339-342.

[8]王淑芬，高軍禮，鄒普，等.基于Hadoop的廣域網(wǎng)分布式主題爬蟲系統(tǒng)框架[J].計算機工程與科學，2015，37（4）:670-675.

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

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

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

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

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

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

[15]宋瑩，沈奇威，王晶.基于Hadoop的Web日志預處理的設計與實現(xiàn) [J].電信工程技術與標準化，2011，24（11）:84-89.

[16]李瑞霞，劉仁金，周先存.基于哈希表的MapReduce算法優(yōu)化[J].山東大學學報（理學版），2015（7）:66-70.

[17]陳吉榮，樂嘉錦.基于MapReduce的Hadoop大表導入編程模型 [J].計算機應用，2013，33（9）:2486-2489.

Herarchical scheduling algorithm based on small Hadoop cluster data processing

WANG Wei，SU Qi，LIU Meng，ZHOU Wei，YU Zhan-peng，MU Lin
（State Grid Shandong Electric Power Company，Ji'nan 250001，China）

Scheduling for the current fetch huge amount of data and computationally complex timeconsuming issue，according to the dimension feature attribute data set，by the way cohesion hierarchical clustering data slicing，and apply it to small Hadoop distributed system，Master server maintenance to be stratified MySQL database cube dimensions characterized queue，send to a different server Slave scheduling process.The agglomeration process before Map hierarchical clustering rule as a preprocessing operation to complete the write data template files.MVC design pattern using experimental test:the efficiency of small-scale Hadoop Distributed System Master and Slave node node high of nearly 65%over single reptile efficiency.

Hadoop distributed； agglomerative hierarchical clustering； Master server； Slave server；hierarchical scheduling

TN393

：A

：1674－6236（2017）14-0055-04

2016-05-12稿件編號：201605120

王 瑋（1970—），女，山東濟南人，碩士，高級工程師。研究方向：信息系統(tǒng)軟硬件架構(gòu)設計和管理。