《基于聚类的动态负载均衡在数据采集上的应用.doc》由会员分享，可在线阅读，更多相关《基于聚类的动态负载均衡在数据采集上的应用.doc（6页珍藏版）》请在金锄头文库上搜索。
1、 基于聚类的动态负载均衡在数据采集上的应用摘要：为了构建一个基于微博的社会网络，需要提供大量的微博数据源，那么如何才能实时高效的获取微博信息是构建微博社会网络面临的重大挑战。本文提出了一种基于聚类的动态负载均衡数据采集方法，将聚类算法与动态负载均衡结合是一次新的尝试，测试表明，能够满足对微博数据采集的需求。关键词：微博；聚类；负载均衡；一致hash算法application of clustering-based dynamic load balancing in the data collectionliu dezhi(faculty of computer,guangdong univer
2、sity of technology,guangzhou510006,china)abstract:to build social networks based on microblog,we need to provide large microblogging data source,however how to efficient access to the microblogging information is to build social networks of the major challenges facing.this paper presents dynamic loa
3、d balancing method of data collection based on clustering,combined with clustering and dynamic load balancing is a new attempt,the tests show that it can meet the demand for microblogging data collection.keywords:microblog;clustering;load balance;consistency hash algorithm一、引言随着web2.0技术的快速发展，微博的出现,使
4、人们进入了网络全民媒体的生活方式1。面对大规模规模的数据，如何将任务均衡的分布在每台爬虫机上，是一个具有挑战性的问题。本文提出基于聚类的动态负载均衡的方法，将负载率过高的处理机进行任务转移，达到动态负载均衡的目的。二、动态负载均衡模型采集系统的逻辑架构结构如图1所示，任务管理节点将任务分配到任务数据节点上，然后由管理节点将任务结果的相关信息通知客户端，客户端再从相应的任务节点中提取结果。图1 系统结构图（一）处理机聚类将处理机的权重定义为一组向量，公式如下：其中：l(c)_m为cpu利用率的阀值，l(m) _m为内存利用率的阀值，l(d) _m为磁盘i/o量的阀值，l(p) _m为运行态进程数
5、量的阀值。根据权值向量，将具有同类性能的处理机划分为同一个类别。结合本系统的特点，采用启发式聚类算法比较适合。（二）动态反馈调整处理机的负载率r(i)定义如下：其中l(ci)、l(mi)、l(di)、l(pi)分别为处理机i当前cpu的利用率，内存的利用率，磁盘i/o量，运行态进程数量。在该系统中采用一种局部优先的原则，即优先对类的内部处理机进行动态负载调整。三、算法描述（一）聚类算法处理机聚类采用经典的k-means5算法，分成k个类别，并将类别信息保存在任务管理节点上。为了方便算法描述，进行如下定义：定义 1（处理机之间的距离）设处理机中集合中的pi和pj的权重分别为w(pi)和w(pj)
6、，则pi和pj的距离为定义 2（处理机到类的距离）设处理机类为c，聚类的中心点为pi，pic则设备pj到类c的距离等于pj到pi的距离。得到类别集合后，将任务按照w(cj)的比例分配到各个类别中，类内部采用一致hash布局机制。（二）负载调整对于每个类dm的处理机而言，每隔时间t动态获取负载信息，设h为负载率最高的处理机，l为负载率最低的处理机。设处理节点的虚拟机节点为vp1 , ,vpm，ravg 为类中处理机所有虚节点的平均负载率。具体的伪代码如下：(1) while(rh - rl r_in)(2) sort(vh,vl);/将虚节点按照负载率的大小进行降序排序(3) num=min(r
7、avg rz), (rh ravg);/需要转移的数量(4) num=0;(5) while(num rl)(6)int_transmit(vhi , vlj);/类内部负载转移(7) i+，j-;(8) num+= vhi ;(9)r_update(h,l);/将h和l的负载率更新(10) end while(11) r_update(dm);/将dm类中的负载率更新(12)if(ravgr_out)then/启动类间负载转移算法。(13)out_transmit(h);/ 类间负载转移。(14)endif(15)getr _max_min(d,h,l);/更新h、l(16)end whil
8、e该算法采用由内向外的负载调整策略，在内部通过反复执行int_transmit(vhi , vlj)函数同时更新h和l，将负载率之差缩小在r_in的范围内。如果dm中负载率的平均值超过r_out，将执行out_transmit(h)函数，将警告信号发送给任务管理节点，h的负载转移去向由managenode决定，通过类间负载转移后，可以使得(rh - rl)的值维持在r_in内。（三）类内任务迁移当增加处理机时，首先与每个类d的中心点c进行距离比较，找到最近距离的类别，找到类别之后，采用一致hash原则。删除旧的处理机比较简单，不在描述。四、实验与结果分析利用20台dell r510服务器虚拟出
9、100台不同性能的处理机。在开始进行实验时需要设置参数，配置参数如表1所示。表1配置参数从实验的结果来看，没有出现那台处理机的负载率过高或者过低。然而该模型的稳定性比较依赖初始参数值，由对比图2可以看出，反馈时间间隔和聚类个数k的大小对系统的负载性能都会比较大的影响。图2不同参数的负载性能对比测试五、结束语本文提出一种大规模的面向微博数据的采集模型，结合传统的一致hash数据布局机制，引进k-means聚类算法，并同时对所有处理节点进行动态负载调整，从实验结果数据来看，能达到实时负载平衡。但该模型仍然存在一定的缺陷，聚类个数k以及反馈时间间隔的设定，对系统负载平衡效果有比较大的影响，如何寻找最
10、佳的参数值是下一步研究的重点。参考文献：1smith b g. socially distributing public relations：twitter，haiti，and interactivity in social mediaj.public relations review，2010，36(4)：329-3352karger d,lehman e,leighton t,levine m, lewin d. consistent hashing and random trees: distributed caching protocols for relieving hot spot
11、s on the world wide web.in:proc.of the 29th annual acm symp. on theory of computing (stoc97).el paso:acm press,1997,654-6633邓成玉,章剑涛,刘永山.动态负载均衡策略及相关模型研究j.计算机工程与应用,2011,47(8):131-134.4贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述j.计算机应用研究，2007,24(1):10-145jain a k,dubes r c. algorithms for clustering datam.englewood cliffs,new jersey:prentice hall,1998
