fj_tail_forktail.h File Reference

ForkTail black-box tail-latency approximation for fork-join requests. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/fj/fj_types.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/rootfind.h"

Include dependency graph for fj_tail_forktail.h:

Go to the source code of this file.

Classes
struct	line::fj::ForkTailResult< T >
	Mirrors MATLAB's [xp, alpha, beta] return list. More...

Namespaces
namespace	line
namespace	line::fj

Functions
template<class T>
ForkTailResult< T >	line::fj::fj_tail_forktail (const std::vector< T > &ET, const std::vector< T > &VT, const std::vector< T > &K=std::vector< T >(), const T &p_in=num_traits< T >::from_int(99), const std::vector< T > &P=std::vector< T >())
	ForkTail black-box tail-latency approximation for fork-join requests.
template<class T>
ForkTailResult< T >	line::fj::fj_tail_forktail (const T &ET, const T &VT, const T &K, const T &p=num_traits< T >::from_int(99))
	Homogeneous convenience overload with a scalar mean, variance and fanout.

Detailed Description

ForkTail black-box tail-latency approximation for fork-join requests.

Templated port of matlab/src/api/fj/fj_tail_forktail.m. No JAR counterpart. Approximates the p-th percentile of the response time of a request that forks into K parallel tasks and joins on the last of them, from the mean and variance of the per-branch task response times ALONE. Each branch is a black box whose response time is fitted by a generalized exponential law

F_T(x) = (1 - exp(-x/beta))^alpha, E[T] = beta (psi(alpha+1) - psi(1)), V[T] = beta^2 (psi'(1) - psi'(alpha+1)),

and the request response time is the maximum over the branches, taken as the PRODUCT of the branch CDFs. That product is exact only for independent branches, which is the approximation the method rests on.

Three routes, exactly as in MATLAB:

• homogeneous (one branch mean, scalar K): the product of K identical CDFs raises the shape to K alpha and inverts in closed form, x_p = -beta log(1 - p^(1/(K alpha))).
• random fanout (one branch mean, K a vector with probabilities P): the request law is the mixture sum_i P_i (1-exp(-x/beta))^(K_i alpha), bracketed between the closed forms at min(K) and max(K) and inverted numerically.
• heterogeneous (a vector of branch means): solve sum_i alpha_i log1p(-exp(-x/beta_i)) = log p. F_X is bounded above by the CDF of any single branch, so the request percentile is at least the largest branch percentile, which is where the bracket search starts.

This is a HIGH-LOAD result, from the central limit theorem for G/G/m queues in heavy traffic: the reference reports errors within 20% and 15% at 80% and 90% utilization and makes no claim at low load, where the tail is dominated by the service law and the branch dependence is strongest.

Reference: M. Nguyen, S. Alesawi, N. Li, H. Che, H. Jiang, "ForkTail: A Black-Box Fork-Join Tail Latency Prediction Model for User-Facing Datacenter Workloads", ACM HPDC 2018, pp. 206-217.

ARITHMETIC: the generalized-exponential fit inverts a ratio of digamma and trigamma values, so the exact instantiation is refused.

Definition in file fj_tail_forktail.h.