5D Library › Zero-Touch Multi-Site Fault Tolerance, Payment Anti-Fraud State Machines and Passive Cashflow Queuing · 中文

Chapter 4. Thirty Sites on One Kernel: Queues and Tail Latency

Averages deceive

When 30 sites share one program kernel, a change made once takes effect everywhere, but the requests of every site wait in the same queue. What matters to users is not the mean wait but the slowest small share of requests: experience with large-scale services is that tail latency (the 99th-percentile response time, T99, for instance) sets what users feel, and that the tail is extremely sensitive to queueing (Dean and Barroso 2013).

Queueing theory gives an exact formula for the mean wait. For a single-server queue with Poisson arrivals and general service times (M/G/1), the Pollaczek-Khinchine formula gives a mean wait of Wq=λE[S2]/(2(1−ρ))W_q = \lambda E[S^2]/(2(1-\rho)), where ρ\rho is the load (Kleinrock 1975). Note the second moment of service time in the numerator: the more uneven the service times, the longer the queue. Processor sharing (PS) is another discipline: all requests present share the capacity equally, so short requests need not wait for long ones to finish (Harchol-Balter 2013).

One worker

The program draws service times from a lognormal distribution with mean 40 ms and coefficient of variation 1.5, so E[S2]=0.0052E[S^2] = 0.0052 square seconds. Arrivals come in two kinds: Poisson, and bursty – bursts that come every 120 s on average, last 10 s on average and quadruple the arrival rate (a Markov-modulated Poisson process), with the base rate lowered so that the long-run load is unchanged.

Calculation

# Chapter 4. [p07] Thirty sites, one kernel: M/G/1 and bursty arrivals.
# Requests from 30 sites share one worker. Service times are lognormal
# with mean 40 ms and coefficient of variation 1.5, so E[S^2] = 0.0052
# s^2. For Poisson arrivals the Pollaczek-Khinchine formula gives the
# mean wait Wq = lam E[S^2] / (2 (1 - rho)). The program then simulates
# 200,000 requests under first-come-first-served (FCFS) and processor
# sharing (PS), with Poisson arrivals and with bursts: arrivals switch
# to 4 times the base rate for an exponential 10 s on average, every
# 120 s on average (a Markov-modulated Poisson process), the base rate
# scaled so the long-run load is still rho. Reported: mean wait and the
# 99th percentile of response time, T99, in milliseconds.
import math
import random

MEAN, CV = 0.040, 1.5
SIG = math.sqrt(math.log(1 + CV * CV))
MU = math.log(MEAN) - SIG * SIG / 2
ES2 = MEAN * MEAN * (1 + CV * CV)

def arrivals(rng, n, rho, burst):
    lam = rho / MEAN
    base = lam / ((120 + 4 * 10) / 130) if burst else lam
    t, out, hot, until = 0.0, [], False, 0.0
    if burst:
        until = rng.expovariate(1 / 120)
    while len(out) < n:
        rate = base * (4 if hot else 1)
        dt = rng.expovariate(rate)
        if burst and t + dt > until:
            t, hot = until, not hot
            until = t + rng.expovariate(1 / (10 if hot else 120))
            continue
        t += dt
        out.append((t, rng.lognormvariate(MU, SIG)))
    return out

def fcfs(jobs):
    free, resp = 0.0, []
    for a, s in jobs:
        start = max(a, free)
        free = start + s
        resp.append(free - a)
    return resp

def ps(jobs):
    resp, active, t, i = [], [], 0.0, 0
    while i < len(jobs) or active:
        nxt_a = jobs[i][0] if i < len(jobs) else math.inf
        if active:
            k = len(active)
            m = min(r for r, _ in active)
            t_done = t + m * k
        else:
            t_done = math.inf
        if nxt_a <= t_done:
            if active:
                d = (nxt_a - t) / len(active)
                active = [(r - d, a) for r, a in active]
            t = nxt_a
            active.append((jobs[i][1], nxt_a))
            i += 1
        else:
            d = (t_done - t) / len(active)
            t = t_done
            keep = []
            for r, a in active:
                if r - d <= 1e-12:
                    resp.append(t - a)
                else:
                    keep.append((r - d, a))
            active = keep
    return resp

def p99(x):
    return sorted(x)[int(0.99 * len(x))]

