李安穎，陳 群，宋 荷

(西北工業(yè)大學(xué)計算機學(xué)院，陜西 西安 710072)

0 引言

Hadoop是由Apache開源組織開發(fā)的、具有高可靠性和高可擴展性的存儲與分布式并行計算平臺[1]。MapReduce是Hadoop的核心模型之一，廣泛應(yīng)用于大數(shù)據(jù)處理[2]。

MapReduce模型將計算分為Map和Reduce兩個處理階段。在Map階段，由各Mapper對輸入的數(shù)據(jù)元組進行分區(qū)處理，并將具有相同分區(qū)值的元組傳送給同一個Reducer進行相關(guān)的計算。Hadoop系統(tǒng)默認采用的是Hash分區(qū)法，同時支持Range和用戶自定義分區(qū)法。由于Map階段產(chǎn)生的數(shù)據(jù)塊大小不一，因此在Reduce階段容易造成數(shù)據(jù)的Reduce節(jié)點分布不均衡，從而產(chǎn)生Reduce階段的數(shù)據(jù)傾斜[3-5]。一旦發(fā)生數(shù)據(jù)傾斜，會使得各個節(jié)點的Reduce節(jié)點的負載不均衡，造成某些節(jié)點的Reduce任務(wù)相對于其他節(jié)點Reduce任務(wù)執(zhí)行時間延長，進而延長了整個Reduce階段的運行時間，從而影響整個任務(wù)的執(zhí)行效率。

本文在充分研究了現(xiàn)有MapReduce數(shù)據(jù)平衡算法的基礎(chǔ)上，提出一種基于離散粒子群算法的Reduce階段數(shù)據(jù)負載平衡解決方法，以提高系統(tǒng)的穩(wěn)定性。該方法將數(shù)據(jù)分區(qū)策略與智能分析算法相結(jié)合，構(gòu)建將數(shù)據(jù)分區(qū)均衡的目標函數(shù)，并利用粒子群算法尋找數(shù)據(jù)分區(qū)的較優(yōu)解，來解決數(shù)據(jù)分區(qū)的不平衡問題。

1 問題描述及模型構(gòu)建

當(dāng)前使用智能算法解決MapReduce調(diào)度的文獻較多，但都沒有深入地解決系統(tǒng)計算效率問題[6-8]。同時，對于解決Reduce階段數(shù)據(jù)傾斜問題的研究工作也較少。避免數(shù)據(jù)傾斜的常用方法有兩種：一是在Mapper運行程序中加入采樣策略；二是先對輸入數(shù)據(jù)進行預(yù)處理，再對數(shù)據(jù)進行制定分區(qū)策略[5]。前一種方法，當(dāng)Mapper運行到特定時刻，根據(jù)采樣所得到的分布信息，對發(fā)生數(shù)據(jù)量傾斜的分區(qū)進行一次拆分[4]。但該方法并沒有給出一個通用的調(diào)整時機。后一種方法則增加了文件的處理時間。

在數(shù)據(jù)Map階段完成后，待處理的數(shù)據(jù)塊的數(shù)量為m，經(jīng)Map處理得到各個數(shù)據(jù)塊的數(shù)據(jù)量，分別為D1,D2,…,Dm。其中，Di表示第i塊數(shù)據(jù)的數(shù)據(jù)量。假設(shè)當(dāng)前系統(tǒng)的Reduce節(jié)點個數(shù)為M，且每個節(jié)點的處理能力相同。在采用Reduce進行處理前，需要計算如何在M個節(jié)點分配m個數(shù)據(jù)塊，使得各個Reduce節(jié)點的負載盡量均衡,即實現(xiàn)各節(jié)點分配的數(shù)據(jù)量的差最小，并能達到數(shù)據(jù)平衡的目標。

假設(shè)m個數(shù)據(jù)塊的Reduce分配向量為v={v1，…，vi,…,vm}，1≤i≤m,i≤vi≤M。vi表示第i個數(shù)據(jù)塊被分配到第vi個Reduce節(jié)點上。根據(jù)分配向量分配的各Reduce節(jié)點的數(shù)據(jù)量為R1,…,Rj，…,RM，1≤j≤M。Rj表示第j個Reduce節(jié)點分配的所有數(shù)據(jù)塊的數(shù)據(jù)量之和。構(gòu)建如下目標函數(shù)：

(1)

式中：R為數(shù)據(jù)量均值。

(2)

