離散粒子群優(yōu)化算法實(shí)現(xiàn)MapReduce負(fù)載平衡

李安穎，陳 群，宋 荷

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

0 引言

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

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

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

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

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

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

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

(1)

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

(2)

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

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

2.1 離散粒子群算法

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

2.2 構(gòu)建粒子

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

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

(3)

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

2.3.1 粒子群算法步驟

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

(4)

(5)

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

則在n維問(wèn)題的空間中：

Vi={Vi1,Vi2,…,Vin}

(6)

Xi={Xi1,Xi2，…,Vin}

(7)

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

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

2.3.2 慣性因子及粒子速度

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

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

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

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

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

2.3.4 算法過(guò)程

(1)初始化。

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

(2)迭代。

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

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

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

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

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

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

no_iteration= no_iteration +1

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

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

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

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

試驗(yàn)結(jié)果對(duì)比如圖1所示。

圖1 試驗(yàn)結(jié)果對(duì)比圖

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

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

圖2 迭代次數(shù)對(duì)運(yùn)行時(shí)間的影響

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

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

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

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