火山引擎数据调度实例的 DAG 优化方案
1. 实例 DAG 介绍
DataLeap 是火山引擎自研的一站式大数据中台解决方案，集数据集成、开发、运维、治理、资产管理能力于一身的大数据研发治理套件。在平台中，一个核心的功能为任务的调度，会根据任务设置的调度频率（月级，日级，小时级等）运行任务，从而生成对应的实例。
在数仓研发中，不同的表之间会存在依赖关系，而产生表数据的任务实例，也会因此存在依赖关系。只有在上游实例运行成功、下游实例到达设定的运行时间且资源充足的情况下，下游实例才会开始执行。所以，在日常的任务运维中，常常需要分析实例上下游的运行情况，根据具体的情况对实例进行置成功、重跑等操作。
而如何清晰地展示实例之间的关系，帮助用户快速地分析整个链路的运行情况，并完成问题定位和运维操作，则是实例 DAG 需要解决的问题。下面对比下优化前后的效果。
优化前：
可以看到在复杂链路中，将所有节点的关系全部展示出来，导致连线混乱，需要通过不停的拖拽、缩放，才能找到没有执行的上游节点。
优化后：
通过采用了将节点聚合的形式，简洁地展示上下游关系。同时，采用了将实例状态进行分类的形式，提供快捷操作的按钮，让用户可以只关注特定状态的实例，减少了无用信息对用户运维操作的干扰。下面将详细介绍优化的整体过程。
1.1 概念
- 任务：在 DataLeap 数据研发平台中，对数据执行一系列操作的定义。
- 实例：通过任务配置的执行频率（月级、天级等）而创建的一个任务的快照。
- DAG：全称为 Directed Acyclic Graph，指有向无环图，具备严密的拓扑性质，有很强的流程表达能力。
- DAG 布局：指根据有向无环图中边的方向，自动计算节点层级和位置的布局算法。
1.2 业务场景
以其中一个场景为例：
对于任务 test_3 在 2022-09-29 的实例进行分析可知。当前实例没有运行，是由于上游任务 test_2 在 2022-09-29 的实例运行失败导致的，那么此时可联系上游实例对应的任务的负责人，对实例进行处理（包括但不限于重跑，置成功等操作）。
2. 问题
在当前的实例 DAG 图中，用户在实际使用中会碰到如下问题：
-
复杂的实例 DAG 图无法渲染。
在一些业务方向中，会出现 DAG 图中有几千节点。由于数据处理的复杂和采用了 svg 的渲染方案，常常会导致前端浏览器的崩溃。
-
同层级节点过多，操作困难。
以下图为例，在分析上游实例中，是哪个实例没有运行，导致当前实例没有执行时，需要通过连续拖拽，才能定位到关注的上游实例。
- 查看节点依赖时，只能不断展开，在对不同的上游依赖进行展开时，会导致图展示混乱。
3. 需求分析
在通过用户调研及使用过程中发现，使用 DAG 进行分析时主要有以下场景：
-
当前实例已经到达指定运行时间，但是没有运行。
在这种情况下，用户关注的是上游没有运行的实例 / 运行失败的实例，联系上游实例的责任人进行问题定位。
-
当实例已经运行成功，但是完成时间比正常情况下有延迟。
在这种情况下，用户关注的是上游实例中，最晚完成的实例。从而判断是否对链路进行治理优化。
-
当实例运行失败，导致下游没有运行。
在这种情况下，用户关注的是依赖当前实例的所有下游实例，同时需要对下游实例进行聚合筛选，比如任务的优先级（代表任务的核心程度），以通知下游实例进行重跑等操作。
结合上面存在的问题可得到，主要原因是由于在复杂链路情况下，上述需求比较难满足。而在旧版的 DAG 中，针对简单链路和复杂链路的处理是一致的，为此，我们需要设计解决复杂链路场景下的方案。
4. 功能设计
针对上面存在的问题以及对需求的分析，我们可以进行如下的功能实现与设计：
4.1 渲染方案替换
将 svg 的渲染方案替换成 canvas 渲染，通过减少页面中 DOM 的数量，提高前端渲染性能。
4.2 不同场景的功能设计
通过上面的需求分析，我们设计了不同的功能模式以满足不同的需求。
| 模式名称 | 功能 |
|---|---|
| 通用模式 | 分析上游阻塞下游运行的原因、查看上游最晚完成的实例 |
| 统计模式 | 对依赖当前实例的所有下游进行分组查看 |
| 链路模式 | 分析两个实例之间的链路关系 |
4.2.1 通用模式
在通用模式中，用户关注的是 节点上下游的关系 ，在复杂链路中 快速找到阻塞节点 ，同时关注 阻塞节点的信息 。
针对复杂链路，我们设计了多种优化形式：
首先，在同一层的节点超过一定的数量（可自定义）后，所有节点将聚合在一起，我们称之为 聚合节点 。这种优化下，可以解决上面提到的由于同一层级节点过多，查找特定状态节点不便的问题。也支持点击聚合详情，通过列表的形式，查看所有被聚合的节点。并支持筛选，快速查找到关注的节点并通过展开，恢复与当前节点的依赖关系。
其次，以用户最关注的实例状态，对被聚合的节点进行分类，同时新增快捷展开操作。以下图为例，当前实例处于等待上游依赖完成状态，在这种情况下，用户关注的，则是 上游没有开始执行的节点 。在聚合节点中，可以清晰地看到存在一个实例，是在等待执行的，点击数字 1，即可快速展开实例。
在这个例子中，就将不需要关注的上游成功节点隐藏在列表中，突出图所需要关注的重点信息。
同时，为了降低节点展示过多导致图显示杂乱的情况，新增了收起功能及跳转功能。
收起功能是指在通过在聚合节点展开的节点的情况，或是在直接展开上 / 下游的情况下，都支持对某个上游 / 下游节点的整条链路收起，方便用户在浏览完一条链路后，恢复图之前的状态，继续浏览下一条链路，减少对后续分析的干扰。
跳转功能是在查看当前节点的上游的其他下游，或是下游的其他上游，此时，用户关注的节点已经转化为其他的上游 / 下游节点。所以，通过跳转新页面的形式，将需要关注的不同节点的上 / 下游信息区分开，减少在一张图中展示所有信息。
并且由于图中的节点承载信息的能力有限，在通过点击节点时，会在下方出现与选中实例相关信息，包括属性，日志等，协助用户运维任务。
4.2.2 统计模式
在统计模式中，用户关注的是 依赖当前节点的下游节点 ，下游节点则可以分成直接下游和所有下游。所以设计了分层模式和合并模式，在这两种模式下，可以按照任务的属性（任务类型 / 实例状态 / 责任人等）作为分组维度。
分层模式：
合并模式：
4.2.3 链路模式
指定上游节点，一键展示指定节点与当前节点的链路信息，从而进行精准链路分析。
5. 技术实现
5.1 数据处理
在原始数据中，是以一个数组的形式返回节点信息及依赖关系。所以，需要对数据进行处理形成图所需要的数据，同时，利用多个 map 对数据进行存储，方便后续对数据进行检索，减少时间复杂度。
5.2 自定义节点注册
实例节点的样式需要通过基础图形 Text（文本）、Rect（矩形）、Icon（图标）进行组合，以达到我们的设计要求。
5.3 图预处理
在前面提到，我们需要在复杂的图场景中，将超过一定数量的同层节点聚合起来，以达到清晰直观地传达图所要表达的信息的目的，所以需要对图的层级及节点进行处理，从而生成聚合节点和去掉多余的节点。
5.4 DAG 图布局
通常来说，DAG 的布局可以按照以下步骤实现。
- 去环：包括自环和非自环，为节点分层做准备。
- 节点分层：给所有节点安排合适的层级。
- 节点排序：同层级内节点排序，减少相邻层级中节点连续的交叉点数量。
- 节点坐标分配：根据分层和同层节点的排序计算节点位置。
而在我们的场景中，节点的层级是有明确含义的，比如在节点 A 处于节点 B 的上方一层，且 A, B 之间有连线连接，则可认为 A 是 B 的上游一层节点。因此与传统 DAG 布局产生了以下不同点，我们需要根据场景做定制。
- 节点所在层级固定：DAG 布局既能支持自动计算层级，也能接受直接指定节点分层。
- 可能产生同层级连线：将同一层级里有连线的节点进行分组，进行内部排序后，视为整体再参与当前层级的排序，以减少交叉点的数量。
6. 总结
从功能设计上，我们需要从用户的使用场景出发，区分不同的功能满足用户的诉求。同时，在前端领域中，针对大数据量的场景，需要判断这些大数据量的展示对用户是否存在价值，从大数据量中挖掘出用户的关注点并突出重点，方便用户快速地进行查看分析。
从技术实现上，我们需要结合业务，根据业务的特征去修改已有的 DAG 布局实现，以满足在不同的业务场景下，更好地将信息呈现给用户。
当然，当前的功能设计也存在不足之处，在当前的上游查看分析功能上，由于数据库查询存在瓶颈，只能分析一层的上游，在后续优化查询性能后，可以通过一键分析，直接查找到出现问题的根节点，可以帮助用户减少操作成本以提高分析效率。
7. 参考
-
Dag 布局流程参考：Sugiyama, Tagawa, Toda, et al., "Methods for Visual Understanding of Hierarchical System Structures"
链接：http://media.wix.com/ugd/6cbb0c_289d09ca219c4c9a8df5bf05c16214dc.pdf
-
DAG 算法主体：Gansner, et al., "A Technique for Drawing Directed Graphs"
8. 关于我们
火山引擎大数据研发治理套件DataLeap
一站式数据中台套件，帮助用户快速完成数据集成、开发、运维、治理、资产、安全等全套数据中台建设，帮助数据团队有效的降低工作成本和数据维护成本、挖掘数据价值、为企业决策提供数据支撑。
