黃少卿，胡立強(qiáng)（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司　河北分公司，河北　石家莊　050021）

基于改進(jìn)SALS算法的大數(shù)據(jù)挖掘效率優(yōu)化探究

黃少卿，胡立強(qiáng)
（中國(guó)移動(dòng)通信集團(tuán)設(shè)計(jì)院有限公司河北分公司，河北石家莊050021）

移動(dòng)互聯(lián)網(wǎng)時(shí)代，各類移動(dòng)網(wǎng)絡(luò)終端的使用在為移動(dòng)用戶帶來便利的同時(shí)，也為運(yùn)營(yíng)商提供了海量的可供挖掘數(shù)據(jù)來源。運(yùn)用大數(shù)據(jù)技術(shù)對(duì)非結(jié)構(gòu)、半結(jié)構(gòu)、結(jié)構(gòu)化數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘，可以有效提高挖掘效率，幫助運(yùn)營(yíng)商找到潛在商機(jī)、提升用戶體驗(yàn)、進(jìn)行精確營(yíng)銷。針對(duì)大數(shù)據(jù)挖掘中存在的效率問題，提出了基于改進(jìn)SALS算法的Hadoop推測(cè)調(diào)度，從而減少異構(gòu)環(huán)境下的資源浪費(fèi)，提高大數(shù)據(jù)挖掘效率。

大數(shù)據(jù)挖掘；Hadoop；推測(cè)調(diào)度；SALS

0　引言

移動(dòng)互聯(lián)網(wǎng)時(shí)代，隨著3G/4G的普及，網(wǎng)絡(luò)建設(shè)速度的加快，以及大規(guī)模的數(shù)碼設(shè)備的使用，移動(dòng)運(yùn)營(yíng)商業(yè)務(wù)和數(shù)據(jù)規(guī)模的擴(kuò)張呈幾何級(jí)增長(zhǎng)［1］。以某省的基本數(shù)據(jù)量為例，其語(yǔ)音通話記錄每天入庫(kù)2.5TB，SMS話單記錄每天入庫(kù)800GB以上，MC口信令數(shù)據(jù)每天20TB，GN口信令數(shù)據(jù)每天8TB，警告、性能等數(shù)據(jù)每天約3TB。再計(jì)算通過機(jī)器設(shè)備、服務(wù)器、軟件自動(dòng)產(chǎn)生的各類非人機(jī)會(huì)話數(shù)據(jù)，以非結(jié)構(gòu)和半結(jié)構(gòu)化形式呈現(xiàn)的數(shù)據(jù)已經(jīng)遠(yuǎn)遠(yuǎn)超過了傳統(tǒng)關(guān)系型數(shù)據(jù)處理的能力范疇。

傳統(tǒng)的RDBMS可以處理結(jié)構(gòu)化數(shù)據(jù)，其缺點(diǎn)是系統(tǒng)孤立、處理數(shù)據(jù)量小，面對(duì)移動(dòng)互聯(lián)網(wǎng)時(shí)代數(shù)據(jù)暴增的特點(diǎn)，IT系統(tǒng)的可擴(kuò)展性、成本控制、數(shù)據(jù)有效性挖掘均需要通過低成本的通用設(shè)備，通過構(gòu)建“池化資源”并結(jié)合“大數(shù)據(jù)挖掘”能力來推進(jìn)業(yè)務(wù)進(jìn)展。

池化資源指通過運(yùn)用虛擬化技術(shù)，將單個(gè)物理機(jī)器資源進(jìn)行分割或者將多臺(tái)物理機(jī)器資源進(jìn)行整合，充分利用物理機(jī)的處理能力，實(shí)現(xiàn)物理機(jī)的高效分配和利用［2］。大數(shù)據(jù)挖掘則針對(duì)具有4V特點(diǎn)的海量數(shù)據(jù)進(jìn)行壓縮、去重、整理、交叉分析和對(duì)比，并結(jié)合關(guān)聯(lián)、聚合等傳統(tǒng)數(shù)據(jù)挖掘技術(shù)對(duì)非結(jié)構(gòu)化和半結(jié)構(gòu)化的數(shù)據(jù)進(jìn)行分析［3］。本文通過對(duì)現(xiàn)有大數(shù)據(jù)挖掘技術(shù)的分析比對(duì)，就其中涉及的數(shù)據(jù)查詢的可優(yōu)化部分進(jìn)行深入討論。

