Idempotent Reservations and Exclusion Constraints: Designing a Four-Bay Scheduler That Cannot Double-Book

About this article. We are a tire and oil change shop in Calgary, and the operational constraints described here are real: a small number of physical bays, jobs of tightly clustered durations, and a seasonal changeover rush that concentrates demand into a few weeks. The scheduling system itself is a design exercise written up for other developers, not a description of live production infrastructure. Every schema, query, timestamp, metric and figure below is illustrative — invented to make the reasoning concrete. Treat it as a worked design, and adapt it to your own stack.

The Duplicate That Shows Up on a Tuesday in October

Start with the domain, because it is unusually easy to reason about. A tire shop in Calgary has a handful of physical bays, jobs that run in fairly predictable blocks, and one weekend in October where half the city decides simultaneously that it is time. When a scheduler is wrong, the cost is concrete: a technician standing in a bay with nothing to do, or a customer who drove across the city for a slot that had already been consumed.

The failure worth designing against looks like this in the database:

 reservation_id                        | bay_id | service          | lower(during)             | created_at
--------------------------------------+--------+------------------+---------------------------+---------------------------
 6f2a1c9e-...-a41b                    |      3 | tire_changeover  | 2026-10-20 08:00:00-06    | 2026-10-19 21:14:02.881-06
 c0d7be34-...-9f52                    |      3 | tire_changeover  | 2026-10-20 08:00:00-06    | 2026-10-19 21:14:03.774-06

Two rows. Same bay, same start time, same customer, 893 milliseconds apart. Nobody wanted two of them. The customer was sitting in a parking lot somewhere along Deerfoot with one bar of LTE, the request took long enough that the spinner felt broken, and they tapped the submit control a second time. The mobile client had no memory of the first attempt. Our server had no reason to think the second attempt was the same intention as the first.

The result was a bay that looked occupied for two hours when it was occupied for one, and a second customer who was told there was no room. That is a revenue problem and a trust problem, and it is caused by a bug that has been solved thousands of times in other people's systems. It is worth writing down properly, because most of the write-ups I found either stop at "use an idempotency key" or drift into distributed-consensus territory that a single Postgres instance does not need.

What the Network Actually Promises You

Here is the uncomfortable primitive at the bottom of all of this. A client that issues a POST and then times out cannot distinguish between two worlds:

1. The request never reached the server. Nothing happened.
2. The request reached the server, the server did the work and committed it, and the response was lost on the way home.

There is no protocol trick that collapses those two worlds into one. TCP will not tell you. HTTP will not tell you. A load balancer that returns 504 after 30 seconds is guessing exactly as hard as the client is. This is the ordinary at-least-once delivery problem, and it has exactly one honest resolution: the server must make repetition harmless, and the client must be told precisely how to repeat.

That is what idempotency means here. Not "the operation has no side effects" — creating a reservation obviously has side effects. It means "executing this request N times produces the same observable outcome as executing it once, and returns the same answer every time."

Everything below is the machinery for that sentence.

The Work We Actually Schedule

Before the schemas, the domain, because the domain constrains the design far more than the framework does.

We do tire work and oil changes. That is the whole catalogue. It matters for the scheduler because the durations cluster tightly and the resource is coarse: a small number of physical bays, each of which can hold exactly one vehicle at a time. The service types we encode are the ones described on the public pages — seasonal changeover work, puncture repair, balancing, fresh installation, and oil service. Nothing else lands in the enum, because nothing else happens in the bays.

Illustrative durations, which is what our seed data uses in tests:

Service code	Typical bay time	Notes
tire_changeover	45 min	Faster when the second set is already mounted on its own rims
tire_installation	75 min	Mount, balance, torque, valve stems
wheel_balancing	40 min	Sometimes a follow-on to a road-force complaint
tire_repair	30 min	Dismount, inspect, patch-plug from inside, remount
oil_change	30 min	Only bay 1 and bay 4 are plumbed for it

Those numbers are example figures for the model, not a price list and not a promise. The point is the shape: durations vary by more than a factor of two, they are not multiples of a single grid unit, and one service type is restricted to a subset of bays. Any design that assumes uniform fixed-size slots will start lying to you within a month.

The seasonal rhythm matters too. Calgary gets a first real snowfall warning somewhere in October, and the request volume on the changeover pages goes up by an order of magnitude in about six hours. That is the week the concurrency bugs surface, because that is the week two people genuinely are competing for the same 8:00 AM slot in the same bay, and the week a cell tower on the Trail is congested enough to produce ambiguous timeouts.

Two Different Problems Wearing One Costume

The failure I opened with is really two failures that happen to look identical from the customer's side.

Problem one is request duplication. The same intention arrives twice. This is a transport-layer artifact. The fix lives at the edge of your API and is about recognising that two byte streams represent one decision.

Problem two is resource contention. Two genuinely different intentions arrive and both want the last available bay. This is a data-integrity problem. The fix lives in the storage engine and is about making an invalid state unrepresentable.

Neither mechanism solves the other. An idempotency key will not stop two different customers from overbooking bay 3. An exclusion constraint will not stop one customer from creating two reservations in two different bays because their phone retried. If you build only one, you will spend a quarter chasing the symptoms of the other. Build both, and know which one you are relying on for which failure.

The Idempotency Record, In Full

Start with the table, because the columns encode most of the decisions.

