Problem RestatementProblem
Design a car rental reservation service (asked at Salesforce). A customer searches for available cars at a location for a time interval (e.g., pick up Friday 10:00, return Sunday 18:00), places a temporary hold on one, then confirms (pays) or cancels. They can see their reservations later. Core rule: two confirmed or held reservations for the same car must never overlap in time, even when many customers try at once.
RequirementsRequirements
- Search available cars (or car classes) by location, time range and filters.
- Hold a car for ~10 minutes, then confirm or cancel. Holds expire automatically.
- View, modify and cancel reservations.
- No double booking under concurrency.
Data ModelData model
CREATE TABLE locations (location_id INT PRIMARY KEY, name TEXT, timezone TEXT);
CREATE TABLE cars (car_id BIGINT PRIMARY KEY, location_id INT, class TEXT, -- compact, SUV
make TEXT, model TEXT, status TEXT); -- active, maintenance
CREATE TABLE reservations (
reservation_id UUID PRIMARY KEY, car_id BIGINT, customer_id BIGINT,
period TSTZRANGE, -- [pickup, return)
status TEXT, -- held, confirmed, cancelled, expired
hold_expires_at TIMESTAMPTZ, created_at TIMESTAMPTZ
);
-- The key safety net (PostgreSQL): no two active reservations of the same car may overlap.
ALTER TABLE reservations ADD CONSTRAINT no_overlap
EXCLUDE USING gist (car_id WITH =, period WITH &&) WHERE (status IN ('held', 'confirmed'));- Storing the reservation as a time range makes overlap checks natural:
&&means "overlaps". - The exclusion constraint makes the database itself reject any overlapping active reservation, which covers every code path and every race.
Deep Dive — Knowing a car is free for an intervalDeep dive
Availability here is not a flag — it is a question about a time range, asked against reservations that overlap it.
A status column on the car
Cars have status = 'available' | 'rented', and search filters on it.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["Available Friday 10:00 to Sunday 18:00?"] --> ST["cars.status = 'available'"]
ST --> NOW["Only describes right now"]
NOW --> M1["A car out today but free on Friday looks unavailable"]
NOW --> M2["A car free today but booked all weekend looks available"]A single flag cannot answer a question about a future interval. The search both hides cars that are genuinely bookable and offers cars that are not — and the second is the one that produces an angry customer at the counter.
Look for overlapping reservations, then insert
Query for reservations on that car whose period overlaps the requested one; if there are none, insert the booking.
This asks the right question. It is still check-then-act: two customers searching the same car at the same moment both find it free, and both insert. The database has no idea the two rows conflict, because nothing told it that overlapping periods for one car are illegal.
Let the range be the constraint, and hold before confirming
Store the reservation's interval as a range and have the database enforce non-overlap:
SELECT c.* FROM cars c
WHERE c.location_id = $loc AND c.status = 'active'
AND NOT EXISTS (
SELECT 1 FROM reservations r
WHERE r.car_id = c.car_id AND r.status IN ('held','confirmed')
AND r.period && tstzrange($pickup, $return)
AND (r.status = 'confirmed' OR r.hold_expires_at > now()));%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
SEARCH["Search - NOT EXISTS overlapping active reservation"] --> PICK["Customer picks a car"]
PICK --> HOLD["Insert status 'held', hold_expires_at now + 15 min"]
HOLD --> EXCL["Exclusion constraint on (car_id, period) rejects any overlap"]
HOLD --> PAY{"Confirms?"}
PAY -->|"yes"| CONF["status 'confirmed'"]
PAY -->|"no / timeout"| EXP["Hold lapses - the car is bookable again"]
CONF --> BUF["Period widened by a cleaning buffer"]- A GiST index on
(car_id, period)makes the overlap test fast, and an exclusion constraint on the same pair makes a double booking impossible regardless of which code path inserted the row. - Holds carry an expiry and are treated as occupying the car only while live — which is why the query checks
hold_expires_at > now()rather than relying on a sweeper having already run. - Widen the stored period by the turnaround buffer — an hour for cleaning — so the constraint enforces the operational rule instead of the application remembering to add it to every query.
The general lesson worth naming: when the thing being booked is an interval, the interval belongs in the schema. Representing it as a status flag pushes a scheduling problem into application code that cannot enforce it.
FlowsFlows
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
S["Search"] --> Q["Availability query"]
Q --> H["Hold - insert held reservation"]
H -->|"constraint violation"| RETRY["Pick another car"]
H --> PAY["Payment"]
PAY -->|"success"| CONF["Confirm - held to confirmed"]
PAY -->|"fail / timeout"| REL["Release"]
EXP["Expiry job"] -->|"held past expiry"| REL- Hold: insert a
heldreservation withhold_expires_at = now + 10 min. If two customers race for the same car, one insert succeeds and the other fails on the exclusion constraint, so the app offers another car of the same class. - Confirm:
UPDATE reservations SET status='confirmed' WHERE id=? AND status='held' AND hold_expires_at > now(). If 0 rows are updated, the hold expired, so try to hold again. - Cancel / expire: set
cancelled/expired. The constraint no longer applies to them, so the car is free again. - An expiry job runs every minute to mark old holds
expired. The availability query also ignores expired holds, so correctness doesn't depend on the job's timing.
Design Choices and Variants
- Book a class, not a specific car: customers usually reserve "an SUV". Assign the specific car later (at pickup), checking that on every time slot the reserved count stays ≤ the number of cars of that class. This gives better utilization.
- Without PostgreSQL exclusion constraints: lock the car row (
SELECT ... FOR UPDATE), check for overlaps, insert, and commit. Or model time as slots (hours or days) with a unique(car_id, slot)key. - Late returns: if a car isn't back, the next reservation may need a different car. Detect it and reassign proactively.
- Scale: availability is per location, so shard by location and cache search results briefly (holds are re-checked by the constraint anyway).
Wrap-UpWrap-up
Store reservations as time ranges and let the database guarantee no overlaps for held or confirmed reservations of the same car (an exclusion constraint, or row locks with an overlap check). Search availability with a NOT EXISTS overlap query, hold with an insert that fails cleanly on races, confirm with a conditional update before expiry, and release cancelled or expired holds, optionally booking by car class and assigning specific cars at pickup.