1　現(xiàn)行的大數(shù)據(jù)挖掘技術(shù)

自大數(shù)據(jù)概念誕生以來，陸續(xù)出現(xiàn)了多種大數(shù)據(jù)挖掘處理技術(shù)，如果以處理的實(shí)時(shí)性來分類，可以將大數(shù)據(jù)挖掘處理技術(shù)分為兩類：實(shí)時(shí)類處理技術(shù)和批處理技術(shù)。實(shí)時(shí)類大數(shù)據(jù)挖掘處理技術(shù)有Storm、S4［4］等，而批處理技術(shù)或者稱為線下處理技術(shù)的典型代表則是MapReduce。對(duì)于移動(dòng)運(yùn)營(yíng)商來講，實(shí)時(shí)處理能力固然重要，但是通過大批量的線下數(shù)據(jù)處理找到潛在的商業(yè)契機(jī)、提升用戶體驗(yàn)、實(shí)施決策分析、精準(zhǔn)營(yíng)銷推薦、運(yùn)營(yíng)效能提升、創(chuàng)新商業(yè)模式等對(duì)于運(yùn)營(yíng)商來說更為重要。本文關(guān)注大數(shù)據(jù)批處理中現(xiàn)有技術(shù)的性能提升。

1.1MPP架構(gòu)新型數(shù)據(jù)庫(kù)技術(shù)

MPP（Massive Parallel Processing）從構(gòu)成上來講，是由多個(gè)SMP服務(wù)器橫向擴(kuò)展組成的分布式服務(wù)器集群［5］。但MPP架構(gòu)并不是一種池化資源的大數(shù)據(jù)處理架構(gòu)，集群中的每個(gè)節(jié)點(diǎn)均可訪問本地資源，采用Share Nothing結(jié)構(gòu)，集群節(jié)點(diǎn)之間并不存在共享及互訪問的問題，而是通過統(tǒng)一的互聯(lián)模塊來調(diào)度、平衡節(jié)點(diǎn)負(fù)載和并行處理過程。其架構(gòu)如圖1所示。

圖1　MPP服務(wù)器架構(gòu)圖

1.2大數(shù)據(jù)一體機(jī)

大數(shù)據(jù)一體機(jī)是商業(yè)公司專門為處理大數(shù)據(jù)而設(shè)計(jì)的軟硬件一體機(jī)，由集成服務(wù)器、存儲(chǔ)、操作系統(tǒng)、數(shù)據(jù)庫(kù)軟件、其他數(shù)據(jù)分析軟件等統(tǒng)一封裝在機(jī)箱內(nèi)，經(jīng)過運(yùn)營(yíng)商對(duì)數(shù)據(jù)處理流程進(jìn)行優(yōu)化，從而形成高性能的大數(shù)據(jù)處理能力。

1.3Hadoop開源大數(shù)據(jù)技術(shù)

Hadoop技術(shù)框架是以MapReduce為核心的一個(gè)開源大數(shù)據(jù)處理框架，其架構(gòu)如圖2所示。其中，最底層的HDFS為分布式文件系統(tǒng)，底層使用廉價(jià)x86進(jìn)行冗余備份；MapReduce分為map、shuffle和 reduce階段［6］，map階段對(duì)處理數(shù)據(jù)進(jìn)行分解映射，分開處理，shuffle階段拽取map階段數(shù)據(jù)到reduce端，reduce階段對(duì)處理子集進(jìn)行歸約合并，得到處理結(jié)果；HBase不同于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)，是一種基于列的分布式數(shù)據(jù)庫(kù)。

圖2　Hadoop服務(wù)器架構(gòu)圖

1.4小結(jié)

