PBS：一种面向集群环境的ETL调度算法∗

韩文彪 李晖 陈梅 戴震宇

算法与分析

PBS：一种面向集群环境的ETL调度算法∗

韩文彪 李晖 陈梅 戴震宇

（贵州大学先进计算与医疗信息服务工程实验室贵阳550025）

论文设计并实现了一个集群式ETL（Extract-Transform-Load）任务处理平台，该平台支持异构数据源的多源数据集，提出了基于预测时间调度算法。该算法对任务进行调度优化，以提高数据抽取、转换和加载等任务的执行效率。基于实际应用的实验结果证明，集群式ETL任务调度技术对于减少多个ETL任务并行执行的总时间，提升ETL任务的执行效率具有良好的效果。

ETL；调度系统；异构数据源

Class NumberTP301.6

1 引言

随着信息化的快速发展，不少企业都积累了大量的数据［1～2］。“洞察”数据，分析数据背后的“内涵”能够有效帮助企业在激烈的市场竞争环境中占据优势，因而企业对数据的价值也愈发敏感和重视。在数据的分析利用过程中，摆在企业面前的第一个难点是数据的抽取、转换和对加工后的数据进行装载集成。目前，很多具有一定信息化程度的企业，是从企业内部的多个业务系统数据库中抽取、转换和加载（Extract Transform Load，ETL）数据，以供后续的分析处理环节使用。当企业积累了海量的数据时，数据抽取所耗费的时间将非常长，进而影响到数据的分析效率，最终影响企业决策对市场的反应速度。

目前，市面上具有不少的ETL产品，既有开源也有商业的ETL产品。但普遍采用的是集中式架构，集中式架构往往只涉及相对较少的数据源的抽取，抽取过程简单，所需要的ETL处理器的数量也相对较少，因此不会涉及多处理器任务分配问题［3］。集中式ETL技术多侧重于对工作流的优化，例如，Alkis Simitsis［4］等提出的利用状态空间算法优化ETL工作流程理论、韩京宇［5］等提出的基于ETL“主表衍生”模式的流水线优化方案等理论。随着ETL任务数量和数据规模的不断增加，传统的集中式架构越来越难以满足快速采集和抽取海量数据的需求。

针对上述问题，本文设计并实现了基于集群环境的ETL处理平台。为了将ETL任务合理地分配到各个节点来减少总任务的执行时间，本文设计基于预测时间调度算法（Task Scheduling Based on the Predicting time，PBS），面向总体执行时间对任务执行序列进行调度优化。通过实验验证该调度方法的有效性。

本文的主要工作如下：

1）面向集群环境设计并实现了ETL任务处理平台；

2）通过历史数据建立线性回归模型预测下一次ETL任务的执行时间；

3）设计并实现基于任务预测执行调度算法PBS，对任务队列中的ETL任务进行调度。

2 ETL集群架构及关键技术

本文设计的集群式ETL任务处理平台主要包括一个主节点和多个子工作节点。主节点接收提交的ETL任务并进行任务调度分配到各个子工作节点，监控各个子节点中的任务执行状态反馈给用户；子工作节点执行从主节点接收到ETL任务，从不同的数据源中开始抽取数据并传输到平台中，在平台中经过清洗、转换后传输并装载到数据仓库。本文设计的集群式ETL任务处理平台的框架示意图如图1所示。

图1 集群式ETL系统框架

2.1数据抽取

数据抽取一般有两种方式：全量抽取、增量抽取。全量抽取类似于数据迁移或数据复制，它将数据源中的数据原封不动地从数据库中抽取出来加载到数据仓库中；而增量抽取只抽取自上次抽取以来数据库中要抽取的表中新增或修改的数据［6］。在建立数据仓库前期一般采用全量抽取方式将来自不同业务系统的数据库中的数据抽取至数据仓库。全量抽取完成后，采用增量抽取方式抽取每天产生或变化的数据。增量抽取捕获变化数据主要有触发器、时间戳、全表对比、日志表等方式［7］。此外，企业的多个业务系统采用的数据库可能来自不同厂商，这需要将这多个数据库集成起来，以满足能从不同数据库中抽取数据的需求。因此，数据集成主要面临数据源异构问题，所以在设计ETL处理平台时要考虑数据源的通用性和扩展性，本文在实现ETL处理平台中尽可能地支持常用的关系型数据库和数据文件。

2.2数据转换

