譚造樂 ，郝志峰 ，蔡瑞初 ，肖曉軍 ，盧宇

（1.廣東工業(yè)大學(xué)計算機學(xué)院，廣東 廣州510006；2.廣州優(yōu)億信息科技有限公司，廣東 廣州 510630）

基于信息增益的Hadoop瓶頸檢測算法

譚造樂1，郝志峰1，蔡瑞初1，肖曉軍2，盧宇2

（1.廣東工業(yè)大學(xué)計算機學(xué)院，廣東 廣州510006；2.廣州優(yōu)億信息科技有限公司，廣東 廣州 510630）

當今，Hadoop已經(jīng)成為了大數(shù)據(jù)存儲和大數(shù)據(jù)挖掘的主要平臺。雖然Hadoop平臺通過分布式的機器集群來實現(xiàn)高性能的并行計算，但由于其由廉價主機組成，故當集群負載增大時，便不可避免地在某機器上出現(xiàn)瓶頸。針對此問題，提出一種基于信息增益的瓶頸檢測算法，該算法通過計算各個資源的信息增益來檢測集群的瓶頸資源。實驗證明了該瓶頸檢測算法具有可行性。

大數(shù)據(jù)；Hadoop；信息增益；瓶頸檢測

1 引言

而今互聯(lián)網(wǎng)迅猛地發(fā)展，無論是網(wǎng)民規(guī)模還是網(wǎng)頁規(guī)模均呈現(xiàn)出爆炸式增長。截至2015年12月，我國網(wǎng)民規(guī)模達6.88億人，而網(wǎng)頁數(shù)量更是高達2 123億個[1]。隨之而來的便是網(wǎng)絡(luò)數(shù)據(jù)的指數(shù)增長。故傳統(tǒng)的數(shù)據(jù)處理框架已經(jīng)難以應(yīng)對當今海量數(shù)據(jù)的處理。而Hadoop的出現(xiàn)可以很好地解決海量數(shù)據(jù)分析處理的難題。其通過分散數(shù)據(jù)集，使計算能在分布式集群里高度并行地執(zhí)行。Hadoop使得在廉價機器集群上處理大數(shù)據(jù)集得以實現(xiàn)。

雖然Hadoop很好地解決了大數(shù)據(jù)的存儲和處理問題，但隨著數(shù)據(jù)的多樣化以及企業(yè)對數(shù)據(jù)處理的需求更嚴格，Hadoop在性能方面也呈現(xiàn)出了缺陷。國內(nèi)有不少學(xué)者針對Hadoop優(yōu)化方面進行了研究。如參考文獻[2]通過mapFile、HBase等Hadoop生態(tài)系統(tǒng)的相關(guān)組件，對小文件處理進行優(yōu)化；參考文獻[3]在底層的調(diào)度器方面對Hadoop進行優(yōu)化；而參考文獻[4-6]則通過MapReduce參數(shù)調(diào)整優(yōu)化了提高Hadoop性能。但這些都只局限于優(yōu)化，而忽視了具體瓶頸檢測方面的研究。針對系統(tǒng)瓶頸檢測，參考文獻[7]用機器學(xué)習(xí)的方法來計算SLO滿意度并對系統(tǒng)瓶頸進行檢測；參考文獻[8]提出一種基于決策樹的瓶頸檢測方法，但其局限于針對運行Web服務(wù)的平臺進行檢測?；诖耍疚奶岢鲆环N基于資源信息增益的瓶頸檢測算法，通過對集群性能進行監(jiān)控，檢測瓶頸的出現(xiàn)。然后通過各個資源使用率和評價指標響應(yīng)滿意度（response satisfaction，RS）的樣本計算各種資源的信息增益，選取信息最大的資源作為集群的瓶頸資源。在確定瓶頸資源后便可以針對該瓶頸資源進行相應(yīng)調(diào)節(jié)措施，從而對集群進行優(yōu)化。實驗通過Wordcount和文本聚類這兩類測試用例來驗證瓶頸檢測算法的可行性。通過增加Wordcount輸入文件大小和文本聚類數(shù)據(jù)量來不斷增加負載，然后使用本文的檢測算法來確定瓶頸資源。實驗證明，應(yīng)用本文的檢測算法后的集群性能比優(yōu)化前有很好的提升?？梢姳疚奶岢龅钠款i檢測算法能有效地檢測出具體的瓶頸資源，為集群調(diào)整優(yōu)化提供了堅實的基礎(chǔ)。

