利用啟發(fā)式數(shù)據(jù)分發(fā)策略求解全比較問(wèn)題

余先昊，周 鳳

(1.貴州商學(xué)院 計(jì)算機(jī)與信息工程學(xué)院，貴州 貴陽(yáng) 550001； 2.貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025)

0 引 言

商業(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ù)載平衡性。

1 數(shù)據(jù)分布的公式化表述

本節(jié)將介紹用于數(shù)據(jù)分布的計(jì)算框架。首先從總體上考量和假設(shè)。然后，提出降低存儲(chǔ)占用和提高計(jì)算性能的公式。最后，通過(guò)一個(gè)總體優(yōu)化問(wèn)題，以詳細(xì)說(shuō)明數(shù)據(jù)分布的要求。

1.1 總體考量和假設(shè)

求解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ì)算的性能。

1.2 降低存儲(chǔ)使用

數(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ù)量大致相同。

1.3 提升計(jì)算性能的方法

在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。

1.4 優(yōu)化數(shù)據(jù)分布的約束

當(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)

2 提出的數(shù)據(jù)分發(fā)策略

2.1 數(shù)據(jù)分發(fā)的啟發(fā)式規(guī)則

一般可以通過(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ā)的算法及具體步驟。

2.2 數(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)。

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

實(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 存儲(chǔ)節(jié)約和數(shù)據(jù)本地性的性能

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ù)載均衡都納入考量。

3.2 執(zhí)行時(shí)間的性能

該節(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的性能比較

3.3 可擴(kuò)展性

為支持對(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ò)展性分析

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

為解決帶有大數(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)秀的性能。