Phoenix framework: Designing a concurrent framework for business from 0 to 1, automatically constructing directed acyclic graph design.

From 0 to 1 Designing Business Concurrent Framework Series:

Phoenix automatically builds a business concurrent framework with a directed acyclic graph. The core lies in not requiring developers to worry about the sorting problem of calling layers and dependency mutual exclusion. It automatically builds, collects Task tasks, detects cycles or dependencies through algorithms, and finally prints concurrent group layer information.

This article explains how to build a directed acyclic graph design implementation and the problems encountered.

Implementation Solution#

The construction of the directed acyclic graph uses the strategy pattern in the design pattern. First, define the implementation method of the Builder as follows:

/**  
 * @author debuginn  
 */
public interface PhoenixBuilder {  
  
    // Filter Task tasks used by Phoenix API  
    Map<String, ArrayList<TaskObj>> filterApiUsedTask(ArrayList<TransObj> transObjArrayList);  
  
    // Get the trans to be executed based on the api    
    Map<String, ArrayList<TransObj>> apiTransMap(ArrayList<TransObj> transObjArrayList);  
  
    // Check if there is a dependency relationship  
    void isHaveLoop(Map<String, ArrayList<TaskObj>> apiUsedTaskMap);  
  
    // Process concurrent group layer division  
    Map<String, ArrayList<ArrayList<TaskObj>>> processConcurrentGroup(Map<String, ArrayList<TaskObj>> apiUsedTaskMap);  
  
    // Print concurrent group layer information  
    void printConcurrentGroup(Map<String, ArrayList<ArrayList<TaskObj>>> phoenixApiArrayListMap);  
}

PhoenixBuilder needs to implement 6 methods:

First, group the collected Tasks according to the API, and collect Tasks that have dependency calls;
Collect Trans based on the API, and subsequent Trans are executed in series using request threads;
Determine whether the collected Tasks for each API have mutual dependencies or circular dependencies;
Group the collected Tasks for each API according to the order of dependencies;
Print concurrent group information for debugging and verification by developers;

Dividing Concurrent Invocation Groups

Due to the existence of dependency relationships, layering design is required. You can refer to Phoenix Framework: How to Organize and Design a Framework to see. However, each layer does not need to be concerned about the execution order. The simplest data structure is used here to store the layering information, with Map<String, ArrayList<ArrayList<TaskObj>>> as the Key to identify which API request the concurrent group belongs to, and Value uses the simplest two-dimensional array for storage, with each dimension storing the Task tasks that need to be executed.

Problems Encountered#

How to Determine the Existence of Cycles#

Since we want to build a directed acyclic graph, it is not feasible to have Tasks that depend on each other in the framework design logic. If there are mutual dependencies, which Task should be executed first?

As shown in the above figure, there are only two scenarios:

Mutual Dependency: TaskB and TaskD have mutual dependencies, so the execution order cannot be determined;
Circular Dependency: TaskD, TaskF, TaskG, and TaskE form a dependency cycle, and the execution order cannot be determined;

Determining mutual dependencies is relatively simple, just check if TaskA that TaskB depends on also depends on TaskA. Determining circular dependencies is relatively more complex, requiring traversing all paths of the graph. If a closed loop exists in the path, it means that a cycle exists. Otherwise, there is no loop, indicating a unidirectional dependent branch path.

How to Divide Concurrent Groups#

Dividing concurrent groups means grouping Tasks that have no dependency relationship according to the order of dependencies, which is actually depth-first traversal of the graph.

Due to the existence of dependency relationships, upward traversal or downward traversal can be used. We use a stack-based approach:

Upward Traversal#

First, find the Tasks that are not dependent on other Tasks, which is a group, and then store them in an array and push them to the bottom of the stack;
Collect the Tasks that depend on the bottom of the stack, and determine if these collected Tasks are also dependent on other Tasks. If they are dependent, save them in a temporary Task array. Finally, the remaining Tasks are the Tasks that are only dependent on the Task array at the bottom of the stack, so continue to push this group into the stack;
Repeat step 2, replacing the Task array at the bottom of the stack with the topmost array in the stack, and then append the temporary Tasks to the collected dependent Tasks, remove duplicates, and repeat;
Finally, when there are Tasks left that do not depend on any Tasks, this is the last concurrent group, and then push it into the stack;

When the program is executed, the top of the stack is the first concurrent group to be executed, and then it is executed by popping the stack.

Downward Traversal#

First, find the Tasks that do not depend on other Tasks, which is a group, and then store them in an array and push them to the bottom of the stack;
Collect the Tasks that depend on this group, and determine if these collected Tasks are also dependent on other Tasks. If they are dependent, save them in a temporary Task array. Finally, only the Tasks that are dependent on the Task array at the bottom of the stack are left, and then push this array into the stack;
Repeat step 2, replacing the Task array at the bottom of the stack with the topmost array in the stack, and then append the temporary Tasks to the collected dependent Tasks, remove duplicates, and repeat;
Finally, when there are no Tasks dependent on the remaining Tasks, this is the last concurrent group, and then push it into the stack;

At this time, the stack stores the concurrent groups to be executed first at the bottom of the stack and the last to be executed at the top. It needs to be reversed and then executed in order.

Why Use the "Strategy Pattern"#

When developing programs, everyone pays attention to the horizontal scalability of the program without agreement. The key tasks are split into specific execution sub-tasks, which not only improves the readability of the program, but also allows for the extension of different traversal algorithms for continuous optimization of the framework in the future.

Not only that, the Phoenix framework tries to use the strategy pattern as much as possible to implement the core functionality, and modular design is achieved for the core functional points. This design is exactly the original intention of the Phoenix framework, which is constantly iterating and evolving.

Conclusion#

This article mainly explains the ideas and problems encountered in automatically building a directed acyclic graph. In fact, in development, there are many scenarios for solving dependency relationships. Regardless of the implementation of upper-level business or framework requirements, the bottom line is the most basic data structure and algorithm. Graph traversal scenarios are also the same in the current popular AI scenarios.

Thank you for reading. If you have good solutions or ideas, you can communicate with me. Finally, if you are interested, I recommend following the official account or subscribing to this site. Welcome to interact and communicate. Let's become stronger together~