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

余先昊，周 鳳

(1.貴州商學院 計算機與信息工程學院，貴州 貴陽 550001； 2.貴州大學 計算機科學與技術學院，貴州 貴陽 550025)

0 引 言

商業(yè)應用和科學研究的計算服務經(jīng)常涉及到大規(guī)數(shù)據(jù)集的密集型計算[1]，系統(tǒng)需要在用戶可接受的時間范圍內(nèi)對海量數(shù)據(jù)進行存儲、檢索、定位和可視化等操作[2]。全比較[3](ATAC)問題廣泛存在于大數(shù)據(jù)處理任務中，例如海量數(shù)據(jù)挖掘、海量信息管理和生物統(tǒng)計學等。

在ATAC中，數(shù)據(jù)文件的每個數(shù)據(jù)項需要與數(shù)據(jù)集中其它數(shù)據(jù)文件的所有數(shù)據(jù)項進行比較。因此，其計算模式與Map Reduce的計算模式[4]不同。如果數(shù)據(jù)集中的文件數(shù)量(或數(shù)據(jù)項)很多，那么對于ATAC問題，需要進行的計算規(guī)模將非常大。

為處理ATAC問題，研究人員使用了多種分布式系統(tǒng)和數(shù)據(jù)庫。如Li等[5]提出了一種大型數(shù)據(jù)集上的全比較數(shù)據(jù)分發(fā)模型，采用異構(gòu)多核集群運行算法，所有數(shù)據(jù)分發(fā)到每個計算節(jié)點上。Gao等[6]提出基于圖覆蓋的數(shù)據(jù)分配算法(DAABGC)，通過理論分析將大數(shù)據(jù)全比較問題轉(zhuǎn)換為圖覆蓋問題。Hong等[7]提出了BLAST算法在GPU-CPU混合式異構(gòu)系統(tǒng)中的設計和優(yōu)化，但對硬件的依賴比較強。與之類似，Wang等[8]也對硬件的要求較高。

現(xiàn)有解決方案主要關注不同算法的并行執(zhí)行，以及負載平衡，但很少關注數(shù)據(jù)分發(fā)問題。在處理大型數(shù)據(jù)集時擴展性較差，效率低下。為此，本文提出ATAC問題的分布式計算方法，其中，所有的比較任務都有著相同或相近的執(zhí)行時間，自動決定數(shù)據(jù)副本的數(shù)量，并針對比較任務實現(xiàn)較好的數(shù)據(jù)本地性和負載平衡性。

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

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

1.1 總體考量和假設

求解ATAC問題的一般工作流程如圖1所示，由圖1可以觀察到，為高效求解ATAC問題，需要對數(shù)據(jù)分發(fā)和任務計算階段都進行改善。分布式環(huán)境中大數(shù)據(jù)處理的整體計算性能受到兩個問題的影響：①數(shù)據(jù)本地性；②計算任務的分配。其中，數(shù)據(jù)本地性要求當計算操作被分配到工作節(jié)點時，該計算操作的效率一般會更高。由于網(wǎng)絡通信和數(shù)據(jù)傳輸?shù)呢摀^為繁重，需要存取遠程數(shù)據(jù)集的計算任務的效率可能會非常低。因此，當把適當?shù)娜蝿辗峙浣o具有對應處理能力的工作節(jié)點時，分布式系統(tǒng)的性能會得到明顯提升，分布式系的工作效能會更高[9]。

圖1 求解ATAC問題的一般工作流程

為了利用圖1的流程，需要開發(fā)出數(shù)據(jù)分發(fā)策略。首先，本文通過數(shù)據(jù)分發(fā)策略生成數(shù)據(jù)分布解。然后，基于給出的分布解對所有的數(shù)據(jù)文件進行部署。在數(shù)據(jù)分布中，考慮以下兩個方面：

(1)分布式系統(tǒng)的存儲情況。由于ATAC問題涉及的數(shù)據(jù)量巨大，在分配節(jié)點任務時，需要考慮到每個節(jié)點在其容量內(nèi)的存儲空間使用情況，還需要將數(shù)據(jù)分發(fā)的總時間保持在可接受的水平。

(2)比較計算的性能。對于分布式計算，在分配比較任務時，使系統(tǒng)中所有可用的計算能力都得到充分的利用非常重要。此外，數(shù)據(jù)的本地性越好，計算的效率越高，兩者關系密切。因此，對于全比較問題，數(shù)據(jù)分發(fā)需滿足：數(shù)據(jù)項的分配必須提高比較計算的性能。

