AUTOMATICALLY DETECTING LATENCY BOTTLENECKS IN ASYNCHRONOUS WORKFLOWS
The disclosed embodiments provide a system for processing data. During operation, the system generates, from a set of traces of an asynchronous workflow, a graph-based representation of the asynchronous workflow. Next, the system uses a set of causal relationships in the asynchronous workflow to update the graph-based representation. The system then analyzes the updated graph-based representation to identify a set of high-latency paths in the asynchronous workflow. Finally, the system uses the set of high-latency paths to output an execution profile for the asynchronous workflow, wherein the execution profile includes a subset of tasks associated with the high-latency paths in the asynchronous workflow.
1 . A method, comprising:
generating, from a set of traces of an asynchronous workflow, a graph-based representation of the asynchronous workflow;
using a set of causal relationships in the asynchronous workflow to update the graph-based representation;
analyzing, by a computer system, the updated graph-based representation to identify a set of high-latency paths in the asynchronous workflow; and
using the set of high-latency paths to output an execution profile for the asynchronous workflow, wherein the execution profile comprises a subset of tasks associated with the high-latency paths in the asynchronous workflow.
2 . The method of claim 1 , further comprising:
using the set of latencies to calculate a set of performance metrics associated with the high-latency paths; and
including the performance metrics in the outputted execution profile.
3 . The method of claim 2 , wherein the set of performance metrics comprises at least one of:
a frequency of occurrence of a task in the high-latency paths;
a maximum value associated with the set of latencies;
a percentile associated with the set of latencies;
a median associated with the set of latencies; and
a change in a performance metric over time.
4 . The method of claim 2 , wherein the outputted execution profile comprises an ordered list of the tasks with highest latency in the high-latency paths.
5 . The method of claim 1 , wherein the set of causal relationships comprise:
a predecessor-successor relationship; and
a parent-child relationship.
6 . The method of claim 5 , wherein using the set of causal relationships in the asynchronous workflow to update the graph-based representation comprises:
identifying the parent-child relationship between a parent task and a child task executed by the parent task;
separating the parent task into a front task and a back task; and
replacing the parent task and the child task in the graph-based representation with a path comprising the front task followed by the child task followed by the back task.
7 . The method of claim 6 , wherein using the set of causal relationships in the asynchronous workflow to update the graph-based representation further comprises:
placing, in the path, a predecessor task of the parent task before the front task and a successor task of the parent task after the back task.
8 . The method of claim 5 , wherein using the set of causal relationships in the asynchronous workflow to update the graph-based representation comprises:
identifying the predecessor-successor relationship between a successor task that begins executing after a predecessor task stops executing; and
updating the graph-based representation with an edge between the predecessor and successor tasks.
9 . The method of claim 1 , wherein analyzing the updated graph-based representation to identify the set of high-latency paths in the asynchronous workflow comprises:
using a topological sort of the updated graph-based representation to identify the set of high-latency paths.
10 . The method of claim 1 , wherein the set of high-latency paths comprises a critical path in the asynchronous workflow.
11 . The method of claim 1 , wherein the set of traces comprises a start time and an end time for each task in the asynchronous workflow.
12 . The method of claim 1 , wherein the graph-based representation comprises a directed acyclic graph (DAG).
13 . An apparatus, comprising:
one or more processors; and
memory storing instructions that, when executed by the one or more processors, cause the apparatus to:
generate, from a set of traces of an asynchronous workflow, a graph-based representation of the asynchronous workflow;
use a set of causal relationships in the asynchronous workflow to update the graph-based representation;
analyze the updated graph-based representation to identify a set of high-latency paths in the asynchronous workflow; and
use the set of high-latency paths to output an execution profile for the asynchronous workflow, wherein the execution profile comprises a subset of tasks associated with the high-latency paths in the asynchronous workflow.
14 . The apparatus of claim 13 , wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:
use the set of latencies to calculate a set of performance metrics associated with the high-latency paths; and
include the performance metrics in the outputted execution profile.
15 . The apparatus of claim 14 , wherein the set of performance metrics comprises at least one of:
a frequency of occurrence of a task in the high-latency paths;
a maximum value associated with the set of latencies;
a percentile associated with the set of latencies;
a median associated with the set of latencies; and
a change in a performance metric over time.
16 . The apparatus of claim 13 , wherein the set of causal relationships comprise:
a predecessor-successor relationship; and
a parent-child relationship.
17 . The apparatus of claim 16 , wherein using the set of causal relationships in the asynchronous workflow to update the graph-based representation comprises:
identifying the parent-child relationship between a parent task and a child task executed by the parent task;
separating the parent task into a front task and a back task; and
replacing the parent task and the child task in the graph-based representation with a path comprising the front task followed by the child task followed by the back task.
18 . The apparatus of claim 17 , wherein using the set of causal relationships in the asynchronous workflow to update the graph-based representation further comprises:
placing, in the path, a predecessor task of the parent task before the front task and a successor task of the parent task after the back task.
19 . The apparatus of claim 13 , wherein analyzing the updated graph-based representation to identify the set of high-latency paths in the asynchronous workflow comprises:
using a topological sort of the updated graph-based representation to identify the set of high-latency paths.
20 . A system, comprising:
an analysis module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to:
generate, from a set of traces of an asynchronous workflow, a graph-based representation of the asynchronous workflow;
use a set of causal relationships in the asynchronous workflow to update the graph-based representation;
analyze the updated graph-based representation to identify a set of high-latency paths in the asynchronous workflow; and
a management module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to use the set of high-latency paths to use the set of high-latency paths to output an execution profile for the asynchronous workflow, wherein the execution profile comprises a subset of tasks associated with the high-latency paths in the asynchronous workflow.