2 Hadoop平臺架構(gòu)

Hadoop是開源社區(qū)Apache根據(jù)谷歌公布的分布式文件系統(tǒng)（GFS）技術(shù)[9]和 MapReduce[10]編程模型而開發(fā)出的分布式處理框架。其不僅使用一種廉價的方式對海量數(shù)據(jù)進行存儲，還提供高效可靠且可擴展的數(shù)據(jù)處理機制。其中，分布式文件系統(tǒng)HDFS(Hadoop distributed file system)和MapReduce是Hadoop的核心部分。HDFS為海量的數(shù)據(jù)提供了存儲，MapReduce則為海量的數(shù)據(jù)提供了計算。HDFS的流程架構(gòu)如圖1所示。其中，nameNode（主節(jié)點）扮演著管理者的角色，其保存了整個集群文件系統(tǒng)的所有元數(shù)據(jù)。這些元數(shù)據(jù)包含文件名、訪問權(quán)限和各個塊的位置，一般保存在內(nèi)存中，從而保證快速的隨機訪問。而dataNode（數(shù)據(jù)節(jié)點）是存儲的基本單元。HDFS是基于塊結(jié)構(gòu)的文件系統(tǒng)。其將單個文件拆分成固定大小的塊，然后將這些塊保存在數(shù)據(jù)節(jié)點中。同時數(shù)據(jù)節(jié)點會周期性地向主節(jié)點發(fā)送心跳信息和本地的塊報告。當客戶端需要讀數(shù)據(jù)時，首先從主節(jié)點獲取數(shù)據(jù)所在的位置信息，即哪些數(shù)據(jù)節(jié)點保存有要讀數(shù)據(jù)的塊。然后客戶端與最近的數(shù)據(jù)節(jié)點進行通信，讀取所需數(shù)據(jù)。

而MapReduce編程模型采用“分而治之”的思想。其運行機制示意如圖2所示。mapper任務(wù)調(diào)用用戶自定義map函數(shù)后對中間結(jié)果進行局部排序，然后運行combiner對數(shù)據(jù)進行合并。當所有mapper任務(wù)都完成后，reducer任務(wù)會接收到mapper的通知，然后通過RPC遠程調(diào)用將mapper任務(wù)產(chǎn)生的M份屬于自己的數(shù)據(jù)文件遠程拉（pull）取到本地。當所有中間結(jié)果數(shù)據(jù)拉取成功后，采用歸并排序來對中間結(jié)果key進行排序，然后調(diào)用用戶自定義的reduce函數(shù)進行業(yè)務(wù)邏輯處理并輸出結(jié)果。雖然Hadoop集群很好地解決了海量數(shù)據(jù)的分布式存儲和并行計算問題，但當集群負載增大時，還是不可避免地會出現(xiàn)瓶頸，從而導(dǎo)致集群性能下降。

3 瓶頸檢測算法

圖1 HDFS的流程架構(gòu)

當集群運行出現(xiàn)瓶頸而沒有及時檢測出瓶頸資源時，不能采取相應(yīng)優(yōu)化措施，會嚴重影響整個集群的正常運行，這將大大降低集群性能，甚至使集群運行停滯。針對此，提出一種基于信息增益的瓶頸檢測算法，通過將該算法模型部署到集群中，實時檢測集群的性能。當在某節(jié)點中檢測到瓶頸出現(xiàn)時，通過計算各種資源的信息增益，從而確定最可能成為瓶頸的資源。