三種大數(shù)據(jù)挖掘處理技術(shù)各有特點(diǎn)，綜合比較如下：根據(jù)CAP理論，在兼顧分區(qū)性、一致性和分區(qū)可容忍性的情況下，MPP擴(kuò)展能力有限，目前最多可以橫向擴(kuò)展至500個(gè)節(jié)點(diǎn)，并且MPP成本較高，以處理結(jié)構(gòu)性重要數(shù)據(jù)為主。大數(shù)據(jù)一體機(jī)環(huán)境封閉，例如Oracle的ExtData，技術(shù)實(shí)現(xiàn)細(xì)節(jié)不清晰，在處理性能上難以做出橫向?qū)Ρ?，且成本高，這里暫不做討論。Hadoop以處理非結(jié)構(gòu)化和半結(jié)構(gòu)化數(shù)據(jù)為主，橫向擴(kuò)展能力達(dá)到1 000個(gè)節(jié)點(diǎn)以上，并且支持廠家和社區(qū)龐大，成本低廉，是一項(xiàng)較好的大數(shù)據(jù)挖掘框架技術(shù)。

2　現(xiàn)行的Hadoop推測(cè)調(diào)度對(duì)大數(shù)據(jù)挖掘的影響

采用Hadoop開源框架進(jìn)行大數(shù)據(jù)挖掘，具有較多的便利條件：Hive的使用可以簡(jiǎn)化數(shù)據(jù)挖掘程序的編寫，只需要掌握普通SQL操作即可進(jìn)行程序編寫；基于HDFS和MapReduce的分布式特點(diǎn)，數(shù)據(jù)挖掘任務(wù)可以在多臺(tái)機(jī)器、不限地域的情況下實(shí)施，縮短了挖掘時(shí)間，提高了挖掘效率。但是，Hadoop對(duì)分布式任務(wù)進(jìn)行推測(cè)調(diào)度的算法上存在效率問題［7］，下面對(duì)該調(diào)度進(jìn)行概要分析。

（1）為防止任務(wù)因機(jī)器故障、程序意外中斷引起的任務(wù)執(zhí)行時(shí)間過長(zhǎng)，Hadoop啟用了推測(cè)調(diào)度，即啟用新節(jié)點(diǎn)對(duì)卡殼任務(wù)進(jìn)行重新執(zhí)行；

（2）對(duì)于每一個(gè)運(yùn)行在節(jié)點(diǎn)上的Task，其執(zhí)行剩余時(shí)間=（1-當(dāng)前進(jìn)度）/任務(wù)平均計(jì)算速度，其中任務(wù)平均計(jì)算速度=當(dāng)前進(jìn)度/執(zhí)行時(shí)間；

（3）根據(jù)（2）對(duì)所有Task執(zhí)行剩余時(shí)間進(jìn)行排序，選出最大的 Task，若其平均計(jì)算速度＜其他任務(wù)平均速度，則對(duì)該任務(wù)進(jìn)行推測(cè)，啟用新節(jié)點(diǎn)執(zhí)行該節(jié)點(diǎn)的任務(wù)；

（4）當(dāng)推測(cè)節(jié)點(diǎn)任務(wù)執(zhí)行完畢后，強(qiáng)制結(jié)束執(zhí)行同任務(wù)節(jié)點(diǎn)進(jìn)程。

上述過程在同構(gòu)環(huán)境且多任務(wù)運(yùn)行的情況下，可以一定程度地避免硬件故障及程序bug對(duì)整個(gè)MapReduce的影響。但其存在如下可能的推測(cè)調(diào)度缺陷：（1）由于啟動(dòng)新節(jié)點(diǎn)重復(fù)執(zhí)行某任務(wù)，會(huì)造成同時(shí)存在兩個(gè)以上節(jié)點(diǎn)執(zhí)行同樣任務(wù)，造成資源浪費(fèi)；（2）當(dāng)在異構(gòu)環(huán)境下（硬件機(jī)器廠商不同、運(yùn)行操作系統(tǒng)差異、機(jī)器性能差異等），任務(wù)節(jié)點(diǎn)的資源性能并不等同，以上述標(biāo)準(zhǔn)判斷是否需要啟動(dòng)推測(cè)調(diào)度，會(huì)出現(xiàn)較大誤差，形成無(wú)效的調(diào)度，從而使新任務(wù)得不到節(jié)點(diǎn)來執(zhí)行任務(wù)；（3）Hadoop針對(duì)Reduce階段任務(wù)劃分為復(fù)制、排序、歸并，并規(guī)定每一階段占據(jù)1/3進(jìn)度；然而，統(tǒng)計(jì)表明，復(fù)制階段最消耗時(shí)間和資源，明顯存在不合理調(diào)度。

