IDENTIFYING REQUEST-LEVEL CRITICAL PATHS IN MULTI-PHASE PARALLEL TASKS
The disclosed embodiments provide a system for processing data. During operation, the system obtains a set of latencies for a set of requests in a multi-phase parallel task. Next, the system includes the latencies in a graph-based representation of the multi-phase parallel task. The system then analyzes the graph-based representation to identify a set of high-latency paths in the multi-phase parallel task. Finally, the system uses the set of high-latency paths to output an execution profile for the multi-phase parallel task, wherein the execution profile includes a subset of the requests associated with the high-latency paths.
1 . A method, comprising;
obtaining a set of latencies for a set of requests in a multi-phase parallel task;
including the latencies in a graph-based representation of the multi-phase parallel task;
analyzing, by a computer system, the graph-based representation to identify a set of high-latency paths in the multi-phase parallel task; and
using the set of high-latency paths to output an execution profile for the multi-phase parallel task, wherein the execution profile comprises a subset of the requests associated with the high-latency paths.
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 request 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;
a change in a performance metric over time; and
a potential improvement associated with the request.
4 . The method of claim 3 , wherein using the set of latencies to calculate the set of performance metrics associated with the high-latency paths comprises:
obtaining a first statistic associated with a slowest request in a phase of the multi-phase parallel task and a second statistic associated with a second-slowest request in the phase; and
calculating the potential improvement associated with the slowest request using a difference between the first and second statistics and the frequency of occurrence of the slowest request in the phase.
5 . The method of claim 1 , wherein analyzing the graph-based representation to identify the set of high-latency paths in the multi-phase parallel task comprises:
identifying a first request with a highest latency in a first phase of the multi-phase parallel task;
identifying, for a path comprising the first request in the multi-phase parallel task, a second request with the highest latency in a second phase of the multi-phase parallel task; and
including the first and second requests in a high-latency path of the multi-phase parallel task.
6 . The method of claim 1 , wherein obtaining the set of latencies for the set of requests in the multi-phase parallel task comprises:
for each request in the set of requests, obtaining a start time and an end time from a trace of the request.
7 . The method of claim 1 , wherein the multi-phase parallel task is used to generate a ranking of content items in a content feed.
8 . The method of claim 7 , wherein the set of requests comprises:
a request to a query data proxy for a set of parameters used to generate the content feed.
9 . The method of claim 7 , wherein the set of requests comprises:
a request to a first-pass ranker for a set of content items in the content feed.
10 . The method of claim 7 , wherein the set of requests comprises:
a request to a feature proxy for a set of features used to generate the content feed.
11 . The method of claim 1 , wherein the graph-based representation comprises a directed acyclic graph (DAG).
12 . The method of claim 1 , wherein the set of high-latency paths comprises:
a slowest path in the multi-phase parallel task; and
a second-slowest path in the multi-phase parallel task.
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:
obtain a set of latencies for a set of requests in a multi-phase parallel task;
include the latencies in a graph-based representation of the multi-phase parallel task;
analyze the graph-based representation to identify a set of high-latency paths in the multi-phase parallel task; and
use the set of high-latency paths to output an execution profile for the multi-phase parallel task, wherein the execution profile comprises a subset of the requests associated with the high-latency paths.
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 request 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;
a change in a performance metric over time; and
a potential improvement associated with the request.
16 . The apparatus of claim 15 , wherein using the set of latencies to calculate the set of performance metrics associated with the high-latency paths comprises:
obtaining a first statistic associated with a slowest request in a phase of the multi-phase parallel task and a second statistic associated with a second-slowest request in the phase; and
calculating the potential improvement associated with the slowest request using a difference between the first and second statistics and the frequency of occurrence of the slowest request in the phase.
17 . The apparatus of claim 13 , wherein analyzing the graph-based representation to identify the set of high-latency paths in the multi-phase parallel task comprises:
identifying a first request with a highest latency in a first phase of the multi-phase parallel task;
identifying, for a path comprising the first request in the multi-phase parallel task, a second request with the highest latency in a second phase of the multi-phase parallel task; and
including the first and second requests in a high-latency path of the multi-phase parallel task.
18 . The apparatus of claim 13 , wherein the set of requests comprises:
a request to a query data proxy for a set of parameters used to generate a content feed;
a request to a first-pass ranker for a set of content items in the content feed; and
a request to a feature proxy for a set of features used to generate the content feed.
19 . A system, comprising:
an analysis module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to:
obtain a set of latencies for a set of requests in a multi-phase parallel task;
include the latencies in a graph-based representation of the multi-phase parallel task;
analyze the graph-based representation to identify a set of high-latency paths in the multi-phase parallel task; 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 output an execution profile for the multi-phase parallel task, wherein the execution profile comprises a subset of the requests associated with the high-latency paths.
20 . The system of claim 19 , wherein analyzing the graph-based representation to identify the set of high-latency paths in the multi-phase parallel task comprises:
identifying a first request with a highest latency in a first phase of the multi-phase parallel task;
identifying, for a path comprising the first request in the multi-phase parallel task, a second request with the highest latency in a second phase of the multi-phase parallel task; and
including the first and second requests in a high-latency path of the multi-phase parallel task.