面向军用网格的广域分布式数据处理框架

张 智，江 果，蒋鸣远

(中国电子科技集团公司第二十九研究所，成都 610036)

0 引 言

目前，数据挖掘、机器学习、人工智能等大数据技术为各行各业带来了解决问题的新思路[1]，军事应用领域也不例外，能否通过海量数据的训练使军用信息系统更智能化成为当前热门的议题。随着信息化、网络化程度的提高，全国范围内的部队在每天的训练过程中会积累下非常可观的数据。当需要分析多个部队收集到的作战数据时，这些数据分散在各个部队内部，而这些部队之间由于地域的隔离、专用带宽有限等因素，往往会消耗大量的时间来传输原始数据[2]。

Google公司在大数据的三大论文[3]中提出了利用多台计算机同时工作以实现对海量数据高效处理的思路，基于这个思路，工程师们创造了以Hadoop、Spark等为代表的分布式计算框架，这些框架将用户提交的计算请求拆分成若干个子任务，分别由不同的计算资源并发地执行子任务，最终按照一定的规则将结果汇总后反馈给用户。网格计算是分布式计算在发展过程中涌现出的一个细分类，它将松散连接的计算机通过网络聚合起来构成的一个虚拟超级计算系统以执行大规模计算任务，支持跨管理域的能力使它与传统的计算集群或传统的分布式计算相区别。但是，现阶段主流的分布式计算框架和网格计算框架旨在将大量计算机闲置计算资源利用起来以提高整体的计算能力，没有考虑到军用广域场景下由数据隔离分散造成的数据不可见、不可取才是真正的瓶颈，难以直接应用到跨域的大规模作战数据分析场景中。为了实现高效的大规模跨域作战数据分析，亟需一种能够适用于军网专用网络协议环境下的大数据处理框架来统管广域范围内的海量作战数据，以解决对于任何单一数据源或单一计算节点来说仍然大得难以解决的问题。

根据上述应用场景分析，本文首先对业界主流的分布式计算框架进行比较分析，提出一种基于DAG模型实现广域分布式数据处理的核心思路；其次，结合军用网格环境下系统复杂度高、处理请求多的特点，分别从逻辑层面和物理层面设计出框架内核的架构；然后，考虑到不同用户提交的数据处理请求具有不同的优先级，设计了以计算、通信资源为争夺目标的优先级排队策略；最后，按照前文设想实现了广域分布式数据处理框架原型软件，并模拟军事应用中的跨域数据场景设计、实施仿真实验，通过分析实验结果证实本框架相对于传统计算方式在计算效率上有显著提高。

1 DAG计算调度模型

1.1 主流分布式计算框架分析

现有的各类分布式计算框架主要应用于局域网环境下的计算，具有带宽要求高、防火墙设置复杂、计算节点数据交互频繁等特点。Hadoop、Spark等分布式计算框架于2008年以后陆续流行于国内，众多互联网企业、高校以及科研机构都开始研究和使用这类分布式计算框架。在初期，技术实力较强的公司在上述几类分布式计算框架基础上根据自身业务需求进行改造，例如百度利用Hadoop进行网页分析、腾讯基于Spark搭建商品推荐系统、阿里巴巴通过Storm建立海量日志分析系统。随着分布式计算经验的积累，国内也涌现出一些新的分布式计算框架，Fourinone、Paracel、DC4C以及Pydra就属于这一类型。

业界主流的分布式调度模型主要有基于MapReduce模型[4]和基于有向无环图模型(DAG)两种方案。从成熟度、复杂度、数据处理、通信方式、主要应用场景以及存储依赖性等方面比较MapReduce模型和有向无环图模型两种分布式协同计算模型的优缺点，如表1所示。

表1 MapReduce模型和有向无环图模型比较

一方面，军用领域的分布式计算具有数据源动态变化、业务流程离散的特点，与有向无环图模型相契合；另一方面，由于跨广域网之间通信带宽的限制，商用分布式文件系统难以在部队之间直接应用，计算节点之间直接进行数据传输更能够有效利用带宽资源。

综合比较以上两种分布式计算模型后，本文采用有向无环图模型实现分布式计算框架。

1.2 DAG模型