CREATE TABLE idempotency_records (
  requester_id     uuid        NOT NULL,
  endpoint         text        NOT NULL,
  idem_key         text        NOT NULL,
  request_digest   bytea       NOT NULL,
  state            text        NOT NULL
                   CHECK (state IN ('in_flight', 'completed', 'failed')),
  response_status  smallint,
  response_body    jsonb,
  result_ref       uuid,
  lease_until      timestamptz,
  finished_at      timestamptz,
  expires_at       timestamptz NOT NULL,
  first_seen_at    timestamptz NOT NULL DEFAULT now(),
  PRIMARY KEY (requester_id, endpoint, idem_key)
);

CREATE INDEX idempotency_records_expiry
  ON idempotency_records (expires_at)
  WHERE state <> 'in_flight';

Three things about that primary key.

It is scoped by requester_id. Keys are client-generated, and clients are not coordinated with each other. If two different mobile installs both use a UUIDv4 you are statistically fine, but if some integration partner uses an incrementing counter you will get collisions between tenants and start replaying one customer's response to another. Scoping by requester makes that impossible rather than unlikely.

It is scoped by endpoint. The same key reused against a different route is almost certainly a client bug, and treating the two as unrelated records is far kinder than replaying a reservation payload to a cancellation route.

request_digest is a hash, not the body. Storing the full body is tempting for debugging and terrible for retention. A SHA-256 over a canonical serialisation is 32 bytes, tells you everything you need for the equality check, and carries no plate numbers or phone numbers into a table you will eventually forget to encrypt.

Fingerprinting a Request Without Lying to Yourself

The digest is where most implementations quietly break. If you hash the raw bytes, a client that reorders JSON keys between attempts — which many HTTP libraries will happily do — produces a different digest for an identical intention, and your server rejects a legitimate retry.

So canonicalise first, and be explicit about what is excluded.

import hashlib
import json

VOLATILE_FIELDS = frozenset({
    "client_timestamp",   # regenerated on every attempt
    "device_id",          # not part of the intention
    "trace_id",           # observability plumbing
    "attempt",            # the client's own retry counter
})

def request_digest(payload: dict) -> bytes:
    stable = {k: v for k, v in payload.items() if k not in VOLATILE_FIELDS}
    canonical = json.dumps(stable, sort_keys=True, separators=(",", ":"),
                           ensure_ascii=False)
    return hashlib.sha256(canonical.encode("utf-8")).digest()

Two rules I would enforce in review. First, the exclusion list is an allowlist inverted, and it must be small and deliberate; every field you drop is a field where a genuine change slips past the equality check. Second, nested structures need the same treatment recursively if your serialiser does not sort deeply — json.dumps(sort_keys=True) does, but a Protobuf-to-dict conversion might not.

Same Key, Different Body

Now the interesting case. A request arrives with a key we have already seen, but the digest does not match what we stored.

Return 409 Conflict. Do not process it. Do not overwrite the stored record. Do not silently replay the old response either.

The reasoning is that you are being asked to do something incoherent, and every alternative is worse:

• Process it as new. You have just created a second reservation under a key that was supposed to guarantee at most one. The key is now decorative.
• Replay the old response. The client asked for a 9:30 slot and you hand back a receipt for 8:00. It will believe you. Somebody drives to the wrong time.
• Update the record and process it. Same as processing it as new, with extra steps and a corrupted audit trail.

409 is the only answer that preserves the contract, and the body should say why in machine-readable form:

{
  "error": "idempotency_key_reuse",
  "message": "This key was already used for a request with a different body.",
  "key": "01J9XW7Q4S6R8T2V3M5N7P9Q1R",
  "first_seen_at": "2026-10-19T21:14:02.881-06:00"
}

That error code matters because it separates two 409s that mean entirely different things. idempotency_key_reuse is a client defect and must never be retried. slot_unavailable, which we will get to, is a legitimate business outcome and should be surfaced to a human, not to a retry loop. If both return a bare 409 with prose, some well-meaning SDK will retry the first one forever.

The Lifecycle of a Record

A record is a tiny state machine with three terminal-ish states:

                 claim (INSERT ... ON CONFLICT DO NOTHING)
                          |
                          v
                    +-----------+
                    | in_flight |
                    +-----+-----+
                          |
          success         |          deterministic failure
      +-------------------+-------------------+
      |                                       |
      v                                       v
+-----------+                           +----------+
| completed |                           |  failed  |
+-----------+                           +----------+
      |                                       |
      +---------------+-----------------------+
                      |
                  expires_at passes, row is reaped

Transient failures — a lost connection to the database, a 500 from a downstream service, a deadlock — do not move the record to failed. They delete the claim entirely, or let its lease lapse, so the client's retry gets a clean attempt. Only deterministic outcomes are recorded, because only deterministic outcomes will be identical on replay. If you persist a 503 and replay it for the next 24 hours, you have built a machine for turning a five-second blip into a day-long outage for one customer.

There is a fourth implicit state worth naming: abandoned. A process claims a key, writes in_flight, and then the container is evicted mid-transaction. The row is stranded. That is what lease_until is for. Any record whose lease has expired is fair game for reclamation, and reclamation is just a conditional update:

UPDATE idempotency_records
   SET state       = 'in_flight',
       lease_until = now() + interval '30 seconds',
       request_digest = $4
 WHERE requester_id = $1
   AND endpoint     = $2
   AND idem_key     = $3
   AND state        = 'in_flight'
   AND lease_until  < now()
