car-rental

How it is built

Architecture overview

A car rental platform sells a perishable resource: a vehicle for a time interval at a branch, in a class (compact, SUV, van) rather than as a specific car, until pickup. It has to answer "what is available and at what price" in a fraction of a second for many searches, commit a reservation without selling the same capacity twice, move cars between branches to where demand will be, and handle the physical event of pickup, use and return, with money held, charged and refunded along the way. The idea that makes it work is a split between state that must be exact (inventory per class and interval, payment state, the rental agreement), which sits behind a small transactional core with idempotent operations and explicit state machines, and estimates that may be wrong (demand forecasts, prices, rebalancing plans), which are computed offline or in the background and handed to the core as numbers. Everything else (partner feeds, notifications, accounting, telematics) is driven by events published from the core, never by direct writes into it.

Parts:

• Availability and reservation — class/branch/interval inventory with holds, no overselling — inventory-reservation (no page yet), Interval tree, Optimistic concurrency control, conditional-writes (no page yet), Hierarchical timing wheel, Idempotency keys, calendar-date-arithmetic (no page yet), Sharded counters
• Demand forecasting — expected pickups, returns and utilisation per branch and class — Time-series forecasting, Exponential smoothing, STL decomposition, Time-series cross-validation, arima (no page yet), croston-method (no page yet), Gradient-boosted trees, Linear and logistic regression, Kalman filter
• Pricing and revenue management — the price and booking limits per class, length of rental and day — revenue-management-emsr (no page yet), Dynamic pricing, Linear programming (simplex), Robust statistics, Evaluation metrics
• Fleet allocation — where each class should be tomorrow and how to move cars there — min-cost-flow (no page yet), Dijkstra, bellman-ford-negative-cycles (no page yet), d-ary heap, Geodesic distance, point-in-polygon (no page yet)
• Rental agreement and payments — the lifecycle from quote to final invoice, with deposits and refunds — Payment state machine, Hierarchical state machine, Event sourcing, Saga pattern, Exponential backoff with jitter, Money representation, largest-remainder-rounding (no page yet), Floating-point error
• Events and integration — reliable hand-off of state changes to other services, partners and accounting — Transactional outbox, Change data capture, Durable job queue, Dead-letter queue, Event deduplication, Consumer offsets, Message sequence numbers, Incremental sync cursors, cursor-pagination (no page yet), Leases, Fencing tokens, Write-ahead log, Segmented log
• Vehicle connectivity — location, fuel, mileage, doors and keyless access — can-bus-framing (no page yet), ble-gatt (no page yet), mqtt-protocol (no page yet), Kalman filter, Geodesic distance, CRC32C checksums, Cryptographic hashes
• Condition inspection — damage found by comparing pickup and return photos — Object detection, Convolutional networks, Non-maximum suppression, Data augmentation, Evaluation metrics

 customer / broker / partner feed
        │ search, quote, book                     nightly                  telematics (CAN, BLE, MQTT)
        ▼                                            │                              │
  ┌─────────────┐ reads  ┌───────────────┐   ┌──────▼───────┐               ┌──────▼───────┐
  │ search /    │───────►│ availability  │◄──│ pricing +    │◄── forecasts ─│ fleet state  │
  │ quote API   │        │ + holds (OCC) │   │ revenue mgmt │               │ + positions  │
  └──────┬──────┘        └───────┬───────┘   └──────────────┘               └──────┬───────┘
         │ book (idempotent)     │ commit                                          │
         ▼                       ▼                                                 ▼
  ┌──────────────────────────────────────────┐   outbox / CDC   ┌───────────────────────────┐
  │ rental agreement + payment state machine │─────────────────►│ queue → billing, notify,  │
  │ (events, sagas, deposits, refunds)       │                  │ partner sync, accounting  │
  └──────────────────────────────────────────┘                  └───────────────────────────┘
         ▲ pickup / return at branch (agent app, photos, damage check)

The platform has two modes. The commerce path (search, quote, book) is latency-bound and read-heavy with a short, strict write. The operations path (pickup, return, cleaning, transfers) is slower, driven by people and vehicles, and creates the events that close the loop with the financial path.

How the parts fit together

Availability and reservation

The unit of capacity is "cars of class C at branch B", and a reservation occupies it for an interval. The count for any instant is the number of cars (fleet minus out of service) minus the reservations overlapping that instant. An Interval tree answers "which reservations overlap this window" for a branch; the usual production alternative is a per-day or per-hour counter row per class, which is cheaper to update and read. Which one wins depends on how long rentals are and how fine the time grid is: counters fit rentals counted in days, intervals fit hour-level pricing and one-way trips.

