Branch‑Path Graph Scheduling Framework for Vivo Real‑Time Advertising Estimation Service

This article, based on Zhou Baojian’s talk at the 2022 Vivo Developer Conference, introduces a graph‑based scheduling framework that supports branch paths, addressing the scalability limitations of traditional finite‑directed‑graph (FDG) scheduling in online services.

In vivo’s real‑time advertising estimation service, which handles billions of daily requests, relies on numerous downstream components (feature services, AB testing platform, streaming data, model computation, etc.). The service uses asynchronous calls, making scheduling complex. Historically, three asynchronous management approaches have been used:

Procedural method – simple but leads to tangled callback code as downstream services grow.

Tree scheduling – improves extensibility but cannot accurately represent complex call flows.

Finite directed‑graph (FDG) – widely adopted, offers better extensibility, yet struggles with managing branch paths because it treats the graph as a full‑path schedule.

To illustrate FDG’s limitations, the article abstracts the scheduling flow of the ad estimation service, showing that as nodes increase, the number of possible paths and state variables grows exponentially, making the system hard to control.

Consequently, a new branch‑path graph scheduling framework is proposed. It augments the existing graph scheduler with two features: (1) introduction of branch nodes, and (2) support for “AND” and “OR” activation semantics for node triggering, akin to logical circuits. This transforms the FDG (an NFA) into a deterministic finite automaton (DFA), dubbed DDAG (Deterministic Directed Acyclic Graph).

The implementation replaces the skip‑state variable used in FDG with explicit branch logic, eliminating the exponential growth of control variables. Visual diagrams (included in the original article) compare the original full‑path graph with the revised branch‑path graph, highlighting clearer path selection and reduced state management.

In the vivo ad estimation service, the revised framework was applied to a simplified scheduling flow. After migration, branch nodes and conditional logic made the three distinct execution paths (blue, cyan, red) explicit, removing numerous skip variables and improving readability and maintainability.

Further benefits observed include easier timeout and exception handling, and potential for automated graph simplification. The branch‑path framework helped engineers lower development risk and accelerate iteration, enhancing the overall efficiency of the advertising prediction service.

Overall, the branch‑path graph scheduling framework offers a more scalable and maintainable solution for asynchronous scheduling in large‑scale backend systems.