DAG概述及在快手电商业务中的使用

随着Web应用程序的快速发展，前端开发日益复杂。为了提高前端应用程序的性能和可维护性，前端开发人员需要使用各种工具和技术来管理前端代码和资源。其中，DAG（有向无环图）是一种用于表示依赖关系的数据结构，其在前端领域中得到了广泛的应用。

在本文中，我们将讨论DAG在前端领域中的几个应用场景，并且将会以快手电商业务领域中的投放引擎为例，介绍DAG在任务流程编排中的使用。

1 DAG在前端领域的应用

1.1 资源加载优化

在Web应用程序中，资源的加载顺序是影响页面性能的一个关键因素，因为某些资源可能需要在其他资源加载完成之后才能加载。为解决该问题，可使用DAG来管理资源之间的依赖关系。

在使用DAG进行资源加载优化时，将每个资源表示为DAG中的节点。如果两个资源之间存在依赖关系，可以在这两个节点之间建立一条有向边。在执行资源加载时，可以使用拓扑排序算法对DAG进行排序，从而保证每个资源的依赖关系得到正确地解决。通过使用DAG进行资源加载优化，可以减少不必要的资源加载，从而提高Web应用程序的性能。

1.2 前端组件库构建

前端组件库是一组可以被重复使用的前端组件，可以用于构建不同的Web应用程序。在构建前端组件库时，需要对组件之间的依赖关系进行管理，以确保每个组件都可以正确地加载和使用。为了解决这个问题，可以使用DAG来管理组件之间的依赖关系。

在使用DAG进行前端组件库构建时，可以将每个组件表示为DAG中的节点。如果两个组件之间存在依赖关系，可以在这两个节点之间建立一条有向边。在执行组件加载时，可以使用拓扑排序算法对DAG进行排序，从而保证每个组件的依赖关系得到正确地解决。通过使用DAG进行前端组件库构建，可以提高组件的复用性和可维护性。

1.3 任务流程可视化编排

在开发中，任务的并行执行是提高应用性能的关键因素之一。然而，任务之间可能存在依赖关系，例如某个任务需要在另一个任务完成后才能执行。使用DAG可以管理任务之间的依赖关系，并将任务分解成多个子任务，实现任务的并行执行。

2 DAG优势与劣势

2.1 优势

可视化和可理解性：DAG可以以图形化的方式展示任务之间的关系，使得整个流程编排更加直观和可理解。通过可视化的DAG图，开发人员和业务人员可以清楚地了解任务的执行顺序和依赖关系，更好地进行流程设计和调整。

灵活性和可扩展性：DAG可以支持复杂的任务调度和流程控制需求。通过定义任务的依赖关系和触发条件，可以灵活地调整任务的执行顺序和流程的推进。同时，DAG的结构也支持扩展，可以方便地添加新的任务或修改现有任务的依赖关系。

2.2 劣势

复杂性：DAG的管理和维护可能变得复杂。随着流程的复杂度增加，DAG的节点和边的数量也会增加，这可能导致DAG的可读性和理解性下降。同时，更复杂的DAG可能需要更复杂的算法来进行任务调度和依赖管理，这对于开发人员而言可能增加了工作的复杂性。

循环依赖问题：DAG的一个基本限制是不能存在循环依赖，即任务之间不能形成闭环。然而，在复杂的流程中，循环依赖的情况可能难以避免。处理循环依赖问题可能需要额外的逻辑和算法，以确保任务的执行顺序不会陷入死循环。

难以处理动态变化：在某些情况下，流程编排中的任务可能会根据运行时的条件或数据发生变化。然而，DAG在创建时需要明确定义任务的依赖关系，这使得在运行时动态地修改和调整DAG变得困难。为了解决这个问题，可能需要采用其他的编排机制或引入动态调度和执行引擎。

3 DAG在快手电商业务领域的使用

