Ordering and Duplicates

The previous pages made you paranoid about individual inputs: zero, one, many; empty, null, and boundaries; and extremes, overflow, and invalid input. Each of those asked, “what single value breaks this?”

This page asks a harder question: what breaks when the values are fine but their sequence is not? An event that is perfectly valid on its own can still detonate if it shows up early, shows up twice, or shows up at the exact same moment as another. These are the bugs that pass every unit test and then surface in production at 3 a.m., because production is the only place where the network reorders packets, users double-click, and two servers write the same row in the same millisecond.

The hidden assumption: “things happen in the order I wrote them”

Almost all code is written as a story: first this, then that, then the other thing. The author pictures a single, tidy timeline. Reality does not honor that picture. Messages cross a network out of order. A client retries a request it thinks failed. Two workers pull the same job off a queue. The moment your code touches anything asynchronous — a queue, a network, a database, another thread — the tidy timeline is a hope, not a guarantee.

A tester’s job is to attack that hope directly. There are three attacks, and they compound:

  Ordering      ── events arrive in the "wrong" sequence
  Duplication   ── the same event arrives more than once
  Concurrency   ── two events arrive "at the same time"

Concurrency is the worst of the three because it causes the other two: parallel actors are exactly what produce reordering and duplication in the first place.

Attack 1: out-of-order arrival

Ask of every piece of code that consumes a stream of events: does it assume they come in the order it expects? If the answer is “yes, obviously,” you have found a test to write.

Consider a system that tracks a user’s account balance from an event log:

  expected order            actual order (reordered in transit)
  ─────────────             ─────────────
  1. account created        1. account created
  2. deposit  +100          3. withdraw  -30    ← arrives first
  3. withdraw  -30          2. deposit  +100

If the consumer applies events as they arrive, the withdrawal hits an empty account and either errors, goes negative, or is silently dropped. The individual events are all valid. The order is the bug.

Tests to write:

Feed events in a shuffled order and assert the final state matches the in-order result (if the code claims order-independence).
Feed events in reverse and assert it either buffers/reorders correctly or rejects the out-of-order event loudly — silent acceptance is the failure mode.
Include a “gap”: event 4 arrives before event 3. Does the code wait, or does it process 4 and corrupt itself?

The key insight: “handles any order” and “requires strict order” are both valid designs — but they demand different tests, and a system that silently assumes the second while receiving the first is broken.

A useful discipline: for every stream consumer, write down which of these it is supposed to be, then write the test that proves it:

  Design               required test
  ──────               ─────────────
  order-independent    shuffle input → same final state
  order-required       out-of-order event → loud rejection, not silent drop
  order-buffering      gap in sequence → wait/reorder, never process past it

If you cannot say which of the three a piece of code is, that ambiguity is itself the bug — no test can pass a spec that does not exist.

Attack 2: duplicates and idempotency

Now attack repetition. What happens when the same thing arrives twice?

Duplicates are not exotic. They are the normal result of retries, at-least-once message delivery, impatient users, and double-clicks. Any networked system will deliver some messages more than once; this is a design fact, not a bug you can test away. The question is whether your code tolerates it.

The word for “tolerates it” is idempotency: an operation is idempotent if doing it twice has the same effect as doing it once.

  Idempotent            f(f(x)) == f(x)
  ────────────
  SET balance = 100     applying twice → still 100   ✓ safe to retry
  DELETE user 42        applying twice → still gone   ✓ safe to retry

  NOT idempotent
  ──────────────
  balance = balance+10  applying twice → +20          ✗ retry double-counts
  INSERT order row      applying twice → two orders    ✗ retry duplicates

Tests to write:

Duplicate keys. Insert the same key twice. Does the second insert overwrite, error, or silently create a phantom duplicate? A test that inserts ("hits", 0) and then ("hits", 5) should assert exactly which value survives — the specification must have an answer, and the test pins it.
Repeated submission. Submit the same “create order” request twice with the same idempotency key. Assert that exactly one order exists.
The double-click. Fire two identical requests with no delay between them. This is duplication and concurrency at once — the nastiest test, and the most realistic.

