一种改进的多维计算资源任务分配算法研究

刘凤

摘   要：当今时代，互联网技术发展迅速，人们的社交需求日益增长，网络爬虫技术已被成熟地应用于各大搜索引擎和检索领域。文章针对分布式爬虫系统中的任务分配问题，提出了具体的爬行任务分配算法。本算法建立了多维度计算机资源模型，采用优先匹配启发式算法进行爬行任务的静态分配，通过求解目标函数，使整个系统的费用开销最小化。实验证明该算法能在满足系统需求的前提下，当系统需求确定时，使得总费用最小。

关键词：资源分配;启发式匹配;网络爬虫

當今时代，互联网快速发展，网络爬虫被应用于各个搜索引擎和检索领域[1]。随着大数据时代的到来，分布式爬虫技术被广泛应用于各个领域。分布式爬虫技术中最重要的问题就是爬取任务的分配问题，这也是传统分布式爬虫能够Spark改造的最关键问题。本团队研究的重点是怎样分割任务。通常来讲，可以根据Web、区域或域名划分，分割后将任务分配给相应的爬虫节点，基本没有根据爬行节点自身属性进行划分的分配方法[2]。本研究提出的融合了多维度计算机资源模型和优先匹配启发式任务分配的算法，能够根据计算机本身所拥有的资源（包括CPU、内存等），进行建模，最终使得花费最小[3]。

1    相关概念

任务分配指的是，当系统处于初始化时，有多个爬虫节点，并且有多个需要爬取的任务，可以将任务分配到不同的爬虫节点[4]，重点是如何合理地分配任务和选择适当的爬虫节点去执行任务，使得系统能够在确保稳定运行的同时达到高的执行效率，也就是确保系统运行的时间和系统运行的费用竟达到最小值。可见，在分配爬行任务的整个过程里，本研究要考虑很多因素，包括计算机本身的配置、费用和占用的时间。所以，在分布式爬行过程中，任务的分配问题实际上是一种组合优化，在实质上和向量装箱问题是一样的[5]。

2    算法的设计与实现

在分配爬行任务时，本研究采用优先匹配启发式算法。首先需要有一个准则，本研究的目标是选择合适的爬虫节点去完成任务，使得系统在完成任务的过程中，整体的系统花费最小。本研究设计一种新的费用模型，能够在分布式爬虫任务分配过程中保证花费最小（包括CPU、内存以及带宽）。在系统实际运行时，不同时期的花费略有不同，本算法包含3种费用：

（1）预留费用。指的是在进行爬取之前预留相应节点产生的花费[6]。

（2）使用费用。指的是系统在爬取数据时产生的费用。

（3）附加费用。指的是在系统预留的爬虫节点不能完成任务时，本研究需要分配更多的爬虫节点协助完成爬取，此时产生的新的费用。

可见，每个节点在执行任务时产生的费用是由以上3种费用共同构成的。本算法不考虑系统执行的时间长短，只关心每台计算机的CPU、内存、带宽的开销，使得花费最小即可。

本研究设计了一种优先匹配启发式爬行任务分配算法，此方法在资源分配算法的基础上进行了改进，不是从所有的节点随意选择一个或多个机器去执行任务，而是根据不同任务的规模，从正在工作的爬虫节点中优先寻找，如果正在工作的节点满足需求，则不用启用空闲节点，只有当所有的正在工作的机器均不能达到任务要求时，才启用空闲节点，从空闲节点中选择合适的节点来完成任务。改进的算法可以减小节点的占用率，提高机器的利用率，从而减少系统的开销，提高系统的负载能力，保证系统的稳健性。

该算法的部分代码如下：

（1）当系统初始化时，从所有机器中随意挑选一个节点分配任务，一般选择序列中的第一个节点。其他时候，首先从已经占用的节点中选取一个节点，分配任务后，一般选择序列中的第一个节点。

（2）判断此爬虫节点的多个资源量（CPU、内存以及带宽）能否满足当前任务的需求，如果资源足够，则选择该节点，分配任务;如果不能满足资源的要求，查找序列中下一个正在工作的节点，一直操作到寻找到满足条件的节点为止，并将任务分配给它。

（3）如果已经查遍所有正在工作的节点，并且节点的资源没有办法完成当前任务，这时在空闲的节点序列中选择一个节点，将任务分配给它。分配任务前，要检验空闲节点的资源能否满足任务需求，如果资源足够，则选择该节点，分配任务;如果不能满足资源的要求，查找序列中下一个空闲的节点，一直操作到寻找到满足条件的节点为止，并将任务分配给它。

（4）重复步骤（1—3），直到完成所有任务序列中的任务为止，也有可能空闲爬虫节点序列为空，此时只能等待。

3    实验结果与分析

通过利用Matlab软件，本研究仿真了分布式爬虫的任务分配算法，包括当系统的需求确定时，执行系统需要多少节点，需要分别使用和预留多少节点，以及这些节点数目和总的花费之间的关系。仿真试验的结果如图1所示。

假设整个系统运行的总节点数目是固定的，那么，预留的节点数目越多，预留的费用会逐渐增加，而使用费用会先上升，当达到系统要求时，则不再变化。相反，附加费用会先下降，当达到系统要求时，会下降至0。需要看的是总的费用=预留费用+使用费用+附加费用，总的费用先下降然后逐渐上升。所以，当达到系统所需的机器总数时，得到最小花费点。

如果系统没有预留工作节点，在系统执行时，所有的节点都属于附加，从图中可以看到，由于附加价格实际高于预留价格和使用价格的总和，所以总花费会变多。如果预留的节点数目少于系统实际需求的节点数目，系统附加节点的附加费用也是一笔大的花销。如果预留的节点数目大于系统实际需求的节点数目，显然系统不再需要附加费用，而是在预留费用上花费更多。

图1  固定需求下各种费用关系

综上所述，当系统需求固定时，不能预留太多节点，否则就需要支付更多的预留费用;预留节点也不能太少，否则就需要支付额外的附加费用;只有当预留节点数目等于需求节点数目时，总费用才能最小。这与现实生活一致，需要多少就留多少，这样不会有额外的费用，总花费才能达到最少。

4    结语

本算法建立了一种多维度计算机资源模型，在系统执行爬虫任务时，采用了优先匹配启发式算法，为各个节点分配任务。通过实验，对目标函数求解，求得目标函数的最小值，从而保证系统的花费最小。實验结果表明，该算法能在满足系统需求的前提下，当系统需求确定时，使得总费用最小。

[参考文献]

[1]JADIDI O，ZOLFAGHARI S，CAVALIERI S.A new normalized goal programming model for multi-objective problems： a case of supplier selection and order allocation[J].International Journal of Production Economics，2014（1）：158-165.

[2]CHOUDHARY D，SHANKAR R.A goal programming model for joint decision making of inventory lot-size， supplier selection and carrier selection[J].Computers & Industrial Engineering，2014（1）：1-9.

[3]JADIDI O，CAVALIERI S，ZOLFAGHARI S.An Improved multi-choice goal programming approach for supplier selection problems[J].Applied Mathematical Modelling，2014（14）：4213-4222.

[4]LUO J，LAN C E.Determination of weighting matrices of a linear quadratic regulator[J].Journal of Guidance Control & Dynamics，2015（6）：1462-1463.

[5]EJSMONT W.A characterization of the normal distribution by the independence of a pair of random vectors[J].Statistics & Probability Letters，2016（114）：1-5.

[6]QUN Y.Laws of the iterated logarithm for ρ-mixing random variables with normal distribution[J].应用数学学报（英文版），2016（2）：385-394.