企业在构建数据仓库的过程中需要建立元数据，所谓元数据是指管理数据的数据，具有解释数据意思的目的［8］。当前，拥有多个内部数据库的企业其数据大都没有统一的规范，例如在医疗数据中，医院对药品“青霉素”有“注射用青霉素钠”、“青霉素粉针”等各种命名，规格项也有80U、0.48g等不同表述［9］。数据没有统一的规范，以至于企业无从汇总数据。在企业建立了元数据之后，需要对业务系统中的数据抽取，并将其转换成标准的规划化数据。数据转换就是用来解决如何将非规范化的数据转换成规范化的数据的问题［10］。

2.3数据加载

本文使用分布式数据库Greenplum构建数据仓库。Greenplum Database是一个大规模的并行数据库，支持下一代数据仓库并且可以进行大规模的数据分析，可以对数据自动分区和并行查询［11］。在数据加载时使用批量加载工具（GPload）和命名管道技术来将处理后的规范数据加载到数据仓库中。GPload是对外部表的一层封装，对数据进行并行加载［11］。GPload和命名管道的结合，可以实现无落地文件的并行加载，即可以提高海对量数据的加载效率，也避免了使用传统落地文件方式加载的过大存储开销。

元数据库主要用来存储用户提交的ETL任务各种描述性信息，主节点从元数据库中获取所有的任务并对任务进行排序分配到各个子节点上执行，将数据集成到数据仓库中来支持决策分析。

3 任务调度系统的设计

任务调度问题是一个NP（non-deterministic polynomial）完全问题［12］，其致力于在mn个任务调度的解空间中寻找近似最优解，使得总任务的执行时间最小。本文在设计ETL任务调度的工作主要包括基于数据量预测每次ETL任务执行时间、基于预测时间的调度策略（PBS）对任务进行调度两部分。

在企业数据的集成中采用增量抽取方式，每次

1）假如有m个ETL任务，ETL任务之间没有相互依赖且ETL任务并行时不会影响单个ETL任务的执行时间，每个ETL任务不可以再次划分，定义ETL任务集合E={E1,…,Ei,…,Em}；

2）定义ETL任务数据量集合V= {V1,…,Vi,…,Vm}，Vi表示第i个任务的此次处理的数据量；

3）定义集合F={F1,…,Fi,…,Fm}，Fi表示第i个ETL任务对应的线性回归方程；

4）定义有n个子节点参与ETL任务调度，任何一个任务在不同节点上的执行时间相同；在同一个时间段内，每一个节点只能执行一个ETL任务；

5）定义每个子节点上任务队列执行总时间Tj(1≤j≤n)等于在该节点队列中所有任务的执行时间的总和；

6）所有节点可以并行执行，所以总任务的整体执行时间T等于max(Tj)。

目标：

将整体任务执行时间T最小化的问题转化为如何将任务分配到不同的节点上，求出max(Tj)最小。

任务调度问题求解：

当m≤n时，考虑任务分配问题，只要将m个任务并行执行。总任务执行时间T=max(Tj)；

当m＞n时，选取PBS算法对ETL任务进行调度，具体步骤如下：

步骤1：初始化时间数组T：初始化n个节点上现有任务执行总时间Tj(1≤j≤n)为零；

步骤2：计算任务执行时间：选取任务队列中ETL任务集成的数据可能是当天、某几天或者当前一周的数据，而且ETL任务设计完成后一般不会改变，在整个ETL任务执行时，唯一变化只有每次处理的数据量。本文基于式（1）通过每次处理的数据量来预测当前任务的执行时间，并且采用普通最小二乘法来估算不同ETL任务的系数β,ε。

在企业进行数据集成时，获取每个ETL任务每次所要抽取的数据量，通过数据量预测任务此次执行时间。由于各个子节点的资源限制，限制每个节点的任务并行度。任务执行时，不同ETL任务之间没有依赖性并且ETL任务并行时不会影响ETL任务单独执行时间。如何对ETL任务进行调度，可以将总任务执行时间最小。

在本文工作中，对ETL任务的建模如下：的任务Ei，并选取对应的线性方程Fi，计算出任务Ei的执行时间ti(1≤i≤m)；

步骤3：任务分配：从尚未分配的任务队列中选取执行时间最大的任务Ei，并选取min(Tj)的节点，将任务分配到第j个节点上；

步骤4：从任务队列中删除任务Ei；

步骤5：重复步骤3、4，直到任务队列为空。