Duplicate delivery is common enough that most message systems document it as a guarantee, not an accident.

  Delivery semantics       what your code must assume
  ──────────────────       ──────────────────────────
  at-most-once             may LOSE a message   → detect gaps
  at-least-once (common)   may REPEAT a message → be idempotent
  exactly-once             expensive, often "effectively once" via dedup

  A retry policy of 3 attempts on a 1%-flaky endpoint means
  ~1 in 100 successful calls was actually delivered 2+ times.
  At 1,000,000 calls/day → ~10,000 duplicates/day to survive.

The lesson: if your transport is at-least-once — and most are — “handle the duplicate” is not an edge case, it is a daily event.

Attack 3: the retry problem

Retries deserve their own attention because they are the most common source of duplicates and the most dangerous when they go wrong. A client sends a request. The response is slow or the connection drops. The client cannot tell whether the server processed the request or not — so it retries. If the server already succeeded, the retry is a duplicate.

The canonical disaster is the double-charge:

  1. client → POST /charge  $50
  2. server charges card, begins reply
  3. network drops the reply    ← server succeeded, client never heard
  4. client retries → POST /charge  $50
  5. server charges AGAIN → customer billed $100

The fix is to make the write idempotent, usually with an idempotency key: the client sends a unique token with the request, and the server records “I already processed token X → here is the same result” instead of doing the work twice.

Tests to write for any retry-able write:

Send the same request with the same idempotency key twice; assert the side effect happened once (one charge, one row, one email).
Send it twice with different keys; assert it happened twice (proving the dedup is keyed, not blanket).
Simulate the “reply lost after success” case: the operation completes but the caller retries. The retry must return the original result, not redo the work and not error.

A retried request that double-charges or double-inserts is not a rare bug — it is the default behavior of any naive write. You have to test that you built the defense, because the network will test it for you in production.

Attack 4: concurrency and race conditions

The deepest layer. What happens when two writers act at the same time? Here the bug is not in any single line of code — every line is correct — it is in the interleaving of two correct sequences.

The classic is the lost update. Two threads both want to increment a counter. Each reads, adds one, writes back. If they interleave, one increment vanishes:

  Thread A            Thread B            counter
  ─────────           ─────────           ───────
  read  → 0                               0
                      read  → 0           0
  add 1 → 1                               0
                      add 1 → 1           0
  write → 1                               1
                      write → 1           1   ← should be 2! one update LOST

This is not hypothetical. It appears verbatim in this repo’s real concurrency tests. In rust/kvlite/tests/concurrency.rs, one test hammers a shared store from eight threads. When every thread writes a distinct key, the final count is exact:

// Each thread writes its own key range → all keys distinct.
// The final length must be exactly THREADS * PER_THREAD.
assert_eq!(store.len().unwrap(), THREADS * PER_THREAD);

But a second test has every thread incrementing one shared key with a read-then-write across two separate lock acquisitions — the lost-update pattern above. Its assertion is deliberately weakened, and the comment says why:

// get-then-set across two lock acquisitions is a classic lost-update
// race between the two calls — so this asserts only that no thread
// panicked and the value is in range.
let total = store.get(&"hits".to_string()).unwrap().unwrap();
assert!(total <= (THREADS * PER_THREAD) as u64); // NOT ==
assert!(total > 0);

That <= instead of == is the whole lesson written into a single operator: the test documents that this code cannot promise exactness, and the correct fix is a single write-locked method or an atomic — not two calls the scheduler can slip between.

Under the hood — why race tests are hard to write

A race condition is a bug that depends on timing, and timing is exactly what tests struggle to control. Run the increment test once and it might pass by luck; the threads happened not to interleave. This is why concurrency bugs are so insidious — they are nondeterministic, so a passing test proves nothing.

Techniques that make the hidden interleavings visible:

Volume and repetition. Thousands of iterations across many threads (as kvlite does) makes a rare interleaving likely. Still probabilistic, but far better than a single run.
Stress under contention. Point every thread at the same key, not distinct keys. Sharing is what forces interleaving; distinct keys hide it.
Deterministic schedulers / model checkers. Tools that explore interleavings systematically (loom in Rust, or a model checker) turn “maybe it races” into “here is the exact interleaving that fails.”
Assert invariants, not exact traces. You usually cannot predict the interleaving, so assert what must hold regardless of it: “no update lost,” “count never exceeds N,” “no negative balance.”

Sorting, dedup, and stable ordering are assumptions too

Three operations quietly encode ordering assumptions, and each is worth a test in its own right:

Sorting. Is the sort stable — do equal elements keep their input order? Code that later relies on that stability will break silently the day someone swaps in an unstable sort. Test with equal keys and assert the tiebreak order.
Deduplication. When you dedup, which copy survives — the first or the last? “Keep the latest” and “keep the earliest” are different specs; a test must pin which one you meant.
Stable ordering across runs. Iterating a hash map, or a query with no ORDER BY, returns rows in an unspecified order that can change between runs or versions. Code that assumes it is stable is relying on an accident. Test explicitly, or add an explicit sort.

The pattern uniting all three: an ordering property that “just happens to hold” today is a latent bug. Make it an assertion, or make it explicit in the code.

On the morning of August 1, 2012, the trading firm Knight Capital deployed new software to its servers — but reportedly missed one of the eight. A repurposed feature flag then reactivated dormant old code on that lone server. As orders flowed in, the mismatched fleet sent a storm of unintended trades: the system kept firing orders that a defunct routine failed to mark as filled, so it never stopped. In roughly 45 minutes the firm accumulated a loss reported near $440 million and was effectively destroyed within days.

The specifics are widely retold and some details are disputed, but the testing lessons are not: a partial rollout left the fleet in inconsistent states (an ordering-of-deployment problem), and a non-idempotent, self-repeating action multiplied a single mistake into a catastrophe. Test what happens when some nodes are updated and others are not, and never let a repeatable action lack a stop condition.

The architect’s lens

Why does it exist? Ordering, duplication, and concurrency testing exists because real systems are distributed and parallel: networks reorder, transports redeliver, and multiple actors write at once. The tidy single-timeline mental model that code is written against does not survive contact with production.
What problem does it solve? It catches the class of bugs that are invisible to single-input testing — lost updates, double-charges, phantom duplicates, silent corruption from out-of-order events — before a customer is billed twice or a balance goes negative.
What are the trade-offs? These tests are harder to write and inherently probabilistic; a passing concurrency test never proves absence of a race. They cost real effort (idempotency keys, stress harnesses, model checkers) that a purely sequential system would not need.
When should I avoid it? When the code is genuinely single-threaded, single-writer, and consumes an in-order, exactly-once source — a pure function on local data has no ordering, duplicate, or race surface to test. Do not manufacture concurrency tests where no concurrency exists.
What breaks if I remove it? The bugs do not disappear; they move to production and hide, surfacing rarely and nondeterministically. You lose the ability to distinguish “correct” from “correct most of the time,” which is the distinction that separates a system you can trust with money from one you cannot.

Check your understanding

An event consumer processes messages in the order they arrive from a network queue. What single assumption is it making, and what is the first test you would write to attack it?
Define idempotency in one sentence, then give one idempotent and one non-idempotent database write.
A client retries a POST /charge after a dropped reply. Explain precisely how this double-charges, and what mechanism prevents it.
In the kvlite concurrency test, why does the shared-counter test assert total <= N instead of total == N, while the distinct-keys test can assert == N?
Why is a passing concurrency test weaker evidence than a passing test for a pure function, and name two techniques that strengthen it.

Show answers

It assumes the queue delivers messages in the order the producer sent them (and that “arrival order” equals “logical order”). The first test: feed the same events in a shuffled or reversed order and assert the code either reaches the correct final state or rejects the out-of-order event loudly — a silent wrong answer is the failure.
An operation is idempotent if applying it twice has the same effect as applying it once. Idempotent: SET balance = 100 (or DELETE user 42). Non-idempotent: balance = balance + 10 (or INSERT a new order row) — each repeat changes the result.
The server processes the first charge and succeeds, but the reply is lost, so the client cannot tell success from failure and retries; the server, having no memory that it already charged, charges again. An idempotency key sent with the request lets the server recognize the retry and return the original result instead of redoing the work.
With distinct keys, no two threads touch the same entry, so there is no interleaving to lose data — the count is exact. With one shared key and a read-then-write across two lock acquisitions, threads interleave and lose updates, so the exact total is nondeterministic; the test can only assert it never exceeds the maximum and is non-zero.
Concurrency bugs are timing-dependent and nondeterministic, so a passing run may simply mean the unlucky interleaving did not occur this time — it does not prove the race is absent, unlike a deterministic pure function. Strengthen it with high-volume repetition under contention (many threads on one key) and with deterministic schedulers or model checkers (e.g. loom) that explore interleavings systematically; assert invariants rather than exact traces.