Tail latency of a k-of-n (QUORUM) fork-join request. More...

#include <cmath>
#include <cstddef>
#include <vector>
#include "line/api/fj/fj_tail_forktail.h"

Include dependency graph for fj_tail_ordstat.h:

Namespaces
namespace	line
namespace	line::fj

Functions
template<class T>
ForkTailResult< T >	line::fj::fj_tail_ordstat (const std::vector< T > &ET, const std::vector< T > &VT, std::size_t K=1, const T &p_in=num_traits< T >::from_int(99), std::size_t kreq=0)
	Tail latency of a k-of-n (QUORUM) fork-join request.

Detailed Description

Tail latency of a k-of-n (QUORUM) fork-join request.

Templated port of matlab/src/api/fj/fj_tail_ordstat.m, mirrored by jline.api.fj.FJ_tail_ordstat. The request forks into N parallel tasks and joins on the KREQ-th of them: KREQ = N is the ordinary AND-join and reproduces fj_tail_forktail EXACTLY, KREQ = 1 is the first completion.

Each branch is the same black box ForkTail uses – its task response time is fitted by a generalized exponential law F_i(x) = (1-exp(-x/beta_i))^alpha_i matched on the branch mean and variance by detail::ge_fit – and the request completes once KREQ of the N branches have, so its law is the KREQ-th ORDER STATISTIC of independent, not identically distributed branch times,

F_X(x) = P(at least KREQ of the N branches are done by x),

the upper tail of a Poisson-binomial with success probabilities F_i(x). It is evaluated by the convolution recurrence over the branches, whose terms are all non-negative so it adds no cancellation, and inverted by bisection.

THE BRACKET IS STRUCTURAL, not searched: X_(KREQ) lies between the FIRST completion and the LAST, so the smallest single-branch percentile bounds it below and the AND-join percentile – which is what fj_tail_forktail returns – bounds it above.

At KREQ = N the recurrence reduces TERM BY TERM to prod_i F_i(x), so a full join evaluates exactly as it did before this header existed; the code returns the ForkTail root directly there rather than re-deriving it.

BRANCH INDEPENDENCE is assumed, as in ForkTail: the branches of one request are positively correlated through their shared arrival instant, so the true quorum percentile is somewhat larger than this one. The same heavy-traffic caveat applies, see fj_tail_forktail.h.

References: 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, for the branch law; A. Thomasian, "Analysis of Fork/Join and Related Queueing Systems", ACM Computing Surveys 47(2), Article 17, 2014, Sec. 3, for the quorum.

Definition in file fj_tail_ordstat.h.

Namespaces

Functions

Detailed Description