基于多變量動態(tài)算法的Hadoop負載均衡優(yōu)化與實現(xiàn)*

武 娟 ，黃 海 ，錢 鋒 ， 李擁軍 ，壽質(zhì)彬

（1.中國電信股份有限公司廣東研究院 廣州510630；2.華南理工大學計算機科學與工程學院 廣州510006）

1 引言

云計算是一種基于互聯(lián)網(wǎng)的、大眾參與的計算模式，其計算資源是動態(tài)、可伸縮、虛擬化的，而且以服務(wù)的方式提供。Google是云計算研究的先驅(qū)者，陸續(xù)提出GFS模型、MapReduce模型、BigTable模型，同時在Apache網(wǎng)站上發(fā)布MapReduce和GFS對應(yīng)的Hadoop開源項目，它是一個運行在由大量廉價機器組成的集群上的分布云計算系統(tǒng)，具有廉價、高效、可靠以及可伸縮等特點[1]。Hadoop利用NameNode節(jié)點管理Hadoop集群，DataNode節(jié)點保存數(shù)據(jù)，并且引入了負載均衡機制。其負載均衡包含兩方面含義：其一是在保存文件和數(shù)據(jù)時，將文件塊保存任務(wù)平攤分給每個DataNode，讓每個DataNode均勻保存一定數(shù)量的文件塊；其二是當系統(tǒng)出現(xiàn)負載不均衡時（如系統(tǒng)加入新的節(jié)點或現(xiàn)有節(jié)點發(fā)生故障），HDFS可以進行系統(tǒng)均衡處理，以保證每個DataNode的文件塊數(shù)量均衡。

對于第一個均衡機制而言，根據(jù)Hadoop源碼分析可以得出Hadoop默認的數(shù)據(jù)塊放置策略[2]是在本地機架某臺DataNode放置一個數(shù)據(jù)塊副本，另外一個數(shù)據(jù)塊副本存放在不同(遠端)的機架上的某臺DataNode上，最后一個數(shù)據(jù)塊副本放置在同一個遠端機架的另外一臺DataNode上。這種策略減少了機架內(nèi)的寫負載，從而總體上提高了寫性能。由于整個機架失效的概率要比單個節(jié)點失效的概率小得多，因此這種方法不會影響數(shù)據(jù)的可靠性。但是，采用這種策略，文件塊并不是均勻地放置在HDFS里，2/3的數(shù)據(jù)塊被放置在了同一機架上，另外1/3被放置在了另一個機架上。當然，可以通過改變Hadoop數(shù)據(jù)塊放置策略來優(yōu)化其負載均衡機制，比如通過評價函數(shù)[3]和加權(quán)二叉樹[4]進行數(shù)據(jù)節(jié)點的選擇等，都可以有效地避免集群在存儲數(shù)據(jù)時造成的負載不均衡。

對于第二個均衡機制而言，則是在整個集群的負載不均衡的情況下進行的。比如當集群里增加了新的DataNode，那么相對于集群里其他 DataNode來說，該DataNode的存儲空間是很低的。如果新增加的DataNode為幾十個，則造成集群負載的嚴重不均衡。此時，需要人工對Hadoop集群進行負載均衡。在HDFS里，通過手動調(diào)用均衡器(balancer)設(shè)置閾值（threshold）達到負載均衡，threshold取值范圍為0%～100%（默認是10%）。threshold設(shè)置越小，那么HDFS各個DataNode的使用率越接近，整個集群也更加平衡，但會需要消耗更多的時間和資源來達到該平衡狀態(tài)。對于操作非常頻繁的HDFS集群，可能永遠不會達到threshold所指定的平衡狀態(tài)。threshold設(shè)置得越大，那么HDFS各個DataNode的使用率差距越大，容易達到指定狀態(tài)，但HDFS可能不是一種均衡的狀態(tài)。因此，threshold取值不應(yīng)該過小也不應(yīng)該過大，既要保證集群的均衡狀態(tài)，又要讓均衡器程序能夠達到給定的HDFS狀態(tài)。

2 基于多變量動態(tài)Hadoop的負載均衡優(yōu)化

針對Hadoop負載均衡的不足，設(shè)想在每次均衡器迭代前，獲取系統(tǒng)相關(guān)信息來評估threshold的值，在均衡器程序運行時動態(tài)改變threshold的值以達到實時控制均衡器的運行狀態(tài)，而不是使用一個固定不變的threshold值。

本文依據(jù)系統(tǒng)兩個信息參數(shù)來評估threshold的值：所有DataNode的使用率的標準差；大于系統(tǒng)平均連接數(shù)的DataNode的百分比。

參數(shù)1即代表了整個集群里磁盤空間使用率的分布狀況，參數(shù)1越大，說明集群負載越不均衡；相反，越小說明集群越均衡。同時，參數(shù)1代表了評估時候的均衡器運行時的集群空間因素。

參數(shù)2即代表了整個集群里的集群繁忙狀態(tài)，連接數(shù)是每個DataNode與外界建立的active連接數(shù)，一般用于傳輸或接收數(shù)據(jù)、發(fā)送控制信號等。參數(shù)2越大，說明集群越繁忙；相反，越小說明集群越空閑。同時，參數(shù)2代表了評估時候的均衡器運行時的時間因素。

