余先昊,周 鳳
(1.貴州商學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,貴州 貴陽(yáng) 550001; 2.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,貴州 貴陽(yáng) 550025)
商業(yè)應(yīng)用和科學(xué)研究的計(jì)算服務(wù)經(jīng)常涉及到大規(guī)數(shù)據(jù)集的密集型計(jì)算[1],系統(tǒng)需要在用戶可接受的時(shí)間范圍內(nèi)對(duì)海量數(shù)據(jù)進(jìn)行存儲(chǔ)、檢索、定位和可視化等操作[2]。全比較[3](ATAC)問(wèn)題廣泛存在于大數(shù)據(jù)處理任務(wù)中,例如海量數(shù)據(jù)挖掘、海量信息管理和生物統(tǒng)計(jì)學(xué)等。
在ATAC中,數(shù)據(jù)文件的每個(gè)數(shù)據(jù)項(xiàng)需要與數(shù)據(jù)集中其它數(shù)據(jù)文件的所有數(shù)據(jù)項(xiàng)進(jìn)行比較。因此,其計(jì)算模式與Map Reduce的計(jì)算模式[4]不同。如果數(shù)據(jù)集中的文件數(shù)量(或數(shù)據(jù)項(xiàng))很多,那么對(duì)于ATAC問(wèn)題,需要進(jìn)行的計(jì)算規(guī)模將非常大。
為處理ATAC問(wèn)題,研究人員使用了多種分布式系統(tǒng)和數(shù)據(jù)庫(kù)。如Li等[5]提出了一種大型數(shù)據(jù)集上的全比較數(shù)據(jù)分發(fā)模型,采用異構(gòu)多核集群運(yùn)行算法,所有數(shù)據(jù)分發(fā)到每個(gè)計(jì)算節(jié)點(diǎn)上。Gao等[6]提出基于圖覆蓋的數(shù)據(jù)分配算法(DAABGC),通過(guò)理論分析將大數(shù)據(jù)全比較問(wèn)題轉(zhuǎn)換為圖覆蓋問(wèn)題。Hong等[7]提出了BLAST算法在GPU-CPU混合式異構(gòu)系統(tǒng)中的設(shè)計(jì)和優(yōu)化,但對(duì)硬件的依賴比較強(qiáng)。與之類似,Wang等[8]也對(duì)硬件的要求較高。
現(xiàn)有解決方案主要關(guān)注不同算法的并行執(zhí)行,以及負(fù)載平衡,但很少關(guān)注數(shù)據(jù)分發(fā)問(wèn)題。在處理大型數(shù)據(jù)集時(shí)擴(kuò)展性較差,效率低下。為此,本文提出ATAC問(wèn)題的分布式計(jì)算方法,其中,所有的比較任務(wù)都有著相同或相近的執(zhí)行時(shí)間,自動(dòng)決定數(shù)據(jù)副本的數(shù)量,并針對(duì)比較任務(wù)實(shí)現(xiàn)較好的數(shù)據(jù)本地性和負(fù)載平衡性。
本節(jié)將介紹用于數(shù)據(jù)分布的計(jì)算框架。首先從總體上考量和假設(shè)。然后,提出降低存儲(chǔ)占用和提高計(jì)算性能的公式。最后,通過(guò)一個(gè)總體優(yōu)化問(wèn)題,以詳細(xì)說(shuō)明數(shù)據(jù)分布的要求。
求解ATAC問(wèn)題的一般工作流程如圖1所示,由圖1可以觀察到,為高效求解ATAC問(wèn)題,需要對(duì)數(shù)據(jù)分發(fā)和任務(wù)計(jì)算階段都進(jìn)行改善。分布式環(huán)境中大數(shù)據(jù)處理的整體計(jì)算性能受到兩個(gè)問(wèn)題的影響:①數(shù)據(jù)本地性;②計(jì)算任務(wù)的分配。其中,數(shù)據(jù)本地性要求當(dāng)計(jì)算操作被分配到工作節(jié)點(diǎn)時(shí),該計(jì)算操作的效率一般會(huì)更高。由于網(wǎng)絡(luò)通信和數(shù)據(jù)傳輸?shù)呢?fù)擔(dān)較為繁重,需要存取遠(yuǎn)程數(shù)據(jù)集的計(jì)算任務(wù)的效率可能會(huì)非常低。因此,當(dāng)把適當(dāng)?shù)娜蝿?wù)分配給具有對(duì)應(yīng)處理能力的工作節(jié)點(diǎn)時(shí),分布式系統(tǒng)的性能會(huì)得到明顯提升,分布式系的工作效能會(huì)更高[9]。

