The harness in code · Code exercises

An idempotency key store

Implement the store that lets each invoice through once, expires keys on a clock duplicates never reset, and refuses a changed amount under a live id.

codeeasyExercise · 3 min · 42 of 75

On this page

At-least-once delivery means any invoice webhook may arrive twice, so the automation needs a memory of what it has already sent. The store is a dozen lines; the two rules it keeps, a clock that duplicates never reset and a first payload that nothing overwrites, are the whole exercise.

The situation

The 40-person wholesaler this module uses in place of the agency, from why we write these five by hand, supplies 900 cafés and issues invoices in its accounting system, which announces each one by webhook, at least once. The automation emails every invoice to the café and records the send. Last week 1,240 deliveries covered 1,180 invoices; 60 were duplicates, and two reached clients twice, because nothing remembered the first copy.

The sender retries a delivery it believes failed for up to 48 hours, so a duplicate can arrive two days late. Now and then an invoice is re-issued under the same id with a corrected amount; that must never silently overwrite the first, because the café may already have paid it. Keys expire after 72 hours, the 48-hour retry span plus a day of margin. At 1,180 invoices a week that is about 1,180 × 72 ÷ 168 ≈ 506 live keys; duplicates add none. The tests use a TTL of 60 seconds to keep the numbers short; production passes 259,200.

The question

Implement the store so the cases below hold, with each key's clock started at first sight and never refreshed.

def solve(events, ttl):
    """events: [(t, key, payload)], t non-decreasing, in seconds; ttl in seconds.
    A key is live while t - first_seen < ttl. An absent key is processed and stored;
    the same payload under a live key is skipped and does not refresh its clock; a
    different payload under a live key is refused: neither processed nor stored, so
    the first payload stands. Returns the payloads that were processed, in order."""

TESTS = [
    (([(0, "inv-1", "A"), (5, "inv-1", "A"), (9, "inv-2", "B")], 60), ["A", "B"]),
    (([(0, "inv-1", "A"), (30, "inv-1", "A"), (65, "inv-1", "A")], 60), ["A", "A"]),
    (([(0, "inv-1", "A"), (60, "inv-1", "A")], 60), ["A", "A"]),
    (([(0, "inv-1", "A"), (1, "inv-1", "A2")], 60), ["A"]),
    (([], 60), []),
    # added: a refused correction leaves the first payload, so the original's retry is still a duplicate
    (([(0, "inv-1", "A"), (10, "inv-1", "A2"), (20, "inv-1", "A")], 60), ["A"]),
    # added: the production clock, a retry 48 hours late inside a 72-hour TTL
    (([(0, "inv-7", "4200.00"), (172800, "inv-7", "4200.00")], 259200), ["4200.00"]),
]

A strong answer · Rubric · Where answers go wrong · Solution

Write your answer first, then open

A strong answer

An insertion-ordered dict from key to (first seen, payload). On each event, first drop entries whose age is at least ttl. Because a duplicate never refreshes the clock, insertion order is expiry order: the oldest entry is always at the front, so expiry pops from the front until it meets a live one. That is amortised O(1) per event, and the store is bounded by expiry, about 506 keys at last week's volume.

Then three cases. Key absent: process the payload and store it with the current time. Same payload under a live key: skip, without refreshing the clock (test 2: the repeat at 30 is skipped, the one at 65 is a fresh invoice, because first sight at 0 is now 65 seconds old). At exactly ttl the entry has expired, so the repeat is processed (test 3). Different payload under a live key: refuse and escalate, never overwrite (test 4). The function returns only what it processed; the caller puts each refusal in a review queue with both amounts, and a person decides between a credit note and a corrected invoice.

The store never picks the "better" payload and never drops a key early. The decision that matters is the TTL, sized from the sender: 72 hours covers its 48-hour retries with a day to spare. Evidence that would change it is a webhook log showing duplicates more than 72 hours apart, or a sender whose retry span grows; the TTL moves with it, because a duplicate older than the TTL is emailed as a new invoice.