PBS算法描述如图2。

图2 PBS算法流程图

可以看出在每次提交任务队列后，通过各自任务的任务量V来计算出各自任务执行时间t；在任务分配时，获取任务队列中所需执行时间最大的任务，将该任务分配到当前所有节点上总执行最小的节点上，然后将该任务从任务队列中删除。

4 实验结果与分析

4.1实验环境

在本文实验环境中每个节点都采用64位操作系统CentOS-6.4，内核版本为3.10.0。数据仓库使用4.3.9.1版本的Greenplum数据库搭建四个节点的集群，管理节点Master内存为10Gb，磁盘为50Gb，三个Segment节点，每个Segment配置两个Segment Instance，内存为8Gb，磁盘为100Gb。集群式ETL采用一个Master节点和三个Worker节点，Master节点内存为10Gb，硬盘为50Gb，Worler节点内存为16Gb，硬盘为50Gb。元数据库采用关系型数据库Mysql，内存为10Gb，硬盘大小为100Gb。

本文的实验数据来源于贵州省1600余家医院的真实医疗数据，实验中选取了HIS系统中的门诊处方表、门诊费用表、患者信息表、区域表和时间表共10G医疗数据。基于门诊费用数据、门诊处方数据和患者信息数据设计了5组不同的ETL任务，任务详细信息如表1所示。

表1 ETL任务详细说明

4.2实验分析

4.2.1 任务执行时间预测

本实验主要是为了验证和分析ETL任务预测时间的准确性。本文调度策略是基于ETL任务预测时间进行任务调度，保证了任务预测时间的准确性，可以提高任务执行的效率。在本实验中，选取了表1中的5个ETL任务和不同规模数据集中进行了测试，得到的实验结果如图3所示。

图3 任务实际时间和预测时间

由图3可知，通过每次ETL任务处理的数据量来进行ETL任务的预测执行时间和任务的实际执行时间基本相同。由于ETL2任务是门诊处方表与时间表进行Join连接，而ETL1任务是在ETL2基础上再与区域表在做一次Join连接，所以ETL1的执行时间在相同数据量下是大于ETL2任务的执行时间。同理，ETL3是对门诊费用表全字段进行集成，而ETL4任务是对门诊费用表一半字段进行抽取，所以ETL3的执行时间在相同数据量下是大于ETL4任务的执行时间。

4.2.2 任务执行序列调度

本实验主要是为了测试调度算法的性能。在本实验中，选取表1中的5种不同类型的ETL任务，每个ETL任务处理10种不同规模的数据集（50万行，100万行，…，500万行），共计50个ETL任务，组成了任务集C（E1，E2，…，E50）。在测试过程中，我们每次从集合C中随机选取10个不同的任务，如此重复10次，可以得到10个任务集（C1，C2，…，C10）。本文选取的对比算法是先来先服务算法（FCFS），并在本文搭建的集群式ETL任务处理平台上加以验证，实验结果如图4所示。

图4 两种算法下执行效率

在实验中通过选取不同的任务集，来衡量PBS和FCFS两种算法下任务的执行效率。由实验结果图4可知，本文提出的PBS算法在10组不同的ETL任务队列中的总执行时间均小于FCFS算法下的ETL任务的总执行时间。因为PBS算法选取下一个任务时都会做出当前最好的选择，保证当前所有任务的执行时间最小，从而保证整体任务的总执行时间可以在一定程度上减小。

5 结语

为了提高ETL任务的执行效率，本文实现了一个面向集群环境的多源异构数据ETL任务处理平台，并在任务执行时间和任务的并发数的约束条件下，设计了基于任务执行时间预测的面向执行时间最小化进行优化的调度算法PBS。实验证明，所有的ETL任务队列的总体执行时间均有不同程度的缩减，达到了预期目的，并已经在贵州省基层医疗信息管理平台中得以应用。目前，PBS算法虽然有效减少了总任务的执行时间，但并没有特别考虑到单个任务的等待时间，在某些场景下，有可能导致某个任务的等待时间过长。在后续的工作中，将会针对此问题进一步优化PBS技术，以更好地满足实际应用需求。

［1］徐立新.基于异构数据资源整合的方法和系统实现［J］.计算机技术与发展，2014（12）：173-179.

XU Lixin.Method and System Implementation Based on Heterogeneous Data Resources Integration［J］.Computer Technology and Development，2014（12）：173-179.

