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

Chapter 3. The Order State Machine: Exhaustive Checking and the Idempotency Window

Why exhaust the possibilities?

An order passes through several states from creation to release, verification and possibly a charge-back. The code that handles them is usually a set of functions, “on event X, do Y”. In a real network, events may arrive twice (the sender retries), out of order (what was sent later arrives first), or at any moment. Hand testing checks the normal order; errors tend to hide in the abnormal ones. Model checking writes the system as finite states and transitions, then enumerates every possible sequence of events and checks that every reachable state satisfies the invariants (Clarke et al. 1999).

Two sets of handlers

The program gives two sets of handlers. The naive set acts on an event without looking at the current state: on “release” it opens access and pays commission; on “audit failed” it closes access but does not take the commission back. The guarded set uses a transition table: a transition runs only from an allowed state, access is opened once, commission is paid only after verification, and both are withdrawn on rejection or charge-back.

Three invariants are required: I1, access is opened at most once; I2, once an order has been rejected or charged back it never has access again; I3, once an order has been rejected or charged back no commission on it remains outstanding. The program enumerates by breadth-first search every event sequence of length up to 8 and reports the shortest sequence violating each invariant.

Calculation

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

The naive set breaks all three invariants with two events each: “release, release” opens access twice (I1); “fail, release” gives a rejected order access again (I2); “release, fail” leaves a commission that should not have been paid (I3). All three sequences are ordinary in a real network: duplicate delivery, a late message, release-then-audit. The guarded set has only 7 reachable states and no violation within the depth searched.

The value of exhaustion is a guarantee of “no counterexample up to this depth”, not “a few examples worked”. It is, of course, a guarantee about the model only: things outside the model (a failed database write, say) need checking separately.

Retries and idempotency keys

Payment notices (webhooks) are usually delivered “at least once”: a sender that receives no acknowledgement resends, doubling the interval each time (1, 2, 4 … 256 minutes). The receiver remembers notices already handled by an idempotency key (Gray and Reuter 1993); but the key is kept only for a time-to-live (TTL), and a copy arriving after it expires is handled as a new notice. The program simulates 100,000 orders: an acknowledgement is lost at random with probability 0.03; each order also has a 0.05 chance of meeting a receiver slow-down (lasting 30 minutes on average) during which work is done but every acknowledgement times out; and a 0.005 chance that a proxy resends it once after about 0.05 s.

Calculation

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

Resending is the normal case, not the exception: 100,000 orders produce 26,883 extra copies, 486 of them “race” copies arriving almost at once. The whole retry schedule spans 511 minutes. With keys kept for 10 minutes, 9,912 copies are still handled twice; with 60 minutes, 3,015. Once keys outlive the whole schedule (600 minutes or more), the 486 left are all race copies: two copies arrive within the 0.2 s it takes to process one and both pass the “does the key exist?” check. Only when check-and-insert is atomic do double handlings fall to 0.

These two requirements complement the transition table of the first section: the table ensures that the same event arriving twice has no second effect, and the key ensures that one notice is not taken for two different events. Both are needed.

Hypothesis · not established

The author’s interpretation (not yet tested): in the author’s system, keeping idempotency keys for 24 hours, implementing atomic check-and-insert with a database uniqueness constraint, and writing order handling as a transition table can bring double releases to zero. What would show this wrong: if reconciliation after launch still found one payment matched to two releases, or an order regaining access after rejection, the model would have missed some event or path.

Summary

Handlers that act without looking at state produce double release, renewed access for rejected orders and unreturned commission with just two events; the transition table has no counterexample within the depth exhausted. Under at-least-once delivery, resending is normal; idempotency keys must outlive the whole retry schedule and be checked and written atomically.

References

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