分布式网页内容安全监测系统任务调度方法

陈 超，李柏岩，刘晓强，冯珍妮

(东华大学 计算机科学与技术学院，上海 201620)

0 引言

近年来，随着云计算技术的日益成熟，越来越越多的应用系统被以各种方式部署到云平台。云服务器一般按实际使用资源来计费，可动态扩展和缩减，为充分利用购买的计算资源，节省计算成本，需要对应用系统的任务进行合理调度，使服务器负载均衡，并对应用系统随着应用规模扩展对使用云资源的需求进行预测。

开放网络环境下的分布式系统往往采用松耦合的面向服务的（Service-Oriented Architecture，SOA）架构，将复杂应用按照功能特点划分为不同的服务，这些服务是一些粗粒度并且可以被调用的软件实体，具有高可用性、扩展性和重用性特征。这样的结构允许系统的组件按需部署。在大型系统中，随着系统业务和用户的不断增加，系统的任务数量也会增多，分布式的任务处理架构在使系统提高并发性、可扩展性、容错性的同时，也会产生因负载不均而导致的资源浪费问题。为保证系统的工作效率，最大限度地利用计算机资源，应用系统自身也需根据实际情况进行合理的任务调度。

任务调度是分布式系统的一个基本问题，而且一般形式下的任务调度是一个 NP完全问题（Non-deterministic Polynomial，NP），学者对此进行过大量的研究工作。参考文献[1]使用改进蚁群算法对Storm任务调度进行优化，并通过实验证明改进后的调度方法在算法效率上相比 Storm默认的轮询调度算法得到了大幅的提高；参考文献[2]采用随机森林分类器将任务按照执行时长进行分类，再使用粒子群优化算法对问题进行优化，不仅均衡了计算节点的CPU和内存的利用率，还对任务完成时间进行了优化，减少了任务完成的总体时间；参考文献[3]针对定时任务在未来一段时间内产生的负载，提出了静态调度的可行性，并基于遗传算法设计了一种适用于定时任务的负载均衡算法；参考文献[4]针对蚁群算法在进行任务调度时，存在收敛速度慢，局部搜索能力差以及容易陷入局部最优等问题，结合了模拟退火算法，利用模拟退火算法较强的局部搜索能力，实现一种能有效减少任务完成时间以及保证资源负载均衡的任务调度算法；参考文献[5]先用模糊 C均值聚类将任务分类，再用min-min算法进行任务调度，减少了任务完成时间；参考文献[6]采用粒子群优化算法结合遗传算法，实现了粒子群优化算法对离散问题的求解能力，并通过离散改进后的粒子群算法求解模糊柔性作业车间的多目标调度，在保留调度算法多样性的同时，降低了算法后期陷入局部最优解的概率。

本文研究一个分布式网页内容安全监测系统的任务调度优化问题，针对系统任务完成时间的实时性约束，提出了一种改进粒子群优化算法并结合遗传算法解决了系统任务调度优化问题，并通过实验证实所提出的调度策略有较好的负载均衡度及较短的优化完成时间。

1 网页内容安全监测系统的任务调度问题

网页内容安全监测系统是一个部署在云平台上，为目标网站群提供实时安全监测服务的分布式应用系统。它定时扫描目标客户网站，对网站中所有网页进行分析，检测网页是否可用，是否被篡改，以及是否出现违规词、敏感词、敏感图片等，并对网站出现的异常情况进行预警提示[7]。系统的监测分析任务如图1所示，主要包括网站存活监测、网站爬虫、网站解析、网页变更监测、违规词监测、违规图片监测、敏感信息监测以及预警处理等。除了爬虫任务要稍微提前外，系统中的每项任务基本上互不影响，独立工作。

图1 网页内容安全监测系统任务调度示意图Fig.1 Schematic diagram of task scheduling of web content security monitoring system