針對(duì)這些問題，本文在SALS算法基礎(chǔ)上進(jìn)行改進(jìn)，從而提高Hadoop的推測(cè)調(diào)度效率，減少重復(fù)任務(wù)，加快MapReduce的執(zhí)行。

3　采用改進(jìn)SALS算法對(duì)Hadoop推測(cè)調(diào)度調(diào)優(yōu)

SALS算法原本用于鄰近節(jié)點(diǎn)搜索，首先確定節(jié)點(diǎn)集合，然后根據(jù)權(quán)重與節(jié)點(diǎn)間舉例建立聯(lián)系圖。這里，選取節(jié)點(diǎn)集合節(jié)點(diǎn)的判定，在第二階段根據(jù)Hadoop的推測(cè)調(diào)度進(jìn)行修改。

（1）對(duì)所有運(yùn)行Task節(jié)點(diǎn)進(jìn)行排隊(duì)，形成TaskQueue，該隊(duì)列保存Slave節(jié)點(diǎn)任務(wù)的索引，以節(jié)省空間；

（2）根據(jù)歷史平均速率，對(duì)空閑節(jié)點(diǎn)進(jìn)行排隊(duì)，速率高節(jié)點(diǎn)在隊(duì)列頭部，從未運(yùn)行過節(jié)點(diǎn)速率為所有空閑節(jié)點(diǎn)平均速率，插入到隊(duì)列中，形成FreeQueue；

（3）對(duì)TaskQueue進(jìn)行動(dòng)態(tài)排隊(duì)，每1分鐘1次，并對(duì)隊(duì)尾節(jié)點(diǎn)進(jìn)行判定：

（a）運(yùn)行時(shí)間超過其他節(jié)點(diǎn)運(yùn)行時(shí)間的1.5倍；

（b）若為非Reduce任務(wù)，任務(wù)進(jìn)度與上次更新差別在10％以內(nèi)；

（c）若為Reduce任務(wù)，根據(jù)shuffle數(shù)據(jù)量更新進(jìn)度，任務(wù)進(jìn)度與上次更新差別在10％以內(nèi)。

（4）符合（3）-（a）且符合（3）-（b）或（3）-（c）時(shí)，對(duì)隊(duì)尾任務(wù)啟動(dòng)新節(jié)點(diǎn)進(jìn)行執(zhí)行，立即結(jié)束當(dāng)前節(jié)點(diǎn)并做標(biāo)記，形成BugQueue以備檢查節(jié)點(diǎn)狀態(tài)。

4　實(shí)驗(yàn)驗(yàn)證

為檢驗(yàn)上述算法的有效性，啟用1臺(tái)機(jī)器作為主節(jié)點(diǎn)（2GB內(nèi)存，80GB存儲(chǔ)，Ubuntu OS），4臺(tái)機(jī)器作為從屬節(jié)點(diǎn)（分別為1GB、256MB、256MB、512MB內(nèi)存，兩個(gè)Ubuntu OS，兩個(gè)Red Hat OS）進(jìn)行試驗(yàn)。先后部署Hadoop環(huán)境和改進(jìn)推測(cè)調(diào)度的Hadoop環(huán)境進(jìn)行驗(yàn)證，結(jié)果如圖3所示。

圖3　推測(cè)算法驗(yàn)證