圖1 求解ATAC問(wèn)題的一般工作流程
為了利用圖1的流程,需要開(kāi)發(fā)出數(shù)據(jù)分發(fā)策略。首先,本文通過(guò)數(shù)據(jù)分發(fā)策略生成數(shù)據(jù)分布解。然后,基于給出的分布解對(duì)所有的數(shù)據(jù)文件進(jìn)行部署。在數(shù)據(jù)分布中,考慮以下兩個(gè)方面:
(1)分布式系統(tǒng)的存儲(chǔ)情況。由于ATAC問(wèn)題涉及的數(shù)據(jù)量巨大,在分配節(jié)點(diǎn)任務(wù)時(shí),需要考慮到每個(gè)節(jié)點(diǎn)在其容量?jī)?nèi)的存儲(chǔ)空間使用情況,還需要將數(shù)據(jù)分發(fā)的總時(shí)間保持在可接受的水平。
(2)比較計(jì)算的性能。對(duì)于分布式計(jì)算,在分配比較任務(wù)時(shí),使系統(tǒng)中所有可用的計(jì)算能力都得到充分的利用非常重要。此外,數(shù)據(jù)的本地性越好,計(jì)算的效率越高,兩者關(guān)系密切。因此,對(duì)于全比較問(wèn)題,數(shù)據(jù)分發(fā)需滿足:數(shù)據(jù)項(xiàng)的分配必須提高比較計(jì)算的性能。
在現(xiàn)實(shí)應(yīng)用中,很多數(shù)據(jù)都具有相同或相似的大小,且所有的比較任務(wù)都有著相等或相似的執(zhí)行時(shí)間。典型的例子有:協(xié)方差矩陣計(jì)算、聚類和分類中的相似性計(jì)算等。下文將分析分布式系統(tǒng)的存儲(chǔ)使用要求,以及比較計(jì)算的性能。
數(shù)據(jù)分發(fā)[10]上所耗費(fèi)的時(shí)間受很多因素的影響,如網(wǎng)絡(luò)帶寬、數(shù)據(jù)項(xiàng)的大小、網(wǎng)絡(luò)結(jié)構(gòu)等。由于數(shù)據(jù)分發(fā)的時(shí)間與待分發(fā)的數(shù)據(jù)項(xiàng)數(shù)量成正比。有
tdis∝D
(1)
式中:D表示待分發(fā)的數(shù)據(jù)文件。tdis表示數(shù)據(jù)分發(fā)的時(shí)間。相關(guān)研究表明,每個(gè)工作節(jié)點(diǎn)的存儲(chǔ)使用量必須在其容量限制范圍之內(nèi),如果對(duì)所有的數(shù)據(jù)集進(jìn)行均勻的分發(fā),則可以滿足這一要求[9]。
假設(shè)系統(tǒng)分配到節(jié)點(diǎn)i的文件數(shù)量為 |Di|, 分發(fā)的策略是將 |D1|,…,|DN| 最大值,之后再最小化,即
minimize max{|D1|,|D2|,…,|DN|}
(2)
對(duì)工作節(jié)點(diǎn)中數(shù)據(jù)文件的最大數(shù)量進(jìn)行最小化,有以下好處:①最小化能夠使得所有工作節(jié)點(diǎn)中的數(shù)據(jù)文件的數(shù)量大致相同;②最小化還能夠使得所有的工作節(jié)點(diǎn)可執(zhí)行的比較任務(wù)的數(shù)量大致相同。
在ATAC的分布式計(jì)算中,最后一個(gè)完成工作的節(jié)點(diǎn)從某種程度上決定了總計(jì)算時(shí)間[11]。
設(shè)K表示分配到最后一個(gè)完成任務(wù)的工作節(jié)點(diǎn)的比較任務(wù)的數(shù)量,tcomp(k)代表比較k個(gè)任務(wù)所用的時(shí)間,tsave(k)代表對(duì)涉及任務(wù)k數(shù)據(jù)存取所用的時(shí)間。則執(zhí)行比較任務(wù)的總實(shí)際運(yùn)算時(shí)間,tcomp具體定義如下
(3)
式中:本文提出的數(shù)據(jù)分發(fā)策略通過(guò)滿足兩個(gè)約束項(xiàng),降低了總執(zhí)行時(shí)間Ttol:①工作節(jié)點(diǎn)的負(fù)載平衡;②良好的數(shù)據(jù)本地性。
為了進(jìn)行負(fù)載平衡的約束,需要在任務(wù)完成后,對(duì)最大比較數(shù)量進(jìn)行最小化處理。設(shè)Ti表示工作節(jié)點(diǎn)i所執(zhí)行的逐對(duì)比較任務(wù)的數(shù)量。對(duì)于一個(gè)有著N個(gè)工作節(jié)點(diǎn)和M個(gè)數(shù)據(jù)文件的分布式系統(tǒng),需要分配到工作節(jié)點(diǎn)的比較任務(wù)的總數(shù)量為M(M-1)/2個(gè)。通過(guò)以下公式,對(duì)K的數(shù)值進(jìn)行最小化