if __name__ == "__main__":
    rng = random.Random(75007)
    s99 = math.exp(MU + 2.3263 * SIG)
    print("   service time alone: mean 40 ms, S99 {:.0f} ms".format(
        1000 * s99))
    print("   rho  PK mean wait   arrivals  FCFS mean  FCFS T99   PS T99")
    for rho in (0.5, 0.7, 0.85):
        pk = (rho / MEAN) * ES2 / (2 * (1 - rho))
        for burst in (False, True):
            jobs = arrivals(rng, 200000, rho, burst)
            f = fcfs(jobs)
            wq = sum(r for r in f) / len(f) - MEAN
            print("   {:4.2f} {:11.1f} {:>10s} {:10.1f} {:9.0f} {:8.0f}"
                  .format(rho, 1000 * pk, "burst" if burst else "poisson",
                1000 * wq, 1000 * p99(f), 1000 * p99(ps(jobs))))
    print("\nReading: even with Poisson arrivals one worker misses a")
    print("500 ms T99 at half load, because the service time's own tail")
    print("is long. Bursts change the scale: four-fold arrivals for ten")
    print("seconds push the worker past saturation, and the backlog, not")
    print("the average load, sets T99 - tens of seconds, not tenths.")
    print("Processor sharing reorders the queue; it cannot add capacity.")
#    service time alone: mean 40 ms, S99 277 ms
#    rho  PK mean wait   arrivals  FCFS mean  FCFS T99   PS T99
#    0.50        65.0    poisson       62.8       726      648
#    0.50        65.0      burst     2946.2     27006    31926
#    0.70       151.7    poisson      145.6      1158     1133
#    0.70       151.7      burst     5033.9     44062    56631
#    0.85       368.3    poisson      416.8      2719     2668
#    0.85       368.3      burst    14905.5     87927   115933
#
# Reading: even with Poisson arrivals one worker misses a
# 500 ms T99 at half load, because the service time's own tail
# is long. Bursts change the scale: four-fold arrivals for ten
# seconds push the worker past saturation, and the backlog, not
# the average load, sets T99 - tens of seconds, not tenths.
# Processor sharing reorders the queue; it cannot add capacity.

Even with Poisson arrivals, one worker at half load has a T99 of 726 ms, above a 500 ms target; the reason is that service times themselves have a long tail, with a 99th percentile of 277 ms for a single request. The formula’s mean wait (65.0 ms at load 0.50) agrees with the simulation (62.8 ms).

Bursts change the order of magnitude. At the same load of 0.50, the mean wait under bursty arrivals is 2946.2 ms and T99 reaches 27006 ms: four times the arrivals for ten seconds overload the worker during a burst, and the backlog takes a long time to clear. T99 is then set by the backlog of bursts, not by the average load. Processor sharing is slightly better under Poisson arrivals (T99 648 against 726) and worse under bursts (31926 against 27006): it spreads capacity over all requests and drags long ones out further. PS changes who goes first; it cannot add capacity.

How many workers?

Now let the 30 sites send 20 requests a second in total (a load of 0.80 on a single worker), served by cc workers sharing one first-come-first-served queue (M/G/c).

Calculation

# Chapter 4. [p08] How many workers for T99 < 500 ms, and load shedding.
# The 30 sites send 20 requests a second on average (the load of 0.80
# on one worker); service times as in p07 (lognormal, mean 40 ms, CV
# 1.5). Arrivals are Poisson or bursty (4 times the base rate for an
# exponential 10 s every 120 s on average, same long-run mean). c
# workers serve one FCFS queue (M/G/c). The program reports T99 for c =
# 1..8 and the smallest c meeting 500 ms. Then, with c = 3 and bursts,
# requests that find more than Q waiting are refused at once (HTTP
# 503): the refused share and the T99 of those served are reported.
import heapq
import math
import random

MEAN, CV, LAM = 0.040, 1.5, 20.0
SIG = math.sqrt(math.log(1 + CV * CV))
MU = math.log(MEAN) - SIG * SIG / 2

def arrivals(rng, n, burst):
    base = LAM / ((120 + 4 * 10) / 130) if burst else LAM
    t, out, hot = 0.0, [], False
    until = rng.expovariate(1 / 120) if burst else math.inf
    while len(out) < n:
        dt = rng.expovariate(base * (4 if hot else 1))
        if t + dt > until:
            t, hot = until, not hot
            until = t + rng.expovariate(1 / (10 if hot else 120))
            continue
        t += dt
        out.append((t, rng.lognormvariate(MU, SIG)))
    return out

def serve(jobs, c, qmax=None):
    free = [0.0] * c
    starts, resp, refused = [], [], 0
    for a, s in jobs:
        while starts and starts[0] <= a:
            heapq.heappop(starts)
        if qmax is not None and len(starts) > qmax:
            refused += 1
            continue
        f = heapq.heappop(free)
        st = max(a, f)
        heapq.heappush(free, st + s)
        if st > a:
            heapq.heappush(starts, st)
        resp.append(st + s - a)
    resp.sort()
    return resp[int(0.99 * len(resp))], refused / len(jobs)