The commit step must not oversell. Two designs work. Optimistic concurrency control reads the counters, computes the new value and writes with a version check; a conflicting booking retries. conditional-writes (no page yet) is the same idea on a key-value store, and the hold lives with an expiry so an abandoned checkout returns its capacity (a Hierarchical timing wheel is the in-memory structure for many expirations; a TTL column and a sweeper is the simple version). Hot rows are the problem: a small branch with few cars of one class at peak is contended by definition, and Sharded counters only help when overselling by a small bound is allowed, which for cars is a business rule (overbooking is deliberate, see Pricing) and not an accident.

Every booking call carries an Idempotency key: a client that times out retries the same request and gets the same reservation back. Dates and times need one rule set (calendar-date-arithmetic (no page yet)): the rental period is in the pickup branch's local time zone, a "day" is 24 hours from pickup on most price lists, and a DST change inside the interval must not change the price by accident.

Demand forecasting

Fleet and price decisions look ahead by days to weeks, per branch, class and length. Time-series forecasting is the recipe: set the horizon, beat a seasonal-naive baseline, and validate by rolling-origin cross-validation. Exponential smoothing and STL decomposition handle weekly and yearly seasonality per series cheaply; arima (no page yet) is the classical alternative. Many small branches have intermittent demand for rare classes, where croston-method (no page yet) fits better than smoothing. Gradient-boosted trees take features (day of week, holiday, local events, flight arrivals, lead time, current bookings on hand) and produce a forecast and quantiles of it; Linear and logistic regression is the baseline for "probability a booking is cancelled or does not show". Observations of the pace of bookings can be filtered with a Kalman filter. Since reservations are censored (the sold-out class hides demand), use Robust statistics and unconstrain demand before fitting. The contract with pricing: each forecast is a distribution (mean and a spread), not a point.

Pricing and revenue management

The price list is a function of class, length of rental, lead time and utilisation. revenue-management-emsr (no page yet) is the classic way to set booking limits when capacity is shared by fare classes: the EMSR heuristic by Belobaba is cited below, and the National Car Rental case study in the sources is the car-rental application. The output is a bid price or a booking limit per class and length: a booking below the bid price is declined or priced up because that capacity is expected to sell for more. When demand for one-day and multi-day rentals competes for the same cars, the allocation is an LP; Linear programming (simplex) solves it, and its dual values are the bid prices. Dynamic pricing covers the price-response side, how a price moves with remaining capacity and demand. Evaluate by Evaluation metrics of forecast error and by holdout revenue, not by model loss alone.

Fleet allocation

Cars drift: one-way rentals and airport demand leave some branches empty and others full. Repositioning is a minimum-cost flow problem (min-cost-flow (no page yet)): branches are nodes with supply (surplus cars) and demand (shortfall from the forecast), edges are transfer lanes with cost (driver, transporter, opportunity), and the solution is the cheapest set of moves that meets demand. The shortest-path building blocks are Dijkstra with a d-ary heap when costs are non-negative and bellman-ford-negative-cycles (no page yet) when the residual graph has negative edges. Geodesic distance gives the first estimate of lane length, and point-in-polygon (no page yet) decides which branch or geofence a telematics ping belongs to. Alternatives: the same problem as a general LP with Linear programming (simplex), or interior-point solvers for very large networks.

Rental agreement and payments

A rental is a long-lived state machine: quoted, held, confirmed, picked up, returned, closed, and the side branches cancelled, no-show, extended, disputed. Hierarchical state machine keeps that tractable (a "picked up" state with substates for "inspected" and "fuel surcharge applied"), and Event sourcing records each transition, which gives an audit trail for disputes and the events the other services consume. Payment has its own life: Payment state machine authorises a deposit at pickup, captures the rental charge at return, and voids or refunds the rest; a gateway timeout is "unknown", not "failed", and is resolved by querying, never by charging again.

Booking across services (inventory, payment, partner confirmation, notification) is a Saga pattern: each step has a compensation (release the hold, void the authorisation), and a failure runs them in reverse. Retries to external gateways use Exponential backoff with jitter. Money is integer minor units (Money representation), tax and fees are split so the parts sum exactly (largest-remainder-rounding (no page yet)), and Floating-point error is why no price touches a binary float except in a forecast.

Events and integration

