Package jline.api.fj

Class FJ_tail_ordstat

java.lang.Object
jline.api.fj.FJ_tail_ordstat
public class FJ_tail_ordstat extends Object
Tail latency of a k-of-n (quorum) fork-join request.

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 FJ_tail_forktail.geFit(double, double). 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, which adds no cancellation, and inverted by bisection. At KREQ = N it reduces term by term to prod_i F_i(x), the product of the branch CDFs that ForkTail inverts, so a full join evaluates exactly as it did before this class existed.

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.

Port of matlab/src/api/fj/fj_tail_ordstat.m.

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.

  • Method Summary

    Modifier and Type
    Method
    Description
    static double
    fj_tail_ordstat(double[] ET, double[] VT, double p, int kreq)
    Tail latency of a quorum request over heterogeneous branches, one entry per branch.
    static double
    fj_tail_ordstat(double ET, double VT, int K, double p, int kreq)
    Tail latency of a quorum request over K identical branches.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • fj_tail_ordstat

      public static double fj_tail_ordstat(double ET, double VT, int K, double p, int kreq)
      Tail latency of a quorum request over K identical branches.
      Parameters:
      ET - mean task response time of a branch
      VT - variance of the task response time of a branch
      K - number of branches
      p - percentile, a fraction in (0,1) or a percentage in (0,100)
      kreq - the join fires on the kreq-th branch
      Returns:
      the predicted p-th percentile of the request response time

    • fj_tail_ordstat

      public static double fj_tail_ordstat(double[] ET, double[] VT, double p, int kreq)
      Tail latency of a quorum request over heterogeneous branches, one entry per branch.
      Parameters:
      ET - mean task response time per branch
      VT - variance of the task response time per branch
      p - percentile, a fraction in (0,1) or a percentage in (0,100)
      kreq - the join fires on the kreq-th branch
      Returns:
      the predicted p-th percentile of the request response time