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 , where 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 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 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.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 waiting is refused at once (“service busy”, HTTP 503). At only 0.0005 of requests are refused and T99 for the rest is 470 ms; at , 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
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).