(4)

M(M-1)/2≥N,M>2
(5)
良好的數(shù)據(jù)本地性可以利用數(shù)學(xué)表達(dá)式的形式來(lái)獲得。在某些情況下,本地節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)可以為某些任務(wù)提供便利,無(wú)需遠(yuǎn)程調(diào)用數(shù)據(jù),即達(dá)到了“自給自足”。意味著tsave(k)為最小值,該數(shù)值可能的最低數(shù)值為0。數(shù)據(jù)本地性定義如下

(6)
式中: (x,y) 表示對(duì)數(shù)據(jù)x和y進(jìn)行比較,T表示比較任務(wù)的集合,Ti表示節(jié)點(diǎn)i執(zhí)行的任務(wù),Di為節(jié)點(diǎn)i中的當(dāng)?shù)財(cái)?shù)據(jù)。當(dāng)N=2時(shí),上述討論的數(shù)據(jù)分布變得不再重要。在這種情況下,需要至少有一個(gè)節(jié)點(diǎn)中存儲(chǔ)著式(4)和式(6)所要求的所有數(shù)據(jù)文件。因此,一個(gè)定義完善的數(shù)據(jù)分布問(wèn)題要求:N>2。
當(dāng)同時(shí)考慮存儲(chǔ)使用和計(jì)算性能時(shí),數(shù)據(jù)分發(fā)策略應(yīng)該滿足式(2)中的目標(biāo),同時(shí)還需要滿足式(4)和式(6)中的約束。由此降低對(duì)所有數(shù)據(jù)集進(jìn)行分發(fā)所耗費(fèi)的時(shí)間(tdis)。滿足式(4)和式(6)中的約束可以理解為總比較時(shí)間tcomp的數(shù)值被最小化。從而,數(shù)據(jù)分發(fā)和任務(wù)執(zhí)行的總體運(yùn)行時(shí)間將得到顯著下降
ttol=tdis+tcomp
(7)
因此,數(shù)據(jù)分發(fā)問(wèn)題可以被表示為一個(gè)約束性優(yōu)化問(wèn)題

