## System Design: Car Rental Booking System Design an online car rental system (like Hertz or Avis) that lets users **search** for available rental cars, get a **price quote**, **book** a car, and later **cancel or modify** the reservation. The core user flows you must support: 1. **Search** for available cars by pickup location, a `[pickup, return)` date/time window, car class (economy/SUV/etc.), and optional filters (price, seats, transmission). 2. **Quote** a total price (base rate + fees + taxes + add-ons). 3. **Book** a car for the selected window. 4. **Cancel or modify** an existing reservation (change dates, class, or location). The single hardest requirement is correctness under concurrency: the same physical car must **never** be double-booked for two overlapping time ranges, even when many users try to book it at the same instant during a promotion. At the same time, search is extremely read-heavy and bursty, and must stay fast. ```hint Where to start Separate the two pressures into two different paths. **Booking** is the *correctness* problem — it needs a strongly consistent write. **Search** is the *scale* problem — it is read-heavy and can tolerate slightly stale data. Designing them as one path forces you to either over-serialize search or under-protect booking. ``` ```hint The core race The double-booking bug is a classic read-then-write race: two requests both "check availability" (see the slot free), then both "insert a reservation." The fix is to make the *overlap check* and the *reservation write* a **single atomic operation** — never two separate round trips. Think about which database primitive can express "no two active reservations for this car may overlap in time" as an invariant the engine enforces (range/interval exclusion, pessimistic row lock + overlap check, or optimistic CAS). ``` ```hint Holds vs. payment Payment is a slow external call (seconds). You cannot hold a DB transaction open across it. Introduce a short-lived intermediate **HELD** state with a TTL that reserves the slot *before* payment, then run the payment as a saga that flips HELD → CONFIRMED or releases it. This also tells you how to make retries safe (idempotency keys). ``` ```hint Search at scale Don't range-scan the live `reservations` table on every search — that couples read load to the write path. Maintain a derived, eventually-consistent **availability projection** fed by reservation events, and re-validate the truth transactionally only at booking time. Note the trap: a per-day "available count" cannot answer a contiguous *multi-day* window correctly — model **busy intervals**, not per-day scalars. ``` ### Constraints & Assumptions State and use scale numbers like these (illustrative — you may pick your own reasonable defaults and justify them): - **Fleet:** a large operator, e.g. ~2,000 locations × ~200 cars ≈ a few hundred thousand cars. Each car belongs to exactly one location. - **Booking write volume is small:** even tens of millions of bookings/year is only single-digit writes/sec average, low hundreds/sec at promotional peak. - **Search is the scaling problem:** read:write skew on the order of 1000:1 → tens of thousands of search QPS at peak. - **Latency targets:** search p95 in the low hundreds of ms; booking may take a few seconds because it involves a payment call. - **A reservation is a half-open interval $[\text{pickup}, \text{return})$** with timezone-aware timestamps; store time in UTC, keep each location's IANA timezone for display and billing math. - **Consistency stance:** booking must be strongly consistent (no double-booking, ever); search may serve slightly stale availability as long as booking re-validates transactionally. A rare false "unavailable" under contention is acceptable; a double-booking is not. ### Clarifying Questions to Ask - Do customers book a **specific car (VIN)** or a **car class** (any car in that class at the location)? This heavily affects the concurrency-control strategy. - What is the database engine of record — does it support range/interval **exclusion constraints** (Postgres) or must the design work on MySQL too? - What are the **cancellation and refund** rules, and is there a free-cancellation window? - Is **pricing dynamic** (surge/seasonal) or are rate plans relatively static? Must the quoted price be locked for the duration of the booking flow? - What is the expected **promotion spike** magnitude, and which locations/classes get hot? - Are **partial-day / hourly** rentals supported, or whole-day only? How is a day that spans a DST transition billed? ### What a Strong Answer Covers A strong answer addresses the following dimensions (these are the things the interviewer is listening for, not the answers themselves): - **Requirements split & key tradeoff:** explicitly separating the strongly-consistent booking path from the eventually-consistent search path, and naming staleness-vs-correctness as the central tradeoff. - **Rough sizing:** back-of-envelope numbers that justify "booking writes are small, search reads are the scale challenge," and therefore the data-store choice. - **Data model:** locations, cars, car classes, rate plans, reservations (with the time interval), payments — and where the no-double-booking invariant lives. - **High-level architecture:** stateless search service, a single booking system-of-record, pricing, payment, an event bus, and a derived availability projection. - **APIs:** search, quote, hold, confirm, modify, cancel — with idempotency on the mutating endpoints. - **Concurrency control:** an atomic check-and-insert via exclusion constraint, pessimistic locking, or optimistic CAS — and why a read-then-write split is wrong; class-level retry to spread contention. - **Hold + payment saga:** a short-lived HELD state with TTL so the slow PSP call never holds a DB transaction; idempotency keys for retry-safety. - **Search/availability scaling:** an interval-aware projection (busy intervals, not per-day counts) served from cache/index, re-validated at booking time. - **Reliability & edge cases:** hold expiry sweeper, the self-overlap subtlety in *modify*, refunds, time zones/DST, and observability metrics. - **Bottlenecks & scaling plan:** hot-class contention, projection staleness, PSP latency — and how each is mitigated. ### Follow-up Questions - How exactly do you implement **modify** when a user extends the return date on the *same* car, so the new window overlaps their own still-active reservation? (Why does a naïve "insert new window first" fail, and what are two correct approaches?) - If the database of record were **MySQL** (no `EXCLUDE USING gist`), how would you preserve the same atomic check-and-insert guarantee? - Would you ever use a **Redis distributed lock** for booking? What can it and can it *not* be relied on for? - How would you handle **cross-location one-way rentals** (pick up in city A, drop off in city B) in the data model and availability projection? - A class shows "available" in search but the `hold` fails because someone just took the last car. How do you make this a clean UX rather than an error?