随着快手电商的快速发展，其业务流程也越来越复杂。而前后端研发为不同场景的业务处理复杂度也越来越高。

例如，在C端场景下，不同的用户可以看到不同数据。如何做到千人千面的投放，逐渐成为前后端研发重点考虑的问题。

例如：在快手双11活动中，共有10000个商家提报参与大促，但这10000个商家中并不是所有商家都符合大促提报条件，因此就需要按照设定规则经过多层筛选，例如：GMV值、在线时长等条件，这些条件或是并集操作，或是交集操作，最后经过指定流程处理后，只有1000个商家符合条件参与大促。

针对不同的处理方式，如果用代码编写就需要大量的if-else 操作。但如果将每个业务模块抽离为算子，配合业务逻辑连线，即可完成业务流程编写，最后通过执行引擎执行，即可实现千人千面的投放需求。

下图就是我们为实现千人千面投放，结合DAG数据结构，开发的DAG可视化流程编排引擎。

在该平台中，我们底层使用了Antv旗下的前端可视化框架x6，此外，为提升用户体验，完善周边配套，降低原数据接入成本，我们还提供了以下能力：

• 提供自动编排能力：即按照既定的数据格式，无需借助UI位置等信息，通过引擎自带的自动编排能力实现DAG图的渲染，这为已有数据接入的需求提供了可能；

• 提供低成本接入能力：对于任何想接入引擎的研发同学，只需要提供对应的数据存储接口即可，不需要再关心引擎编排能力，也无需对数据做parse等。我们目前已经提供的数据结构与快手社科组的dragonfly数据结构一致，对已经有数据的项目来说，可实现0成本接入；

• 提供低代码，低成本配置能力：本产品另外一个重要的价值就在于，可以实现低代码低成本的配置，主要体现在两个方面：

• 通过拖拽的形式，可以实现流程图的配置，完全避开了硬编码操作；

• 每个节点的配置信息，后端可以根据自己的需求动态下发，引擎会解析为对应的表单配置项

4 实现思路

接下来，结合快手电商的投放引擎，我们一起来探索实现思路。

在投放页面中，主要包含3部分：左侧的算子列表面板，中间的DAG图编排面板，右侧的算子配置面板

4.1 算子列表面板

在下面提供了单个算子的数据结构。后端只要将所有的算子push到数组中下发给前端，投放引擎就可将算子列表按照分类，处理为树形结构，并在页面展示。每个算子的数据格式如下：