网页内容安全监测系统的几乎所有的监测任务都是定时触发的，任务的启动频率由客户自行选择。由于客户较多，而且每个客户一般有多个网站需要监测，因此系统同时监测的目标网站数量很大，网页数量十分庞大。随着监测网站数量的增加，系统并发运行的任务数会急剧增长。为了能够在第一时间发现网站的问题，及时进行处理，监测系统必须在限定时间内完成每个网站的监测任务，对发现的问题及时进行报告。因此，对系统进行合理的任务调度，不同的任务负载均衡地分配到现有的服务器，保障现有资源能够被充分利用。

2 监测系统的任务调度解决方案

2.1 监测任务整合

由于监测系统的核心任务都是周期性定时触发的，在运行环境和监测目标不变的情况下，产生的任务数量与执行时间基本稳定。为减少开销，本文采用静态调度策略对系统中的任务进行调度。为了掌握任务的基本信息，本文首先对各种任务的资源占用情况进行了多次测量，并计算出各任务平均用时，如表1所示。其中，违规词监测、违规词监测、敏感词监测、网站爬虫以及网页变更监测是针对网站所有页面，故处理时间为处理每个页面所需的平均时间，网站存活检测和网站信息获取只针对主页。测量在多个相同参数配置的租用服务器上进行，得到相近的结果。

表1 任务平均资源消耗表Tab.1 Task average resource consumption table

对于监测系统中的每个目标网站，系统每次检测都会产生7个任务（见表1）。由于要监测网站数量庞大，每日要监测多次，所以产生的任务数量十分巨大，调度算法进行优化时所需的计算量也会很大。为此，本文将一段时间内的同一种类任务合并，不但能简化调度的难度，还能减少调度的次数。这里之所以能进行“归并”是因为同一种任务即便针对不同网站，其所需的计算资源也大致相同，归并之后可以将它们看成一个任务在时间上的拉长。

对每类业务做“归并”，将同类任务按时间段分段归并，称为“归并任务”，记为 Task。第 j个归并任务taskj用向量表示为：

2.2 监测任务调度

2.2.1 监测任务调度定义

任务调度就是将系统任务集里的任务以某种策略合理地分配到各分布式计算节点上进行处理，并以任务资源利用率、可靠性和负载均衡等指标作为调度目标[8]。本调度问题有以下具体约束：

①每台服务器所有并发Task所需 CPU资源总和不大于服务器CPU资源上限。

②每台服务器所有并Task所需内存资源总和不大于服务器内存资源上限。

③每台服务器所有Task完成时间不大于Φ。

对于系统中的m个Task，其调度向量可表示为：

D=[s1,s2,…,sm]

其中sj(j=1,2,…,m)为服务器编号。如D=[1，3，1，2]表示为task1分配给服务器1，task2分配给服务器 3，task3分配给服务器 1，task4分配给服务器 2。有了任务调度向量，下面定义评价指标，建立调度优劣的评价标准。

定义2.n台服务器机组的平均资源利用率：

定义3.服务器机组的负载均衡度：

当 LD越大时，服务器机组的负载均衡度越高，调度策略越优秀。

2.2.2 监测任务调度算法

粒子群优化算法（Particle Swarm Optimization，PSO）是一种优化计算的技术[9-11]，它通过模拟鸟群合作寻找食物的过程，快速地搜索最优解，常用来优化调度策略。PSO算法参数简单、收敛速度快。算法随机生成初始化粒子群，粒子有两个属性：速度和位置，每个粒子代表了一种解的可能并对应一个适应值。在搜寻过程中每个粒子有着个体最优化位置，粒子群有全局最优位置，每个粒子根据个体最优位置和全局最优位置更新自己的速度和位置。其更新公式如下：

由式（4）及（5）可知PSO算法可用于求解连续优化问题，而本文调度问题明显是一离散优化问题，需对算法进行离散化改进，使其能够解决离散型问题。

本文的调度算法是为求解调度向量 D，由于广义的PSO算法并不合适解决离散问题，故将遗传（Genetic Algorithm，GA）算法中的交叉和变异操作引入PSO算法来重构其速度和位置的更新算法[12-14]，不但能解决不适合应用于离散优化的问题，同时利用GA算法提高了算法迭代到后期的多样性[15]。改进离散PSO算法如下所示：

离散PSO算法更新过程如下：

输入：迭代次数G，参数c1,c2，粒子群数N