在現(xiàn)實應用中，很多數(shù)據(jù)都具有相同或相似的大小，且所有的比較任務都有著相等或相似的執(zhí)行時間。典型的例子有：協(xié)方差矩陣計算、聚類和分類中的相似性計算等。下文將分析分布式系統(tǒng)的存儲使用要求，以及比較計算的性能。

1.2 降低存儲使用

數(shù)據(jù)分發(fā)[10]上所耗費的時間受很多因素的影響，如網(wǎng)絡帶寬、數(shù)據(jù)項的大小、網(wǎng)絡結(jié)構(gòu)等。由于數(shù)據(jù)分發(fā)的時間與待分發(fā)的數(shù)據(jù)項數(shù)量成正比。有

tdis∝D

(1)

式中：D表示待分發(fā)的數(shù)據(jù)文件。tdis表示數(shù)據(jù)分發(fā)的時間。相關研究表明，每個工作節(jié)點的存儲使用量必須在其容量限制范圍之內(nèi)，如果對所有的數(shù)據(jù)集進行均勻的分發(fā)，則可以滿足這一要求[9]。

假設系統(tǒng)分配到節(jié)點i的文件數(shù)量為 |Di|， 分發(fā)的策略是將 |D1|,…,|DN| 最大值，之后再最小化，即

minimize max{|D1|,|D2|,…,|DN|}

(2)

對工作節(jié)點中數(shù)據(jù)文件的最大數(shù)量進行最小化，有以下好處：①最小化能夠使得所有工作節(jié)點中的數(shù)據(jù)文件的數(shù)量大致相同；②最小化還能夠使得所有的工作節(jié)點可執(zhí)行的比較任務的數(shù)量大致相同。

1.3 提升計算性能的方法

在ATAC的分布式計算中，最后一個完成工作的節(jié)點從某種程度上決定了總計算時間[11]。

設K表示分配到最后一個完成任務的工作節(jié)點的比較任務的數(shù)量，tcomp(k)代表比較k個任務所用的時間，tsave(k)代表對涉及任務k數(shù)據(jù)存取所用的時間。則執(zhí)行比較任務的總實際運算時間，tcomp具體定義如下

(3)

式中：本文提出的數(shù)據(jù)分發(fā)策略通過滿足兩個約束項，降低了總執(zhí)行時間Ttol：①工作節(jié)點的負載平衡；②良好的數(shù)據(jù)本地性。

為了進行負載平衡的約束，需要在任務完成后，對最大比較數(shù)量進行最小化處理。設Ti表示工作節(jié)點i所執(zhí)行的逐對比較任務的數(shù)量。對于一個有著N個工作節(jié)點和M個數(shù)據(jù)文件的分布式系統(tǒng)，需要分配到工作節(jié)點的比較任務的總數(shù)量為M(M-1)/2個。通過以下公式，對K的數(shù)值進行最小化

(4)

M(M-1)/2≥N,M>2

(5)

良好的數(shù)據(jù)本地性可以利用數(shù)學表達式的形式來獲得。在某些情況下，本地節(jié)點存儲的數(shù)據(jù)可以為某些任務提供便利，無需遠程調(diào)用數(shù)據(jù)，即達到了“自給自足”。意味著tsave(k)為最小值，該數(shù)值可能的最低數(shù)值為0。數(shù)據(jù)本地性定義如下

(6)

式中： (x,y) 表示對數(shù)據(jù)x和y進行比較，T表示比較任務的集合，Ti表示節(jié)點i執(zhí)行的任務，Di為節(jié)點i中的當?shù)財?shù)據(jù)。當N=2時，上述討論的數(shù)據(jù)分布變得不再重要。在這種情況下，需要至少有一個節(jié)點中存儲著式(4)和式(6)所要求的所有數(shù)據(jù)文件。因此，一個定義完善的數(shù)據(jù)分布問題要求：N>2。

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

當同時考慮存儲使用和計算性能時，數(shù)據(jù)分發(fā)策略應該滿足式(2)中的目標，同時還需要滿足式(4)和式(6)中的約束。由此降低對所有數(shù)據(jù)集進行分發(fā)所耗費的時間(tdis)。滿足式(4)和式(6)中的約束可以理解為總比較時間tcomp的數(shù)值被最小化。從而，數(shù)據(jù)分發(fā)和任務執(zhí)行的總體運行時間將得到顯著下降

