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

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

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

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

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

大數據挖掘；Hadoop；推測調度；SALS

0　引言

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

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

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

1　現行的大數據挖掘技術

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

1.1MPP架構新型數據庫技術

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

圖1　MPP服務器架構圖

1.2大數據一體機

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

1.3Hadoop開源大數據技術

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

圖2　Hadoop服務器架構圖

1.4小結

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

2　現行的Hadoop推測調度對大數據挖掘的影響

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

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

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

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

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

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

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

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

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

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

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

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

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

（b）若為非Reduce任務，任務進度與上次更新差別在10％以內；

（c）若為Reduce任務，根據shuffle數據量更新進度，任務進度與上次更新差別在10％以內。

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

4　實驗驗證

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

圖3　推測算法驗證

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

5　結論

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

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

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

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

［4］孫朝華.基于Storm的數據分析系統設計與實現［D］.北京：北京郵電大學，2014.

［5］辛晃，易興輝，陳震宇.基于Hadoop+MPP架構的電信運營商網絡數據共享平臺研究［J］.電信科學，2014（4）：135-145.

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

［7］周揚.Hadoop平臺下調度算法和下載機制的優(yōu)化［D］.長沙：中南大學，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-），通信作者，男，碩士，系統分析師，主要研究方向：軟件工程、Web數據挖掘、IT支撐系統。E-mail：leo12_leo@163.com。

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