Concurrent Car Reservation Service

0) Problem Restatement

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.

1) Requirements

• 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.

2) Data 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.

3) Availability Query

SELECT c.* FROM cars c
WHERE c.location_id = $loc AND c.status = 'active' AND c.class = COALESCE($class, c.class)
  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()));

An index on reservations (car_id, period) (GiST) keeps it fast. Add a buffer between rentals (e.g., 1 hour for cleaning) by widening the range.

4) Flows

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

1. Hold: insert a held reservation with hold_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.
2. 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.
3. Cancel / expire: set cancelled / expired. The constraint no longer applies to them, so the car is free again.
4. 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.

5) 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).

6) Wrap-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.