ttol=tdis+tcomp

(7)

因此，數(shù)據(jù)分發(fā)問題可以被表示為一個約束性優(yōu)化問題

(8)

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

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

一般可以通過滿足式(4)和式(6)中的約束，來推導出式(8)分發(fā)問題的可行解。本文以滿足式(4)和式(6)中的約束為前提，將所有的比較任務分配到工作節(jié)點。本文分發(fā)數(shù)據(jù)的啟發(fā)式規(guī)則如下：

規(guī)則1：對于之前從未被分配過的比較任務，可以通過遵循式(4)的約束條件設計出一個數(shù)據(jù)分發(fā)策略，將盡可能多的此類任務分配到節(jié)點i。

規(guī)則2：對于已經(jīng)被分配過的比較任務，可以遵循式(4)的約束條件設計出數(shù)據(jù)分發(fā)策略，對此類任務中的每一個任務進行再次分配。舉例來說，如果一個比較任務task已經(jīng)被分配到工作節(jié)點q，則該策略將對被分配到節(jié)點i和節(jié)點q的比較任務之間的數(shù)量進行比較。如果工作節(jié)點i上的比較任務數(shù)量較少，則將任務task重新分配到節(jié)點i。根據(jù)這些啟發(fā)式規(guī)則，可以設計出用于實際的數(shù)據(jù)分發(fā)的算法及具體步驟。

2.2 數(shù)據(jù)分發(fā)算法

本文提出的任務驅(qū)動的啟發(fā)式數(shù)據(jù)分發(fā)策略如算法1所示。

算法1： 數(shù)據(jù)分發(fā)算法

起始： 集合U為所有未分配的逐對比較任務；

變量： 變量數(shù)據(jù)集D和節(jié)點集合C， 兩者初始均為空集；

(1)while未分配的任務的集合U不是空集do

(2)D←φ；C←φ； // 空集D和C

(3) 找到未分配任務的所有數(shù)據(jù)文件；

(4) 將這些數(shù)據(jù)文件放入到集合D中；

(5) 對于集合D中的每個文件，對需要該文件的未分配任務進行計數(shù);

(6) 將集合D以該計數(shù)的數(shù)字大小進行降序排列；

(7)while節(jié)點集合C是空集do

(8) 選擇集合D中第一個數(shù)據(jù)文件。設d表示該文件；

(9)for系統(tǒng)中所有的工作節(jié)點do

(10) 找到不包含文件d的節(jié)點的集合；

(11) 將這些節(jié)點放入集合C；

(12)for集合C中的所有節(jié)點do

(13) 找到并標記被分配任務的數(shù)量最少的節(jié)點；

(14) 將所有被標記的節(jié)點從C中移除；

(15)for集合C中的所有節(jié)點do

(16) 找到并標記被分發(fā)文件的數(shù)量最少的節(jié)點；

(17) 將所有被標記的節(jié)點從C中移除；

(18)if集合C變?yōu)榭占痙o

(19) 將文件d從集合D中移除；

(20)for集合C中的每個工作節(jié)點ido

(21)if節(jié)點i為空then

(22) 將數(shù)據(jù)文件d分發(fā)到這一節(jié)點i；

(23) break；// 跳出這個for循環(huán)

(24)else

(25) 計算通過添加文件d， 可以被分配到這個節(jié)點i的新的比較任務的數(shù)量(規(guī)則1)；

(26)if數(shù)據(jù)文件d沒有被分發(fā)過then

(27) 以第(25)步中的數(shù)量大小， 將C以降序排列；

(28) 將數(shù)據(jù)文件d分發(fā)到集合C的第一個節(jié)點；

(29) 將第(25)步中發(fā)現(xiàn)的這個節(jié)點的所有新任務分配到這個節(jié)點上。

(30) 更新未分配任務的集合U

(31) 重新分配：對于已經(jīng)在之前被分配到了其它節(jié)點的，由添加數(shù)據(jù)文件d所帶來的比較任務，遵循規(guī)則2對這些任務進行重新分配。