［2］王学松，郭强.医疗数据分析及数据挖掘方法的应用［J］.电子技术与软件工程，2014（2）：218-219.

WANG Xunsong，GUO Qiang.The Application of Data An⁃alysing and Mining in Medical Field［J］.Electronic Tech⁃nology&Software Engineering，2014（2）：218-219.

［3］王春阳，赵书良，王长宾.粒子群算法在分布式ETL任务调度中的应用［J］.计算机工程与应用，2013，49（9）：150-155.

WANG Chunyang，ZHAO Shuliang，WANG Changbin.Ap⁃plication for particle swarm algorithm in distributed ETL job scheduling［J］.Computer Engineering and Applica⁃tions，2013，49（9）：150-155.

［4］Simitsis A，Vassiliadis P，Sellis T.Optimizing ETL pro⁃cesses in data warehouses［C］//21stInternational Confer⁃ence on Data Engineering（ICDE'05）.IEEE，2005：564-575.

［5］韩京宇，徐立臻，董逸生.ETL执行的流水线优化［J］.小型微型计算机系统，2005，26（6）：1013-1017.

HAN Jingyu，XU Lizhen，DONG Yisheng.Optimization of ETL Execution by Pipelining Method［J］.Journal of Chi⁃nese Mini-Micro Computer Systems，2005，26（6）：1013-1017.

［6］梁尚锟.基于流水线工作的ETL工具设计与实现［D］.长春：吉林大学，2014.

LIANG Shangkun.Design and Implementation of ETL tools based on assembly line work［D］.Changchun：Jilin University，2014.

［7］施霖，杨爱民.一种基于时间戳和日志的增量数据捕获和抽取方法［P］.CN，CN 102915336 A，2013.

SHI Lin，YANG Aimin.Incremental Data Capture and Ex⁃traction Method Based on Timestamp and Log［P］.CN，CN 102915336 A，2013.

［8］陈进.关于数据仓库元数据管理系统的研究与建立［D］.青岛：中国海洋大学，2011.

CHENG Jin.Research and Application of the Metadata management system in the Data Warehouse［D］.Qingdao：Ocean University of China，2011.

［9］姚华彦，徐俊，何萍.加强区域医疗信息平台标准代码的管理［J］.中国数字医学，2015，10（1）：10-12.

YAO Huayan，XU Jun，HE Ping.Reinforce Management of Standard Code of the Regional Healthcare Information Platform［J］.China Digital Medicine，2015，10（1）：10-12.

［10］Kakish K，Kraft T A.ETL evolution for real-time data；warehousing［C］//Proceedings of the Conference on Infor⁃mationSystemsAppliedResearchISSN.2012，2167-1508.

［11］Gollapudi S.Getting Started with Greenplum for Big Data Analytics［M］.Packt Publishing Ltd，2013.

［12］林建昌.电力行业分布式ETL数据集成系统研究与实现［D］.成都：电子科技大学，2015.

LIN Jianchang.Research And Implementation Of Distrib⁃uted EtlData Integration System In Electric Power Indus⁃try［D］.Chengdu：University of Electronic Science and Technology of China，2015.

PBS：An ETL Scheduling Algorithm for Cluster Environment

HAN WenbiaoLI HuiCHEN MeiDAI Zhenyu
（Guizhou Engineering Lab for ACMIS，Guizhou University，Guiyang550025）

This paper designs and realizes a clustered ETL（Extract-Transform-Load）task processing platform.The platform supports multi-source data integration of heterogeneous data sources，and proposes the scheduling algorithm based on the predicat⁃ing time.The algorithm realizes task scheduling optimization，which mainly improving the execution efficiency of data extracting，transforming and loading etc.Based on the experimental results of actual applications，it is known that the cluster ETL task schedul⁃ing technology has a great effect for reducing the multiple ETL task parallel execution time and improving ETL task execution effi⁃ciency.

ETL，scheduling system，heterogeneous data sources

TP301.6

10.3969/j.issn.1672-9722.2017.05.001

2016年11月12日，

2016年12月20日

国家自然科学基金（编号：61462012，61562010，U1531246）资助。

韩文彪，男，硕士研究生，研究方向：大数据管理与分析。李晖，男，副教授，硕士生导师，研究方向：大规模数据管理与分析，高性能数据库，云计算。陈梅，女，教授，硕士生导师，研究方向：数据库新技术、计算机应用技术。

戴震宇，男，实验师，研究方向：数据库新技术、计算机应用技术。