Exactly-once is an illusion: at-most-once RPC with session dedup

Last week I built a storage engine that survives a crash. This week I put it behind a network — and
the network immediately started lying to me. A client sends a write, waits, and hears… nothing. Did
the write happen? It cannot tell. That single ambiguity is the reason “exactly-once” delivery is a
myth, and the reason every serious system quietly does something cleverer.

What I built

A networked key-value store: a Clerk (client) talking to a KVServer over a tiny RPC layer with
a deliberately unreliable network — one that drops requests, drops replies, and adds delays, so I can
reproduce the failures on demand.

Clerk.Append("k","b")                          KVServer
  │  same Seq on every retry                       │  dedup: ClientID → last Seq applied
  ▼                                                ▼
  Call("PutAppend", {…, ClientID, Seq}) ──────►  seen this Seq? yes → skip (ack OK)
  ▲                                              │                no  → apply, record Seq
  └────────────── reply (may be dropped!) ───────┘

The concepts that made it work

• “Exactly-once” = at-least-once delivery + at-most-once execution. It’s not a property the
  network gives you; it’s one the client and server build together. The client keeps retrying
  (at-least-once); the server refuses to apply the same write twice (at-most-once).
• Call() == false is ambiguous. A failure means “I didn’t hear back” — the request may have run
  and only the reply was lost. My RPC layer proves this: under drops, the server executes more calls
  than the client ever gets answers for.
• An idempotency key makes retries safe. Every write carries (ClientID, Seq), chosen once and
  reused across retries. The server dedups on it. This is exactly Stripe’s Idempotency-Key header —
  same idea, ten lines of code.
• Reads are different from writes. Get is idempotent, so it retries blindly with no dedup. Half
  of API design is noticing which operations already are idempotent.

The thing that bit me

Two traps, both about a value collision. First: it’s the dropped reply, not the dropped request,
that forces dedup — the request already ran, so a naive retry double-applies. Second, and sneakier:
sequence numbers have to start at 1, not 0. The server’s dedup table returns 0 for a client it’s
never seen, and its check is Seq <= lastSeqSeen. Start counting at 0 and your very first write reads
as 0 <= 0 → “already applied” → silently dropped. The empty state and a real value must never share
a bit pattern.

Tradeoffs & the road not taken

I shipped the simplest thing that’s correct, which leaves two honest holes:

• The dedup table grows forever. One entry per client, never reclaimed — a real memory leak. The
  fix is to have the client acknowledge “I’ve received replies through Seq N” so the server can forget
  older state. I left it out to keep the core legible.
• One server = no fault tolerance. If it crashes, both the data and the dedup table vanish. That’s
  not a bug to patch here — it’s the entire reason the next few weeks exist.

Where this sits in the system

Last week: a single-node store. This week: that store behind an RPC boundary, where retries are
unavoidable and dedup is mandatory. Next: Raft — replicate the write log across machines so a
server can die and the store keeps its word. (And the dedup state? It’ll have to live in that
replicated log, not just local memory — but that’s a problem for future me.)

Part of a series building a distributed database from scratch.