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 小时、用数据库唯一约束实现原子的「检查并写入」,并把订单处理写成转移表,可以把重复放行降到零。什么会证明这一判断错:若上线后的对账仍发现同一笔付款对应两次放行,或者同一订单在被拒绝后重新获得访问,说明模型漏掉了某种事件或某条路径。

小结

不看状态就执行的处理函数,两个事件就能造成重复放行、被拒订单重获访问与佣金不退;转移表在穷举的深度内没有反例。至少一次投递下,重发是常态;幂等键必须保存得比整个重试计划更久,并且以原子方式检查与写入。

参考文献

Clarke, Edmund M., Orna Grumberg, and Doron A. Peled. 1999. Model Checking. MIT Press.
Gray, Jim, and Andreas Reuter. 1993. Transaction Processing: Concepts and Techniques. Morgan Kaufmann.

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).