DAG模型即有向无环图模型(Directed acyclic graph)[5]，若我们将一个分布式数据处理任务按照特定的顺序约束拆分成为先后实施的子任务，而每个子任务由不同的计算节点相对独立地执行，那么一个分布式数据处理任务可以用一个节点和边均带权值的有向无环图来表示。它是一个四元组G=(V,E,W,C)其中，V=(V1,V2,…，V|V|)表示子任务的集合，每个子任务包含任务ID、计算节点、计算指令、计算参数等信息，表达式|V|则表示子任务的个数；E=(eij|vi,vj∈V)⊆V×V，表示有向边的集合，若子任务vi和子任务vj之间存在有向边eij，那么表明子任务vi是子任务vj的直接前驱节点，子任务vj的执行依赖于子任务vi产生的中间数据，|E|表示有向边的个数；节点权值W表示各个子任务本身的执行时间，而有向边权值C表示两个子任务之间的通信数据量。

因此，一个DAG任务的总处理时间可表示为

(1)

即所有子任务的执行之间与所有通信时间的总和，B表示通信带宽速率。

2 分布式数据处理架构设计

2.1 逻辑架构设计

本框架从广域网整体出发将接入系统的所有部队及其相关的计算、数据、网络资源看作是一个网格环境，以每一个部队作为计算节点单元，并选取其中一个部队(通常是上级部队)作为分布式计算调度中心，如图1所示。其中，分布式计算调度中心负责将用户提交的分布式计算请求解析成任务，并分发给分布式计算节点按照有向无环图完成执行，最终将收集到的计算结论推送给用户；而计算节点单元负责接收并执行分布式计算调度中心下发的计算任务。

图1 基于DAG的逻辑架构

由于参与计算的目标数据通常集中在确定的计算节点(部队)内，用户需要根据数据分布情况从系统中选择若干部队(计算节点)，按照有向无环图(DAG)模型组织成为计算请求，由分布式计算调度中心驱动相关的部队节点按照指定的DAG顺序完成计算任务。

2.2 物理架构设计

跨地域的分布式系统之间通常是异构的，这意味着系统之间的接口标准、数据格式、通信协议都可能有差异，并且系统之间的状态往往不是同步的。将跨地域的系统集成以后，系统的整体规模也有极大的增长。假如一台电脑无故障连续运行一个月的概率是99.99%，那么1000台电脑同时无故障连续运行一个月的概率只有90.48%。由于系统复杂度高、规模大，难以保障系统内所有软件、硬件长时间无故障运行。同时，随着系统用户数量的增长，必然存在多用户同时提交分布式数据处理请求的情况，良好的架构设计应该支持多任务并发的情况。

微服务体系架构在复杂度控制、服务并发性、系统容错性以及扩展能力方面都具有一定的优势[6-7]。每一个微服务只具有单一功能，它将一个庞大的整体应用分解成一组服务，将业务粒度控制在单个服务范围内。当某一组业务功能发生故障时，故障会被隔离在单个服务中，其他服务可通过备份、退化等机制实现应用层面的容错。微服务体系架构从线程、进程等多种粒度提供不同的多实例实现模式，能够覆盖本框架的并发设计需求。

如图2所示，本文采用微服务体系结构来实现前文所述的DAG计算调度模型。分布式计算调度中心部署在调度部队，而分布式计算节点部署在任务执行部队。分布式计算调度中心主要由请求接收服务、节点注册服务、通信管理服务、任务执行监控服务、通信录服务以及结论推送服务等构成；分布式计算节点主要由任务接收服务、任务执行服务以及任务完成服务构成。在运行状态下，每个服务至少包含一个热备份实例，当主服务故障时，服务路由机制自动将服务请求转发至热备份服务实例，同时在后台重启故障的服务，保障框架内核服务的高可靠性。

图2 服务划分示意图

3 优先级策略

