分布式系统大数据分层调度算法

王 玮，田 兵，刘 荫，苏 琦，周 伟

（国网山东省电力公司信息通信公司，山东 济南 250001）

分布式系统大数据分层调度算法

王 玮，田 兵，刘 荫，苏 琦，周 伟

（国网山东省电力公司信息通信公司，山东 济南 250001）

互联网时代数据量激增，数据的抓取调度已成为有效采集关键信息的重点问题。提出一种分布式系统的大数据分层调度算法，该算法依据数据集的维度特征属性，利用凝聚层次聚类对数据集进行分层处理，结合小型Hadoop分布式系统实现数据集分层调度。该算法为互联网时代下大数据的快速采集调度问题提出了一种新的解决思路。

分布式系统；凝聚层次聚类；分层调度

0 引言

随着全球进入互联网时代，数据的抓取调度成为关键信息有效采集的重点问题［1-3］。与此同时，计算机受物理器件性能的限制，仅依靠CPU主频的提升并不能降低数据库的调度处理压力，使用快速有效的算法成为目前大数据挖掘的主流［4-5］。本文主要研究大数据挖掘分层调度处理算法，在抓取数据集的维度特征信息后，通过凝聚层次聚类对数据集进行分层处理，结合小型Hadoop分布式系统实现数据集分层调度，实现一种自配置的Hadoop分布式数据调度算法。

1 算法基本思想

1.1 Hadoop分布式系统

选用基于Hadoop的筛选过滤系统来实现大数据的分布式并行计算处理。Hadoop采用主从式架构，由一台Master主控节点、多个Slave节点和计算节点组成，由控制节点对数据库进行数据特征归列后分发到各个计算节点进行处理。Master节点同时还负责对Slave服务器的各种服务载荷进行调度管理和评估，以使得Slave服务器能够合理高效的分配与利用计算节点的资源［6］。其基本结构如图1所示。

图1 Hadoop主从式基本结构

1.2 凝聚层次聚类算法

层次聚类算法用于实现大数据集合的多层次归类。具体又可分为凝聚和分裂两种方案［7］。凝聚层次聚类由下而上进行操作，它先选取集合内的元素作为子簇，再将其合并，最终累积为更大的簇，这个过程持续到所有的元素都包括在一个簇内，或者运行到其他的终结条件再结束。分裂层次聚类则采用由下而上进行操作的方式，与凝聚的层次聚类相反，该算法先在集合内规划好所有的元素，再将其定义为一个一个小簇，逐步细化，这样的过程持续到集合内的子簇自成一簇，或者运行到其他的终结条件再结束［8］。选取最小距离的凝聚型层次聚类算法，算法流程如图2所示。

图2 最小距离的凝聚层次聚类算法流程

2 数据的分层调度

2.1 基于小型Hadoop集群的数据分层提取

利用层次聚类的方法进行数据分层主要用于同一数据库出现频率较高、而在其他数据库中很少出现的数据，这些数据具有很好的类别区分能力且适合用来分类［9］，可有效应用于数据信息挖掘。基于小型Hadoop集群的数据分层提取，主要工作是根据数据集的多维度特征结构对数据进行分类［10］，并从中提取出关键信息完成数据的筛选。由于数据信息的提取是实现数据分类调度工作的基础，因此在提取数据集的维度信息要求尽量做到不重不漏。与此同时，随着数据的不断存入，数据的分层会随着时间改变，离现在越久的聚类分层，变化的可能性越大，很久以前的分层对于构建层次聚类模型来说意义不大，因此需要考虑数据量分层相对时间的衰减。选用MySQL数据库存储发生时间戳与上一周期存储的秒数差与一个周期的总秒数的比值，作为一个线性衰减要素加入到算法中。

数据集调度功能的伪代码实现如下。

2.2 数据的分层调度处理

基于Hadoop的数据分层调度处理分为两个过程［11］：Map过程和Reduce过程。在Map过程之前，可将凝聚层次聚类规则作为预处理操作：即根据初始MySQL数据库提取数据集分层信息，以键值的形式保存。Map函数根据list_data加载相应的数据集维度列表，利用事先定义好的特征规则，提取其中的分层数据，并完成MySQL数据库信息的遍历，提取出来的信息以的格式输出［12］。Reduce函数主要工作是接受Map函数的输入，对输出格式进行调整并依据凝聚层次聚类匹配规则完成数据的处理与归类，最终得到结果输出文件［13］，相同键值的输入会由同一个Reduce函数处理。

数据的分层调度处理过程如下：

Step.1：加载模板文件，初始化凝聚层次聚类模板类，获取初始数据信息分层；

Step.2：根据层次聚类分配准则，对加载的初始数据信息分层进行子集提取操作，提取出的子集依次加入数据集的维度队列中，同时写入列表文件；

Step.3：从数据信息列表中取出数据子集，加载数据集内容；

