分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

贺鹏 目前就职某互联网金融公司负责架构及开发管理工作,在分布式领域和风控领域深入研究。

I.内容提要

定时调度系统(定时任务、定时执行)算是工作中经常依赖的中间件系统,简单使用操作系统的 crontab,或基于 Quartz,xxl-job 来搭建任务调度平台,行业有很多优秀的开源产品和中间件。了解其工作和设计原理,有助于我们完善或定制一套适合公司业务场景的任务调度中间件,之前写了两篇文章介绍了调度负载均衡和定时延时任务的内容,可以参考。

  • 分布式调度分发负载均衡及服务保持

  • 分布式调度延时任务实现原理

今天我们探讨另一话题,对调度任务的依赖关系及编排展开分析,实现一套工作流,来满足任务间的复杂依赖的场景。本章内容提要:

  • 任务调度依赖 & 工作流

  • 图相关知识

  • golang 并发相关

II.任务调度依赖

什么是任务依赖?比如 “任务 a” 执行的前提是 “任务 b” 先执行完成,“任务b” 又依赖于 “任务 c” 先执行,那么就形成如下依赖关系。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

这个还比较简单,如果复杂点的如下图所示,形成一个工作流,Azkaban 大数据调度器就实现了工作流模式调度依赖,这是一个典型的图应用案例。

III.图数据结构

提到图数据结构,大部分人既熟悉又陌生,因为大学基本都学过,但一般工作场景都不会用到,这里就先简单回顾一下图相关的知识。

图 graph,图中的元素称为顶点 vertex。图中任一顶点可以与其他顶点建立连线关系,叫做边 edge

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

上面图叫 “无向图”,如果边有 “方向” ,那么就是 “有向图” 了。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

无向图中,顶点有几条边就叫几;有向图中,顶点有入度,表示有多少边指向此顶点,顶点的出度表示该顶点有多少边指向 “远方” 。

上图中 a 指向 b,b 指向 d,d 又指向 a, a、b、d 之间形成一个环,如果将顶点比作调度的任务,那么任务 a 完成必须依赖任务 b,任务 b 又依赖任务 d,任务 d 又依赖任务 a,那么最终肯定无法完成,因此调度问题使用的是有向无环图 (DAG),比如我们最早那张图。

了解了图的基本概念,那么图结构如何用代码表示出来?这里涉及到图的两种存储方式:邻接矩阵、邻接表。

邻接矩阵底层为二维数据,如果有一条边顶点为 x 和 y,对无向图来说,对应的数据 Array[x][y] 和 Array[y][x] 标记为 1;对有向图 x->y ,只将 Array[x][y] 标记为 1 即可,下图为使用邻接矩阵表示的无向图和有向图。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

对于无向图来说,邻接矩阵沿着红色对角线两边是对称的,如果图的顶点连线比较少,这种叫稀疏图,将存储大量的 0 ,浪费存储空间,这时候可以选择使用邻接表表示,相对稀疏图的叫稠密图,使用邻接矩阵可以更好地查询连通性,其原理也是用空间换时间。下图为使用邻接表表示的无向图和有向图。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

最后说下图的遍历,和遍历树一样分为广度优先 BFS 和 深度优先 DFS,但图如果存在成环的情况,访问的节点要做记录,同时可用辅助队列存放待访问的邻接节点。

拓扑排序,对有向无环图的顶点进行遍历,将所有顶点形成一个线性序列,可以用数组(切片)或链表存储,如下图。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

IV.golang 代码实现

回顾了图的相关知识,那么回到最开始的任务依赖工作流中,将每个任务看成图的顶点,任务 a 依赖 任务 b,使用一条有向线从 a 指向 b,最后将所有任务顶点连线形成一个图,这个图是一个有向无环图 DAG,对 DAG 进行拓扑排序,形成一个任务执行链表,反向执行即可解决依赖问题。

首先定义一个图结构体,这里使用邻接矩阵方式存储,图的顶点结构体存储 Key 和 Value 代表任务的相关执行信息。

//图结构type DAG struct { Vertexs *Vertex}//顶点type Vertex struct { Key string Value interface{} Parents *Vertex Children *Vertex}

为图添加顶点和添加边,这里是有向图,from 代表边的起始顶点, to 代表边的终止顶点。

//添加顶点func (dag *DAG) AddVertex(v *Vertex) { dag.Vertexs = append(dag.Vertexs, v)}//添加边func (dag *DAG) AddEdge(from, to *Vertex) { from.Children = append(from.Children, to) to.Parents = append(to.Parents, from)}