if __name__ == "__main__":
    rng = random.Random(75008)
    pois = arrivals(rng, 300000, False)
    bur = arrivals(rng, 300000, True)
    print("    c   T99 poisson (ms)   T99 bursts (ms)")
    need = {}
    for c in range(1, 9):
        a, _ = serve(pois, c)
        b, _ = serve(bur, c)
        for k, v in (("poisson", a), ("burst", b)):
            if v < 0.5 and k not in need:
                need[k] = c
        print("   {:2d} {:18.0f} {:17.0f}".format(c, 1000 * a, 1000 * b))
    print("   smallest c for T99 < 500 ms: poisson {}, bursts {}".format(
        need.get("poisson"), need.get("burst")))
    print("   c = 3 with bursts, refuse when more than Q are waiting:")
    print("      Q   refused   T99 of served (ms)")
    for q in (5, 10, 20, 40):
        t99, ref = serve(bur, 3, q)
        print("     {:2d} {:9.4f} {:14.0f}".format(q, ref, 1000 * t99))
    print("\nReading: a queue that is fine on average is not fine in a")
    print("burst; meeting the tail target takes more workers than the")
    print("mean load suggests. Refusing a small share of requests at")
    print("the door during bursts keeps the rest fast - a choice the")
    print("site must make explicitly, not discover in an outage.")
#     c   T99 poisson (ms)   T99 bursts (ms)
#     1               1739             77741
#     2                325              9253
#     3                280               514
#     4                278               285
#     5                278               275
#     6                278               274
#     7                278               274
#     8                278               274
#    smallest c for T99 < 500 ms: poisson 2, bursts 4
#    c = 3 with bursts, refuse when more than Q are waiting:
#       Q   refused   T99 of served (ms)
#       5    0.0188            289
#      10    0.0094            312
#      20    0.0032            376
#      40    0.0005            470
#
# Reading: a queue that is fine on average is not fine in a
# burst; meeting the tail target takes more workers than the
# mean load suggests. Refusing a small share of requests at
# the door during bursts keeps the rest fast - a choice the
# site must make explicitly, not discover in an outage.
T99 against the number of workers, for Poisson and bursty arrivals. The dashed line is 500 ms. Log scale.

Under Poisson arrivals, 2 workers bring T99 below 500 ms; under bursts it takes 4. Three workers under bursts give a T99 of 514 ms, just over the line. The alternative is load shedding: with 3 workers, a new request that finds more than QQ waiting is refused at once (“service busy”, HTTP 503). At Q=40Q = 40 only 0.0005 of requests are refused and T99 for the rest is 470 ms; at Q=5Q = 5, 0.0188 are refused and T99 falls to 289 ms.

This turns an implicit choice into an explicit one: pay for one more worker, or refuse a very small share of requests during bursts. Either is better than “the average load is only 0.80, it should be fine”, which lets every request slow down together in a burst.

Hypothesis · not established

The author’s interpretation (not yet tested): traffic to the author’s sites comes mainly from concentrated social-media reposting, burstier than this book’s setting (every 120 s, lasting 10 s, four-fold); a shared kernel should therefore be sized by bursts rather than by average load and should have a queue limit. What would show this wrong: if real access logs showed arrivals close to Poisson (for example, a variance of requests per second close to its mean), sizing by average load would be enough and the worry about bursts would be needless.

Summary

The long tail of service times keeps one worker from a 500 ms T99 even at half load; bursty arrivals push T99 to tens of seconds, set by the backlog rather than the average load. Processor sharing cannot add capacity. With the book’s parameters Poisson arrivals need 2 workers and bursts 4; or 3 workers with a queue limit trade 0.0005 of requests refused for a T99 of 470 ms.

References

Dean, Jeffrey, and Luiz André Barroso. 2013. “The Tail at Scale.” Communications of the ACM 56 (2): 74–80.
Harchol-Balter, Mor. 2013. Performance Modeling and Design of Computer Systems: Queueing Theory in Action. Cambridge University Press.
Kleinrock, Leonard. 1975. Queueing Systems, Volume 1: Theory. Wiley.

Fan, Y. (2026). Zero-Touch Multi-Site Fault Tolerance, Payment Anti-Fraud State Machines and Passive Cashflow Queuing: Receipt-Hash Deduplication, Self-Referral Blocking, Host-Header Routing and Availability Bounds [零人工多站点容错架构、支付防欺诈状态机与被动现金流排队论] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090201 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).