您的位置:首页>>千赢国际娱乐app

千赢智能运维 | 百度云海量日志处理——任务调度实践与优化

发布时间:2018-06-25 15:33:58  千赢:千赢国际   编辑:贺飞  背景:

  处理大规模日志计算任务是运维团队经常遇到的问题。为保证任务分配均匀性和稳定性,百度云智能运维架构团队对原始一致性哈希算法进行改进。新算法在保持原始一致性哈希算法稳定性的同时,通过设置不均衡因子来控制分配的不均匀范围,达到负载分配均匀性与稳定性有效兼容。

  业务场景

  分布式系统在应用中经常会面对如下业务场景:

  计算系统每分钟有大量的定时任务需要及时调度并按时完成,单机在处理能力和时效性上都无法满足要求,需要将任务分配到大量Work节点上进行并行计算,如何均匀分配这些任务,并且在任务增减,Work节点退出/加入(伸缩能力)时保持任务分配的稳定性(不会引起大量任务迁移)。

  分布式存储系统,海量数据被分片存储,那么如何让每个Data节点上分片更加均匀,并且在Data节点退出/加入时保持数据分片的稳定性。

  高并发Web系统中,架构上几乎都是一个或多个反向代理服务器(如Nginx)来做七层负载均衡,后端使用应用服务器集群(如Tomcat)提供服务,这种架构具备水平伸缩能力,那么反向代理如何均匀分配请求,并且尽量保证请求Session粘性。

  问题分析

  上述问题可以抽象为对分配算法如下几个方面的要求:

  公平性:即算法的结果要尽可能地公平,不能造成分配不均问题,这点在分布式系统中尤其重要,公平性就是要尽可能避免由于负载过重/过轻导致系统出现慢节点/饥饿节点影响系统整体性能和资源利用率。

  稳定性:分布式系统中,集群节点维护、故障、宕机、重启、扩缩容是非常常见的,稳定性就是要保证计算任务、数据、请求在节点加入/退出时尽可能保持稳定,不引起大量计算任务重分配、数据迁移、请求转移,这对系统整体可靠性、稳定性、高性能至关重要。

  可行性:算法在工程实践上一定是可行的,具体体现在这两个方面:时间复杂度、空间复杂度,时间复杂度要求一定要快,满足业务场景对响应时间的要求,空间复杂度要求占用资源少,满足业务在资源投入和收益上的平衡。

  常见算法

  面对这些问题有很多常见的处理方法,例如轮询(Round-Robin)、取模哈希、一致性哈希、按ID范围分段、自定义分段策略,下面我们选择几种常见分配算法,分析它们在公平性,稳定性及可用性方面的能力:

  从上面表格对比可知这几种常见算法都无法兼具三种特性,那么有没有一个算法,能同时具备公平性、稳定性以及可行性?接下来介绍的这个算法能在保持原始一致性哈希稳定性的同时还具备可控的均匀性,已经实际应用于我们的分布式近线计算系统中用于分配定时计算任务,目前来看效果还不错。

  有界负载一致性哈希

  有界负载一致性哈希(Bounded-Load Consistent Hash)算法是对原始一致性哈希算法的改进,相对于原始一致性哈希算法的不均匀问题,新算法能通过设置一个不均衡因子,来控制整个分配的不均衡范围。

  算法描述

  1. 假设计算节点数为n,任务数为m,则每个计算节点的平均任务数t=⌈m/n⌉(取上界是为了保证t*n >= m,保证所有任务都能被分配执行)。

  2. 设置不均衡因子c(取值范围为1 < c < ∞)用于控制最大不均匀范围,则每个节点分配的最大任务数为c*t。

  3. 使用一致性哈希算法为任务寻找计算节点,当所选节点已有任务数大于tc时,顺序寻找下一个已有任务数不大于tc的节点,直到找到并将任务分配给该节点。

  4. 重复步骤3直到所有任务分配完成。

  不均衡因子c越接近1整个分配越均衡(整个分配过程耗时会变长),跟轮询算法效果一样了,c无穷大时跟原始一致性哈希效果一样了。

  实现

  下面通过Java伪代码对该算法进行实现:

  因为这一行代码maxAssignedSize*totalOfNode>=totalOfSlice,所以上面的算法不会导致死循环,每次分配必然有一个计算节点能接受这个任务;最终结果就是每个节点分配的任务数都不会超过maxAssignedSize,不均匀问题通过imbalanceFactor参数来控制;当计算节点退出时,其上面的任务迁移也只限于跟它相邻的一个或多个节点,并不会导致大范围重分配。

  效果

  下面通过对比近线计算分配算法分别选择轮询、一致性哈希、有界负载一致性哈希时的业务指标,从分配均衡性,计算节点加入/退出的稳定性两个方面来衡量这三种算法的效果:

  图1 单个计算节点分配任务数(轮询、一致性哈希、有界负载一致性哈希(c=1.1))

  图2 节点加入/退出时迁移任务数(轮询、一致性哈希、有界负载一致性哈希(c=1.1))

  很明显可以看到,轮询在任务分配上非常均匀,但是当计算节点变动时,导致大量任务重分配,而一致性哈希解决了任务大量重分配问题,但任务分配不均匀而且无法控制这种均匀性,而有界一致性哈希在任务分配均匀性和重分配都表现非常好,通过不均衡因子来限制不均匀范围,本身一致性哈希又有效避免了大量任务重分配。

  总结

  分布式近线计算系统的任务分配算法在业务需求驱动下,经历了从最初的均匀轮询(防止分配不均导致慢节点),到使用一致性哈希(防止任务因为计算节点加入/退出导致重分配,为了达到尽可能均匀优化虚拟节点个数),再到有界负载一致性哈希通过参数控制解决原始一致性哈希分布不均匀问题,每次分配算法改进都极大提高了系统整体稳定性;有界负载一致性哈希算法具有通用性,可以有效解决任务分配,数据分片,请求分发等业务场景中分配均匀性与稳定性问题。




