利用启发式数据分发策略求解全比较问题

余先昊，周 凤

(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具备优秀的性能。