與Hadoop的數(shù)據(jù)分發(fā)策略[12]相比較，本文提出的解決方案具有以下優(yōu)勢。首先，Hadoop隨機進行數(shù)據(jù)項分發(fā)，而沒有考慮到計算任務的需求。在這種情況下，必須在運行時對大量的數(shù)據(jù)文件進行遷移以完成計算任務，這將導致大量的數(shù)據(jù)移動，并造成性能下降。而本文提出的解決方案則考慮到了計算任務需求。提出的方案的數(shù)據(jù)項分發(fā)中，所有的數(shù)據(jù)項均可在本地進行處理，使得其對于所有計算任務均具備良好的數(shù)據(jù)本地性。其次，通過本文提出的數(shù)據(jù)分發(fā)策略，可以實現(xiàn)靜態(tài)系統(tǒng)的負載平衡。與之相反，Hadoop沒有提供靜態(tài)任務分配的解決方案[13]。為在Hadoop中實現(xiàn)負載平衡，必須在多個機器之間對大量數(shù)據(jù)進行移動。

3 實驗與分析

實驗在一個分布式系統(tǒng)上進行，構(gòu)建的異構(gòu)Linux集群中包括通過傳輸速率為1 Gbps的以太網(wǎng)絡互相連接的9個物理服務器。在9個服務器中，一個節(jié)點作為主節(jié)點，剩余的8個節(jié)點作為工作節(jié)點。9個節(jié)點均配置了英特爾i5處理器和64 GB內(nèi)存，且均運行Linux系統(tǒng)。實驗中選擇了CVTree問題[14]。與兩種優(yōu)秀數(shù)據(jù)分發(fā)策略進行比較：基于圖覆蓋的數(shù)據(jù)分配算法(DAABGC)和成熟的Hadoop策略[15]。

本文實驗以生物信息學中的CVTree問題作為全比較案例，該問題是生物信息學中典型且重要的全比較問題。實驗數(shù)據(jù)采用NCBI提供的dsDNA公開文件集合(序列基因文件)，總體數(shù)據(jù)量大小略高于20 GB，數(shù)據(jù)格式多為“*.fasta”或“*.fq”。之所以選擇CVTree，是因為CVTree問題是全比較領域中的公認且典型的案例。目前，全比較問題存在于生物信息學、數(shù)據(jù)挖掘等任務中，雖然這些任務的背景和目的不盡相同，但解決方法和模式是通用的。

3.1 存儲節(jié)約和數(shù)據(jù)本地性的性能

3.1.1 與默認副本設置兩種策略比較

在第1組實驗中，對本文的數(shù)據(jù)分發(fā)策略與使用默認副本設置的Hadoop策略進行比較。對于M=256個文件，實驗結(jié)果見表1，包括存儲使用、存儲節(jié)約以及數(shù)據(jù)本地性，Hadoop中數(shù)據(jù)副本數(shù)量設置為3個。由表1可以觀察到，對于大規(guī)模的ATAC問題，Hadoop和本文提出的數(shù)據(jù)分發(fā)策略都有著顯著的存儲節(jié)約性能，Hadoop的數(shù)據(jù)分發(fā)時間更少，特別是在節(jié)點數(shù)量變得較大的情況下[16]。對于64個節(jié)點的集群，本文提出的數(shù)據(jù)分發(fā)策略實現(xiàn)了80%的存儲節(jié)約，DAABGC的數(shù)據(jù)分發(fā)策略實現(xiàn)了76%，而Hadoop策略甚至達到了95%的存儲節(jié)約。因此，在存儲節(jié)約方面，Hadoop策略是最優(yōu)的。

雖然提出的數(shù)據(jù)分發(fā)策略在存儲節(jié)約方面低于Hadoop，但從表1中可以清楚地看到，對于所有的計算任務，

表1 存儲情況和數(shù)據(jù)局部性比較

提出的方法實現(xiàn)了100%的數(shù)據(jù)本地性。相比較之下，Hadoop以大量降低數(shù)據(jù)本地性來達到存儲節(jié)約。如表1，對于64個節(jié)點的集群系統(tǒng)，Hadoop的數(shù)據(jù)本地性大幅降低，低至28%，而提出的數(shù)據(jù)分發(fā)策略則達到了90%以上。特別是對于大規(guī)模的全比較問題，良好的數(shù)據(jù)本地性至關重要。

3.1.2 與增加數(shù)據(jù)副本數(shù)量的策略比較