建立 a – i 所有顶点,再对每个顶点连线。

var dag = &DAG{}//添加顶点va := &Vertex{Key: \"a\", Value: \"1\"}vb := &Vertex{Key: \"b\", Value: \"2\"}vc := &Vertex{Key: \"c\", Value: \"3\"}vd := &Vertex{Key: \"d\", Value: \"4\"}ve := &Vertex{Key: \"e\", Value: \"5\"}vf := &Vertex{Key: \"f\", Value: \"6\"}vg := &Vertex{Key: \"g\", Value: \"7\"}vh := &Vertex{Key: \"h\", Value: \"8\"}vi := &Vertex{Key: \"i\", Value: \"9\"}//添加边dag.AddEdge(va, vb)dag.AddEdge(va, vc)dag.AddEdge(va, vd)dag.AddEdge(vb, ve)dag.AddEdge(vb, vh)dag.AddEdge(vb, vf)dag.AddEdge(vc, vf)dag.AddEdge(vc, vg)dag.AddEdge(vd, vg)dag.AddEdge(vh, vi)dag.AddEdge(ve, vi)dag.AddEdge(vf, vi)dag.AddEdge(vg, vi)

对该图进行广度优先遍历,通过引入队列来减少时间复杂度,遍历后生成一个包含所有顶点的 slice 。

  1. 选择起始节点入队列

  2. 节点出队列

2.1 队列空了,说明遍历完毕返回 2.2 已访问跳过,未访问顶点放入输出 slice 中

2.3 将节点的所有未访问邻接节点 Children 放入队列

3. 重复执行 2

注意 slice 加入顺序,因为执行要从 i 到 a 的顺序,所以将每次遍历后的元素放到 slice 第一个位置。

