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

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

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

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

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

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

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

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

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

1 算法基本思想

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

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

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

1.2 凝聚層次聚類(lèi)算法

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

圖2 凝聚層次聚類(lèi)算法流程

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

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

利用Hadoop平臺(tái)對(duì)分布式的數(shù)據(jù)進(jìn)行分層，主要功能是根據(jù)數(shù)據(jù)集的多維度特征結(jié)構(gòu)[12]，對(duì)數(shù)據(jù)進(jìn)行分類(lèi)并從數(shù)據(jù)中提取出關(guān)鍵的信息完成數(shù)據(jù)的篩選，其中數(shù)據(jù)信息的提取是為數(shù)據(jù)分類(lèi)調(diào)度工作做準(zhǔn)備的，所以最終的目的在于完整提取MySQL數(shù)據(jù)庫(kù)中所有數(shù)據(jù)集的維度信息，并且要求盡量做到不重不漏。利用層次聚類(lèi)的方法進(jìn)行數(shù)據(jù)分層主要在于使用在同一數(shù)據(jù)庫(kù)出現(xiàn)頻率較高的數(shù)據(jù)，即出現(xiàn)率較高的數(shù)據(jù)，并且在其他數(shù)據(jù)庫(kù)中很少出現(xiàn)，則認(rèn)為此數(shù)據(jù)具有很好的類(lèi)別區(qū)分能力且適合用來(lái)分類(lèi)[13]。將其應(yīng)用到數(shù)據(jù)信息挖掘中，與此同時(shí)，隨著數(shù)據(jù)的不斷存入，數(shù)據(jù)的分層會(huì)隨著時(shí)間改變，離現(xiàn)在越久的聚類(lèi)分層，變化的可能性越大，很久以前的分層對(duì)于構(gòu)建層次聚類(lèi)模型來(lái)說(shuō)意義不大，因此需要考慮數(shù)據(jù)量分層相對(duì)時(shí)間的衰減。本研究選用MySQL數(shù)據(jù)庫(kù)存儲(chǔ)發(fā)生時(shí)間戳與上一周期存儲(chǔ)的秒數(shù)差與一個(gè)周期的總秒數(shù)的比值，作為一個(gè)線性衰減要素，加入到算法中。為了方便程序的編寫(xiě)，下面給出數(shù)據(jù)集調(diào)度功能的偽代碼實(shí)現(xiàn)：

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

基于Hadoop的數(shù)據(jù)分層調(diào)度處理分為兩個(gè)過(guò)程[14]：Map過(guò)程和Reduce過(guò)程。在Map過(guò)程之前，本系統(tǒng)將凝聚層次聚類(lèi)規(guī)則作為預(yù)處理操作：即根據(jù)初始MySQL數(shù)據(jù)庫(kù)提取數(shù)據(jù)集分層信息，以鍵值對(duì)＜type，list_url＞的形式保存。這個(gè)過(guò)程比較簡(jiǎn)單，代碼實(shí)現(xiàn)也不算復(fù)雜，因此，本系統(tǒng)采用單機(jī)預(yù)處理的方式實(shí)現(xiàn)就可以了[15]。Map函數(shù)輸入＜type，list_url＞格式的數(shù)據(jù)，根據(jù)list_data加載相應(yīng)的數(shù)據(jù)集維度列表頁(yè)面，根據(jù)事先定義好的數(shù)據(jù)集維度列表鏈接的特征規(guī)則，提取數(shù)據(jù)集維度列表中的分層數(shù)據(jù)，并且根據(jù)pageNum遍歷所有MySQL數(shù)據(jù)庫(kù)信息，提取出來(lái)的信息以＜type_id，data＞的格式輸出[16]。Reduce函數(shù)接受Map函數(shù)的輸入，相同key值的輸入會(huì)由同一個(gè)Reduce函數(shù)處理，Reduce函數(shù)主要的工作是對(duì)輸出格式進(jìn)行調(diào)整，并依據(jù)Hadoop的準(zhǔn)則完成數(shù)據(jù)的處理與歸類(lèi)，最終得到結(jié)果輸出文件[17]。數(shù)據(jù)的分層調(diào)度處理過(guò)程為：

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

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

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

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

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

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

3 案例分析

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

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

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

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

圖3 MVC模式

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

表1 硬件配置

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

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

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

4 結(jié) 論

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

[1]賀瑤，王文慶，薛飛.基于云計(jì)算的海量數(shù)據(jù)挖掘研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013（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）:1125-1138.

[4]張偉麗，江春華，魏勁超.MySQL復(fù)制技術(shù)的研究及應(yīng)用[J].計(jì)算機(jī)科學(xué)，2012，39（3）:168-170.

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

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

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

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

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

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

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

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

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

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

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

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

[17]陳吉榮，樂(lè)嘉錦.基于MapReduce的Hadoop大表導(dǎo)入編程模型 [J].計(jì)算機(jī)應(yīng)用，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稿件編號(hào)：201605120

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