Hadoop中并沒有給出在給定的分布式環(huán)境中，如何針對全比較問題設定數(shù)據(jù)副本數(shù)量的指南。一旦完成設置，副本數(shù)量則變成一個常數(shù)，這造成了對于其它ATAC的求解不具備靈活性。此外，即使副本數(shù)量可以每次手動調(diào)節(jié)，也不能完全解決數(shù)據(jù)的本地性問題。相反，本文數(shù)據(jù)分發(fā)策略可以較好解決該問題，因為所提方法可以自適應地確定數(shù)據(jù)副本的數(shù)量，并能夠?qū)崿F(xiàn)90%以上的數(shù)據(jù)本地性。BAABGC首先構(gòu)建最優(yōu)圖覆蓋的解，需要更多的存儲空間，副本數(shù)量也需要手動調(diào)節(jié)。與之相比，本文方法具有更多的優(yōu)勢。

為了進行驗證，本文進行了第2組實驗，對Hadoop和BAABGC的數(shù)據(jù)分發(fā)策略的數(shù)據(jù)副本數(shù)量進行了手動調(diào)節(jié)，使其在一個節(jié)點上的數(shù)據(jù)文件的最大數(shù)量近似于本文提出的分發(fā)策略。由此，如表2中所示，對于有著8、16、32、64個數(shù)據(jù)節(jié)點的分布式系統(tǒng)，分別將一個數(shù)據(jù)文件相應地復制6、9、12、15次。通過這些手動設置，表2中的實驗結(jié)果表明本文提出的數(shù)據(jù)策略在存儲節(jié)約方面的性能要優(yōu)于Hadoop。雖然Hadoop的存儲使用要高于提出的數(shù)據(jù)分發(fā)策略，但Hadoop的數(shù)據(jù)本地性非常差。例如，對于64個節(jié)點的分布式系統(tǒng)，提出的方法實現(xiàn)了90%的數(shù)據(jù)本地性，比Hadoop高約60%。這主要是因為Hadoop固有屬性，數(shù)據(jù)本地性較差。Hadoop以犧牲數(shù)據(jù)本地性的代價獲得數(shù)據(jù)存儲方面的優(yōu)勢。BAABGC與本文類似，但在數(shù)據(jù)局部性方面，本文表現(xiàn)更佳，這主要是因為在開發(fā)該策略時，本文將分布式計算任務的存儲使用、數(shù)據(jù)本地性和負載均衡都納入考量。

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

該節(jié)對時間度量都進行了評估，Ttol用于度量進行全比較任務的執(zhí)行性能。如式(7)所示，ttol是數(shù)據(jù)分發(fā)的時間tdis和數(shù)據(jù)比較計算的時間tcomp之和。

表2 不同變量下的實驗結(jié)果

圖2給出了在M(數(shù)據(jù)文件數(shù)量)的不同數(shù)值下，3個不同的數(shù)據(jù)分發(fā)策略的ttol： 提出的方法、Hadoop(3)，以及Hadoop(4)。對于ttol的每個條形圖，底部和頂部分別代表著tdis和tcomp。 由圖2中可以很清楚地看到，本文提出的數(shù)據(jù)分發(fā)策略在Ttol上的時間性能要大大優(yōu)于Hadoop和BAABGC。這也驗證了，當簡單地將Hadoop的數(shù)據(jù)分發(fā)策略中數(shù)據(jù)副本的數(shù)量從3個增加到4個時，其生成的節(jié)點上的數(shù)據(jù)文件數(shù)量要高于本文方法，但并沒有為Hadoop的ttol的性能帶來明顯的提升，從圖2中還可以看到，使用本文數(shù)據(jù)分發(fā)策略得出的tdis的性能要略差于Hadoop(3)，但優(yōu)于Hadoop(4)。這是因為提出的分布策略的存儲節(jié)約要低于Hadoop(3)，但高于Hadoop(4)，較多的存儲節(jié)約意味著較短的數(shù)據(jù)分發(fā)時間。對于BAABGC方法，特點是圖覆蓋問題的求解，確保比較問題都包含本地數(shù)據(jù)，其計算性能也優(yōu)于Hadoop。但圖覆蓋問題的最優(yōu)解計算是一個NP完全問題，其計算量大于本文的啟發(fā)式規(guī)則方法，因此，總計算時間高于本文方法。

圖2 不同方法的時間性能比較

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

圖3 tcomp的性能比較

3.3 可擴展性

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

圖4 本文方法的可擴展性分析

4 結(jié)束語

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