(8)
一般可以通過(guò)滿足式(4)和式(6)中的約束,來(lái)推導(dǎo)出式(8)分發(fā)問(wèn)題的可行解。本文以滿足式(4)和式(6)中的約束為前提,將所有的比較任務(wù)分配到工作節(jié)點(diǎn)。本文分發(fā)數(shù)據(jù)的啟發(fā)式規(guī)則如下:
規(guī)則1:對(duì)于之前從未被分配過(guò)的比較任務(wù),可以通過(guò)遵循式(4)的約束條件設(shè)計(jì)出一個(gè)數(shù)據(jù)分發(fā)策略,將盡可能多的此類任務(wù)分配到節(jié)點(diǎn)i。
規(guī)則2:對(duì)于已經(jīng)被分配過(guò)的比較任務(wù),可以遵循式(4)的約束條件設(shè)計(jì)出數(shù)據(jù)分發(fā)策略,對(duì)此類任務(wù)中的每一個(gè)任務(wù)進(jìn)行再次分配。舉例來(lái)說(shuō),如果一個(gè)比較任務(wù)task已經(jīng)被分配到工作節(jié)點(diǎn)q,則該策略將對(duì)被分配到節(jié)點(diǎn)i和節(jié)點(diǎn)q的比較任務(wù)之間的數(shù)量進(jìn)行比較。如果工作節(jié)點(diǎn)i上的比較任務(wù)數(shù)量較少,則將任務(wù)task重新分配到節(jié)點(diǎn)i。根據(jù)這些啟發(fā)式規(guī)則,可以設(shè)計(jì)出用于實(shí)際的數(shù)據(jù)分發(fā)的算法及具體步驟。
本文提出的任務(wù)驅(qū)動(dòng)的啟發(fā)式數(shù)據(jù)分發(fā)策略如算法1所示。
算法1: 數(shù)據(jù)分發(fā)算法
起始: 集合U為所有未分配的逐對(duì)比較任務(wù);
變量: 變量數(shù)據(jù)集D和節(jié)點(diǎn)集合C, 兩者初始均為空集;
(1)while未分配的任務(wù)的集合U不是空集do
(2)D←φ;C←φ; // 空集D和C
(3) 找到未分配任務(wù)的所有數(shù)據(jù)文件;
(4) 將這些數(shù)據(jù)文件放入到集合D中;
(5) 對(duì)于集合D中的每個(gè)文件,對(duì)需要該文件的未分配任務(wù)進(jìn)行計(jì)數(shù);
(6) 將集合D以該計(jì)數(shù)的數(shù)字大小進(jìn)行降序排列;
(7)while節(jié)點(diǎn)集合C是空集do
(8) 選擇集合D中第一個(gè)數(shù)據(jù)文件。設(shè)d表示該文件;
(9)for系統(tǒng)中所有的工作節(jié)點(diǎn)do
(10) 找到不包含文件d的節(jié)點(diǎn)的集合;
(11) 將這些節(jié)點(diǎn)放入集合C;
(12)for集合C中的所有節(jié)點(diǎn)do
(13) 找到并標(biāo)記被分配任務(wù)的數(shù)量最少的節(jié)點(diǎn);
(14) 將所有被標(biāo)記的節(jié)點(diǎn)從C中移除;
(15)for集合C中的所有節(jié)點(diǎn)do
(16) 找到并標(biāo)記被分發(fā)文件的數(shù)量最少的節(jié)點(diǎn);
(17) 將所有被標(biāo)記的節(jié)點(diǎn)從C中移除;
(18)if集合C變?yōu)榭占痙o
(19) 將文件d從集合D中移除;
(20)for集合C中的每個(gè)工作節(jié)點(diǎn)ido
(21)if節(jié)點(diǎn)i為空then
(22) 將數(shù)據(jù)文件d分發(fā)到這一節(jié)點(diǎn)i;
(23) break;// 跳出這個(gè)for循環(huán)
(24)else
(25) 計(jì)算通過(guò)添加文件d, 可以被分配到這個(gè)節(jié)點(diǎn)i的新的比較任務(wù)的數(shù)量(規(guī)則1);
(26)if數(shù)據(jù)文件d沒(méi)有被分發(fā)過(guò)then
(27) 以第(25)步中的數(shù)量大小, 將C以降序排列;
(28) 將數(shù)據(jù)文件d分發(fā)到集合C的第一個(gè)節(jié)點(diǎn);
(29) 將第(25)步中發(fā)現(xiàn)的這個(gè)節(jié)點(diǎn)的所有新任務(wù)分配到這個(gè)節(jié)點(diǎn)上。
(30) 更新未分配任務(wù)的集合U
(31) 重新分配:對(duì)于已經(jīng)在之前被分配到了其它節(jié)點(diǎn)的,由添加數(shù)據(jù)文件d所帶來(lái)的比較任務(wù),遵循規(guī)則2對(duì)這些任務(wù)進(jìn)行重新分配。
與Hadoop的數(shù)據(jù)分發(fā)策略[12]相比較,本文提出的解決方案具有以下優(yōu)勢(shì)。首先,Hadoop隨機(jī)進(jìn)行數(shù)據(jù)項(xiàng)分發(fā),而沒(méi)有考慮到計(jì)算任務(wù)的需求。在這種情況下,必須在運(yùn)行時(shí)對(duì)大量的數(shù)據(jù)文件進(jìn)行遷移以完成計(jì)算任務(wù),這將導(dǎo)致大量的數(shù)據(jù)移動(dòng),并造成性能下降。而本文提出的解決方案則考慮到了計(jì)算任務(wù)需求。提出的方案的數(shù)據(jù)項(xiàng)分發(fā)中,所有的數(shù)據(jù)項(xiàng)均可在本地進(jìn)行處理,使得其對(duì)于所有計(jì)算任務(wù)均具備良好的數(shù)據(jù)本地性。其次,通過(guò)本文提出的數(shù)據(jù)分發(fā)策略,可以實(shí)現(xiàn)靜態(tài)系統(tǒng)的負(fù)載平衡。與之相反,Hadoop沒(méi)有提供靜態(tài)任務(wù)分配的解決方案[13]。為在Hadoop中實(shí)現(xiàn)負(fù)載平衡,必須在多個(gè)機(jī)器之間對(duì)大量數(shù)據(jù)進(jìn)行移動(dòng)。
實(shí)驗(yàn)在一個(gè)分布式系統(tǒng)上進(jìn)行,構(gòu)建的異構(gòu)Linux集群中包括通過(guò)傳輸速率為1 Gbps的以太網(wǎng)絡(luò)互相連接的9個(gè)物理服務(wù)器。在9個(gè)服務(wù)器中,一個(gè)節(jié)點(diǎn)作為主節(jié)點(diǎn),剩余的8個(gè)節(jié)點(diǎn)作為工作節(jié)點(diǎn)。9個(gè)節(jié)點(diǎn)均配置了英特爾i5處理器和64 GB內(nèi)存,且均運(yùn)行Linux系統(tǒng)。實(shí)驗(yàn)中選擇了CVTree問(wèn)題[14]。與兩種優(yōu)秀數(shù)據(jù)分發(fā)策略進(jìn)行比較:基于圖覆蓋的數(shù)據(jù)分配算法(DAABGC)和成熟的Hadoop策略[15]。
本文實(shí)驗(yàn)以生物信息學(xué)中的CVTree問(wèn)題作為全比較案例,該問(wèn)題是生物信息學(xué)中典型且重要的全比較問(wèn)題。實(shí)驗(yàn)數(shù)據(jù)采用NCBI提供的dsDNA公開(kāi)文件集合(序列基因文件),總體數(shù)據(jù)量大小略高于20 GB,數(shù)據(jù)格式多為“*.fasta”或“*.fq”。之所以選擇CVTree,是因?yàn)镃VTree問(wèn)題是全比較領(lǐng)域中的公認(rèn)且典型的案例。目前,全比較問(wèn)題存在于生物信息學(xué)、數(shù)據(jù)挖掘等任務(wù)中,雖然這些任務(wù)的背景和目的不盡相同,但解決方法和模式是通用的。
3.1.1 與默認(rèn)副本設(shè)置兩種策略比較
在第1組實(shí)驗(yàn)中,對(duì)本文的數(shù)據(jù)分發(fā)策略與使用默認(rèn)副本設(shè)置的Hadoop策略進(jìn)行比較。對(duì)于M=256個(gè)文件,實(shí)驗(yàn)結(jié)果見(jiàn)表1,包括存儲(chǔ)使用、存儲(chǔ)節(jié)約以及數(shù)據(jù)本地性,Hadoop中數(shù)據(jù)副本數(shù)量設(shè)置為3個(gè)。由表1可以觀察到,對(duì)于大規(guī)模的ATAC問(wèn)題,Hadoop和本文提出的數(shù)據(jù)分發(fā)策略都有著顯著的存儲(chǔ)節(jié)約性能,Hadoop的數(shù)據(jù)分發(fā)時(shí)間更少,特別是在節(jié)點(diǎn)數(shù)量變得較大的情況下[16]。對(duì)于64個(gè)節(jié)點(diǎn)的集群,本文提出的數(shù)據(jù)分發(fā)策略實(shí)現(xiàn)了80%的存儲(chǔ)節(jié)約,DAABGC的數(shù)據(jù)分發(fā)策略實(shí)現(xiàn)了76%,而Hadoop策略甚至達(dá)到了95%的存儲(chǔ)節(jié)約。因此,在存儲(chǔ)節(jié)約方面,Hadoop策略是最優(yōu)的。
雖然提出的數(shù)據(jù)分發(fā)策略在存儲(chǔ)節(jié)約方面低于Hadoop,但從表1中可以清楚地看到,對(duì)于所有的計(jì)算任務(wù),