同時，設(shè)計的動態(tài)閾值計算式必須符合以下特點：

·式子必須具有為時間和空間設(shè)置權(quán)重的效果；

·式子的結(jié)果即為threshold并且取值為0～100；

·隨著參數(shù)1增大，式子的結(jié)果遞減；

·隨著參數(shù)2增大，式子的結(jié)果遞增。

做出上述規(guī)定的原因如下。

·在運行均衡器時要權(quán)衡運行時間和最終的空間狀態(tài)兩因素。因此，必須對時間和空間做出權(quán)衡以保證運行時更傾向于運行時間還是運行后的空間狀態(tài)。

·基于Hadoop提供的均衡器程序上進行改動，在盡可能不改變其他模塊的基礎(chǔ)上，必須讓threshold取值為0～100來滿足均衡器的正常運行。

·隨著參數(shù)1的增大，即系統(tǒng)空間利用率變得不均衡了，均衡器程序應(yīng)該適當減小threshold以保證在運行完均衡器程序后系統(tǒng)負載是均衡的。

·隨著參數(shù)2的增大，即系統(tǒng)變繁忙了，均衡器程序應(yīng)該適當增大threshold，以保證均衡過程不會因為threshold過小且系統(tǒng)過于繁忙而一直運行下去。

基于上述要求，設(shè)計的計算threshold的式子如下：

其中，k是權(quán)重，取值0～1，a是參數(shù)1，b是參數(shù)2，max是集群里偏移均值的最大值。

由于均衡器程序里定義磁盤空間使用率范圍在0～100，故參數(shù)max取值是0～100。并且標準差是各個樣本到平均使用率的平均距離，因此，參數(shù)1的取值是0～100，且max>a。參數(shù)2是超過平均連接數(shù)的DataNode的百分比乘上100。因此，參數(shù) 2的取值也為 0～100。參數(shù) max、參數(shù) 1、參數(shù)2和k的取值保證了計算出來的threshold取值為0～100。避免計算出的threshold為0，一旦計算出的threshold為0，那么將自動被改成10。同時，在計算參數(shù)1時，程序首先計算一下集群整體的標準差，然后再檢測每個樣本，除去那些高于或低于2倍標準差的異常樣本，重新計算參數(shù)1，從而保證計算出來的threshold不會因為個別不正常的DataNode而受影響。即防止如果集群大部分節(jié)點都處于均衡狀態(tài)，而個別節(jié)點不均衡，那么未排除異常節(jié)點而算出的標準差將會比排除異常節(jié)點算出的標準差大，但實際上沒有必要把threshold設(shè)計過小。此外，為了避免不必要的計算，優(yōu)化步驟在計算threshold之前會判斷使用率在平均使用率±標準差范圍之外的DataNode的數(shù)量，如果超過了總數(shù)的X%，則說明該集群有必要進行負載均衡，或者集群里使用率最高的節(jié)點和最低的節(jié)點的使用率相差超過了Y%，也同樣說明該集群的極值相差太大，有必要進行均衡操作。否則就將threshold的值設(shè)為99。修改后的均衡器流程如圖1所示。

為了優(yōu)化Hadoop的均衡器，設(shè)計的優(yōu)化算法增加了幾個關(guān)鍵的變量和函數(shù)：函數(shù)CalculateAvgU()是計算集群平均使用率；函數(shù)CalculateVarianceU()是計算集群使用率的方差；函數(shù)CalculateAvgC()是計算集群平均連接數(shù)；函數(shù)CalculateAboveNum()是計算高于平均連接數(shù)的DataNode的數(shù)量；函數(shù)Calculateupdown()是計算使用率在平均使用率±標準差范圍之外的DataNode的數(shù)量；函數(shù)find_max()是計算集群里使用率最高的數(shù)據(jù)節(jié)點與平均使用率的差距；函數(shù)find_min()是計算集群里使用率最低的數(shù)據(jù)節(jié)點與平均使用率的差距；函數(shù)CalculateThreshold()是通過式子計算threshold。

閾值優(yōu)化算法如圖2所示。

3 實驗驗證與分析

3.1 實驗環(huán)境和參數(shù)選擇

實驗集群配置如下：1個NameNode，8個DataNode(包括NameNode所在的機器)。每個節(jié)點的服務(wù)器硬件配置如下：CPU為2.67 GHz；內(nèi)存為512 MB；硬盤空間為80 GB。

由于實驗所用的集群比較小，系統(tǒng)處在空閑的狀態(tài)占大部分時間，故實驗參數(shù)選擇k=0.1，即均衡時空間權(quán)重為0.9，時間權(quán)重為0.1，偏重空間均衡效果。同時，X取值為40，Y取值為10，即使用率在平均使用率±標準差范圍之外的DataNode的數(shù)量的百分比高于40%時，或者使用率最高和最低的節(jié)點的使用率差大于10%，則認為系統(tǒng)需要進行均衡操作。

3.2 實驗結(jié)果

