黃少卿，胡立強（中國移動通信集團設(shè)計院有限公司　河北分公司，河北　石家莊　050021）

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

黃少卿，胡立強
（中國移動通信集團設(shè)計院有限公司河北分公司，河北石家莊050021）

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4小結(jié)

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

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

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

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

（2）對于每一個運行在節(jié)點上的Task，其執(zhí)行剩余時間=（1-當前進度）/任務(wù)平均計算速度，其中任務(wù)平均計算速度=當前進度/執(zhí)行時間；

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

（4）當推測節(jié)點任務(wù)執(zhí)行完畢后，強制結(jié)束執(zhí)行同任務(wù)節(jié)點進程。

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

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

3　采用改進SALS算法對Hadoop推測調(diào)度調(diào)優(yōu)

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

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

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

（3）對TaskQueue進行動態(tài)排隊，每1分鐘1次，并對隊尾節(jié)點進行判定：

（a）運行時間超過其他節(jié)點運行時間的1.5倍；

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

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

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

4　實驗驗證

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

圖3　推測算法驗證

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

5　結(jié)論

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

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

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

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

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

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

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

［7］周揚.Hadoop平臺下調(diào)度算法和下載機制的優(yōu)化［D］.長沙：中南大學(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。

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