表1 存儲(chǔ)情況和數(shù)據(jù)局部性比較
提出的方法實(shí)現(xiàn)了100%的數(shù)據(jù)本地性。相比較之下,Hadoop以大量降低數(shù)據(jù)本地性來(lái)達(dá)到存儲(chǔ)節(jié)約。如表1,對(duì)于64個(gè)節(jié)點(diǎn)的集群系統(tǒng),Hadoop的數(shù)據(jù)本地性大幅降低,低至28%,而提出的數(shù)據(jù)分發(fā)策略則達(dá)到了90%以上。特別是對(duì)于大規(guī)模的全比較問(wèn)題,良好的數(shù)據(jù)本地性至關(guān)重要。
3.1.2 與增加數(shù)據(jù)副本數(shù)量的策略比較
Hadoop中并沒(méi)有給出在給定的分布式環(huán)境中,如何針對(duì)全比較問(wèn)題設(shè)定數(shù)據(jù)副本數(shù)量的指南。一旦完成設(shè)置,副本數(shù)量則變成一個(gè)常數(shù),這造成了對(duì)于其它ATAC的求解不具備靈活性。此外,即使副本數(shù)量可以每次手動(dòng)調(diào)節(jié),也不能完全解決數(shù)據(jù)的本地性問(wèn)題。相反,本文數(shù)據(jù)分發(fā)策略可以較好解決該問(wèn)題,因?yàn)樗岱椒梢宰赃m應(yīng)地確定數(shù)據(jù)副本的數(shù)量,并能夠?qū)崿F(xiàn)90%以上的數(shù)據(jù)本地性。BAABGC首先構(gòu)建最優(yōu)圖覆蓋的解,需要更多的存儲(chǔ)空間,副本數(shù)量也需要手動(dòng)調(diào)節(jié)。與之相比,本文方法具有更多的優(yōu)勢(shì)。
為了進(jìn)行驗(yàn)證,本文進(jìn)行了第2組實(shí)驗(yàn),對(duì)Hadoop和BAABGC的數(shù)據(jù)分發(fā)策略的數(shù)據(jù)副本數(shù)量進(jìn)行了手動(dòng)調(diào)節(jié),使其在一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)文件的最大數(shù)量近似于本文提出的分發(fā)策略。由此,如表2中所示,對(duì)于有著8、16、32、64個(gè)數(shù)據(jù)節(jié)點(diǎn)的分布式系統(tǒng),分別將一個(gè)數(shù)據(jù)文件相應(yīng)地復(fù)制6、9、12、15次。通過(guò)這些手動(dòng)設(shè)置,表2中的實(shí)驗(yàn)結(jié)果表明本文提出的數(shù)據(jù)策略在存儲(chǔ)節(jié)約方面的性能要優(yōu)于Hadoop。雖然Hadoop的存儲(chǔ)使用要高于提出的數(shù)據(jù)分發(fā)策略,但Hadoop的數(shù)據(jù)本地性非常差。例如,對(duì)于64個(gè)節(jié)點(diǎn)的分布式系統(tǒng),提出的方法實(shí)現(xiàn)了90%的數(shù)據(jù)本地性,比Hadoop高約60%。這主要是因?yàn)镠adoop固有屬性,數(shù)據(jù)本地性較差。Hadoop以犧牲數(shù)據(jù)本地性的代價(jià)獲得數(shù)據(jù)存儲(chǔ)方面的優(yōu)勢(shì)。BAABGC與本文類似,但在數(shù)據(jù)局部性方面,本文表現(xiàn)更佳,這主要是因?yàn)樵陂_(kāi)發(fā)該策略時(shí),本文將分布式計(jì)算任務(wù)的存儲(chǔ)使用、數(shù)據(jù)本地性和負(fù)載均衡都納入考量。
該節(jié)對(duì)時(shí)間度量都進(jìn)行了評(píng)估,Ttol用于度量進(jìn)行全比較任務(wù)的執(zhí)行性能。如式(7)所示,ttol是數(shù)據(jù)分發(fā)的時(shí)間tdis和數(shù)據(jù)比較計(jì)算的時(shí)間tcomp之和。