RETURNING *;

Pick the lease to be comfortably longer than your slowest legitimate handler and comfortably shorter than your client's first retry delay. Ours is 30 seconds against a handler p99 of about 400 milliseconds and a first client retry at 2 seconds, which is generous in both directions on purpose.

Insert First, Ask Questions Later

The naive claim is SELECT then INSERT if absent. That is the same race we are trying to eliminate, one layer up. Two concurrent duplicates both see nothing, both insert, one gets a primary-key violation, and now your handler has an error path it did not plan for.

Do the claim as a single statement and let the index arbitrate:

INSERT INTO idempotency_records
       (requester_id, endpoint, idem_key, request_digest,
        state, lease_until, expires_at)
VALUES ($1, $2, $3, $4,
        'in_flight', now() + interval '30 seconds', now() + interval '30 days')
    ON CONFLICT (requester_id, endpoint, idem_key) DO NOTHING
RETURNING first_seen_at;

If you get a row back, you own the claim and you proceed. If you get zero rows, somebody else owns it or owned it, and you go read the existing record to decide what to say. That branch is where the three answers live: replay the stored response, return 409 for a digest mismatch, or tell the caller that an attempt is currently running.

For the third case, I favour failing fast over waiting:

409 Conflict
Retry-After: 1
{"error": "request_in_progress", "key": "01J9XW..."}

Holding the HTTP connection open while polling for the other transaction to finish is superficially friendlier and operationally awful. It ties up a worker, it converts a duplicate-request problem into a connection-pool-exhaustion problem, and during the October surge it is precisely the moment you cannot afford either. A client that receives request_in_progress and honours Retry-After gets the real answer one second later, having cost you nothing.

Capacity Is a Physical Fact, Not a Counter

Now the second half of the problem, and the half people get wrong more often.

We have four indoor bays. Not "a capacity of four" — four actual concrete rectangles, two of which have the oil-service plumbing, one of which is closest to the balancer and therefore preferred for road-force work. That distinction is not pedantry. If you model capacity as an integer you decrement, you have thrown away the constraint that a specific vehicle occupies a specific bay for a specific interval, and you will not be able to answer "which bay is this vehicle going into" without inventing an assignment step later, under time pressure, in the middle of the rush.

CREATE TYPE service_kind AS ENUM (
  'tire_changeover',
  'tire_installation',
  'wheel_balancing',
  'tire_repair',
  'oil_change'
);

CREATE TABLE bays (
  bay_id       smallint    PRIMARY KEY,
  label        text        NOT NULL,
  oil_plumbed  boolean     NOT NULL DEFAULT false,
  active       boolean     NOT NULL DEFAULT true
);

CREATE TABLE reservations (
  reservation_id  uuid         PRIMARY KEY DEFAULT gen_random_uuid(),
  bay_id          smallint     NOT NULL REFERENCES bays (bay_id),
  service         service_kind NOT NULL,
  during          tstzrange    NOT NULL,
  status          text         NOT NULL DEFAULT 'held'
                  CHECK (status IN ('held','confirmed','cancelled','completed')),
  customer_ref    uuid         NOT NULL,
  plate           text,
  raised_at       timestamptz  NOT NULL DEFAULT now(),
  CONSTRAINT during_is_bounded CHECK (
    lower(during) IS NOT NULL AND upper(during) IS NOT NULL
  )
);

Note during tstzrange rather than a start column and an end column. That choice is what makes the rest of this section short.

Why SELECT-Then-INSERT Cannot Work

The obvious handler reads:

-- Step 1
SELECT count(*) FROM reservations
 WHERE bay_id = 3
   AND status IN ('held','confirmed')
   AND during && tstzrange('2026-10-20 08:00-06', '2026-10-20 08:45-06', '[)');

-- Step 2, if the count was zero
INSERT INTO reservations (bay_id, service, during, customer_ref)
VALUES (3, 'tire_changeover',
        tstzrange('2026-10-20 08:00-06', '2026-10-20 08:45-06', '[)'),
        '...');

Under Postgres's default READ COMMITTED isolation, each statement sees a snapshot taken at the start of that statement. Uncommitted rows from other transactions are invisible. So two transactions running this pair concurrently both observe an empty bay, both insert, and both commit. No error is raised. Nothing in the database objects. You have a read-modify-write race with a comfortable window measured in milliseconds, which during a surge is more than wide enough to hit several times an hour.

This is not a Postgres quirk. It is what READ COMMITTED is defined to do. The check you performed was a predicate over rows that did not exist yet, and no isolation level below SERIALIZABLE gives predicates any protection.

Two Transactions, One Bay: The Exact Interleaving

Here is the sequence, written out, because I find the abstract version never lands the way a trace does. T1 and T2 are two application workers handling what turned out to be the same customer's duplicate submission, though it would look identical for two different customers.

Time	T1	T2	Committed state
0 ms	BEGIN;		bay 3 at 08:00 is free
4 ms	SELECT count(*) ... during && [08:00,08:45) returns 0		unchanged
9 ms		BEGIN;	unchanged
12 ms		SELECT count(*) ... returns 0	unchanged
18 ms	INSERT ... reservation A succeeds		A exists but is invisible to T2
21 ms		INSERT ... reservation B succeeds	B exists, invisible to T1
25 ms	COMMIT;		A is durable
27 ms		COMMIT;	A and B are both durable