Rubric

measures the TTL from first sight and never refreshes it on a duplicate
neither processes nor stores a different payload under a live key, so the first one stands
expires entries, so the store is bounded: about 506 keys at last week's volume
treats an event at exactly ttl as expired, and has a test on that boundary
does amortised O(1) work per event, by expiring from the front of an insertion-ordered map
sizes the 72-hour TTL from the sender's 48-hour retry span

Where answers go wrong

"A set of keys, no expiry." It passes test 1 and fails test 2. It grows by about 1,180 keys a week forever, and it blocks a legitimate re-issue after 72 hours.

"Refresh the TTL on each duplicate, so a busy key stays remembered." Test 2 returns ["A"]. A retry storm keeps the key alive for as long as it keeps retrying, and the clock no longer means anything that can be compared with the sender's schedule.

"Overwrite with the newer payload, because the latest amount is the right one." The café that paid the first amount gets a second invoice under the same number, and the record of what was sent no longer matches the email that went out.

Solution

Python 3 · standard library35 lines · 9 of 9 tests passing

"""An idempotency key store — one send per invoice id, a clock on every key, and no silent overwrite."""
from collections import OrderedDict


def expire(store, t, ttl):
    """Drop every entry whose age is at least ttl.

    The clock is never refreshed, so insertion order is first-seen order, which is
    also expiry order: the oldest entry is always at the front, and the loop stops
    at the first live one. Amortised O(1) per event, because each key leaves once.
    """
    while store:
        key, (first_seen, _) = next(iter(store.items()))
        if t - first_seen < ttl:
            break                                 # every entry behind this one is younger
        store.popitem(last=False)


def solve(events, ttl):
    """events: [(t, key, payload)], t non-decreasing, in seconds; ttl in seconds.
    A key is live while t - first_seen < ttl. An absent key is processed and stored;
    the same payload under a live key is skipped and does not refresh its clock; a
    different payload under a live key is refused: neither processed nor stored, so
    the first payload stands. Returns the payloads that were processed, in order."""
    store = OrderedDict()                         # key -> (first_seen, payload)
    processed = []
    for t, key, payload in events:
        expire(store, t, ttl)
        if key not in store:
            store[key] = (t, payload)             # first sight starts the one clock this key gets
            processed.append(payload)
        # Otherwise the key is live. The same payload is a duplicate delivery; a different one
        # is a changed amount under a live id, which the caller escalates. Neither touches the
        # store: the clock is not refreshed and the first payload is never overwritten.
    return processed

The cases that ran

TESTS = [
    # plan section 4, verbatim
    (([(0, "inv-1", "A"), (5, "inv-1", "A"), (9, "inv-2", "B")], 60), ["A", "B"]),
    (([(0, "inv-1", "A"), (30, "inv-1", "A"), (65, "inv-1", "A")], 60), ["A", "A"]),
    (([(0, "inv-1", "A"), (60, "inv-1", "A")], 60), ["A", "A"]),
    (([(0, "inv-1", "A"), (1, "inv-1", "A2")], 60), ["A"]),
    (([], 60), []),
    # a refused correction leaves the first payload in place, so the original's retry is still a duplicate
    (([(0, "inv-1", "A"), (10, "inv-1", "A2"), (20, "inv-1", "A")], 60), ["A"]),
    # keys expire in first-seen order while others stay live
    (([(0, "inv-1", "A"), (30, "inv-2", "B"), (70, "inv-2", "B"), (75, "inv-1", "A")], 60), ["A", "B", "A"]),
    # production clock: a retry 48 hours late inside a 72-hour TTL is skipped
    (([(0, "inv-7", "4200.00"), (172800, "inv-7", "4200.00")], 259200), ["4200.00"]),
    # a corrected re-issue after the key has expired is a new invoice
    (([(0, "inv-1", "A"), (1, "inv-1", "A2"), (60, "inv-1", "A2")], 60), ["A", "A2"]),
]