Step.4：根据凝聚层次聚类匹配规则完成抽取调度，并写入输出文件；

Step.5：判断列表是否加载完成维度队列中的全部特征。如全部加载完毕，则该类分层下的数据集分层工作完成，否则继续加载下一个维度特征，重复进行第4步操作；

Step.6：若列表为空则数据的调度工作完成，否则重复进行第3步操作。

3 应用分析

选取一套MVC模式的应用系统，用于对本文提出的算法效果进行测试验证，分别在单机和分布式的环境下进行了3 h的数据调度测试。其中分布式环境选用了两台PC服务器分别作为Master节点和Slave节点组建Hadoop集群，服务器配置如表1所示，测试比较结果如表2所示。

通过对表2测试结果的分析可以看出，分布式集群中单个节点的效率同单机节点相比略低，这是由于分布式环境中存在网络带宽等瓶颈因素，同时分布式系统还需承担作业调度、系统IO等额外开销导致的。但是两个节点的总体运行效率比单机提高了约59.58%，随计算节点的增加运行效率还可进一步提高，这也是分布式计算的优势。

表1 Hadoop集群服务器硬件配置

表2 Hadoop分布式与单机的调度数据集数量比较

4 结语

设计并实现了一种分布式系统的大数据分层调度算法，算法依据数据集的维度特征属性，利用凝聚层次聚类对数据集进行分层处理，结合小型Hadoop分布式系统实现数据集分层调度。通过在MVC模式系统中对算法的实际测试验证，双节点集群的总体运行效率比单机提高了约59.58%，且随计算节点的增加运行效率还可进一步提高。

［1］贺瑶，王文庆，薛飞.基于云计算的海量数据挖掘研究［J］.计算机技术与发展，2013，23（2）：69-72.

［2］胡文瑜，孙志挥，吴英杰.数据挖掘取样方法研究［J］.计算机研究与发展，2011，48（1）：45-54.

［3］王元卓，靳小龙，程学旗.网络大数据：现状与展望［J］.计算机学报，2013，36（6）：1 125-1 138.

［4］申彦，朱玉全.CMP上基于数据集划分的K-means多核优化算法［J］.智能系统学报，2015，10（4）：607-614.

［5］张继福，李永红，秦啸，等.基于MapReduce与相关子空间的局部离群数据挖掘算法［J］.软件学报，2015，26（5）：1 079-1 095.

［6］傅巍玮，李仁发，刘钰峰，等.基于Solr的分布式实时搜索模型研究与实现［J］.电信科学，2011，27（11）：51-56.

［7］李春忠，徐宗本，乔琛.带信息反馈的凝聚层次聚类算法［J］.中国科学：信息科学，2012，42（6）：730-742.

［8］张爱琦，左万利，王英，等.基于多个领域本体的文本层次被定义聚类方法［J］.计算机科学，2010，37（3）：199-204.

［9］余长俊，张燃.云环境下基于Canopy聚类的FCM算法研究［J］.计算机科学，2014，41（z2）：316-319.

［10］李昌，陈金花.基于最大熵功率谱估计的Hadoop高速数据访问［J］.科技通报，2014，30（8）：59-61.

［11］唐珊珊，朱跃龙，朱凯.基于Map／Reduce的外壳片段立方体并行计算方法［J］.计算机工程与应用.2015，51（22）：124-129.

［12］李瑞霞，刘仁金，周先存.基于哈希表的MapReduce算法优化［J］.山东大学学报（理学版），2015，50（7）：66-70.

［13］陈吉荣，乐嘉锦.基于MapReduce的Hadoop大表导入编程模型［J］.计算机应用，2013，33（9）：2 486-2 489.

Hierarchical Scheduling A lgorithm of Large Data for Distributed System s

WANGWei，TIAN Bing，LIU Yin，SU Qi，ZHOUWei
（Information&Communication Company，State Grid Shandong Electric Power Company，Jinan 250001，China）

Capturing and scheduling of the key data from the vast information has become the focus of the information acquisition under the background of information explosion in the internet era.This paper proposes a hierarchical scheduling algorithm of big data for distributed system.Based on the dimension feature of the data sets，this algorithm realizes the processing of data sets by hierarchical clustering and the hierarchical scheduling through Hadoop distributed system.This algorithm presents a new solution to the problem of rapid acquisition and scheduling of big data in the Internetera.

Distributed Systems；agglomerative hierarchical clustering；hierarchical scheduling

TP311.1

A

1007－9904（2017）06－0045－04

2017－03－16

王 玮（1970），女，高级工程师，从事电力信息系统建设和运维工作；田 兵（1965），男，高级工程师，从事电力信息系统规划和设计工作；刘 荫（1985），男，工程师，从事电力信息系统运维工作；苏 琦（1981），男，经济师，从事电力信息系统建设工作；周 伟（1984），男，工程师，从事电力信息系统建设工作。