利用啟發式數據分發策略求解全比較問題

余先昊，周 鳳

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

0 引 言

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

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

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

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

1 數據分布的公式化表述

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

1.1 總體考量和假設

求解ATAC問題的一般工作流程如圖1所示，由圖1可以觀察到，為高效求解ATAC問題，需要對數據分發和任務計算階段都進行改善。分布式環境中大數據處理的整體計算性能受到兩個問題的影響：①數據本地性；②計算任務的分配。其中，數據本地性要求當計算操作被分配到工作節點時，該計算操作的效率一般會更高。由于網絡通信和數據傳輸的負擔較為繁重，需要存取遠程數據集的計算任務的效率可能會非常低。因此，當把適當的任務分配給具有對應處理能力的工作節點時，分布式系統的性能會得到明顯提升，分布式系的工作效能會更高[9]。

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

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

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

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

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

1.2 降低存儲使用

數據分發[10]上所耗費的時間受很多因素的影響，如網絡帶寬、數據項的大小、網絡結構等。由于數據分發的時間與待分發的數據項數量成正比。有

tdis∝D

(1)

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

假設系統分配到節點i的文件數量為 |Di|， 分發的策略是將 |D1|,…,|DN| 最大值，之后再最小化，即

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

(2)

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

1.3 提升計算性能的方法

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

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

(3)

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

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

(4)

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

(5)

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

(6)

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

1.4 優化數據分布的約束

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

ttol=tdis+tcomp

(7)

因此，數據分發問題可以被表示為一個約束性優化問題

(8)

2 提出的數據分發策略

2.1 數據分發的啟發式規則

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

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

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

2.2 數據分發算法

本文提出的任務驅動的啟發式數據分發策略如算法1所示。

算法1： 數據分發算法

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

變量： 變量數據集D和節點集合C， 兩者初始均為空集；

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

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

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

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

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

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

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

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

(9)for系統中所有的工作節點do

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

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

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

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

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

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

(16) 找到并標記被分發文件的數量最少的節點；

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

(18)if集合C變為空集do

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

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

(21)if節點i為空then

(22) 將數據文件d分發到這一節點i；

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

(24)else

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

(26)if數據文件d沒有被分發過then

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

(28) 將數據文件d分發到集合C的第一個節點；

(29) 將第(25)步中發現的這個節點的所有新任務分配到這個節點上。

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

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

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

3 實驗與分析

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

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

3.1 存儲節約和數據本地性的性能

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

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

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

表1 存儲情況和數據局部性比較

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

3.1.2 與增加數據副本數量的策略比較

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

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

3.2 執行時間的性能

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

表2 不同變量下的實驗結果

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

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

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

圖3 tcomp的性能比較

3.3 可擴展性

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

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

4 結束語

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