Honig和Schiffmann提出了一种关于多DAG共享分布式资源的调度策略[8]。Zhao和Sakellariou在此基础上，首次提出了多DAG调度时存在的多个DAG之间的公平性问题，进而提出了关于多DAG调度公平性的定义方法和 Fairness(公平)算法[9]。Yu和Shi为了解决调度不同用户在不同时间提交的多个DAG时可能出现的不公平性调度问题，提出了动态的调度模型和策略[10]。田国忠等人在提高多个DAG共享异构资源应用的吞吐率和降低运行费方面实现了进一步的研究[11-13]。这些调度策略都是基于各个计算节点完全对等的前提，也就是说同一个任务在计算节点A上执行和在计算节点B上执行的结果完全一样。然而在军用网格场景下，各个计算节点之间因为数据资源的差异难以形成对等的关系，由于某项任务的相关数据可能只在某一确定的计算节点上存在，那么该任务就只能在对应的计算节点上执行。也就是说，每个分布式数据处理过程在用户提交时就已经确定了各个任务执行的路径，剩下的调度问题就是当不同分布式数据处理请求的任务到达同一个计算节点时面临的优先获取计算、网络资源的问题。因此，本文将作为NP完全问题的DAG任务调度问题按照贪心策略退化成为每个计算节点内任务之间的优先级调度问题。

由于计算机性能、运营成本等因素限制，相同服务最多同时启动一定限制数量的线程，如果待执行的分布式数据处理请求数目超过了这个限制，多个分布式数据处理请求就需要进行计算资源竞争；此外，由于网络带宽有限，当分布式计算调度中心同时有多个任务需要下发给不同的网络节点或者分布式计算节点同时要向多个后继节点发送中间数据，多个任务之间就会进行网络资源竞争。本质上，这类似于一个共享有限资源的多处理器调度算法。

本框架为每个计算任务设置从高到底抢占式优先、非抢占式优先以及普通三种优先级，并对每种优先级设置一个排队队列(即抢占式优先队列、非抢占式优先队列以及普通队列)。当接收到新任务时，根据不同的优先级进入相应队列的队尾，如果抢占式优先级队列中没有待执行的任务则优先执行非抢占式优先队列中的任务；反之，则从当前最低优先级中寻找开始执行时间最晚的任务，将该任务占用的资源移交给抢占式任务，同时提高被抢占资源任务的优先级。详细调度算法如图3所示。

图3 优先级调度算法示意图

4 仿真实验与分析

分布式计算框架技术主要有三种本地化应用趋势：第一、直接采用Hadoop、Spark等成熟的分布式计算框架，通过长期的积累，针对各种场景形成特有的算法库；第二、针对成熟的分布式计算框架进行深入分析，将其改造后适配到本地环境；第三、参考现有框架进行轻量化实现，最大限度的掌控分布式计算框架的内核。本文采用第三种方式，基于Python语言和ICE服务中间件实现了面向军用网格的广域分布式数据处理框架，并根据典型军事应用场景设计以下仿真实验：

上级部队发现部队A、部队B、部队C都侦收到了某一目标的信息，需要将这些信息进行统一的筛选、分析以及统计处理。传统方式下，需要将所有原始数据传输到上级部队后统一进行数据分析处理；基于本文框架方式下，上级部队将编排好的分布式数据处理请求发送到各个部队的计算节点进行分布式处理，然后将中间数据反馈到上级部队进行最终汇总。其中，为模拟有限专用网络环境，将部队节点之间的传输带宽限制为2Mbps。

以3个部队节点为例，通过设置不同大小的目标数据并按照公式(1)比对传统计算方式与分布式数据处理方式的总花费时间如图4、图5所示。可以看出，在仿真场景下当待处理的目标数据大小超过200 MB以后，分布式数据处理总计算效率相对于传统计算方式平均提高了6倍。

图4 总计算时间对比

图5 总效率提升曲线

由于在仿真实验场景中模拟了广域网有限带宽的状态，通过将监视得到的网络占用时间与总计算时间相比较，得出两种方式下的通信占用时间情况如图6所示。

图6 通信占用时间比例

5 结 语

针对军用网格广域环境下的分布式数据处理问题，本文提出了通过传输计算请求来代替传输海量原始数据的核心思路，从而提高分布式计算的效率，并基于DAG模型从逻辑和物理层面设计出分布式数据处理框架内核的架构。同时，采用微服务架构解决了军用网格环境下系统复杂度高、处理请求多的具体问题；提供了抢占式优先、非抢占式优先及普通优先级等三种任务优先等级，以满足不同数据处理请求的不同优先级需求。最后，通过仿真实验对比，当待处理的目标数据大小超过200 MB以后，分布式数据处理总计算效率相对于传统计算方式有较为显著的提高。