Background
Directed Acyclic Graph (DAG) is an important concept in graph theory, and it is widely used in a wide range of scenarios. First of all, as a daily example, the following diagram uses a directed acyclic diagram to represent the dependencies between different courses.
In terms of software design, directed acyclic graphs are used a lot, such as Git, which is a very well-known use case for data storage and version control. Git uses Merkle Tree + DAG as a combined data structure Merkle DAG to implement distributed version control. In the design of Excel, the function function is a very important part, and the dependencies of the functions conform to the characteristics of DAG graphs, which use directed acyclic graphs to store the dependencies between all functions in the table, which is called the dependency graph of the table.
Scheduling and data processing networks are also inseparable from directed acyclic graphs, such as Spark.
Directed acyclic graphs can well represent complex multivariate systems, and algorithmic models based on directed acyclic graphs are also abundant, such as Bayesian networks (typical case - student network).
02
Directed acyclic graph
2.1 Concept
In graph theory, if a directed graph cannot return to the point from any vertex through several edges, then the graph is a directed acyclic graph (DAG).
2.2 Features
2.2.1 Check for rings
- 拓扑排序(Topological Sort)
The loop performs two steps: (1) select a vertex with a degree of 0 and output, and (2) delete the vertex and all outgoing edges from the graph. At the end of the loop, if the number of vertices output is less than the number of vertices in the net, it means that there is a loop.
- Traversal method
Use DFS to determine whether there are rings in an undirected graph and in a directed image. In a depth-first traversal graph, if a node has an edge pointing to a node that has been visited, and the node that has been visited is not the node accessed in the previous step, it means that there is a loop.
2.2.2 Traversal
- 深度优先（Depth First Search，DFS）
The basic idea is to first visit the starting vertex v, then start from v, and then visit each unvisited adjacent vertex of v w1, w2 , ... ,wi , then visit all unvisited adjacent vertices of w1, w2 , ... , w~i~, and then start from these visited vertices and access all of their unvisited adjacent vertices until all vertices in the graph have been visited. If there are vertices in the graph that have not been accessed at this time, select another vertex in the graph that has not been visited as the starting point, and repeat the process until all vertices in the graph have been visited.
- 广度优先（Breadth First Search，BFS）
The basic idea: first visit a starting vertex v in the graph, then start from v and visit any vertex w1 that is adjacent to v and has not been visited, and then visit any vertex w2 that is adjacent to w1 and has not been visited...... Repeat the above process. When it can no longer continue to access downwards, it will fall back to the most recently visited vertice, and if it has any adjacent vertices that have not been visited, the above search process will continue from that point until all vertices in the graph have been visited.
03
DAG task orchestration and driving
3.1 Graph Arrangement
This paper proposes a task orchestration-driven scheme based on directed acyclic graphs to deal with scenarios with multi-task parallelism and complex dependencies. THE FOLLOWING FIGURE SHOWS THE CORE MODEL OF THE SOLUTION, WHICH CONSISTS OF THREE PARTS: JOB, STAGE, AND TASK.
3.1.1 JOB
A JOB CONSISTS OF MULTIPLE PARALLEL/SERIAL TASK GROUPS STAGE, AND EACH JOB IS A DIRECTED ACYCLIC GRAPH.
3.1.2 STAGE
EACH JOB IS SPLIT INTO SMALLER TASK GROUPS CALLED STAGES, EACH STAGE IS A DIRECTED ACYCLIC NODE, AND THE STAGES ARE INTERDEPENDENT ON EACH OTHER, AND EACH STAGE IS EXECUTED IN ORDER ACCORDING TO THE DEPENDENCIES.
3.1.3 TASK
A TASK IS A TASK EXECUTION UNIT OF THE STAGE, AND THE TASK IS SENT TO THE PROCESSOR FOR EXECUTION DURING SPECIFIC EXECUTION.
3.2 Graph Storage
When the business side uses it, it first completes the configuration of the business scenario (business_code), which is composed of one or more rows of config records, which constitute the "configuration directed acyclic graph" of the business scenario, that is, each row is a node of the configuration map and marked by the config_code.
WHEN A JOB REQUEST IS FORMALLY INITIATED, EACH STAGE IS MARKED BY ITS CORRESPONDING config_code, AND EACH STAGE IS THE NODE OF THE JOB DIRECTED ACYCLIC GRAPH. That is, each STAGE node is mapped to a directed acyclic graph by configuring a directed acyclic graph, and the storage model is as follows.
3.2 Graph Driven
Task-driven, based on the MQ+ event-driven mechanism, the breadth-first traversal of the graph drives the execution of each node.
3.1 STAGE Execution Conditions
- The parent node of STAGE is empty & the current STAGE node meets the service conditions
- All the parent STAGE nodes are successful & the current STAGE node meets the service requirements
- If the current STAGE is successful or empty, the current node sends a driver message to the child node where the current node is configured, and attempts to execute it on the child node.
3.2 Drive Messages
The driver message is composed of the following components: after the system consumes the driver message, it tries to execute the corresponding STAGE task, and the STAGE that meets the conditions described in 3.1 will be executed, and the driver message that does not meet the conditions will be directly discarded, and the driven message will be compensated by the scheduled task.
3.3 Event Mechanism
The system designed in this paper responds to job, stage, and task status changes through the EventBus mechanism.
- TaskEvent
Notify the service caller that the task is successful.
- StageEvent
Notify the service caller that the stage is successful, try to trigger the child node stage to execute the corresponding task, determine the status of other stages under the current job, and trigger job events if necessary.
- JobEvent
Change the job status and notify the service caller of the job status.
04
Demo
4.1 Presentation
, duration 01:26
4.2 Source Analysis
- https://github.com/damaohongtu/dag-demo (updating)
05
Resources
[1] https://en.wikipedia.org/wiki/Directed_acyclic_graph
[2] Machine Learning with Graphs http://web.stanford.edu/class/cs224w/
[3] https://github.com/alibaba/butterfly
Author: Da Yuan
Source: WeChat public account: 大袤宏图
Source: https://mp.weixin.qq.com/s/Q5IMSYedtfmk5TWme4ysmw