該方法求解的最終目標是尋找最佳的分配向量：v={v1,…,vi,…,vm}，使得式(1)的值盡可能小。

2 粒子群算法求解目標函數(shù)

2.1 離散粒子群算法

粒子群算法是一種群體智能進化的算法，是多個粒子參照一定的規(guī)則指導(dǎo)進行的隨機搜索[9-10]。基于生物學(xué)理論，單獨的粒子代表一個物種，粒子群構(gòu)成了一個種群。定義當(dāng)前全局最優(yōu)粒子代表當(dāng)前種群中優(yōu)勢最強、生命力最強的物種，而個體歷史最優(yōu)代表該物種在其進化過程中所保留的最優(yōu)的、最適應(yīng)環(huán)境的生命形態(tài)。當(dāng)前生命力最強的物種未必永遠是生命力最強的，因此需要保存、學(xué)習(xí)其他各物種中最優(yōu)的、最適應(yīng)環(huán)境的生命形態(tài)，以保留該種群潛在的更優(yōu)的生命因素?；谶\動學(xué)理論，單獨的粒子是空間中運動的單個質(zhì)點粒子。粒子的運動既具有隨機性，又具有導(dǎo)向性。離散粒子群算法將離散值作為待優(yōu)化的變量，進而尋找最優(yōu)解。

2.2 構(gòu)建粒子

首先，對通過Map處理后輸出的數(shù)據(jù)進行聚合，即獲取各個Map的輸出數(shù)據(jù)，并將其聚集在一個集合中。該集合的維數(shù)為n，整個集合數(shù)據(jù)的總和與各個Map輸出的數(shù)據(jù)的和相同。然后，使用分配向量構(gòu)建粒子，即構(gòu)建粒子為n維向量x={x1,…,xi,…,xn}。其中，1≤xi≤M構(gòu)成了一個分區(qū)方式，即一個解。在離散粒子群算法中，每個解構(gòu)成了一個粒子。

考慮到粒子在運行優(yōu)化的過程中，可能出現(xiàn)不滿足1≤xi≤M條件的情況。因此，在粒子獲取新的位置后可按照如式(2)進行調(diào)整，使其滿足1≤xi≤M。

(3)

2.3 粒子群算法設(shè)計

2.3.1 粒子群算法步驟

設(shè)搜索空間的維度為n維，總粒子數(shù)為N。在每一次迭代中，所有的粒子在n維空間中進行“移動”以搜索全局得到最優(yōu)解。粒子的速度和位置通過以下更新公式計算得到:

(4)

(5)

式中：i為群中的第i個粒子；t為迭代次數(shù)；ω為慣性因子；C1和C2為學(xué)習(xí)因子，均為正常數(shù)；Pi為第i個粒子迄今為止搜索到的最優(yōu)位置，即局部最優(yōu)解；Pg為整個粒子群迄今為止搜索到的最優(yōu)位置，即全局最優(yōu)解；Vi為第i個粒子的速度向量；Xi為粒子i的位置向量。

則在n維問題的空間中：

Vi={Vi1,Vi2,…,Vin}

(6)

Xi={Xi1,Xi2，…,Vin}

(7)

使用函數(shù)Rand()產(chǎn)生一個(0，1)之間的隨機數(shù)。第d維(d1≤d≤N)的位置變化范圍為[-XMAX,XMAX] ；速度變化范圍為[-VMAX,VMAX] 。

粒子群的初始位置和速度通過隨機函數(shù)進行隨機產(chǎn)生，然后使用式(4)～式(5)進行迭代計算，直至找到較優(yōu)解。

2.3.2 慣性因子及粒子速度

ω值越大，粒子的全局搜索能力越強，適用于對求解空間進行大范圍探察；ω值越小，粒子的局部搜索能力越強。選擇一個合適大小的ω，可以平衡全局和局部搜索能力，并可通過較少的迭代次數(shù)得到最優(yōu)解。

為了平衡局部搜索能力以及全局搜索能力，設(shè)置慣性因子ω。ω的具體參數(shù)值根據(jù)試驗數(shù)據(jù)的大小設(shè)置，一般建議在[0.6,1.0] 之間為宜。

粒子的最大速度VMAX與ω共同配合，對粒子群算法的性能具有影響。當(dāng)最大速度VMAX較小時，ω近似為1，粒子群算法性能較好；當(dāng)最大速度VMAX較大時，ω為0.8，粒子群算法性能較好。

2.3.3 學(xué)習(xí)因子

