Automatically detecting latency bottlenecks in asynchronous workflows

Patent metadata

Field	Value
Publication number	US-2018123918-A1
Application number	US-201615337567-A
Country	US
Kind code	A1
Filing date	Oct 28, 2016
Priority date	Oct 28, 2016
Publication date	May 3, 2018
Grant date	—

Abstract

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.

First claim

What is claimed is:

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.

Assignees

• Linkedin Corp

Inventors

• Steinhauser Antonin
• Li Wing H
• Gong Jiayu
• Long Xiaohui
• Young Joel D

Classifications

• H04L43/10

  Active monitoring, e.g. heartbeat, ping or trace-route · CPC title

• H04L43/0858 Primary

  One way delays · CPC title

• H04L41/142

  using statistical or mathematical methods · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L43/045 Primary

  for graphical visualisation of monitoring data · CPC title