输出：全部迭代完成后的全局最优位置gg

2.3 算法步骤

本文任务调度算法的具体步骤如下：

①进行任务“归并”，得到任务集合。

②设置PSO算法所需参数：迭代次数G，参数c1,c2，粒子群个数N，服务器数量（即PSO算法位置边界）。

③初始化N个粒子位置xi，粒子速度v，计算每个粒子对应的适应值，更新个体历史最优位置以及全局最优位置。

④根据粒子群更新算法更新每个粒子的位置与速度，重新计算每个粒子对应的适应值，更新个体历史最优位置以及全局最优位置。

⑤达到最大迭代次数，返回全局最优位置，否则回到步骤④。

⑥对得到的最优位置进行评价，符合约束，输出调度策略，否则，服务器数量+1，返回步骤③。

3 实验与分析

3.1 任务调度算法实验

本文通过开源仿真平台Cloudsim进行仿真实验，对比了 GA算法以及蚁群（Ant Colony Optimization，ACO）算法，就任务调度算法完成时间，调度策略的负载均衡度两方面，分析了三种任务调度算法的优劣。PSO-GA算法、GA算法、ACO算法的相关参数设置分别如表2、表3以及表4所示。

表2 PSO-GA 相关参数Tab.2 PSO-GA related parameters

表3 GA 相关参数Tab.3 GA related parameters

表4 ACO 相关参数Tab.4 ACO related parameters

实验中设定的任务数从20个逐渐递增到160个，每种情况实验20次，取测试结果的平均值。基于PSO-GA算法，GA算法以及ACO算法对任务调度优化完成所需时间以及任务调度负载均衡度分别如图2，图3所示。

图2 任务调度所需时间Fig.2 Time required for task scheduling

图3 任务调度负载均衡度Fig.3 Task scheduling load balance

从图2可知，三种算法中，GA算法所需计算时间最多，本文算法和 ACO算法则相差不多，GA算法所需时间远超其他两者因在实现时，该算法有对基因DNA有编码和解码过程，增加了计算量。三种算法所需时间大体与任务数量成正比。

从图3可知，随着任务数从20个逐步增加到160个，三种算法的负载均衡度波动最大不超过0.15，其中ACO算法结果最不理想，而本文离散改进的PSO算法最优，最大波动仅为0.02。在有限的迭代次数中，本文提出算法相较于其他两种算法有着更为优秀的收敛速度以及寻优能力。

3.2 服务器需求分析

本文网页内容安全监测系统的业务针对的是用户指定的某个网站，然而不同的网站所包含的网页数量各不相同，系统运行时需对每个页面进行监测，这也导致了同样的业务对不同网站所消耗的计算资源截然不同。对国内三十余所211高校的主站进行3层爬取所获取的网页数量进行统计，将数据进行ks检验，计算出其D值为0.16，P值为 0.33，故而可知高校网站的网页数量服从均值131.59，标准差44.21的正态分布。结合表1的任务平均资源消耗表和本文提出的算法，根据正态分布规律模拟出网站情况。观察在网站数不断增加时，所需服务器数量的变化，记录每次服务器增加时网站数量的临界点。网站数量与所需服务器的关系如下图4所示。从图中可知，本网页内容安全监测系统，大约每增加495个监测网站，就需增加一台服务器以满足系统监测的实时性要求。

图4 监测网站数与服务器数关系图Fig.4 The relationship between the number of monitored websites and the number of servers

4 总结

本文为了使大规模分布式网页内容安全监测系统能够充分利用现有资源，高效稳定地运行，提出了一种可行调度方案，即采用粒子群优化算法结合遗传算法，在综合考虑系统负载均衡和任务完成时间的实时性约束后进行系统任务调度优化。通过实验对比了传统的遗传算法以及蚁群算法，实验表明改进的粒子群优化算法的执行时间短，调度方案负载均衡度更高。本文的任务调度策略现已应用到系统当中，并在实际工作中取得了良好的效果，但本方案尚有不足之处有待改进：其任务调度对象针对的是系统的定时任务，而实际情况中系统还有一些非定时任务，最后得到的调度策略只是近似最优解。