圖2 MapReduce運行機制示意

3.1 性能評價指標

衡量一個系統(tǒng)性能最常見的指標有響應(yīng)時間、吞吐量、資源使用率等，其中最直觀的可能是資源使用率，因為一般瓶頸資源都是使用率比較高的資源。但資源的高使用率并不一定意味著該資源就是瓶頸資源。高使用率只是瓶頸資源的必要條件，而非充要條件。例如在Linux系統(tǒng)中，其總是試圖讓CPU盡量繁忙，從而最大化作業(yè)任務(wù)的吞吐量。而在Hadoop性能指標方面，Apache Eagle[11]，一個開源的分布式實時監(jiān)控及預(yù)警框架主要使用下列指標來評價Hadoop作業(yè)性能是否異常。

· 作業(yè)進度緩慢。當作業(yè)在相當一段時間（15 min）內(nèi)沒有對HDFS或文件進行讀寫時，則認為作業(yè)運行出現(xiàn)異常。

·作業(yè)用時過長。通過作業(yè)運行的耗時來評價Hadoop性能。當作業(yè)持續(xù)耗時超過12 h，則認定作業(yè)性能差。

· reduce數(shù)量過大。若單個作業(yè)reduce數(shù)量超過了1500，

則性能低下。

·作業(yè)與歷史記錄比較，用時太久。通過采集100個歷史樣本，除掉10%最長用時，計算中位數(shù)P和離差倍增數(shù)的95分位數(shù)Dm。當作業(yè)運行時間大于max(P,Dm)時，則認為性能差。

·CPU平均每秒消耗字節(jié)數(shù) （bytes consumed per CPU second）太低。CPU平均每秒消耗字節(jié)數(shù)不低于200 KB。

· 洗牌大?。╯huffle size）。設(shè)定單個reduce對應(yīng)的洗牌大小不可以超過一定閾值（10 GB）。

而根據(jù)eBay 2015年5月的數(shù)據(jù)，各指標比例見表1。

可見，大部分可以從作業(yè)運行進度和時間指標去評價Hadoop性能?；诖?，本文使用響應(yīng)滿意度（RS）來評價集群性能。

其中，Tm為期待最小響應(yīng)時間，Ts為系統(tǒng)響應(yīng)時間。

3.2 資源信息增益

由于影響集群系統(tǒng)性能的資源有很多，且檢測初期并不知道可能成為瓶頸的資源有哪些，故將可能導(dǎo)致系統(tǒng)瓶頸的資源都考慮進去。如CPU、內(nèi)存、硬盤I/O和網(wǎng)絡(luò)帶寬等。在數(shù)據(jù)預(yù)處理中，要對數(shù)據(jù)集進行離散化，即對資源使用率和響應(yīng)滿意度進行等級分類。其中，資源使用率分 5 類：verylow（非常低）（0～20%）、low（低）（20%～40%）、middle（中等）（40%～60%）、high（高）（60%～80%）、veryhigh（非常高）（80%～100%），而響應(yīng)滿意度分 3 類：low（低）（0～60%）、middle（中）（60%～80%）和 high（高）（80%～100%）。例如有樣本：

表1 各類指標比例

s={CPU：45%，mem：25%，I/O：13%，network：66%，RS：85%}則其經(jīng)過離散化后，樣本變?yōu)椋?/p>

s′={CPU：middle，mem：low，I/O：verylow，network：high，RS：high}在數(shù)據(jù)挖掘中，使用ID3算法構(gòu)建決策樹時，通常會使用信息熵和信息增益來確定對目標分類影響最大的主要屬性[12]。本文也類似地通過資源的信息增益來確定與RS關(guān)系最密切的資源。首先需要計算數(shù)據(jù)集的信息熵。這里的信息熵可以理解為用于衡量系統(tǒng)復(fù)雜性的信息量。由上已經(jīng)知道目標屬性RS有3種可能等級，這里記為RSi(i=1,2,3)。假設(shè)在整個數(shù)據(jù)集S中，RSi出現(xiàn)的概率為Pi，則數(shù)據(jù)集S所含的信息熵為：

