写点什么

百度海量日志处理——任务调度实践与优化

  • 2019-09-09
  • 本文字数:2782 字

    阅读完需:约 9 分钟

百度海量日志处理——任务调度实践与优化

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

一 业务场景

分布式系统中我们经常会面对如下业务场景:


  • 计算系统每分钟有大量的定时任务需要及时调度并按时完成,单机在处理能力和时效性上都无法满足要求,需要将任务分配到大量 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 伪代码对该算法进行实现:


1.  public String getTargeNode(String key) {2.       // imbalanceFactor为不均衡因子,取值范围为1 < imbalanceFactor < ∞3.       // 单节点最大分配任务数4.       maxAssignedSize = ⌈(totalOfSlice / totalOfNode)⌉* imbalanceFactor;5.       // nodes中key是依据node名字产生的hash值,value是node的名字6.       SortedMap tail = nodes.tailMap(hash(key));7.       long indexKey;8.       if (tail.isEmpty()) {9.           indexKey = nodes.firstKey();10.      } else {11.          indexKey = tail.firstKey();12.      }13.      String targetNode= nodes.get(indexKey);14.      //getTask获取该节点已分配任务数15.      if (getTask(targetNode) > maxAssignedSize) {16.          // 该节点超过最大任务数,继续顺序寻找下一个节点.17.         do {18.            SortedMap tailMap = nodes.tailMap(indexKey, false);19.            if (tailMap.isEmpty()) {20.                indexKey = nodes.firstKey();21.            } else {22.                indexKey = tailMap.firstKey();23.            }24.            targetNode = tailMap.get(indexKey);25.         } while (getTask(targetNode) > maxAssignedSize);26.      }27.      return targetNode;28. }
复制代码


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

效果

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



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



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


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


总结


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


作者介绍:


运小军,百度高级研发工程师,负责百度运维部大规模日志处理、海量事件数据存储相关设计研发工作,在分布式系统架构、大数据存储计算、高性能网络服务和即时通讯服务有广泛实践经验。


本文转载自公众号 AIOps 智能运维(ID:AI_Ops)。


原文链接:


https://mp.weixin.qq.com/s/xsQ8OrPWlWNJc33Fw0zJ0A


2019-09-09 18:571432

评论

发布
暂无评论
发现更多内容

保安小王分享:四面字节跳动,终拿Offer,只有努力,方能成功

Java架构师迁哥

云洲智造直播间来啦!精彩不停,速来观看

视频云的全景蓝图,想象力的允诺之地

阿里云CloudImagine

阿里云 计算机视觉 云视频 超视频化 图像增强

思购趣拼APP系统开发内容

云服务器、虚拟主机以及服务器如何定义的?三者有什么区别?

行云管家

云计算 服务器 云服务器 虚拟主机

号称下一代消息中间件!来看看它有多牛逼

白亦杨

Java

社区活动|Apache Pulsar 社区志愿者招募

Apache Pulsar

大数据 云原生 pulsar Apache Pulsar 消息中间件

金九银十吃透这份redis笔记文档,让你超过90%的面试者

Java redis 架构 面试

手把手教你,从零开始实战搭建SpringCloud Alibaba!这份笔记太牛了!

Java 架构 面试 微服务

等保二级与等保三级定级标准是怎样?哪个级别更高?

行云管家

网络安全 数据安全 等保 等级保护

IPFS挖矿靠谱吗?IPFS是什么项目是国家许可的吗?

帮你理清学习一个知识点的过程

加百利

大前端 7月日更 primise

CloudQuery 使用教程之 No.5 组织架构

BinTools图尔兹

sql dba 国产数据库 运维开发 数据库管控工具

加电软件系统开发详情

RAID 概念- RAID-0-1-5-10 的工作原理

学神来啦

Linux 运维自动化 linux运维 raid

性能优化:空调能耗节能的强化学习探索之路

鲸品堂

性能调优

最新出炉!这份资料可帮你解决95%的问题

欢喜学安卓

android 程序员 面试 移动开发

走进Android架构!2021大厂Android面试经验

欢喜学安卓

android 程序员 面试 移动开发

低代码行业未来如何?

优秀

低代码

完成GitHub个人主页设计,只需要这三步

百度开发者中心

GitHub 主页

三伏天口腔上火有口气?用这款牙膏降降火

Geek_50a546

汇总十家互联网大厂面试题后,产出Java架构师1575道“完美圣经”

Java架构追梦

Java 阿里巴巴 架构 面试

11张图解单点登录系统,瑞斯拜特!

北游学Java

Java 单点登录

双非本化学跨专业,投岗阿里/滴滴后端三面,最终拿下offer

Java 面试

最新整理:360°深入了解Flutter

欢喜学安卓

android 程序员 面试 移动开发

最新美团点评Android团队面试题:你了解过移动端适配吗

欢喜学安卓

android 程序员 面试 移动开发

Canny 边缘提取相关知识学习,图像处理第 32 篇博客

梦想橡皮擦

7月日更

FIL币价走势如何?FIL币价格未来多少钱一枚?

网络攻防学习笔记 Day73

穿过生命散发芬芳

网络攻防 7月日更

最新出炉!最新阿里+头条+腾讯大厂Android笔试真题

欢喜学安卓

android 程序员 面试 移动开发

一个100%省力的,让城市管廊运维变得轻松的秘诀

一只数据鲸鱼

数据可视化 智慧城市 智慧管理 地下管廊

百度海量日志处理——任务调度实践与优化_文化 & 方法_运小军_InfoQ精选文章