At 27 ms the invariant is broken and no software component noticed. The only reason we ever found out is that a service advisor looked at a printed run sheet and saw the same plate twice.

Now the same trace with the exclusion constraint in place, which we will define in a moment:

Time	T1	T2	What the engine does
18 ms	INSERT ... A succeeds		GiST index entry taken for (3, [08:00,08:45))
21 ms		INSERT ... B	blocks — conflicting index entry is uncommitted
25 ms	COMMIT;	(still blocked)	A becomes durable, lock released
25.1 ms		raises 23P01 exclusion_violation	B never exists

T2's handler catches 23P01, maps it to slot_unavailable, and returns a 409 with a list of nearby alternatives. The invariant held without the application having to think about it.

Making Overbooking Physically Impossible

CREATE EXTENSION IF NOT EXISTS btree_gist;

ALTER TABLE reservations
  ADD CONSTRAINT reservations_one_vehicle_per_bay
  EXCLUDE USING gist (
    bay_id  WITH =,
    during  WITH &&
  ) WHERE (status IN ('held', 'confirmed'));

Read that as: no two rows in the qualifying set may have both an equal bay_id and overlapping during ranges. btree_gist is what lets a scalar column like bay_id participate in a GiST index alongside a range column; without it, the equality operator has no GiST operator class.

Three properties make this the right primitive rather than one option among several.

It is enforced by the storage engine, so it holds regardless of which code path performs the insert. The admin console, the batch importer that loads fleet work, a psql session at 11 PM, a future service written by somebody who never read this article — all of them are covered. Application-level checks protect only the applications that remember to perform them.

It works at READ COMMITTED. You do not need SERIALIZABLE, you do not need a retry loop for serialization failures, and you do not pay the SSI bookkeeping cost on every read.

The partial WHERE clause means cancelled and completed rows drop out of the constraint automatically. A cancelled 08:00 slot stops blocking new work the instant its status changes, with no tombstone handling and no separate cleanup.

The cost is real but small: the GiST index is larger and slower to update than a btree, and range queries against it are not always as fast as a well-chosen composite btree on (bay_id, start_time). At our volume that is irrelevant. At a scale where it matters, you keep the exclusion constraint for correctness and add a btree for the read path.

Ranges Beat Timestamp Pairs When Durations Vary

The half-open bound notation '[)' in tstzrange(start, finish, '[)') is not decoration. It says the range includes its lower bound and excludes its upper. That is what makes a job ending at 09:00 and a job starting at 09:00 not overlap, which is exactly the semantics you want for back-to-back work.

Get this wrong and you produce one of two bugs. With inclusive upper bounds '[]', consecutive jobs conflict and your bay utilisation drops by a slot per boundary. With exclusive lower bounds '()', zero-length and adjacent ranges behave in ways that will surprise you at 7 AM.

The overlapping-duration case from the assignment brief is where ranges really earn their keep. Consider a 75-minute installation starting at 09:00 in bay 2, and someone trying to place a 30-minute repair at 09:45 in the same bay:

SELECT tstzrange('2026-10-20 09:00-06','2026-10-20 10:15-06','[)')
    && tstzrange('2026-10-20 09:45-06','2026-10-20 10:15-06','[)') AS conflicts;
-- conflicts => true

With a start column and a duration column you would be writing that predicate by hand in every query, and every hand-written version is a chance to invert a comparison. With ranges the && operator is the predicate, it is the same predicate the index uses, and there is no second implementation to drift.

A related benefit: buffer time becomes a range operation instead of arithmetic scattered through the code. If you want ten minutes of cushion between vehicles for the pull-in and pull-out, widen the stored range at write time and let the constraint do the rest.

-- Buffered range helper, applied at insert time
SELECT tstzrange(
         lower(r.during) - interval '5 minutes',
         upper(r.during) + interval '5 minutes',
         '[)')
  FROM (SELECT tstzrange($1, $2, '[)') AS during) r;

The Unique Partial Index Alternative

If your durations really are uniform, a unique partial index is simpler and cheaper:

CREATE UNIQUE INDEX one_job_per_bay_slot
    ON reservations (bay_id, lower(during))
 WHERE status IN ('held', 'confirmed');

This gives you the same physical impossibility with a plain btree, no extension, and no GiST overhead. It is a perfectly good answer for a fixed grid — every job is exactly 30 minutes, every start is on the half hour, nothing ever runs long.

It collapses the moment durations vary. A 75-minute installation starting at 09:00 has a distinct lower(during) from a 30-minute repair starting at 09:45, so both indexes entries are unique, and both rows are accepted despite occupying the same bay at the same time. This is a classic way for a "quick" change allowing long jobs to reintroduce the exact bug the index was meant to kill. If there is any chance your service catalogue will grow — and a catalogue covering oil service alongside tire work already mixes durations — start with the range type.

Advisory Locks and Row Locks: Where They Fit

Two other tools come up constantly in this conversation, and both have a place.

SELECT ... FOR UPDATE on a parent row serialises writers through a row lock:

BEGIN;
SELECT bay_id FROM bays WHERE bay_id = 3 FOR UPDATE;
-- every writer for bay 3 now queues here
SELECT count(*) FROM reservations WHERE bay_id = 3 AND during && $1
                                    AND status IN ('held','confirmed');
INSERT INTO reservations (...) VALUES (...);
COMMIT;