然后計算根據(jù)資源劃分后樣本子集的信息熵，即條件熵。假定資源A在數(shù)據(jù)集中存在k個不同的值，那么可以根據(jù)資源A將總樣本集劃分為k個樣本子集{s1,s2,…,sk}，則按資源A劃分后的樣本子集信息熵為：

其中，|Si|(i=1,2,…,k)為子集 Si的樣本數(shù)，|S|為總樣本數(shù)。而信息增益則是樣本劃分前后信息熵的差值，其代表著按資源劃分樣本后而導(dǎo)致期望熵的減少。按資源A劃分總數(shù)據(jù)集S的信息增益為：

信息增益越大，則說明該資源對作業(yè)RS的影響就越大。故當集群系統(tǒng)的RS大幅度下降且降到一定閾值 （如60%）時，通過采集各個資源使用率與響應(yīng)滿意度樣本集并離散化后，計算各個資源的信息增益。最后將具有最高信息增益的資源作為系統(tǒng)的瓶頸資源。然后針對瓶頸資源對集群參數(shù)進行調(diào)整優(yōu)化，以緩解瓶頸問題。例如若檢測到磁盤I/O是最可能造成集群出現(xiàn)瓶頸的資源，則可以通過增大io.sort.mb、dfs.block.siz等參數(shù)，減少作業(yè)運行時的磁盤I/O操作。若網(wǎng)絡(luò)帶寬成為瓶頸資源，則可設(shè)置map.output.compress參數(shù)對作業(yè)運行時中間結(jié)果數(shù)據(jù)進行壓縮，以減少傳輸?shù)膸挕?/p>

4 實驗設(shè)計與分析

實驗通過搭建3臺機器的Hadoop集群來進行實驗，其中，實驗機器 CPU為 Intel XEON 2.0，內(nèi)存為 2 GB，硬盤100 GB，操作系統(tǒng)為Ubuntu 14.04。實驗測試用例選用Wordcount和文本聚類，并通過不斷增加輸入文件大小和文本數(shù)量來測試集群的負載情況，然后記錄不同負載下作業(yè)的RS及集群中各種資源利用率情況，再通過瓶頸檢測算法計算具體的瓶頸資源。具體實驗結(jié)果如圖3所示。

圖3 資源使用率與響應(yīng)滿意度

可見，使用Wordcount測試用例時，當輸入文件增加到18 GB以上時，作業(yè)的響應(yīng)滿意度開始大幅度下降。當集群負載持續(xù)增大時，其響應(yīng)滿意度已經(jīng)開始逐漸趨于零?？梢婋S著負載加大到一定程度，集群開始出現(xiàn)瓶頸。瓶頸的出現(xiàn)會導(dǎo)致集群性能大幅度下降且最后基本處于停滯狀態(tài)。故針對圖3中Wordcount測試用例的資源使用率和對應(yīng)滿意響應(yīng)度數(shù)據(jù)，根據(jù)本文的瓶頸檢測算法來檢測瓶頸資源。由于內(nèi)存（mem）資源一直處于低使用率狀態(tài)，故其不可能成為瓶頸資源。所以只考慮CPU、網(wǎng)絡(luò)帶寬（network）和I/O這3種資源。首先對數(shù)據(jù)進行離散化，離散化后數(shù)據(jù)見表2。

表2 樣本離散化后數(shù)據(jù)

