基于多變量動態算法的Hadoop負載均衡優化與實現*

武 娟 ，黃 海 ，錢 鋒 ， 李擁軍 ，壽質彬

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

1 引言

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

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

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

2 基于多變量動態Hadoop的負載均衡優化

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

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

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

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

同時，設計的動態閾值計算式必須符合以下特點：

·式子必須具有為時間和空間設置權重的效果；

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

·隨著參數1增大，式子的結果遞減；

·隨著參數2增大，式子的結果遞增。

做出上述規定的原因如下。

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

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

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

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

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

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

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

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

閾值優化算法如圖2所示。

3 實驗驗證與分析

3.1 實驗環境和參數選擇

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

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

3.2 實驗結果

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

測試程序結束后系統的空間狀態見表1。

表1 運行均衡器前集群空間狀態

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

表2 運行默認的均衡器后集群空間狀態

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

表3 運行優化的均衡器后集群空間狀態

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

圖3是開始運行均衡器時記錄的相關數據。

圖3 優化負載均衡運算記錄

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

4 結束語

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

1 懷特.Hadoop權威指南.北京：清華大學出版社，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數據放置策略.華南理工大學學報(自然科學版),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