Package jline.api.fj

Class FJ_tail_forktail

java.lang.Object
jline.api.fj.FJ_tail_forktail
public final class FJ_tail_forktail extends Object
ForkTail black-box tail-latency approximation for fork-join requests.

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 treated as a black box: its task 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 (exact only for independent branches): 
   F_X(x) = prod_i (1 - exp(-x/beta_i))^alpha_i,   x_p = F_X^{-1}(p)
   homogeneous: x_p = -beta*log(1 - p^(1/(K*alpha)))
   random fanout: F_X(x) = sum_i P_i * (1 - exp(-x/beta))^(K_i*alpha)

The approximation rests on the central limit theorem for G/G/m queues in heavy traffic, so it is a HIGH-LOAD result: the reference reports errors within 20% and 15% at 80% and 90% utilization respectively, and makes no claim at low load, where the tail is dominated by the service law rather than by queueing. Prefer the FJ_codes route (see FJValidation.isHomogeneous(jline.lang.NetworkStruct)) when the model is in the homogeneous MAP/PH/1 class, which is more accurate there; ForkTail covers the heterogeneous branches and mixed service laws that route rejects.

Port of matlab/src/api/fj/fj_tail_forktail.m and matlab/src/api/fj/fj_mg1_respt_moments.m.

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.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    static class 
    FJ_tail_forktail.GEFit
    Fitted generalized-exponential parameters of one branch.
    static class 
    FJ_tail_forktail.ResptMoments
    Mean and variance of a branch response time.

  • Method Summary

    Modifier and Type
    Method
    Description
    static FJ_tail_forktail.ResptMoments
    fj_mg1_respt_moments(double lambda, double ES, double ES2, double ES3)
    Mean and variance of the M/G/1 FCFS response time, the white-box inputs of ForkTail, from the first three moments of the service time.
    static double
    fj_tail_forktail(double[] ET, double[] VT, double p)
    Tail latency of a request forked over heterogeneous branches, one entry per branch.
    static double
    fj_tail_forktail(double ET, double VT, int[] K, double[] P, double p)
    Tail latency when the fanout itself is random: a request spawns K[i] tasks with probability P[i], over identical branches.
    static double
    fj_tail_forktail(double ET, double VT, int K, double p)
    Tail latency of a request forked over K identical branches.
    static FJ_tail_forktail.GEFit
    geFit(double ET, double VT)
    Matches a generalized exponential law on a mean and a variance.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • fj_mg1_respt_moments

      public static FJ_tail_forktail.ResptMoments fj_mg1_respt_moments(double lambda, double ES, double ES2, double ES3)
      Mean and variance of the M/G/1 FCFS response time, the white-box inputs of ForkTail, from the first three moments of the service time.
      Parameters:
      lambda - arrival rate at the branch
      ES - first moment of the service time
      ES2 - second moment of the service time
      ES3 - third moment of the service time
      Returns:
      the response time mean and variance

    • fj_tail_forktail

      public static double fj_tail_forktail(double ET, double VT, int K, double p)
      Tail latency of a request forked 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)
      Returns:
      the predicted p-th percentile of the request response time

    • fj_tail_forktail

      public static double fj_tail_forktail(double[] ET, double[] VT, double p)
      Tail latency of a request forked 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)
      Returns:
      the predicted p-th percentile of the request response time

    • fj_tail_forktail

      public static double fj_tail_forktail(double ET, double VT, int[] K, double[] P, double p)
      Tail latency when the fanout itself is random: a request spawns K[i] tasks with probability P[i], over identical branches.
      Parameters:
      ET - mean task response time of a branch
      VT - variance of the task response time of a branch
      K - distinct fanouts
      P - probabilities of those fanouts, summing to one
      p - percentile, a fraction in (0,1) or a percentage in (0,100)
      Returns:
      the predicted p-th percentile of the request response time

    • geFit

      public static FJ_tail_forktail.GEFit geFit(double ET, double VT)
      Matches a generalized exponential law on a mean and a variance. The squared coefficient of variation depends on the shape alone and decreases monotonically in it, so the shape is recovered by a scalar root-find on a logarithmic scale and the scale then follows in closed form. SCV = 1 is the exponential case alpha = 1, kept exact.
      Parameters:
      ET - mean of the branch response time
      VT - variance of the branch response time
      Returns:
      the fitted shape and scale