5D Library › 零人工多站点容错架构、支付防欺诈状态机与被动现金流排队论 · English
第三章 订单状态机:穷举检验与幂等窗口
为什么要穷举
一张订单从新建到放行、核验、可能的拒付,要经过几个状态。处理这些状态的代码通常是一组「收到某个事件就做某件事」的函数。在真实的网络中,事件可能重复到达(发送方重试)、乱序到达(先到的是后发的)、在任意时刻到达。人工测试只会检查正常的顺序;而错误往往藏在不正常的顺序里。模型检验的思路是把系统写成有限的状态与转移,然后穷举所有可能的事件序列,检查每一个可达状态是否满足不变量 (Clarke et al. 1999)。
两套处理函数
程序给出两套处理函数。朴素版收到事件就执行,不看当前状态:收到「放行」就开放访问并支付佣金,收到「核验失败」就关闭访问,但不收回佣金。防护版用一张转移表:只有在允许的状态下才执行转移,访问只开放一次,佣金在核验通过后才支付,拒绝或拒付时一并收回。
要求的三个不变量是:I1 访问最多开放一次;I2 订单一旦被拒绝或拒付,就不能再有访问;I3 订单一旦被拒绝或拒付,就不能还有未收回的佣金。程序用广度优先搜索穷举长度不超过 8 的所有事件序列,并给出违反每条不变量的最短序列。
推导
# Chapter 3. [p05] Exhaustive model check of a payment-order state machine.
# States: NEW -> PEND (receipt uploaded) -> PROV (access released) ->
# OK (audit passed) | REJ (audit failed); OK -> REV (charge-back).
# Events: upload, release, pass, fail, chargeback. Any event may arrive
# at any time and any number of times (retries, duplicates, reordering).
# A state is (status, access, grants, commission, closed), where closed
# records that the order has ever been rejected or charged back.
# Two handler sets:
# NAIVE - acts on an event without checking the current status,
# pays commission at release, never claws it back;
# GUARDED - a transition table; grants only when access is off; pays
# commission at OK; claws it back at REJ or REV.
# Invariants: I1 grants <= 1; I2 no access once closed; I3 no commission
# outstanding once closed. Breadth-first search over all event strings
# up to length 8; the shortest violating string is printed.
from collections import deque
EVENTS = ("upload", "release", "pass", "fail", "chargeback")
def naive(s, e):
st, acc, gr, com, cl = s
if e == "upload":
return ("PEND", acc, gr, com, cl)
if e == "release":
return ("PROV", 1, gr + 1, 1, cl)
if e == "pass":
return ("OK", 1, gr + (0 if acc else 1), com, cl)
if e == "fail":
return ("REJ", 0, gr, com, 1)
return ("REV", 0, gr, com, 1)
ALLOWED = {("NEW", "upload"): "PEND", ("PEND", "release"): "PROV",
("PROV", "pass"): "OK", ("PROV", "fail"): "REJ",
("PEND", "fail"): "REJ", ("OK", "chargeback"): "REV"}
def guarded(s, e):
st, acc, gr, com, cl = s
nxt = ALLOWED.get((st, e))
if nxt is None:
return s
if nxt == "PROV" and not acc:
acc, gr = 1, gr + 1
if nxt == "OK":
com = 1
if nxt in ("REJ", "REV"):
acc, com, cl = 0, 0, 1
return (nxt, acc, gr, com, cl)
def check(step, depth=8):
start = ("NEW", 0, 0, 0, 0)
seen = {start: ()}
q = deque([start])
bad = {}
while q:
s = q.popleft()
path = seen[s]
st, acc, gr, com, cl = s
for name, ok in (("I1", gr <= 1), ("I2", not (cl and acc)),
("I3", not (cl and com))):
if not ok and name not in bad:
bad[name] = path
if len(path) == depth:
continue
for e in EVENTS:
t = step(s, e)
if t not in seen:
seen[t] = path + (e,)
q.append(t)
return len(seen), bad
if __name__ == "__main__":
for name, step in (("NAIVE", naive), ("GUARDED", guarded)):
n, bad = check(step)
print(" {}: {} reachable states, violated: {}".format(
name, n, " ".join(sorted(bad)) or "none"))
for inv in sorted(bad):
print(" {} shortest: {}".format(inv, " ".join(bad[inv])))
print("\nReading: the naive handlers break all three invariants")
print("with strings of two events - a duplicated release grants")
print("twice, a late release reopens a rejected order, and a")
print("commission paid at release survives a failed audit. The")
print("transition table admits no violation at any depth searched.")
# NAIVE: 88 reachable states, violated: I1 I2 I3
# I1 shortest: release release
# I2 shortest: fail release
# I3 shortest: release fail
# GUARDED: 7 reachable states, violated: none
#
# Reading: the naive handlers break all three invariants
# with strings of two events - a duplicated release grants
# twice, a late release reopens a rejected order, and a
# commission paid at release survives a failed audit. The
# transition table admits no violation at any depth searched.朴素版只用两个事件就能违反全部三条不变量:「放行、放行」开放了两次访问(I1);「核验失败、放行」让一张已被拒绝的订单重新获得访问(I2);「放行、核验失败」留下了一笔不该付的佣金(I3)。这三个序列在真实网络里都很普通:重复投递、迟到的消息、先放行后抽查。防护版只有 7 个可达状态,在搜索深度内没有任何违反。
穷举的价值在于它给出的是「在这个深度内没有反例」的保证,而不是「测了几个例子都没问题」。当然,这只是对模型的保证:模型之外的事情(例如数据库写入失败)需要另外检验。
重试与幂等键
支付通知(webhook)通常采用「至少一次」投递:发送方没收到确认就会重发,间隔逐次加倍(1、2、4……256 分钟)。接收方用幂等键记住已处理过的通知 (Gray and Reuter 1993);但键只保存一段时间(TTL),过期之后再来的副本会被当成新通知处理。程序模拟 100,000 笔订单:确认以 0.03 的概率随机丢失;每笔订单还有 0.05 的概率赶上接收方变慢(平均持续 30 分钟),这段时间内工作照做、确认却全部超时;另有 0.005 的概率被代理在约 0.05 秒后重发一次。
推导
# Chapter 3. [p06] At-least-once notices and the idempotency window.
# A payment notice (webhook) is retried until acknowledged: the sender
# waits 1, 2, 4, ..., 256 minutes between tries. A delivery that was
# processed is retried anyway when its acknowledgement is lost: with
# chance 0.03 at random, and throughout a receiver slow-down (chance
# 0.05 per order, lasting an exponential time of mean 30 minutes)
# during which work is done but every acknowledgement times out. With
# chance 0.005 a proxy also resends the first copy after about 0.05 s.
# The receiver keeps each idempotency key for a time-to-live (TTL); a
# copy arriving after the key has expired is processed again. Two
# copies within the 0.2 s it takes to process one notice both pass the
# key check unless the check-and-insert is atomic.
# 100,000 orders are simulated; duplicates processed per 100,000 are
# reported for each TTL, without and with an atomic check.
import random
GAPS = [2 ** i for i in range(9)]
def deliveries(rng):
slow = rng.expovariate(1 / 30) if rng.random() < 0.05 else -1.0
t, out = 0.0, []
for g in [0] + GAPS:
t += g
out.append(t)
if t >= slow and rng.random() >= 0.03:
break
if rng.random() < 0.005:
out.insert(1, rng.expovariate(1 / 0.05) / 60)
return out
if __name__ == "__main__":
rng = random.Random(75006)
orders = [deliveries(rng) for _ in range(100000)]
dup = sum(len(o) - 1 for o in orders if o)
print(" retry schedule spans {} minutes".format(sum(GAPS)))
print(" copies delivered beyond the first: {:,d}".format(dup))
print(" race copies within 0.2 s: {:,d}".format(sum(
1 for o in orders for a, b in zip(o, o[1:]) if b - a < 0.2 / 60)))
print(" TTL (min) processed twice, plain with atomic check")
for ttl in (0, 10, 60, 600, 1440):
plain = atomic = 0
for o in orders:
if not o:
continue
first = o[0]
for t in o[1:]:
late = t - first > ttl
race = t - first < 0.2 / 60 and not late
plain += late or race
atomic += late
print(" {:9d} {:24,d} {:19,d}".format(ttl, plain, atomic))
print("\nReading: retries are the normal case, not the exception:")
print("tens of thousands of copies per 100,000 orders, spread by a")
print("slow-down over hours of back-off. A key kept for ten minutes")
print("or an hour still lets thousands through; only a TTL longer")
print("than the whole schedule together with an atomic check-and-")
print("insert stops them all.")
# retry schedule spans 511 minutes
# copies delivered beyond the first: 26,883
# race copies within 0.2 s: 486
# TTL (min) processed twice, plain with atomic check
# 0 26,883 26,883
# 10 9,912 9,426
# 60 3,015 2,529
# 600 486 0
# 1440 486 0
#
# Reading: retries are the normal case, not the exception:
# tens of thousands of copies per 100,000 orders, spread by a
# slow-down over hours of back-off. A key kept for ten minutes
# or an hour still lets thousands through; only a TTL longer
# than the whole schedule together with an atomic check-and-
# insert stops them all.重发是常态而不是例外:100,000 笔订单产生了 26,883 个多余的副本,其中 486 个是几乎同时到达的「竞态」副本。整个重试计划跨越 511 分钟。幂等键只保存 10 分钟时,仍有 9,912 个副本被重复处理;保存 60 分钟时还有 3,015 个。保存时间超过整个重试计划(600 分钟以上)之后,剩下的 486 个都是竞态副本:两个副本在 0.2 秒的处理时间内先后到达,都通过了「键是否存在」的检查。只有「检查并写入」是原子操作时,重复处理才降到 0。
这两条要求与第一节的转移表互补:转移表保证同一事件重复到达时不会造成第二次效果,幂等键保证同一通知不会被当作两个不同的事件。两者都要有。
假说 · 尚未验证
作者的诠释(尚未验证): 在作者的系统中,把幂等键保存 24 小时、用数据库唯一约束实现原子的「检查并写入」,并把订单处理写成转移表,可以把重复放行降到零。什么会证明这一判断错:若上线后的对账仍发现同一笔付款对应两次放行,或者同一订单在被拒绝后重新获得访问,说明模型漏掉了某种事件或某条路径。
小结
不看状态就执行的处理函数,两个事件就能造成重复放行、被拒订单重获访问与佣金不退;转移表在穷举的深度内没有反例。至少一次投递下,重发是常态;幂等键必须保存得比整个重试计划更久,并且以原子方式检查与写入。
参考文献
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).