然后根據(jù)樣本計算各個資源的信息增益。首先計算整個數(shù)據(jù)集信息熵entropy(S)=1.399 6，然后計算基于網(wǎng)絡(luò)帶寬劃分的子樣本的信息熵entropynet(S)=0.633 9，故可以得到gain(network)=0.765 7。同理可以計算出gain(CPU)=0.126 8，gain(I/O)=0.996 9。從而可以判斷集群瓶頸資源為I/O。同理，根據(jù)圖3中文本聚類測試用例數(shù)據(jù)可以算出瓶頸資源為內(nèi)存(信息增益為0.409 9)?？梢婋m然在兩個測試用例中，CPU一直處于高使用率，但其并非是造成瓶頸的主要資源。反觀在Wordcount中，I/O資源使用率開始時隨著輸入文件大小的增加，其利用率保持一定的增長速率。但當輸入文件大小達到一定數(shù)量時，其使用率增長率開始趨于零，與此同時，作業(yè)的RS開始大幅度下降?？芍狪/O資源是導(dǎo)致RS下降的最主要原因，故網(wǎng)絡(luò)帶寬是造成采集模塊瓶頸的資源。而在文本聚類測試用例時，I/O使用率在樣本數(shù)量達到300萬時突然由穩(wěn)定開始上升，這主要是因為當樣本集過大時，內(nèi)存無法緩存所有數(shù)據(jù)，需要將數(shù)據(jù)分批次緩存到內(nèi)存中，增加了磁盤I/O操作，從而提高了I/O使用率。在Wordcount測試用例中，將io.sort.mb參數(shù)從默認的100 MB提升到200 MB，增加排序的內(nèi)存。同時增加dfs.blocksize參數(shù)，將文件塊的大小由64 MB增加到128 MB，從而減少磁盤I/O的操作。而文本聚類則將機器內(nèi)存由2 GB增大到4 GB。調(diào)整優(yōu)化后再進行上述測試用例實驗，得到RS對比如圖4所示?？梢娊?jīng)過瓶頸檢測調(diào)優(yōu)后的集群能有效地避免瓶頸出現(xiàn)。

圖4 針對瓶頸檢測出的資源進行調(diào)優(yōu)前后對比

5 結(jié)束語

本文針對Hadoop分布式處理集群，提出基于信息增益的瓶頸檢測方法。該方法使用RS來評價集群性能。對集群作業(yè)RS和各資源使用的信息進行監(jiān)控。然后計算各類資源增益，確定系統(tǒng)的瓶頸資源。在確定集群瓶頸資源后，便可針對該瓶頸資源進行相應(yīng)調(diào)整措施以優(yōu)化集群，從而提高集群的性能。本文通過實驗，充分證明了其可以有效地檢測Hadoop集群具體的瓶頸資源，可以為集群的優(yōu)化提供科學(xué)的指引和支持。

[1]中國互聯(lián)網(wǎng)絡(luò)信息中心.第37次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計 報 告 [EB/OL].[2016-02-10].http://www.cnnic.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm.China Internet Network Information Center.The 37th China internet network development state statistic report[EB/OL].[2016-02-10].http://www.cnnic.cn/hlwfzyj/hlwxzbg/hlwtjbg/201601/t20160122_53271.htm.

[2]張呈.Hadoop集群下海量小文件優(yōu)化處理[D].武漢：武漢理工大學(xué),2014.ZHANG C.Mass small files to optimize processing under the Hadoop cluster[D].Wuhan:Wuhan University of Technology,2014.

[3]唐霞.Hadoop調(diào)度器優(yōu)化及其在輿情分析中的應(yīng)用 [D].北京：北京化工大學(xué),2015 TANG X.Hadoop scheduler optimization and its application in public opinion analysis[D].Beijing:Beijing University of Chemical Industry,2015.

[4]曾婉琳,陳興蜀,羅永剛.Hadoop節(jié)點資源參數(shù)優(yōu)化策略[J].計算機工程,2016(1):1-6.ZENG W L,CHEN X S,LUO Y G.Hadoop node resource parameter optimization strategy[J].Computer Engineering,2016(1):1-6.