Other systems (accounting, e-mail, brokers, loyalty) need to learn about every state change, exactly once in effect. The Transactional outbox writes the event in the same local transaction as the state change; a relay publishes it. When the system cannot be changed to write the outbox, Change data capture reads the database log instead. A Durable job queue runs the slow work with leases and retries and parks poison messages in a Dead-letter queue. Consumers are idempotent (Event deduplication) because delivery is at least once, they keep their position in Consumer offsets, and per-stream Message sequence numbers show gaps. Partners that sync inventory and reservations pull deltas with Incremental sync cursors over cursor-pagination (no page yet). When only one worker may run a job (nightly repricing), a Lease with Fencing tokens stops a paused ex-owner from writing late. Underneath, the stores rely on a Write-ahead log and a Segmented log for the event stream; CRC32C checksums protect log frames.

Vehicle connectivity

A connected car reports location, odometer, fuel or charge level, and door and ignition state. In-vehicle signals live on a can-bus-framing (no page yet) bus; a telematics unit gateways them to the cloud over mqtt-protocol (no page yet), which gives QoS levels and a session that survives reconnects. Keyless access uses ble-gatt (no page yet) between phone and car, with keys signed and checked with hashes and MACs (Cryptographic hashes). GPS fixes are noisy, so a Kalman filter smooths position; Geodesic distance turns positions into trip distance and geofence distance. The contract with the core: device messages arrive out of order and duplicated, so they carry a device timestamp and a sequence number, and only the newest per car is applied.

Condition inspection

Damage disputes are costly. A pickup and return photo set per car can be compared by an Object detection model (dents, scratches, glass), whose body is a Convolutional network, whose duplicate boxes are removed by Non-maximum suppression, and which is trained with Data augmentation because lighting and angle vary. A review step by a person is the default for any charge above a threshold, so precision on "new damage" matters more than recall; see Evaluation metrics.

Data and control flow

One booking.

1. Search reads the price list, the forecast-derived bid prices and approximate availability from a cache; no write.
2. The customer picks a quote; the API creates a hold on the class and interval (conditional write with a version check) and returns a hold id with an expiry.
3. The payment step authorises the card with an idempotency key; the payment state machine moves to authorised.
4. The reservation commits: the agreement changes from held to confirmed, the counter decrement and the outbox row are written in one local transaction.
5. The relay publishes "reservation confirmed"; consumers send the e-mail, update the partner feed and post the accounting entry. A consumer failure retries and finally lands in the dead-letter queue.
6. If any step fails, the saga runs the compensations: void the authorisation, release the hold.

One rental.

1. At pickup the agent (or the keyless flow) assigns a specific car of the booked class; its odometer, fuel and photos are stored, and a deposit is authorised.
2. During the rental, telematics events update position and mileage; an extension request reprices from the current time and re-checks availability.
3. At return, the system reads mileage, fuel and photos, runs the damage comparison, and computes the final charge from the price list and the extras.
4. Capture the rental charge, release the rest of the deposit, close the agreement; the car goes to cleaning and then back into availability.

One nightly planning cycle.

1. Load bookings and returns, refit or update forecasts per branch and class.
2. Compute bid prices and booking limits from the forecast distribution and the LP.
3. Solve the repositioning flow and create transfer tasks for the branches.
4. Publish new prices and limits; the commerce path picks them up from a cache or table, not from the job.

Scaling

1. Contention on small capacity is the first limit, not request volume: popular classes at one airport branch on one weekend. Partition the inventory by branch and class (so a conflict stays local), shorten the hold window, and keep the commit as a single conditional write.
2. Search fan-out comes next: many searches per booking. Cache prices and approximate availability, recompute on events, never on the request.
3. Forecasting and optimisation compute grows with branches times classes times lengths; run it as a nightly job, per branch in parallel, and keep the model simple (smoothing before trees).
4. Event volume from telematics is the largest stream; sample or aggregate at the edge, keep only the newest position per car online, and log the rest to a segmented log for analytics.
5. Partner and broker sync scales by pull cursors and rate limits, not push to every partner.

Failure modes

Real implementations

Large rental companies (Enterprise, Hertz, Avis Budget) and peer-to-peer platforms (Turo) run mostly internal, closed systems. The open projects below implement individual parts:

Sources

• J. Geraghty and M. Johnson, Revenue Management Saves National Car Rental, Interfaces 27(1), 1997. paper.
• P. Belobaba, Application of a Probabilistic Decision Model to Airline Seat Inventory Control, Operations Research 37(2), 1989: EMSR for nested booking limits. paper.
• H. Garcia-Molina and K. Salem, Sagas, SIGMOD 1987. paper.
• Repositories in the table above (licences from the GitHub API).