This is correct, and it is easy to reason about. The weakness is that its correctness is a convention. Nothing forces the next writer to take the lock. The importer written six months later will not, and the constraint you thought you had was really an agreement between the two functions that happened to exist when you wrote it.

Advisory locks are the same idea without a row to hang it on, useful when the thing you are serialising is not a table row:

SELECT pg_advisory_xact_lock(
  hashtextextended(format('bay:%s:%s', $1::text, $2::date::text), 0)
);

pg_advisory_xact_lock releases automatically at transaction end, which is almost always what you want; the session-scoped variant leaks locks when a pooled connection is handed back without cleanup. Note the hash collision surface: two distinct keys can map to the same bigint, and the consequence is spurious serialisation rather than a correctness bug, so it is tolerable — but it is another reason to prefer a constraint that names the real objects.

My rule: use the exclusion constraint as the source of truth, and reach for a lock only when you need to serialise a multi-row decision that no single constraint can express. Assigning a vehicle to the best available bay out of four, for example, involves reading all four and picking one; a lock makes that read-then-choose deterministic, while the constraint still catches you if the logic is wrong.

Isolation Levels, Stated Plainly

Worth being precise, because this is where hand-waving does the most damage.

READ COMMITTED (the Postgres default): each statement sees rows committed before that statement began. It prevents dirty reads. It does not prevent non-repeatable reads, phantom reads, or the write skew that our double-insert is a form of. Two transactions can each observe "no conflict" and each create one. This is the level at which the exclusion constraint saves you, because the constraint is enforced in the index, not in a snapshot.

REPEATABLE READ: one snapshot for the whole transaction. Postgres's implementation gives you snapshot isolation, which does prevent non-repeatable and phantom reads within your own transaction. It still does not prevent write skew across transactions, because two transactions reading disjoint snapshots and writing disjoint rows never collide. Our race survives here untouched. People are frequently surprised by this.

SERIALIZABLE: Postgres uses Serializable Snapshot Isolation, tracking read-write dependencies between concurrent transactions and aborting one when it detects a dangerous structure. This does catch our race. T2 fails at commit with SQLSTATE 40001, serialization_failure, and you retry the whole transaction from the top.

SERIALIZABLE is genuinely correct and I do not want to talk anyone out of it. But be aware of the bill. Every transaction in the system pays predicate-lock bookkeeping, not only the ones you were worried about. Aborts are probabilistic and can fire on transactions with no real conflict, so every write path needs a retry loop with backoff, including the ones you wrote before you turned it on. And the failure mode under load is a retry storm precisely when load is highest.

The comparison in one table:

Mechanism	Stops our race?	Isolation needed	Enforced against all writers	Retry loop required
App-level check, no lock	No	any	No	No
FOR UPDATE on bay row	Yes	READ COMMITTED	No, by convention only	No
Advisory transaction lock	Yes	READ COMMITTED	No, by convention only	No
Unique partial index	Yes, fixed grid only	READ COMMITTED	Yes	No
GiST exclusion constraint	Yes, any durations	READ COMMITTED	Yes	No
SERIALIZABLE, no constraint	Yes	SERIALIZABLE	Yes	Yes, everywhere

We landed on the exclusion constraint at READ COMMITTED, with a transaction-scoped advisory lock only in the auto-assignment path.

The Handler, Start to Finish

Putting both halves together. This is psycopg3-flavoured Python, trimmed of logging and validation but structurally what runs.

import uuid
from psycopg import errors

LEASE = "30 seconds"
RECORD_TTL = "30 days"

class KeyReuse(Exception): ...
class AttemptRunning(Exception): ...
class SlotUnavailable(Exception): ...

CLAIM = """
INSERT INTO idempotency_records
       (requester_id, endpoint, idem_key, request_digest,
        state, lease_until, expires_at)
VALUES (%(req)s, %(ep)s, %(key)s, %(dig)s, 'in_flight',
        now() + interval %(lease)s, now() + interval %(ttl)s)
    ON CONFLICT (requester_id, endpoint, idem_key) DO NOTHING
RETURNING first_seen_at
"""

FETCH = """
SELECT state, request_digest, response_status, response_body, lease_until
  FROM idempotency_records
 WHERE requester_id = %(req)s AND endpoint = %(ep)s AND idem_key = %(key)s
"""

PLACE = """
INSERT INTO reservations (bay_id, service, during, customer_ref, plate)
VALUES (%(bay)s, %(svc)s, tstzrange(%(from)s, %(to)s, '[)'),
        %(cust)s, %(plate)s)
RETURNING reservation_id
"""

SETTLE = """
UPDATE idempotency_records
   SET state = 'completed', response_status = %(status)s,
       response_body = %(body)s, result_ref = %(ref)s,
       finished_at = now(), lease_until = NULL
 WHERE requester_id = %(req)s AND endpoint = %(ep)s AND idem_key = %(key)s
"""