interface moduleDef  {  operatorTypeId: "左侧tree结构及图中的节点id, 一般与name保持一致，因为都是唯一的",  displayName: "左侧tree结构及图中的节点名称",  description: "左侧tree结构hover单个节点的说明信息",   categoryType: moduleType, //（会根据此值表明该节点类型，例如属于操作类节点或通用类节点等）   categoryTypeName: '功能模块',  configuration: [    {        key: '', // 字段key, 如果没有提供，会与name保持一致        label: '', // required: 后端读取该配置用，同时为UI展示label的名字        errorMessage: '', // not required: 此为配置信息输入错误提示        required: boolean, // not required: 此为配置信息是否为必填        type: attributeType, //(not required: 此为属性类型：输入框，下拉框，单选框, 默认input，详见本文属性类型定义)        defaultValue: '', //(not required: 此为配置信息的默认展示值)        value: '', //(not required: 配置后的值)        options: any,        description: '', //(not required: 此为配置信息提示信息),        disable: boolean, // 默认FALSE    },    {        key: "leafRpcName",        label: '节点名称'        value: ""    },    {        // 该字段为模块默认字段，用来让用户自定义实现逻辑的        key: "scriptConfig",         label: '定制化业务逻辑',        value: "",        type: 'input',        required: false,    },  ],}

4.2 DAG图编排面板

在该部分中，我们底层使用了Antv旗下的前端可视化框架x6，在此基础上，我们还实现了一键重排、自动编排等能力。在这里，重点分析自动编排能力的实现。

在分析自动编排能力之前，我们首先需要知道原始数据格式是什么。由于数据量比较大，我们只演示对自动编排能力有影响的字段。如下所示：

const data = {  NODE_1: {      downstream_processor: ['NODE_2'],      config: [          {              errorMessage: '请输入',              field: 'name',              labelText: '算子名称',              required: true,              type: 'input',              value: '',          },      ],  },  NODE_2: {      downstream_processor: ['NODE_3', 'NODE_4', 'NODE_5'],      config: [],  },  NODE_3: {      downstream_processor: ['NODE_6'],      config: [],  },  NODE_4: {      downstream_processor: ['NODE_6'],      config: [],  },  NODE_5: {      downstream_processor: ['NODE_6'],      config: [],  },  NODE_6: {      downstream_processor: ['NODE_7'],      config: [],  },};

根据上面的结构我们可以看到，downstream_processor这个字段就是表明两个算子之间关系的。接下来，我们就要根据这个字段，来获取节点的位置信息与边的信息。

首先，我们需要对上面的图做数据的第一次处理，得到边的信息：

LinksArray: [  {source: 'NODE_1', target: 'NODE_2', inputPortId: NODE_1_out_1, outPortId: NODE_2_in_1},  {source: 'NODE_2', target: 'NODE_3', inputPortId: NODE_2_out_1, outPortId: NODE_3_in_1},  {source: 'NODE_2', target: 'NODE_4', inputPortId: NODE_2_out_1, outPortId: NODE_4_in_1},  ...]

其次，我们要根据边的信息开始布局节点信息。

具体步骤：从linksArray中的第一项开始，把该项的source，target放入数组，接下来，开始对数组遍历，如果存在跟第一个数组相同的节点，就需要开始插入数组。

插入规则：如果target相同，那么在result数组的target的上一项插入source值，如果是source相同，那么就需要在source的下一项插入target，在插入的时候，要注意判断当前要插入的位置是否存在，存在为push操作，不存在为数组赋值操作。如果遍历到result的最后都没有，说明该项还没有被插入进来，直接在result的最后进行赋值即可

然后进行下一轮的遍历，直到将多余两个节点的信息都遍历结束，插入到result数组中。

在这一步中，我们会得到如下结果：

const result = [  ['NODE_1'],  ['NODE_2']  ['NODE_3', 'NODE_4', 'NODE_5']  ['NODE_6'],  ['NODE_7']]

接下来，根据上面得到的result值对每个节点的位置进行赋值

赋值逻辑：遍历数组的每一项，如果该数组中的第n项中，有一个节点，那么就将该节点放在x为0的位置，如果该项有m个元素，然后用m/2, 得到在中轴的两侧各排列几个节点，然后通过乘固定横向间距，得到每个节点的横向坐标，纵坐标极为第n项目前已经所排列到的纵坐标；依次类推，按照上面的规则，依次得到所有多条连线节点的横纵坐标；

最后，当得到位置信息后，将节点的位置信息与边的信息传给antv x6渲染引擎，即可完成DAG图的展示。

4.3 配置面板

对于配置面板，我们采用的是自研的动态表单渲染引擎来完成渲染。当然，我们当前也在重构使用快手电商的kcube表单动态渲染引擎来完成渲染。

总结

在本文中，阐述了DAG概念、前端领域使用场景、优势与劣势。重点阐述了在快手电商业务领域的使用及实现思路，特别是对自动编排能力的实现及关键步骤的解法。

当然，我们在该领域还有很多优化及提升空间。例如：对于DAG使用场景，我们如何去拓展至前端领域，特别是如何为前端研发效率提升做出努力。对于自动编排能力，我们如何完成大量节点数据处理的性能优化、实现多出度场景的自动编排能力等。

当前，我们在这些方面也取得了一定的成果，未来会在后续文章中与大家一起分享。

如果大家有兴趣共建或一起研究，都可以随时私聊。