實(shí)驗(yàn)表明，基于改進(jìn)的SALS推測(cè)調(diào)度相較于基礎(chǔ)Hadoop推測(cè)調(diào)度能提高40％左右的時(shí)間，達(dá)到了改進(jìn)目的。采用該改進(jìn)的SALS算法后，可以減少重復(fù)任務(wù)的執(zhí)行數(shù)量并及時(shí)釋放可能存在問題的節(jié)點(diǎn)以備檢查。合理更新Reduce任務(wù)進(jìn)度，減少出現(xiàn)活躍任務(wù)節(jié)點(diǎn)被關(guān)閉現(xiàn)象。加強(qiáng)推測(cè)調(diào)度的準(zhǔn)確性，對(duì)節(jié)點(diǎn)資源進(jìn)行高效利用，提高了大數(shù)據(jù)挖掘的效率。

5　結(jié)論

移動(dòng)互聯(lián)網(wǎng)時(shí)代，大數(shù)據(jù)技術(shù)在數(shù)據(jù)挖掘方面所起的作用越來越重要。針對(duì)其中可以優(yōu)化改進(jìn)的流程和技術(shù)環(huán)節(jié)還有許多可以深究之處?；诟倪M(jìn)的SALS算法優(yōu)化的推測(cè)調(diào)度，在流程方面優(yōu)化了大數(shù)據(jù)挖掘，提高了Hadoop推測(cè)調(diào)度的準(zhǔn)確性和有效性。除此之外，大數(shù)據(jù)查詢優(yōu)化、大數(shù)據(jù)不同架構(gòu)之間的融合使用等均值得進(jìn)一步研究。

［1］馬建光，姜巍.大數(shù)據(jù)的概念、特征及其應(yīng)用［J］.國(guó)防科技，2013，34（2）：10-17.

［2］葛中澤，夏小翔.基于資源池的數(shù)據(jù)訪問模式的探討［J］.科學(xué)技術(shù)與工程，2012，12（33）：9066-9060.

［3］吉根林，趙斌.面向大數(shù)據(jù)的時(shí)空數(shù)據(jù)挖掘綜述［J］.南京師大學(xué)報(bào)，2014，37（1）：1-7.

［4］孫朝華.基于Storm的數(shù)據(jù)分析系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)［D］.北京：北京郵電大學(xué)，2014.

［5］辛晃，易興輝，陳震宇.基于Hadoop+MPP架構(gòu)的電信運(yùn)營(yíng)商網(wǎng)絡(luò)數(shù)據(jù)共享平臺(tái)研究［J］.電信科學(xué)，2014（4）：135-145.

［6］張常淳.基于MapReduce的大數(shù)據(jù)連接算法的設(shè)計(jì)與優(yōu)化［D］.合肥：中國(guó)科學(xué)技術(shù)大學(xué)，2014.

［7］周揚(yáng).Hadoop平臺(tái)下調(diào)度算法和下載機(jī)制的優(yōu)化［D］.長(zhǎng)沙：中南大學(xué)，2012.

Research on optimization of big data mining based on SALS algorism

Huang Shaoqing，Hu Liqiang
（China Mobile Group Design Institute Co.，Ltd.，Shijiazhuang 050021，China）

In the Mobile Internet age，all kinds of network terminals bring convenience to the users and provide huge amount of data.Using Big Data technology to mine all the non-structured，half-structured，and structured data.The mobile operators could find potential business model，improve user′s experience and make accurate sale.Aiming at solving efficiency problem in Hadoop speculation scheduling，this paper proposes an improved SALS algorithm to reduce resource wasting and improve big data mining efficiency.

big data mining；Hadoop；speculation scheduling；SALS

TP311

A

1674-7720（2015）12-0011-03

2015-01-09）

黃少卿（1988-），通信作者，男，碩士，系統(tǒng)分析師，主要研究方向：軟件工程、Web數(shù)據(jù)挖掘、IT支撐系統(tǒng)。E-mail：leo12_leo@163.com。

胡立強(qiáng)（1975-）男，碩士，高級(jí)工程師，主要研究方向：移動(dòng)通信支撐網(wǎng)、IP承載網(wǎng)等。