def place_reservation(conn, requester, key, payload):
    dig = request_digest(payload)
    args = {"req": requester, "ep": "POST /v1/reservations", "key": key}

    with conn.transaction():
        claimed = conn.execute(
            CLAIM, {**args, "dig": dig, "lease": LEASE, "ttl": RECORD_TTL}
        ).fetchone()

        if claimed is None:
            row = conn.execute(FETCH, args).fetchone()
            state, stored_dig, status, body, lease_until = row
            if stored_dig != dig:
                raise KeyReuse(key)
            if state == "in_flight" and lease_until > utcnow():
                raise AttemptRunning(key)
            if state in ("completed", "failed"):
                return status, body          # verbatim replay
            # lease has lapsed: fall through and reclaim it
            conn.execute(RECLAIM, {**args, "dig": dig, "lease": LEASE})

        try:
            ref = conn.execute(PLACE, {
                "bay": payload["bay_id"], "svc": payload["service"],
                "from": payload["starts_at"], "to": payload["ends_at"],
                "cust": payload["customer_ref"], "plate": payload.get("plate"),
            }).fetchone()[0]
        except errors.ExclusionViolation:
            body = {"error": "slot_unavailable", "bay_id": payload["bay_id"]}
            conn.execute(SETTLE, {**args, "status": 409,
                                  "body": Jsonb(body), "ref": None})
            raise SlotUnavailable(payload["bay_id"])

        result = {"reservation_id": str(ref), "status": "held"}
        conn.execute(SETTLE, {**args, "status": 201,
                              "body": Jsonb(result), "ref": ref})
        return 201, result

The important structural property: the claim, the reservation insert, and the settle all live inside one transaction. If any of them fails for a transient reason, the whole thing rolls back including the claim, and the client's retry finds no record and gets a genuinely fresh attempt. That is what makes transient failures safe to retry without leaving zombie in_flight rows behind.

Notice also that slot_unavailable is settled into the record as a completed 409 before the exception propagates. That is deliberate. A capacity rejection is a deterministic outcome for that exact request body, and replaying it is correct: if you ask for the same bay at the same time tomorrow morning with the same key, the answer has not changed.

What the Client Owes the Server

Idempotency is a two-party contract, and half of it is client-side discipline. The rule that gets violated most often is the simplest one.

Reuse the same key on retry. A retry is not a new intention. If your HTTP wrapper mints a fresh UUID on every attempt, every one of your carefully designed server mechanisms is bypassed, and you have built a very sophisticated way to create duplicates. Generate the key when the human commits to the action — the moment the submit control is pressed — and hold it for the lifetime of that intention, including across app restarts if you have an offline queue.

Which responses are safe to retry:

Status / condition	Retry?	Why
Connection reset, DNS failure, TLS handshake failure	Yes	Request may never have landed
Client-side timeout, no response	Yes	Ambiguous by construction; this is the core case
408, 425	Yes	Server explicitly says the attempt did not complete
429	Yes, after Retry-After	Rate limit, not a semantic error
500, 502, 503, 504	Yes, with backoff	Transient or ambiguous
409 request_in_progress	Yes, after Retry-After	Another attempt of yours is mid-flight
409 slot_unavailable	No	Deterministic; retrying returns the same answer forever
409 idempotency_key_reuse	No	Client defect; escalate, do not loop
400, 422	No	The payload is wrong and will stay wrong
401, 403	No	Credentials, not concurrency
404	No	Nothing to do

Two of those rows are the ones I would put in a code review checklist: retrying slot_unavailable is how you build a client that hammers a full facility until the customer force-quits the app, and retrying idempotency_key_reuse is how you turn one bug into a sustained one.

Backoff, Jitter, and the Herd After a Snowfall Warning

Fixed-interval retries synchronise. If a thousand clients all get a 503 at the same instant because a deploy briefly dropped a replica, and all of them retry at exactly 1s, 2s, and 4s, you have built a distributed drum circle that will keep the service down long after the original cause is gone. Calgary gives us a very reliable trigger for this: the hour after a snowfall warning is published, when everyone in the city thinks about winter rubber at once.

Full jitter is the version I would default to:

import random
import time

BASE = 0.25      # seconds
CAP  = 20.0      # seconds
MAX_ATTEMPTS = 6

def with_retries(send, idem_key):
    for attempt in range(MAX_ATTEMPTS):
        outcome = send(idem_key)          # SAME key every time
        if outcome.terminal:
            return outcome
        ceiling = min(CAP, BASE * (2 ** attempt))
        time.sleep(random.uniform(0, ceiling))
    raise RetriesExhausted(idem_key)

random.uniform(0, ceiling) rather than ceiling alone is the whole trick: it spreads the herd across the interval instead of stacking it on the boundary. Equal jitter (ceiling/2 + random.uniform(0, ceiling/2)) is a reasonable variant when you care about a floor on latency. Decorrelated jitter is better still under sustained pressure, but full jitter is easy to explain to whoever is on rotation at 6 AM, and that has value.

Two additions that matter more than the exact formula. Cap total elapsed time, not just attempt count, because six attempts with a 20-second cap can span two minutes and the human gave up ninety seconds ago. And carry an attempt counter in a header for observability, excluded from the digest, so you can graph how deep clients are actually going.

Choosing a TTL You Can Defend

expires_at is the field where a lazy default becomes a correctness bug six months later.

The rule is: the TTL must exceed the longest interval over which a client might legitimately replay the same key. If a record expires and is deleted, and then the original request arrives one more time, your server has no memory of it and will happily create a second reservation. The idempotency guarantee has a shelf life, and you chose it.

Twenty-four hours is the common default and it is often too short. Ours is 30 days, for reasons that are specific and boring:

• The mobile client has an offline queue. A phone that loses signal in a parkade, gets put on a charger, and is not opened until Monday will drain that queue on Monday. A weekend plus a holiday is easily 72 hours.
• Integration partners who submit commercial and fleet work run batch jobs whose failure handling is, charitably, unhurried. A stuck batch resubmitted the following week is a real thing that has happened.
• The rows are small. Thirty days of records at our volume is a few hundred megabytes. Buying a month of safety for that is not a difficult trade.

If you cannot make the TTL long enough — and some systems genuinely cannot — then add a second line of defence that does not expire. A natural-key uniqueness constraint on the business meaning of the request survives idempotency-record expiry:

CREATE UNIQUE INDEX reservations_no_repeat_intent
    ON reservations (customer_ref, service, lower(during))
 WHERE status IN ('held', 'confirmed');

That will not catch every duplicate — a customer legitimately placing two jobs for two vehicles at the same time trips it, so you may need the vehicle in the key — but it converts a silent duplicate into a loud constraint violation, and loud is always better.

Reaping Old Records Without Hurting Live Traffic

A single unbounded DELETE FROM idempotency_records WHERE expires_at < now() will, on a busy table, take locks for long enough to matter and generate a spike of WAL and autovacuum work at the worst possible moment. Batch it:

WITH doomed AS (
  SELECT ctid
    FROM idempotency_records
   WHERE expires_at < now()
     AND state <> 'in_flight'
   ORDER BY expires_at
   LIMIT 5000
)
DELETE FROM idempotency_records t
 USING doomed d
 WHERE t.ctid = d.ctid;

Loop that until it deletes fewer than the limit, sleep between iterations, and run it well outside the morning rush. The state <> 'in_flight' guard is not optional: deleting a claim out from under a running handler produces exactly the duplicate you built the table to prevent.

The better answer at volume is to stop deleting rows at all. Partition by day and drop whole partitions:

CREATE TABLE idempotency_records (
  ...
) PARTITION BY RANGE (first_seen_at);

CREATE TABLE idempotency_records_p2026_10_20
  PARTITION OF idempotency_records
  FOR VALUES FROM ('2026-10-20') TO ('2026-10-21');

-- retirement, once the window has passed
DROP TABLE idempotency_records_p2026_09_20;

There is a real tradeoff hiding in that snippet and I want to name it rather than skip past it. Postgres requires the partition key to be part of any unique constraint on a partitioned table, so the primary key becomes (first_seen_at, requester_id, endpoint, idem_key). Uniqueness is now enforced within a partition, not across the table. If the same key arrives on two different days, the index will not stop you. In practice that is fine when your retention window vastly exceeds any plausible replay window, and it is a live hazard when it does not. Decide on purpose.

Reconciliation: Finding What Slipped Through

Constraints prevent the failures you anticipated. Reconciliation finds the ones you did not. Two queries run nightly against the previous day.

Near-simultaneous identical intentions, which is the fingerprint of a client that is not reusing its key properly:

WITH ordered AS (
  SELECT reservation_id, customer_ref, service, during, raised_at,
         LAG(reservation_id) OVER w AS prior_id,
         LAG(raised_at)      OVER w AS prior_raised
    FROM reservations
   WHERE status IN ('held','confirmed')
     AND raised_at >= now() - interval '1 day'
  WINDOW w AS (PARTITION BY customer_ref, service, lower(during)
               ORDER BY raised_at)
)
SELECT customer_ref, reservation_id, prior_id,
       raised_at - prior_raised AS gap
  FROM ordered
 WHERE prior_id IS NOT NULL
   AND raised_at - prior_raised < interval '10 minutes'
 ORDER BY gap;

And one customer holding overlapping slots in different bays, which the per-bay constraint cannot see:

SELECT a.customer_ref,
       a.reservation_id AS earlier,
       b.reservation_id AS later,
       a.during * b.during AS shared_window
  FROM reservations a
  JOIN reservations b
    ON a.customer_ref = b.customer_ref
   AND a.reservation_id < b.reservation_id
   AND a.during && b.during
 WHERE a.status IN ('held','confirmed')
   AND b.status IN ('held','confirmed');

The * operator there is range intersection, which gives you the exact overlapping window rather than a boolean. Handy in a report a human has to act on.

A third check worth running compares the count of completed idempotency records against the count of reservations created in the same window. A persistent gap means some write path is bypassing the claim entirely, and that path is your next incident.

Metrics That Earn Their Storage

Instrument the branches, not the endpoint. The interesting signal is in which arm of the state machine traffic takes.

• idempotency_claims_total — new claims. Your baseline for everything else.
• idempotency_replays_total{outcome="completed"|"failed"} — verbatim replays served. A rising ratio against claims means clients are retrying more, which usually means latency has crept up somewhere upstream. That makes it a leading indicator rather than a lagging one, which is why it belongs on a dashboard instead of in a weekly report.
• idempotency_digest_mismatch_total — 409s for key reuse. This should be flat at approximately zero. Any movement is a client release regression; alert on it.
• idempotency_in_flight_rejections_total — how often a duplicate arrives while the original is still running. Correlates directly with handler latency.
• idempotency_lease_reclaims_total — abandoned claims recovered. Non-zero means processes are dying mid-request.
• reservation_exclusion_violations_total{bay_id} — genuine capacity contention. Per-bay labels tell you which bay is the bottleneck, which is an operational answer, not just an engineering one.
• idempotency_record_age_seconds — histogram of now() - first_seen_at at replay time. This is how you validate your TTL empirically instead of by argument. If the p99 is creeping toward your expiry window, lengthen it.
• reap_rows_deleted_total and reaper duration. A reaper that stops keeping up is a slow-motion disk alert.