編寫測試程序，隨機產(chǎn)生100個100 MB～1 GB大小的文件，然后隨機刪除其中的25個，程序運行時，先關(guān)閉集群里的3個DataNode，然后待測試程序運行完畢后，再將之開啟，使得集群空間負載不均衡，之后便開始運行系統(tǒng)的均衡器進行測試驗證。

測試程序結(jié)束后系統(tǒng)的空間狀態(tài)見表1。

表1 運行均衡器前集群空間狀態(tài)

可看出，其實運行完測試程序后集群的空間負載是分布不均衡的，需要進行負載均衡。假定運行系統(tǒng)默認的均衡器程序，當用戶不知道系統(tǒng)空間分布情況，那么按照默認的閾值threshold=10%來運行均衡器，此時系統(tǒng)空間平均使用率是45.0294005800278%。而45.0294005800278%+10%=55.0294005800278%；45.0294005800278%-10%=35.0294005800278%，按照上述的2個值判斷所有DataNode的使用率都為35%～55%。故均衡程序直接判斷為集群是均衡的并自動停止。此時，運行默認的均衡器后集群效果見表2。

表2 運行默認的均衡器后集群空間狀態(tài)

可看出，運行系統(tǒng)默認的均衡器且在用戶不知集群空間分布的情況下，按照閾值為10進行均衡的效果不太明顯。盡管存儲空間較少的數(shù)據(jù)節(jié)點的使用率有所提升，使用率高的節(jié)點的使用率有所下降。但是全局看，上升和下降的幅度不會很大，同時，系統(tǒng)使用率最低和最高的節(jié)點的使用率相差18.27%，仍然很大，均衡效果不理想。但依據(jù)優(yōu)化算法，運行優(yōu)化后的均衡效果如表3所示。

表3 運行優(yōu)化的均衡器后集群空間狀態(tài)

對比兩次實驗數(shù)據(jù)可以發(fā)現(xiàn)，優(yōu)化負載均衡算法能讓系統(tǒng)空間負載變得均衡。每個DataNode的使用率優(yōu)化明顯，如少于30%的DataNode經(jīng)過優(yōu)化后能上升到40%，而使用率在61%的能下降到48%，最終停止是因為系統(tǒng)空間狀態(tài)達到了均衡器認為此時的系統(tǒng)不需要做均衡操作。

圖3是開始運行均衡器時記錄的相關(guān)數(shù)據(jù)。

圖3 優(yōu)化負載均衡運算記錄

從圖3的實驗數(shù)據(jù)看出，第一次迭代前，優(yōu)化均衡器計算閾值threshold是6.00491904305684，使用率在平均使用率±標準差范圍之外的DataNode的數(shù)量的百分比是37.5%，未超過實驗設(shè)定的40%(X=40)，但是其使用率最大和最小值之差為39.86%，遠遠超出了實驗設(shè)定的10%(Y=10)，因此，需要做均衡操作。同時，由于實驗室集群的8臺機器都是通過一個路由器相連，在進行實驗時并未進行其他的操作，因此每個DataNode都和路由器建立了連接以便傳輸數(shù)據(jù)，換句話說，所有的DataNode的active connection都是1，因此，超過平均連接數(shù)的DataNode的百分比是0，即參數(shù)2是0。參數(shù)1的值有以上記錄可得是16.70273093007874%。通過計算可得max的值為23.37%。最后，均衡器結(jié)束是因為在最終狀態(tài)里，系統(tǒng)平均使用率是45.02315048077547%，而標準差為2.7236926121889855%。此時使用率在平均使用率±標準差范圍之外的DataNode的數(shù)量的百分比是37.5%，并且使用率最大和最小的DataNode之差小于10%。換句話說，此時滿足不需要做均衡操作的條件。

4 結(jié)束語

本文研究了Hadoop的負載均衡機制，對其工作的原理進行了詳細的剖析與解讀，隨后針對閾值threshold設(shè)計不足展開分析和研究，提出了在均衡過程中通過獲取集群的相關(guān)信息，動態(tài)優(yōu)化閾值threshold的方案。設(shè)計實驗進行演算，結(jié)果表明新方法對于Hadoop負載均衡優(yōu)化效果明顯。后續(xù)的研究工作計劃和方向是：對于不同規(guī)模的集群和用戶的需求，需考慮多方面因素對相關(guān)參數(shù)重新進行設(shè)定，深入考慮系統(tǒng)的其他信息和系統(tǒng)均衡情況的聯(lián)系進行更深入的分析。

1 懷特.Hadoop權(quán)威指南.北京：清華大學出版社，2011

2 Borthakur D.The Hadoop distributed file system:architecture and design.http://hadoop.apache.org/hdfs/docs/current/hdfs-design.html，2011

3 林偉偉.一種改進的Hadoop數(shù)據(jù)放置策略.華南理工大學學報(自然科學版),2012,40(1):152～158

4 Myint J,Naing T T.A data placement algorithm with binary weighted tree on PC cluster-based cloud storage system 2011 InternationalConferenceon Cloud and Service Computing(CSC),HongKong,China,2011:315～320