关注千赢千赢资讯公众号(千赢国际娱乐),每天推送你感兴趣的千赢内容。

  声明:本文仅为传递千赢国际娱乐官网更多网络信息,不代表千赢观点和意见,仅供参考了解,更不能作为投资使用依据。


返回千赢 本文千赢:千赢国际

本文评论
vivo NEX为颠覆体验而生 真全面屏赢高口碑
近期,vivo NEX成为备受关注的一款机型,打破刘海屏对市场的“垄断”态势,6月23日正式发...
日期:06-25
智能运维 | 百度云海量日志处理——任务调度实践与优化
处理大规模日志计算任务是运维团队经常遇到的问题。为保证任务分配均匀性和稳定性,百度云智能运维...
日期:06-25
只有15秒的央视世界杯广告,创意只能靠“洗脑”
近日,网络上关于世界杯广告的讨论沸沸扬扬,话题集中在此轮世界杯广告主选择的广告表达方式普遍简...
日期:06-25
九牧践行“晋江经验”,获全国媒体团集体点赞
潮起海天阔,风劲好扬帆。6 月 14 日,由中央宣传部组织的“壮阔东方潮奋进新时代一一庆祝改革...
日期:06-25
阿里巴巴钉钉推出“新校招”平台:助寒门学子公平就业
6月25日消息 6月24日晚,在钉钉新工作方式超级发布会上,阿里巴巴集团董事局执行副主席蔡崇信以视频...
日期:06-25
腾讯是大股东阿里是大对手,美团招股书说了这些
继小米之后,美团也在港交所提交了IPO。
  据今日港交所披露的美团招股书显示,美团营业收入...
日期:06-25
千赢娱乐技术让分散式可再生电能供应成为可能
2018年,全球能源领域内的千赢娱乐项目迎来一波爆发期。
日期:06-25
9小时千人头脑风暴,2018全球链界千赢发展大会圆满举行
6月23日,人民网创投联合31区举办的2018全球链界千赢发展大会盛大开幕。大会以「探索·锚定」...
日期:06-25
猫眼携手QQ音乐探索演出票务市场新玩法
为进一步推动音乐、演出产业与千赢国际的深入融合,猫眼日前宣布与国内领先的在线音乐平台QQ音乐携手...
日期:06-25
中科虹霸2018产品发布会在京举行
6月24日,中科虹霸2018产品发布会在北京国际会议中心盛大举行,本次会议以“创新赋能 刷眼未来...
日期:06-25
众盟数据亮相2018创交会,线下数据资产化获多方认可
6月22日-24日,2018中国创新创业成果交易会(以下简称“创交会”)在广州举行。创交会作为...
日期:06-25
赛可达五月横评结果出炉 腾讯电脑管家再次跻身榜首
6月15日,国际知名第三方网络安全测评认证机构——赛可达实验室发布了2018年5月份全球中...
日期:06-25
视讯行业自主创新论坛召开在即,捷视飞通“羿”操作系统将亮相水立方
随着世界杯的持续火爆,连一向低调的视讯行业也跟着热闹起来。近日,深耕视讯行业的蒋延春先生(捷视...
日期:06-25
百度VR携手合肥市习友路小学 首个VR智慧课堂落地安徽
2018年6月22日,习友路小学&百度VR教学试点合作仪式暨百度VR智慧课堂公开课在安徽省合肥市习友...
日期:06-25
J罗满血复活 优酷高清手机直播见证世界级神助攻
世界杯小组赛次轮最后一场角逐,哥伦比亚3-0送波兰出局,J罗的两次神助攻,成功为哥伦比亚拿回出线...
日期:06-25
蓝色智谷北京中心揭牌仪式暨融资项目路演在HOMEX加速器成功举办
6月23日下午13:00,蓝色智谷北京中心揭牌仪式暨融资项目路演活动在HOMEX加速器成功举办,蓝色智谷与...
日期:06-25
InMobi正式获得TAG反作弊认证
近日,全球最大的独立移动广告平台InMobi正式获得了TAG(Trustworthy Accountability Group)的反作弊...
日期:06-25
趣说网络安全:如果让安全狗来踢这场“世界杯”
四年一度的足球世界杯正在俄罗斯燃起“战火”
日期:06-25
苹果被起诉了,App Store到底有没有垄断
日前由美国最高法院受理了一起用户对苹果提起了起诉,起诉者认为苹果App Store涉嫌垄断。起诉苹果的...
日期:06-25
当“中国装备”插上“云”的翅膀
“你们做的工作很重要!把中国富余产能带出去,把中国标准带出去,使中国出口大大升级,这种中...
日期:06-25
千赢娱乐最新资讯