AI实践哪家强?来 AICon, 解锁技术前沿,探寻产业新机! 了解详情
写点什么

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

  • 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:571543

评论

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

华为云CCE产品文档优化升级

华为云原生团队

云计算 容器 微服务 云原生

Nacos注册中心有几种调用方式?

王磊

Java 面试

EVE-NG的环境导入QEMU组件了解一下

小魏写代码

sip中继的内容介绍

cts喜友科技

SIP sip中继

Python 日期和时间处理教程:datetime 模块的使用

小万哥

Python 程序员 软件 后端 开发

创建CI/CD流水线中的IaC前,需要考虑哪些事项?

SEAL安全

DevOps CI/CD IaC 企业号10月PK榜

CQ 社区版 V2.5.0 发布 | 开放在线试用、自定义高危操作、新增数据源Phoenix、Trino等

BinTools图尔兹

oceanbase 数据库管控 polarDB trino CloudQuery

三维可视化神器带来无限可能,原来三维场景也可以如此轻松实现

袁袁袁袁满

人工智能 三维城市建模

适用于 macOS 的温度和风扇速度控制工具 TG Pro

展初云

Mac Mac软件 风扇控制

聚合支付重构

xzy

惊艳,根本停不下来!GPT-4 全工具模式开始测试

豆哥

多模态 openai ChatGPT GPT-4

【新产品】DPEasy 一款高效的数据库安全风险扫描工具,即将上线!

BinTools图尔兹

数据库 数据库安全

开源合规标准实践-“心寄源”法律沙龙(2023第六期 | 总第十一期)成功召开

开放原子开源基金会

一文读懂多云CDN

火山引擎边缘云

CDN CDN加速 CDN技术 CDN带宽

行业底部期,水泥建材企业如何有效进行数智人力管理升级?

用友BIP

流程制造

推出 Amazon Lightsail for Research

亚马逊云科技 (Amazon Web Services)

Amazon Lightsail

云游长江大桥,3DCAT实时云渲染助力打造沉浸化数字文旅平台

3DCAT实时渲染

元宇宙 实时渲染 元宇宙解决方案

校园物业报修小程序开发笔记一

CC同学

不同版本OpenJDK 源码调试方案

AiDaddy

Openjdk 远程调试 源码调试 openjdk 源码调试

mac电脑温度和风扇速度控制工具 TG Pro最新激活版

胖墩儿不胖y

Mac软件 系统监控软件

某头部证券公司决策:为什么首选 CloudQuery 数据库管控平台?

BinTools图尔兹

案例 数据库安全 客户体验

Web3开发:Web3 的兴起对加密货币发展的影响

区块链软件开发推广运营

交易所开发 dapp开发 区块链开发 链游开发 NFT开发

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