5D Library › 零人工多站点容错架构、支付防欺诈状态机与被动现金流排队论 · English
第四章 三十个站点共用一个内核:排队与尾延迟
平均值骗人
30 个站点共用一套程序内核,好处是一次修改处处生效,代价是所有站点的请求排在同一个队伍里。对用户而言要紧的不是平均等待,而是最慢的那一小部分请求:大规模服务的经验是,尾延迟(例如第 99 百分位的响应时间 T99)决定了用户感受,而尾延迟对排队极其敏感 (Dean and Barroso 2013)。
排队论给出了平均等待的精确公式。对泊松到达、一般服务时间的单服务台队列(M/G/1),Pollaczek-Khinchine 公式给出平均等待 ,其中 是负载 (Kleinrock 1975)。注意分子是服务时间的二阶矩:服务时间越参差,排队越久。处理器共享(PS)是另一种排法:所有在场的请求平分处理能力,短请求不必等长请求做完 (Harchol-Balter 2013)。
一个工作进程
程序设服务时间服从对数正态分布,平均 40 毫秒、变异系数 1.5,因此 平方秒。到达有两种:泊松到达,以及突发到达——平均每 120 秒出现一次、平均持续 10 秒、到达率翻四倍的突发(马尔可夫调制泊松过程),基准到达率相应调低,使长期负载不变。
推导
# 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.即使是泊松到达,单个工作进程在一半负载时 T99 也有 726 毫秒,超过 500 毫秒的目标;原因是服务时间本身就有长尾,单个请求的第 99 百分位就有 277 毫秒。公式给出的平均等待(负载 0.50 时 65.0 毫秒)与模拟(62.8 毫秒)相符。
突发改变的是数量级。负载同为 0.50,突发到达下的平均等待是 2946.2 毫秒,T99 达到 27006 毫秒:四倍的到达持续十秒,工作进程在突发期间超载,积压的工作要很久才能消化。这时决定 T99 的是突发时的积压,而不是平均负载。处理器共享在泊松到达下略好(T99 648 对 726),在突发下反而更差(31926 对 27006):它把处理能力分给了所有请求,长请求被拖得更久。PS 改变的是谁先谁后,不能增加处理能力。
要几个工作进程
现在设 30 个站点合计每秒 20 个请求(相当于单个工作进程负载 0.80),由 个工作进程共用一个先到先服务的队列(M/G/c)。
推导
# 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.泊松到达下,2 个工作进程就能让 T99 降到 500 毫秒以内;突发到达下需要 4 个。3 个工作进程在突发下 T99 是 514 毫秒,刚好超标。另一种办法是限流:3 个工作进程,队伍超过 个请求时,新请求立即返回「服务繁忙」(HTTP 503)。 时只拒绝 0.0005 的请求,其余请求的 T99 是 470 毫秒; 时拒绝 0.0188,T99 降到 289 毫秒。
这把一个隐含的选择变成了明确的选择:要么多付一个工作进程的钱,要么在突发时拒绝极少数请求。两者都比「平均负载才 0.80,应该没问题」要好;后者会在突发时让所有请求一起变慢。
假说 · 尚未验证
作者的诠释(尚未验证): 作者的站群流量主要来自社交媒体的集中转发,突发比本书的设定(每 120 秒一次、持续 10 秒、四倍)更集中;因此共享内核应当按突发而不是平均负载配置工作进程,并设置队列上限。什么会证明这一判断错:若实际的访问日志显示到达过程接近泊松(例如每秒请求数的方差与均值相近),那么按平均负载配置即可,突发的担心是多余的。
小结
服务时间的长尾使单个工作进程在一半负载时就达不到 500 毫秒的 T99;突发到达把 T99 推到数十秒,决定它的是积压而不是平均负载。处理器共享不能增加能力。在本书的参数下,泊松到达需要 2 个工作进程,突发需要 4 个;或者用 3 个工作进程加队列上限,以拒绝 0.0005 的请求换取 470 毫秒的 T99。
参考文献
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).