func BFS(root *Vertex) *Vertex { q := queue.New q.Add(root) visited := make(map[string]*Vertex) all := make([]*Vertex, 0) for q.Length > 0 { qSize := q.Length for i := 0; i < qSize; i { //pop vertex currVert := q.Remove.(*Vertex) if _, ok := visited[currVert.Key]; ok { continue } visited[currVert.Key] = currVert all = append([]*Vertex{currVert}, all...) for _, val := range currVert.Children { if _, ok := visited[val.Key]; !ok { q.Add(val) //add child } } } } return all}

最后就是对所有任务进行执行,这里假定每个任务执行需要 5 秒,然后输出执行结果。

func doTasks(vertexs []*Vertex) { for _, v := range vertexs { time.Sleep(5 * time.Second) fmt.Printf(\"do %v, result is %v n\", v.Key, v.Value) }}

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

通过执行测试用例,可以看到执行按上述生成的 slice 顺序,从左向右逐个执行,满足任务依赖关系。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

但这里有个问题就是执行时间过长,因为每一个都是串行执行,9 个任务要执行 45 秒。那么并行不就解决了?但任务有依赖关系又如何并行呢?

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

通过这个图即可一目了然明白了,分层执行,上层任务依赖下层,但每一层的任务相互独立可以并发执行。

首先在 BFS 遍历生成顶点的时候,需要生成双层切片:

[0] { i }

[1] { h, e, f, g }

[2] { b, c, d }

[3] { a }

func BFSNew(root *Vertex) *Vertex { q := queue.New q.Add(root) visited := make(map[string]*Vertex) all := make([][]*Vertex, 0) for q.Length > 0 { qSize := q.Length tmp := make([]*Vertex, 0) for i := 0; i < qSize; i { //pop vertex currVert := q.Remove.(*Vertex) if _, ok := visited[currVert.Key]; ok { continue } visited[currVert.Key] = currVert tmp = append(tmp, currVert) for _, val := range currVert.Children { if _, ok := visited[val.Key]; !ok { q.Add(val) //add child } } } all = append([][]*Vertex{tmp}, all...) } return all }

同时执行时候按每一层并发执行。这里通过 sync.WaitGroup 保障并发同步等待。

for _, layer := range all { fmt.Println(\"------------------\") doTasksNew(layer)}//并发执行func doTasksNew(vertexs []*Vertex) { var wg sync.WaitGroup for _, v := range vertexs { wg.Add(1) go func(v *Vertex) { defer wg.Done time.Sleep(5 * time.Second) fmt.Printf(\"do %v, result is %v n\", v.Key, v.Value) }(v) //notice } wg.Wait}

上述代码注意,遍历变量被并发调度必须进行绑定,如果按下面这样写将会有问题。

for _, v := range vertexs {

go func {

//…

fmt.Printf(v)

}

}

这是因为 for k, v := rang xx 语句中,每次循环变量 k 和 v 是重新赋值,并非生成新的变量,如果循环中启动协程并引用变量 k 和 v 很可能在循环结束时才开启协程执行,这时所有协程中的变量 k 和 v 都是同一个变量,输出内容也会完全相同。所以这里将 v 加入函数参数中,因为 go 函数都是值传递,会重新绑定到新的变量中。

通过并发改造后,执行时间只有 20 秒了,大大提高了任务执行的效率。

分布式任务调度系统设计:详解Go实现任务编排与工作流(go 分布式任务调度)

通过本章内容,我们实现了任务调度的工作流模式,本文代码可访问 https://github.com/skyhackvip/dag 更多了解。

技术原创及架构实践文章,欢迎通过公众号菜单「联系我们」进行投稿。

高可用架构

改变互联网的构建方式

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

(0)
上一篇 2022年7月6日 上午11:17
下一篇 2022年7月7日 上午9:37

相关推荐

  • 企业邮箱品牌盘点(企业邮箱有哪些品牌)

    数字经济时代下,企业邮箱作为数字营销的第一步,企业邮箱使用独立域名,企业统一个性签名,可大大提升企业形象。目前企业邮箱比较好用的品牌,主要是腾讯企业邮箱、阿里云企业邮箱、网易企业邮…

    科研百科 2023年5月25日
    1.1K
  • 某石油石化研究院任职资格体系搭建项目纪实(石化研究员)

    ——引入“三段九级”能力评价体系,实现人才“多功能”培养 传统的任职资格体系主要考虑年限、经验、资历等因素,部分企业在任职资格体系中也引入了能力指标,但是,实际管理过程中仍然存在很…

    科研百科 2024年4月19日
    108
  • 工程项目合同管理措施

    工程项目合同管理措施 工程项目合同管理措施是确保工程项目顺利实施的重要步骤。合同管理措施包括确定项目范围, 项目目标和预算, 确定项目期限和交付标准, 以及确定合同条款和条件等内容…

    科研百科 2025年1月7日
    0
  • 档案管理的方法与步骤

    档案管理的方法与步骤 档案管理是一个非常重要的工作,可以帮助我们保存和管理我们的文件和资料。一个有效的档案管理方法可以帮助我们更好地组织和管理我们的文件和资料,从而提高工作效率和文…

    科研百科 2025年1月10日
    0
  • 党建带团建怎么抓,云南监狱这样做(党建带团建具体做法)

    云南监狱各级团组织牢牢把握党建带团建主线,大力推进党建带团建促业务,实现党建与共青团工作的深度融合。 党旗所指 团旗所向 提高政治站位 增强引领力 抓好党的二十大精神学习。按照团中…

    科研百科 2023年9月21日
    175
  • 内蒙古“科技悬赏”15个项目 榜单总金额2.7亿(内蒙古科技攻关项目)

    正北方网讯(北方新报正北方网首席记者 刘晓君 实习生 景 媛)“揭榜挂帅”是一种新型的科技计划项目组织形式,本质上是一种“科技悬赏”。9月1日下午,记者从内蒙古自治区研发投入攻坚行…

    科研百科 2024年4月16日
    80
  • 仓储管理软件有哪些好用(仓储管理软件有哪些)

    仓储管理软件是一种用于管理仓库和供应链管理的软件。它们可以帮助仓库管理人员更好地管理库存, 提高生产效率, 减少错误率。随着电子商务的兴起, 仓储管理软件的需求也越来越高。本文将介…

    科研百科 2024年6月3日
    61
  • 多项目管理子系统

    多项目管理子系统: 现代组织中不可或缺的工具 随着现代组织规模不断增大,项目管理能力的需求也在不断提高。多项目管理子系统作为一种新兴的项目管理工具,已成为现代组织中不可或缺的工具。…

    科研百科 2024年12月17日
    0
  • 集成系统项目成本管理

    集成系统项目成本管理 集成系统项目成本管理是集成系统项目成功的关键因素之一。在项目中,正确的成本管理可以帮助团队更好地理解项目的成本结构,制定有效的成本控制计划,并在项目实施过程中…

    科研百科 2024年12月20日
    0
  • 管理 工程软件系统

    管理工程软件系统: 助力企业高效协同 随着信息技术的不断发展,管理工程软件系统已经成为现代企业不可或缺的一部分。这些软件系统可以提供各种功能,包括项目管理、任务管理、质量管理、团队…

    科研百科 2024年10月2日
    19