CSE Roadmap

Common tier · about 4 hours · 12 parts

Part 5 of 12 · 3 min read

A message can be lost, doubled or reordered, and each needs its own fix

Making a channel reliable enough to retry on loss creates a second problem -- duplicates -- that retrying alone cannot solve.

Think of mailing a letter with no tracking. If you don't hear back, you might resend it just in case the first one got lost. But if the first one actually did arrive, the recipient gets two copies and has to notice that for themselves.

In plain words: message passing means agents communicate by sending messages rather than mutating each other's state directly. On an unreliable channel there are two different delivery guarantees to choose between. At-most-once is where a lost message is simply lost. At-least-once retries until acknowledged but can deliver the same message more than once. An idempotency key (a unique id the receiver remembers, so applying a message twice has the effect of applying it once) is what makes at-least-once safe. Separate sequence numbers are what fix ordering, which an idempotency key alone does not.

A worked example. On a channel that drops 20% of messages, duplicates 10%, and loses 20% of acknowledgements: at-most-once loses 20 of 100 messages outright, with no retries to recover them. Plain at-least-once recovers all of them (0 missing) but repeats the effect of 35 messages, because retries triggered by a lost acknowledgement don't know the original actually arrived. Adding an idempotency key removes every repeat (0) at the exact same message traffic (153 sent). But even with the key, 27 of 100 messages were applied out of order. Only adding sequence numbers on top brings that down to 0.

The key lines. From code/mini-statebus/messages.py:

# from code/mini-statebus/messages.py
elif policy == "idempotent":
    if i not in seen:
        seen.add(i); apply(i)
else:
    if i not in seen and i >= nxt:
        seen.add(i); buffer[i] = True
        while nxt in buffer:
            del buffer[nxt]; apply(nxt); nxt += 1

Read it as: the idempotent branch checks i not in seen alone, while the ordered branch adds i >= nxt and buffers anything that arrives ahead of the next expected sequence number. These are two separate mechanisms solving two separate problems. seen is what prevents a duplicate from being applied twice. nxt/buffer is what prevents an out-of-order arrival from being applied before messages that were sent earlier.

Message passing, at-most-once, at-least-once, idempotency key, ordering

Message passing means agents communicate by sending messages; no agent mutates another's state directly. At-most-once sends once; a lost message is lost. At-least-once retries until acknowledged; messages may arrive more than once. An idempotency key is a unique id the receiver remembers, so applying the same message twice has the effect of applying it once. Ordering means sequence numbers let the receiver apply messages in the order they were sent even if they arrive out of order.

Example: going from 35 repeated effects (at-least-once) to 0 (plus an idempotency key) at the identical 153 messages sent is the key doing its entire job for free. It costs no extra traffic. It just stops the receiver from acting twice on what it already knows it saw once.