表2 不同變量下的實(shí)驗(yàn)結(jié)果
圖2給出了在M(數(shù)據(jù)文件數(shù)量)的不同數(shù)值下,3個(gè)不同的數(shù)據(jù)分發(fā)策略的ttol: 提出的方法、Hadoop(3),以及Hadoop(4)。對(duì)于ttol的每個(gè)條形圖,底部和頂部分別代表著tdis和tcomp。 由圖2中可以很清楚地看到,本文提出的數(shù)據(jù)分發(fā)策略在Ttol上的時(shí)間性能要大大優(yōu)于Hadoop和BAABGC。這也驗(yàn)證了,當(dāng)簡(jiǎn)單地將Hadoop的數(shù)據(jù)分發(fā)策略中數(shù)據(jù)副本的數(shù)量從3個(gè)增加到4個(gè)時(shí),其生成的節(jié)點(diǎn)上的數(shù)據(jù)文件數(shù)量要高于本文方法,但并沒(méi)有為Hadoop的ttol的性能帶來(lái)明顯的提升,從圖2中還可以看到,使用本文數(shù)據(jù)分發(fā)策略得出的tdis的性能要略差于Hadoop(3),但優(yōu)于Hadoop(4)。這是因?yàn)樘岢龅姆植疾呗缘拇鎯?chǔ)節(jié)約要低于Hadoop(3),但高于Hadoop(4),較多的存儲(chǔ)節(jié)約意味著較短的數(shù)據(jù)分發(fā)時(shí)間。對(duì)于BAABGC方法,特點(diǎn)是圖覆蓋問(wèn)題的求解,確保比較問(wèn)題都包含本地?cái)?shù)據(jù),其計(jì)算性能也優(yōu)于Hadoop。但圖覆蓋問(wèn)題的最優(yōu)解計(jì)算是一個(gè)NP完全問(wèn)題,其計(jì)算量大于本文的啟發(fā)式規(guī)則方法,因此,總計(jì)算時(shí)間高于本文方法。