[5]董新華,李瑞軒,周灣灣,等.Hadoop系統(tǒng)性能優(yōu)化與功能增強綜述[J].計算機研究與發(fā)展,2013,50(z2):1-15 DONG X H,LI R X,ZHOU W W,et al.Hadoop system performance optimization and function enhanced review [J].Journal of Computer Research and Development,2013,50(z2):1-15.

[6]李懌銘.基于MapReduce性能優(yōu)化的研究 [D].上海:上海師范大學(xué),2015.LI Y M.Based on graphs performance optimization research[D].Shanghai:Shanghai Normal University,2015.

[7]DA V,PRADHAN P,DAN R.Provisioning servers in the application tier for E-commerce systems[J].ACM Transactions on Internet Technology,2007,7(1):57-66.

[8]朱顯杰.大規(guī)模復(fù)雜系統(tǒng)瓶頸檢測和性能預(yù)測方法的研究[D].杭州:浙江大學(xué),2010.ZHU X J.Large-scale complicated system bottleneck detection and performance prediction method research[D].Hangzhou:Zhejiang University,2010.

[9]GHEMAWAT S,GOBIOFF H,LEUNG S T.The Google file system[J].ACM Sigops Operating Systems Review,2003,37(5):29-43.

[10]DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM,2008,51(1):107-113.

[11]Apache Software Foundation.Eagle:secure Hadoop in real time[EB/OL].[2016-02-11].http://eagle.apache.org/.

[12]王小巍,蔣玉明.決策樹 ID3算法的分析與改進 [J].計算機工程與設(shè)計,2011,32(9):3069-3072.WANG X W,JIANG Y M.Analysis and improvement of the decision tree ID3 algorithm[J]. Computer Engineering and Design,2011,32(9):3069-3072.

Hadoop bottleneck detection algorithm based on information gain

TAN Zaole1,HAO Zhifeng1,CAI Ruichu1,XIAO Xiaojun2,LU Yu2
1.School of Computers,Guangdong University of Technology,Guangzhou 510006,China 2.Guangzhou Useease Information Technology Co.,Ltd.,Guangzhou 510630,China

Hadoop has become a major platform for big data storage and large data mining nowadays.Although Hadoop platform achieves high performance parallel computing through a distributed cluster of machines,the bottlenecks will inevitably appear on a machine when cluster load increases,because the cluster is composed of inexpensive host.Aiming at this problem,a bottleneck detection algorithms based on information gain was proposed.The algorithm detected cluster’s bottlenecks resource by computing the information gain of each resource.The experiments show that the bottleneck detection algorithm is feasible.

big data,Hadoop,information gain,bottleneck detection

TP391

A

10.11959/j.issn.1000-0801.2016203

2016-04-05；

2016-07-13

譚造樂(1990-)，男，廣東工業(yè)大學(xué)碩士生，主要研究方向為社交網(wǎng)絡(luò)數(shù)據(jù)挖掘、分布式架構(gòu)。

郝志峰(1968-)，男，廣東工業(yè)大學(xué)教授、博士生導(dǎo)師，主要從事機器學(xué)習(xí)、人工智能等研究工作。

蔡瑞初(1983-)，男，廣東工業(yè)大學(xué)教授、博士生導(dǎo)師，主要從事數(shù)據(jù)挖掘、機器學(xué)習(xí)、信息檢索等研究工作。

肖曉軍(1970-)，男，博士，現(xiàn)就職于廣州優(yōu)億信息科技有限公司，具有多年電信行業(yè)管理工作經(jīng)驗，主要研究方向為大數(shù)據(jù)、數(shù)據(jù)挖掘與電信行業(yè)應(yīng)用等。

盧宇(1983-)，男，廣州優(yōu)億信息科技有限公司高級軟件開發(fā)工程師，主要從事大數(shù)據(jù)、機器學(xué)習(xí)與電信行業(yè)應(yīng)用等相關(guān)研發(fā)工作。