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

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

1 引言

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

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

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

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

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

本文依據(jù)系統(tǒng)兩個(gè)信息參數(shù)來(lái)評(píng)估threshold的值：所有DataNode的使用率的標(biāo)準(zhǔn)差；大于系統(tǒng)平均連接數(shù)的DataNode的百分比。

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

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

同時(shí)，設(shè)計(jì)的動(dòng)態(tài)閾值計(jì)算式必須符合以下特點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)驗(yàn)證與分析

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

3 林偉偉.一種改進(jìn)的Hadoop數(shù)據(jù)放置策略.華南理工大學(xué)學(xué)報(bào)(自然科學(xué)版),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