The two I would put on a wall: digest mismatches, because they are always a bug, and the replay-to-claim ratio, because it is the earliest signal that something is degrading for real users.

A Concurrency Test That Actually Fails on the Naive Version

A test that passes against both implementations is worse than no test, because it tells you the race is handled when it is not. The requirement is that the test reliably fails when you remove the constraint.

Three ingredients: a real Postgres (not SQLite, whose locking model will hide the bug), enough concurrency to make the window wide, and a barrier so every worker arrives at the critical section together.

import threading
import concurrent.futures as cf
import pytest

WORKERS = 32

def test_only_one_reservation_survives_the_stampede(pool, seeded_bay):
    gate = threading.Barrier(WORKERS)
    window = ("2026-10-20T08:00:00-06:00", "2026-10-20T08:45:00-06:00")

    def attempt(n: int):
        body = {
            "bay_id": seeded_bay, "service": "tire_changeover",
            "starts_at": window[0], "ends_at": window[1],
            "customer_ref": str(uuid.uuid4()),
        }
        gate.wait(timeout=10)                 # release all threads together
        with pool.connection() as conn:
            try:
                return place_reservation(conn, REQUESTER, f"k-{n}", body)
            except SlotUnavailable:
                return None

    with cf.ThreadPoolExecutor(max_workers=WORKERS) as ex:
        results = list(ex.map(attempt, range(WORKERS)))

    assert sum(r is not None for r in results) == 1

    with pool.connection() as conn:
        rows = conn.execute(
            "SELECT count(*) FROM reservations "
            "WHERE bay_id = %s AND status IN ('held','confirmed')",
            (seeded_bay,)).fetchone()[0]
    assert rows == 1, f"overbooked: {rows} rows survived"

Note that each worker uses a different idempotency key and a different customer. That is deliberate: this test targets the capacity mechanism specifically, with the duplicate-suppression mechanism removed from the picture. Its twin uses one shared key across all 32 workers and asserts that exactly one row is created and that every other worker got either a replay of the same reservation_id or AttemptRunning.

If the stampede test is flaky against the naive implementation — sometimes it produces 2 rows, sometimes 1 — widen the window deterministically. Inject a controllable pause between the read and the write in a test build:

if HOOK := os.environ.get("RACE_HOOK_MS"):
    time.sleep(int(HOOK) / 1000.0)

With RACE_HOOK_MS=50, the naive path fails every single run, and the exclusion-constraint path still produces exactly one row. That is the pair of outcomes that proves the mechanism rather than the timing.

One more test I recommend and rarely see: assert the error code, not just that an exception occurred. A test that accepts any exception will keep passing when a typo turns your capacity rejection into a NameError.

Where This Design Still Bites

I would rather list the sharp edges than pretend there are none.

Retries at the load balancer are invisible to you. If your ingress retries idempotent-looking requests on its own — and some do, by default, for reads — you can get a duplicate that never passed through client code and therefore has no key discipline behind it. Check your ingress configuration.

Clock skew shifts the meaning of lease_until and expires_at if you compute them in application code across several hosts. Compute them in SQL with now() so a single authority owns time. Every timestamp in the DDL above does this.

Cancellation and rescheduling need their own keys, and the same 409 discipline. A cancel that runs twice is usually harmless; a reschedule that runs twice is a duplicate wearing a different hat.

Multi-resource jobs break the single-constraint model. A vehicle needing both a bay and the balancer for part of its stay is two resources with two overlap constraints, and the ordering of those two inserts becomes a deadlock question. The pragmatic option is widening the bay range to cover the whole job, which is slightly wasteful and completely safe. The general version is a lock ordering convention, and it is the part of this design I like least.

Off-site work would be a separate resource pool entirely. A mobile service unit is not a bay, its capacity is bounded by drive time rather than floor space, and the constraint governing it also has to encode the geographic coverage rules. Same idempotency machinery, different exclusion predicate — and a travel-time term that the bay model does not need at all.

What This Design Buys You

The point is not that duplicates get cleaned up faster. It is that the class of bug stops being reachable. Once non-overlap is a schema constraint rather than a convention, a new service path — say after-hours handling — inherits the guarantee without anyone writing fresh concurrency code for it. That is the entire argument for pushing the invariant down into the database instead of leaving it in a function somebody has to remember to invoke.

The design in one paragraph, for anyone skimming to the end: generate the key on the client at the moment of human intent and reuse it on every retry; claim it server-side with a single conditional insert; store a canonical digest and the serialised response; return 409 for a mismatched body and 409 with Retry-After for a concurrent attempt; model bays as rows and occupancy as a tstzrange; enforce non-overlap with a GiST exclusion constraint so no write path can violate it regardless of isolation level; pick a TTL longer than your worst realistic replay delay and back it with a natural-key index if you cannot; reap in batches or by dropping partitions; reconcile nightly; and write the stampede test with a barrier so it fails loudly against the naive implementation.

The work this machinery would schedule is described in plain language on the customer-facing scheduling pages, and the reasoning behind the service definitions themselves lives in our tire education material. Software of this kind exists to make sure the physical thing — a vehicle, a bay, a technician, forty-five minutes in October — matches what the database says. Everything above exists to keep those two pictures identical.