C1和C2用來控制粒子自身的記憶和同伴粒子記憶之間的相對影響。選擇合適的學(xué)習(xí)因子值，可以提高算法速度，避免陷入局部極小值。普遍認為C1=C2=2是較好的選擇，但試驗證明了C1=C2=0.5也能得到較好的結(jié)果，能夠避免陷入局部極小值。

2.3.4 算法過程

(1)初始化。

設(shè)置算法運行過程中的慣性因子ω，最大迭代次數(shù)nb_iterations，粒子群規(guī)模numberOfParticle。隨機初始化第i個粒子的向量Xi={Xi1,Xi2,…,Xin}和每個粒子的初始速度VI={Vi1,Vi2,…,Vin}，并設(shè)置當(dāng)前迭代次數(shù)no_iteration為0。

(2)迭代。

如果no_iteration≥nb_iterations，則跳轉(zhuǎn)至步驟(5)。否則，對于當(dāng)前粒子群中的每個粒子執(zhí)行如下步驟。

①使用3.3.1中描述的方法用粒子的學(xué)習(xí)后的位置next_location值更新粒子的當(dāng)前位置current_location；按照式(1)～式(2)計算目標函數(shù)值。

②如果當(dāng)前計算出的目標函數(shù)值小于該粒子的局部最優(yōu)解，則用當(dāng)前粒子的位置更新以前的局部最優(yōu)解。

(3)更新全局最優(yōu)解。

求得numberOfParticle個粒子中式(1)的目標函數(shù)值最小的粒子，根據(jù)該粒子的信息更新全局最優(yōu)解。

(4)本次迭代完畢，即：

no_iteration= no_iteration +1

(5)得出結(jié)果，即求得全局最優(yōu)解并輸出。

3 試驗結(jié)果與分析

試驗采用4臺普通的服務(wù)器搭建的Hadoop集群系統(tǒng)環(huán)境，每臺計算機內(nèi)存2 GB，磁盤空間250 GB。Hadoop的版本是hadoop.0.20.2。操作系統(tǒng)的版本是Red Hat Linux 9.0。試驗所采用的測試方法為利用Hadoop進行WordCount 計算,并分別與默認Hadoop和文獻[4] 中的方法進行比較。

數(shù)據(jù)分區(qū)是否均衡可以通過運行時間進行比較和評價。本節(jié)使用Reduce函數(shù)實現(xiàn)PageRank算法，比較第1輪的運行時間。

試驗結(jié)果對比如圖1所示。

圖1 試驗結(jié)果對比圖

由圖1可見，當(dāng)設(shè)置兩種不同數(shù)量的Reduce時，在三種分區(qū)方式中，離散粒子群分區(qū)方式的運行時間均為最短，可以證明其解決數(shù)據(jù)分區(qū)的不平衡問題都比較有效。隨著Reduce數(shù)量的上升，離散粒子群分區(qū)方式的優(yōu)勢更為明顯。

本文還試驗了離散粒子群算法中迭代次數(shù)參數(shù)的選擇對數(shù)據(jù)運行時間的影響，設(shè)置Reduce數(shù)目為20個，如圖2所示。

圖2 迭代次數(shù)對運行時間的影響

從圖2可以看出，當(dāng)?shù)螖?shù)超過第一閾值(如迭代300次)時，在此閾值基礎(chǔ)上，隨著迭代次數(shù)的增加，運行時間的縮短趨勢較快，說明離散粒子群學(xué)習(xí)的結(jié)果較為準確，可獲得相對較優(yōu)的解。在迭代次數(shù)接近第二閾值(如迭代500次)時，運行時間并未顯著縮短，說明離散粒子群算法尋找的較優(yōu)解已接近穩(wěn)定。

4 結(jié)束語

本文研究了采用MapReduce模型解決數(shù)據(jù)平衡問題,并基于智能計算的數(shù)據(jù)平衡方法進行最優(yōu)解的計算求解。試驗結(jié)果表明,與傳統(tǒng)的Hash劃分和預(yù)處理輸入數(shù)據(jù)再制定分區(qū)策略相比,本文提出的基于離散粒子群算法的數(shù)據(jù)平衡方法更為高效。

后續(xù)研究將采用其他的智能算法(包括人工蜂群算法、鳥群算法)解決數(shù)據(jù)不平衡的特征，并將深入探索結(jié)合多種智能算法，以解決數(shù)據(jù)不平衡問題。