圖2 不同方法的時(shí)間性能比較
為驗(yàn)證本文提出的數(shù)據(jù)分發(fā)策略能帶來(lái)良好的負(fù)載平衡,圖3給出了在不同M數(shù)值下,8個(gè)工作節(jié)點(diǎn)中的每一個(gè)節(jié)點(diǎn)的tcomp性能度量。由圖3可以觀察到,對(duì)于相同的數(shù)值M,每個(gè)工作節(jié)點(diǎn)的tcomp非常相似,并且處于式(4)的負(fù)載平衡要求內(nèi)。即,每個(gè)節(jié)點(diǎn)基本上實(shí)現(xiàn)自給自足,都使用本地?cái)?shù)據(jù),不需要節(jié)點(diǎn)間的數(shù)據(jù)傳輸交換。

圖3 tcomp的性能比較
為支持對(duì)包含大數(shù)據(jù)集的問(wèn)題進(jìn)行處理,可擴(kuò)展性相當(dāng)重要。實(shí)驗(yàn)測(cè)試中工作節(jié)點(diǎn)最多為8個(gè)(以及一個(gè)管理器節(jié)點(diǎn)),具體如圖4所示,圖中的線性加速實(shí)線可被視為理想化的加速。圖4給出了本文數(shù)據(jù)分發(fā)策略所實(shí)現(xiàn)的實(shí)際加速情況。從中可以觀察到,本文數(shù)據(jù)分發(fā)策略的表現(xiàn)接近線性加速趨勢(shì)。這代表著總體分布式計(jì)算的良好的可擴(kuò)展性。雖然全比較問(wèn)題會(huì)在網(wǎng)絡(luò)通信中產(chǎn)生不可避免的開(kāi)銷,以及額外的內(nèi)存要求和硬盤(pán)存取,但本文提出的數(shù)據(jù)分發(fā)策略能夠?qū)崿F(xiàn)理想化的線性加速大約91.5%(7.32/8=91.5%)的性能。而B(niǎo)AABGC的加速比是6.335/7=90.5%。在加速比方面優(yōu)于其它策略,即,所提方法的可擴(kuò)展性更佳,更能適合大規(guī)模的分布式計(jì)算。

圖4 本文方法的可擴(kuò)展性分析
為解決帶有大數(shù)據(jù)的ATAC的分布式計(jì)算問(wèn)題,提出了一個(gè)高效可擴(kuò)展的數(shù)據(jù)分發(fā)策略。該策略由比較任務(wù)分配所驅(qū)動(dòng),其基本設(shè)計(jì)理念是最小化工作節(jié)點(diǎn)的存儲(chǔ)使用,且數(shù)據(jù)項(xiàng)目均可在本地進(jìn)行處理,使得集群中的工作節(jié)點(diǎn)數(shù)據(jù)本地性保持了良好的態(tài)勢(shì),對(duì)于5種不同的集群系統(tǒng),其數(shù)據(jù)本地性均在90%以上。同時(shí),根據(jù)約束和啟發(fā)式規(guī)則,每個(gè)工作節(jié)點(diǎn)被分配相似數(shù)量的任務(wù),并自動(dòng)決定數(shù)據(jù)副本數(shù)量,使得節(jié)點(diǎn)間的工作負(fù)載平衡性較好。實(shí)驗(yàn)結(jié)果表明了所提數(shù)據(jù)分發(fā)策略解決ATAC具備優(yōu)秀的性能。