Design a Ride-Hailing Service

Problem and scope

A ride-hailing service connects riders who want a trip with drivers who are nearby and free. You open the app, enter a destination, see a price and an estimated pickup time, tap "Book", and within seconds a driver accepts. While you wait you watch the car move on the map. At the end, the fare is charged automatically. Uber, Ola, Lyft, Rapido and Grab all follow this shape.

It is a favourite interview problem because it combines three things that rarely meet in one system:

1. A firehose of small writes. Every online driver sends their GPS position every few seconds.
2. Geospatial queries. "Find free drivers within 2 km of this point" must be answered in milliseconds.
3. A strict correctness rule. One driver must never be assigned to two riders at the same time, even though many matching requests run in parallel.

Interviewers usually probe how you store and query moving locations (geohash, quadtree, S2, H3), how matching works and stays correct, and how the trip moves through its lifecycle.

Clarifying questions

That last point is a gift. Trips almost never cross between cities, so a city (or a metro region) is a natural unit of partitioning.

Functional and non-functional requirements

Functional:

• Drivers go online and offline, and stream their location while online.
• Riders see nearby cars on the map, get a fare estimate and an ETA.
• Riders request a ride; the system offers it to suitable drivers until one accepts.
• Both sides see live location during pickup and the trip.
• The trip moves through states: requested, accepted, arrived, in progress, completed or cancelled.
• At the end, a fare is calculated and payment is triggered.

Non-functional:

• Low latency for nearby-driver queries (tens of milliseconds) and matching (seconds).
• High write throughput for location updates.
• Strong consistency for assignment: no double assignment of a driver, and a trip never has two drivers.
• High availability: a city's riders cannot book if matching is down, so matching must fail over quickly.
• Durability for trips and payments. Location pings, by contrast, can be lost occasionally without harm: a newer ping arrives four seconds later.

That last contrast drives the storage design: locations are ephemeral and can live in memory; trips are money and must live in a durable database.

Back-of-the-envelope estimates

Assumptions:

• 1 million drivers online at peak, 500,000 on average.
• Each online driver sends one location update every 4 seconds.
• Each update is about 100 bytes (driver id, latitude, longitude, heading, speed, timestamp).
• 10 million completed rides per day; peak hour traffic about 5 times the average.

Location writes. 1,000,000 drivers ÷ 4 seconds = 250,000 updates per second at peak. At 100 bytes each, that is 25 MB per second of incoming data. Large in request count, small in bytes.

Memory for the current positions. We only need the latest position per driver for matching: 1,000,000 × 100 bytes = 100 MB. That fits comfortably in RAM on one machine, so the challenge is the write rate and the query pattern, not the size.

Location history. If we keep every ping for trip replay, fraud checks and ETA model training: 500,000 average drivers × (86,400 ÷ 4) pings per day × 100 bytes ≈ 1.08 TB per day. That goes to cheap append-only storage, not the hot path.

Ride requests. 10,000,000 rides ÷ 86,400 seconds ≈ 116 rides per second on average, and about 580 per second at peak. Price-estimate requests are several times higher because people check prices without booking.

Nearby-car views. Every rider with the app open polls "cars near me" every few seconds. If 2 million riders have the app open at peak and refresh every 5 seconds, that is 400,000 reads per second. Like location writes, these are small and served from memory.

API design

Drivers and riders use different APIs. Driver location usually travels over a persistent connection (WebSocket or a lightweight protocol such as MQTT) because HTTP request overhead every 4 seconds per driver adds up, and the same connection is needed to push trip offers to the driver.

# Driver app (over a persistent connection)
-> LOCATION { "lat": 12.9750, "lon": 77.5990, "heading": 90,
              "speedKmh": 22, "ts": 1760090000 }
-> STATUS   { "status": "AVAILABLE" }        # or OFFLINE
<- OFFER    { "offerId": "of_5", "tripId": "t_77",
              "pickup": {...}, "expiresInSec": 15 }
-> ACCEPT   { "offerId": "of_5" }
-> DECLINE  { "offerId": "of_5" }

# Rider app (HTTPS)
GET  /v1/nearby-drivers?lat=12.9716&lon=77.5946
  200 -> { "drivers": [ { "lat": ..., "lon": ..., "heading": ... } ] }

POST /v1/estimates
  body: { "pickup": {...}, "dropoff": {...}, "product": "SEDAN" }
  200 -> { "estimateId": "est_3", "fare": 245, "currency": "INR",
           "surgeMultiplier": 1.5, "pickupEtaSec": 240,
           "expiresAt": "..." }

POST /v1/trips
  headers: Idempotency-Key: 6b1f...
  body: { "estimateId": "est_3", "paymentMethodId": "pm_1" }
  201 -> { "tripId": "t_77", "status": "REQUESTED" }

GET  /v1/trips/t_77
POST /v1/trips/t_77/cancel

Details worth mentioning:

• The estimate is a locked quote. The fare and surge multiplier are fixed in est_3 for a few minutes, so the rider pays what they saw.
• Idempotency-Key prevents a double booking when the rider taps twice or the app retries after a timeout: the server returns the first trip for the same key.
• nearby-drivers returns approximate, anonymous positions for the map, not driver identities.

Data model and storage choice

Trip table sketch:

CREATE TABLE trips (
  trip_id        BIGINT PRIMARY KEY,
  city_id        INT NOT NULL,
  rider_id       BIGINT NOT NULL,
  driver_id      BIGINT,                 -- null until accepted
  status         VARCHAR(16) NOT NULL,
  pickup_lat     DECIMAL(9,6) NOT NULL,
  pickup_lon     DECIMAL(9,6) NOT NULL,
  dropoff_lat    DECIMAL(9,6) NOT NULL,
  dropoff_lon    DECIMAL(9,6) NOT NULL,
  quoted_fare    INT NOT NULL,           -- in paise or cents
  surge_x100     SMALLINT NOT NULL,      -- 150 means 1.5x
  final_fare     INT,
  version        INT NOT NULL DEFAULT 0, -- optimistic locking
  requested_at   TIMESTAMP NOT NULL,
  completed_at   TIMESTAMP
);
CREATE INDEX idx_trips_rider ON trips (rider_id, requested_at DESC);
CREATE INDEX idx_trips_driver ON trips (driver_id, requested_at DESC);

Money is stored as integers in the smallest currency unit to avoid floating-point rounding errors.

High-level design

 +-------------+                         +-------------+
 | Driver app  |                         | Rider app   |
 +------+------+                         +------+------+
        | WebSocket                             | HTTPS
        v                                       v
 +----------------+                     +----------------+
 | Connection     |                     | API gateway    |
 | gateway        |                     +-------+--------+
 | (driver push)  |                             |
 +---+--------+---+            +----------------+--------+
     |        ^ offers         v                         v
     | pings  |        +---------------+        +---------------+
     v        |        | Trip service  |        | Pricing and   |
 +----------------+    | (state        |<------>| ETA service   |
 | Location       |    |  machine)     |        +-------+-------+
 | service        |    +-------+-------+                |
 +---+--------+---+            |                        v
     |        |                v                +---------------+
     |        |        +---------------+        | Routing/map   |
     v        |        | Matching      |        | service       |
 +--------+   |        | service       |        +---------------+
 | Kafka  |   +------->| (per city)    |
 | (pings)|  updates   +-------+-------+
 +---+----+                    | nearby query
     |                         v
     v                 +---------------+       +-------------+
 +-----------+         | Geo index     |       | Trips DB    |
 | History,  |         | (in memory,   |       | (durable)   |
 | analytics |         |  per city)    |       +-------------+
 +-----------+         +---------------+
                                       +-------------------+
            trip completed  ---------->| Payment service   |
                                       +-------------------+

Main components:

• Connection gateway: holds millions of driver WebSockets, forwards pings to the location service, and pushes offers back to drivers.
• Location service: validates pings (drop impossible jumps), updates the geo index, and writes them to Kafka for history and analytics.
• Geo index: in-memory map from cell to the drivers in that cell, plus driver id to latest position and status. Partitioned by city.
• Matching service: for each new trip, finds candidate drivers, ranks them, sends offers, and assigns exactly one driver.
• Trip service: owns the trip state machine and the durable trips database.
• Pricing and ETA service: fares, surge multipliers and arrival estimates, using a routing service over the road map.
• Payment service: charges the rider after the trip; a separate system.

Request flows step by step

Flow 1: a driver location update

1. The driver app sends LOCATION over its WebSocket every 4 seconds.
2. The connection gateway forwards it to the location service partition for that driver's city.
3. The location service checks the timestamp is newer than the last one stored, and that the move is physically possible (no 300 km jump in 4 seconds).
4. It computes the driver's cell (for example a geohash of length 6). If the cell changed, it removes the driver from the old cell's set and adds them to the new one. It overwrites the driver's latest position.
5. It appends the ping to Kafka asynchronously. If a trip is in progress, the trip's rider is subscribed to these updates and their app gets the new position.

Flow 2: a rider requests a ride

1. The rider asks for an estimate. The pricing service asks the routing service for distance and duration, applies the city's fare rules and current surge multiplier, and stores a quote.
2. The rider taps "Book". The trip service creates a trip in state REQUESTED with the idempotency key and quote.
3. The matching service queries the geo index for available drivers in the pickup cell and neighbouring cells.
4. It asks the ETA service for road-network pickup times for the top candidates (straight-line distance is misleading: a driver across a river may be close in kilometres but far in minutes).
5. It ranks candidates, mostly by pickup ETA, also considering rating, acceptance rate and vehicle type.
6. It reserves the best driver (deep dive 3) and sends them an offer with a 15-second timeout.
7. If the driver accepts, the trip moves to ACCEPTED with driver_id set, in a single conditional update. The rider is notified. If the driver declines or times out, the reservation is released and the next candidate is tried.
8. If nobody accepts within, say, 60 seconds, the trip becomes NO_DRIVERS and the rider is told.

Flow 3: the trip itself

1. The driver drives to the pickup; both apps show live positions.
2. The driver taps "Arrived", then "Start trip" (often after checking a one-time PIN from the rider).
3. During the trip, pings are tagged with the trip id, building the actual route.
4. The driver taps "End trip". The trip service computes the final fare from actual distance and time (or the locked upfront price), moves the trip to COMPLETED, and publishes TripCompleted.
5. The payment service consumes the event and charges the rider. The driver becomes AVAILABLE again.

Deep dive 1: geospatial indexing

We need to answer: "Which available drivers are within about 2 km of this point?" A plain database table with WHERE lat BETWEEN ... AND lon BETWEEN ... uses at most one index range efficiently and scans too much at 250,000 updates per second. We need an index built for two-dimensional points.

All the popular approaches share one idea: divide the map into cells, give every cell an id, and keep a list of drivers per cell. A nearby search becomes "look in this cell and the cells around it". They differ in how cells are shaped and numbered.

Geohash

A geohash encodes a latitude and longitude into a short string. It works by repeatedly halving the world: the first bit says east or west half for longitude, the next says north or south half for latitude, alternating, and every 5 bits become one base-32 character. Each extra character makes the cell about 32 times smaller.

Approximate cell sizes (they vary with latitude):

Worked example in Bengaluru. A rider stands at (12.9716, 77.5946). Three available drivers are nearby. Computing geohashes and straight-line (haversine) distances:

The rider's length-5 cell is tdr1v. Notice two traps:

• D2 is close (1.63 km) but in a different length-5 cell (tdr1y), because a cell boundary runs between them. A search of only the rider's cell would miss D2. That is why you always search the rider's cell plus its 8 neighbours.
• D3 shares the 5-character prefix but is 3.36 km away. Sharing a prefix means "same cell", not "close". So after collecting candidates from the 9 cells, compute real distances and filter.

The algorithm:

1. cell = geohash(rider, precision 6)
2. cells = cell + its 8 neighbours        (9 cells, about 3.6 km x 1.8 km)
3. candidates = union of available drivers in those cells
4. if too few candidates: drop to precision 5 and repeat
5. compute distance (and later road ETA) for each candidate
6. keep those within the radius, sort by ETA

Here is a small, runnable geohash encoder and distance function used to build the table above:

import math
BASE32 = "0123456789bcdefghjkmnpqrstuvwxyz"


def geohash(lat, lon, precision):
    lat_lo, lat_hi, lon_lo, lon_hi = -90.0, 90.0, -180.0, 180.0
    bits, even, out, ch = 0, True, [], 0
    while len(out) < precision:
        if even:
            mid = (lon_lo + lon_hi) / 2
            ch = ch * 2 + (lon >= mid)
            lon_lo, lon_hi = (mid, lon_hi) if lon >= mid else (lon_lo, mid)
        else:
            mid = (lat_lo + lat_hi) / 2
            ch = ch * 2 + (lat >= mid)
            lat_lo, lat_hi = (mid, lat_hi) if lat >= mid else (lat_lo, mid)
        even = not even
        bits += 1
        if bits == 5:
            out.append(BASE32[ch])
            bits, ch = 0, 0
    return "".join(out)


def haversine_km(lat1, lon1, lat2, lon2):
    r = 6371.0
    p1, p2 = math.radians(lat1), math.radians(lat2)
    dp, dl = p2 - p1, math.radians(lon2 - lon1)
    a = math.sin(dp / 2) ** 2 + math.cos(p1) * math.cos(p2) * math.sin(dl / 2) ** 2
    return 2 * r * math.asin(math.sqrt(a))


rider = (12.9716, 77.5946)
drivers = {"D1": (12.9750, 77.5990), "D2": (12.9650, 77.6080), "D3": (12.9900, 77.5700)}
print("rider", geohash(*rider, 6), geohash(*rider, 5))
for d, (la, lo) in drivers.items():
    print(d, geohash(la, lo, 6), round(haversine_km(*rider, la, lo), 2), "km")

Output:

rider tdr1v9 tdr1v
D1 tdr1vf 0.61 km
D2 tdr1y0 1.63 km
D3 tdr1vh 3.36 km

Geohash strengths: very simple, a string prefix works with any key-value store or sorted index, and Redis geo commands use a closely related encoding internally. Weaknesses: cells are rectangles whose shape changes with latitude, and neighbouring cells can have very different prefixes.

Quadtree

A quadtree is a tree where each node covers a rectangle and splits into four children (north-west, north-east, south-west, south-east) when it holds too many points, for example more than 100 drivers. Dense areas such as a city centre get deep, small cells; empty highways stay as large cells.

+-----------------+-----------------+
|                 |        |        |
|   few drivers   |  NW    |  NE    |
|   (leaf)        |--------+--------|
|                 |  SW    |  SE    |
+-----------------+--------+--------+
|                 |                 |
|   few drivers   |   few drivers   |
|   (leaf)        |   (leaf)        |
+-----------------+-----------------+
   the busy top-right quadrant was split again

Search walks down to the rider's leaf and checks neighbouring leaves until enough drivers are found. Strength: adapts to density, so each leaf has a similar number of drivers. Weakness: drivers move constantly, so points jump between leaves and the tree must split and merge. It is a structure you build in memory in your own service, not something a generic database gives you.

S2 and H3

S2 (from Google) projects the sphere onto the six faces of a cube and orders cells along a Hilbert curve, a space-filling curve that keeps nearby cells close in id order. Each cell has a 64-bit id, there are 31 levels from the whole face down to about a square centimetre, and a region such as a circle can be covered by a small set of cells, each becoming a range of ids to scan.

H3 (from Uber) divides the world into hexagons at 16 resolutions. The key property of a hexagon: all six neighbours share an edge and their centres are the same distance away. With squares, diagonal neighbours are farther than edge neighbours. Equal-distance neighbours make "rings" of cells around a point uniform, which is very convenient for smoothing surge prices and computing supply and demand per area.

Keeping the index fresh

With 250,000 updates per second, the index must be cheap to update:

• Keep two maps per city partition: driver_id -> (lat, lon, cell, status, ts) and cell -> set of driver_ids.
• On each ping, update the first map; only when the cell changes, move the id between sets. A driver moving at 30 km/h crosses a 600 m cell roughly every minute or so, so most pings do not change cells.
• Expire drivers whose last ping is older than, say, 30 seconds: they lost signal or closed the app. Never offer a trip to a stale driver.

Deep dive 2: matching riders to drivers

The simplest approach is greedy: for each request, offer it to the driver with the lowest pickup ETA. It is easy and works acceptably, but it is not globally best.

Example of greedy going wrong. Rider R1 requests and the nearest driver D1 is 2 minutes away; D2 is 4 minutes away. One second later, R2 requests; D1 is 3 minutes away from R2, but D2 is 12 minutes away. Greedy gives R1→D1 (2) and R2→D2 (12): total 14 minutes. Assigning R1→D2 (4) and R2→D1 (3) gives 7 minutes. Batch matching collects requests for a short window (a few seconds) and solves an assignment problem (for example with the Hungarian algorithm or a min-cost matching heuristic) that minimises total pickup time across the batch. The trade-off is a small added delay for each request.

Ranking signals beyond ETA include vehicle type, driver rating, acceptance history, and whether the driver is about to finish a nearby trip (a driver 1 minute from finishing a trip nearby may be better than an idle driver 10 minutes away).

Offers. A common pattern is to offer to one driver at a time with a short timeout. Offering to several at once and taking the first to accept is faster, but annoys drivers who accept and then lose the trip. Some systems use small parallel waves.

Deep dive 3: no double assignment

Two matching workers may pick the same driver for two different trips at the same moment. Or a driver may tap accept on an offer that has just expired and been sent elsewhere. We need a guarantee: one driver, at most one active trip; one trip, at most one driver.

The tool is an atomic compare-and-set (CAS): "change this value only if it is still what I expect". Each driver has a status record:

driver D1: { status: AVAILABLE, trip: null, version: 41 }

1. Reserve. The matcher atomically sets D1 from AVAILABLE to OFFERED(t_77) only if status is AVAILABLE. If another matcher already reserved D1, this fails and the matcher picks the next candidate. The reservation carries an expiry (a lease) of, say, 20 seconds.
2. Accept. When D1 accepts, the trip service runs one conditional update in the trips database:

UPDATE trips
SET driver_id = 1001, status = 'ACCEPTED', version = version + 1
WHERE trip_id = 77 AND status = 'REQUESTED' AND driver_id IS NULL;

If one row was updated, the assignment won. If zero rows were updated (the rider cancelled, or another driver already accepted), the accept fails and D1 is told "trip no longer available". Then D1's status changes from OFFERED(t_77) to ON_TRIP(t_77), again with a CAS. 3. Release. On decline or lease expiry, a CAS sets D1 back to AVAILABLE only if it is still OFFERED(t_77), so a late timeout cannot undo a successful accept.

Where should the driver status live? The simplest way to make CAS fast and safe is to give each city (or each region within a large city) a single owner for driver state: one partition leader, with replicas for failover. All matching for that city goes through that owner, so CAS is a local operation. Redis with a WATCH/MULTI transaction or a Lua script, or a database row with a version column, both work.

Deep dive 4: the trip state machine

A trip is a state machine: a fixed set of states and allowed transitions. Writing it down prevents impossible situations like completing a trip that never started.

            rider cancels
   +-------------------------------------+
   |                                     v
REQUESTED --driver accepts--> ACCEPTED --+--> CANCELLED
   |                             |       ^
   | nobody accepts              | driver arrives
   v                             v       |
NO_DRIVERS                    ARRIVED ---+
                                 |
                                 | trip starts (PIN ok)
                                 v
                            IN_PROGRESS
                                 |
                                 | driver ends trip
                                 v
                             COMPLETED --> payment triggered

Rules:

• Every transition is a conditional update: UPDATE ... SET status = 'ARRIVED' WHERE trip_id = ? AND status = 'ACCEPTED'. Illegal transitions affect zero rows and are rejected.
• Every transition is also published as an event (TripAccepted, TripCompleted), ideally through an outbox table written in the same transaction, so notifications, payments and analytics never miss one.
• Cancellation fees depend on the state at cancellation, so the state history is stored for disputes.

Surge pricing at a high level

Surge pricing raises prices in an area when demand exceeds supply, which both rations scarce cars and encourages more drivers to come online or move there.

1. Divide the city into zones, for example H3 hexagons of a few hundred metres to a kilometre.
2. Every minute or so, compute per zone: demand (ride requests and app opens in the last few minutes) and supply (available drivers).
3. Map the demand-to-supply ratio to a multiplier using a configured curve with a cap.
4. Smooth across neighbouring zones and over time, so prices do not jump wildly between adjacent streets or minutes.

Worked example. In one zone, 120 requests arrived in the last 5 minutes and 40 drivers are available, so the ratio is 120 ÷ 40 = 3. With an illustrative curve multiplier = min(2.0, 1 + 0.25 × (ratio − 1)), the multiplier is 1 + 0.25 × 2 = 1.5. A 200-rupee base fare becomes 300 rupees. The multiplier is locked into the rider's estimate, so it does not change after they tap "Book". Real systems use more signals and machine-learned forecasts, and may be constrained by local regulations on price caps.

ETA at a high level

An ETA (estimated time of arrival) is computed on the road network, not with straight lines:

1. The map is a graph: intersections are nodes, road segments are edges weighted by travel time.
2. A shortest-path algorithm (Dijkstra, A*, or a precomputed speed-up technique like contraction hierarchies, which lets queries skip over less important roads) gives a route and its time.
3. Edge weights come from live and historical speeds, which are themselves computed from driver GPS pings. Your own fleet is a traffic sensor.
4. A machine-learning model corrects the routing estimate using time of day, weather, pickup difficulty and past errors.

Matching may ask for many ETAs per request, so the ETA service must be fast; a common optimisation is to compute straight-line distance first, keep the closest 10 to 20 drivers, and compute road ETAs only for those.

Payments handoff

The ride service should not process cards itself. When a trip completes, it publishes TripCompleted with the trip id, rider, final fare and payment method. The payment service consumes it and charges the rider, using the trip id as an idempotency key so a redelivered event never charges twice. Cash rides only record the amount owed to the platform by the driver. Failed charges retry and, if they still fail, mark the rider's account as owing money before their next ride. Driver payouts are aggregated and paid out daily or weekly from a ledger. See Booking and payments design for the payment patterns in more depth.

Scaling and bottlenecks

Partition boundaries. A rider near the edge of a partition may have the best driver on the other side. The matcher queries both partitions; reservation then happens on the driver's owning partition. Make partitions large enough that this is rare.

Failure handling

• Driver loses signal: pings stop; after the staleness timeout the driver is removed from search. An in-progress trip continues and catches up when the signal returns; the app buffers pings offline and uploads them later for fare calculation.
• Location service node dies: a replica takes over; the index rebuilds within seconds because every online driver pings again every 4 seconds. Losing the in-memory state is cheap. This is why in-memory is acceptable here.
• Matching owner fails during a reservation: reservations are leases with expiry, so a stuck OFFERED status frees itself. The trip remains REQUESTED and the new owner retries matching.
• Driver accepts after the offer expired: the conditional update fails, and the driver sees "trip no longer available".
• Rider double-taps Book: the idempotency key returns the same trip.
• Payment service down: TripCompleted events wait in the queue; payments catch up later without affecting rides.
• Whole region outage: fail over cities to a standby region; trips in progress keep working on the apps and reconcile afterwards.

Trade-offs and alternatives

What interviewers probe

"How do you show the rider the car moving smoothly if pings come every 4 seconds?" The app interpolates between points and snaps them to the road map. Pings during a trip can be sent more often if needed.

"How do you handle GPS noise and spoofing?" Map-matching snaps noisy points to roads. Reject physically impossible jumps, compare with cell-tower and Wi-Fi hints, and flag drivers whose patterns suggest fake-location apps.

"How would you add pooled rides?" Matching now inserts a new rider into an existing trip's route, checking that the detour for current riders stays under a limit. The state machine tracks multiple pickups and drop-offs per vehicle.

"Why not use PostGIS for everything?" A spatial database is excellent for durable geographic data and complex queries, and fine at modest scale. At hundreds of thousands of location updates per second, writing every ping to it creates heavy write and index churn for data that is overwritten seconds later. Keep it for history and analytics, and keep the live index in memory.

"What consistency does the map of nearby cars need?" Very little. It is decorative and can be a few seconds stale, so it can be served from read replicas. Only the assignment step needs strong consistency.

Interview questions

Q1. Why keep driver locations in memory rather than in a database?

The current positions of a million drivers take only about 100 MB, but they change 250,000 times per second and are useless after a few seconds. An in-memory index handles that write rate cheaply. If a node dies, the index rebuilds within seconds from the next round of pings, so durability is not needed for this data.

Q2. How does a geohash work?

It alternately halves the longitude and latitude ranges, writing one bit per halving, and encodes every 5 bits as a base-32 character. Points in the same cell share a prefix, and longer hashes mean smaller cells. It turns a 2D lookup into a string prefix lookup that any key-value store can handle.

Q3. Why search neighbouring cells as well?

A nearby driver can be just across a cell boundary and have a completely different prefix. Searching the rider's cell plus the eight around it (or an H3 ring) catches them. You then filter by actual distance, because sharing a cell does not guarantee closeness.

Q4. Compare quadtrees with fixed grids like geohash.

A quadtree splits busy areas into smaller cells and leaves empty areas as large cells, so each leaf holds a similar number of drivers. A fixed grid is simpler and maps to plain keys, but dense cells can hold thousands of drivers while rural cells hold none. Quadtrees are harder to maintain with constantly moving points.

Q5. Why might you choose H3?

H3 uses hexagons, whose six neighbours are all equally distant, so rings around a point are uniform. That makes neighbourhood searches and area statistics such as supply, demand and surge cleaner than with squares. It also offers a fixed hierarchy of resolutions with 64-bit ids.

Q6. How do you prevent assigning one driver to two trips?

Use an atomic compare-and-set on the driver's status: reserve them only if they are available, and confirm the trip with a conditional update that succeeds only if the trip is still unassigned. Reservations carry expiries so crashed matchers do not lock drivers forever. Keeping a single owner per city partition makes these operations local and fast.

Q7. What is batch matching?

Instead of assigning each request instantly to its nearest driver, the matcher collects requests for a few seconds and assigns them together to minimise total pickup time. It produces better overall assignments in busy areas, at the cost of a small delay per request.

Q8. How is ETA computed?

Shortest-path search over a road graph whose edge weights are live and historical travel times, usually sped up with precomputation such as contraction hierarchies. Machine-learned corrections adjust for time of day and local conditions. Straight-line distance is only used to shortlist candidates.

Q9. How does surge pricing work at a high level?

The city is divided into zones; for each, demand and supply over recent minutes produce a ratio that a capped curve maps to a multiplier. Values are smoothed in space and time, and the multiplier is locked into the rider's quote.

Q10. Why model the trip as a state machine?

It makes allowed transitions explicit, so invalid ones such as completing an unstarted trip are rejected by a conditional update. It also gives a clean event stream for notifications, payments and audits, and determines fees such as cancellation charges.

Q11. How do you partition the system?

By city or metro area, since trips rarely cross them, and split very large cities into several geographic partitions. Each partition owns its drivers' live state and matching. Riders near a partition edge query adjacent partitions.

Q12. What happens if a driver accepts an offer that has already expired?

The accept runs a conditional update that requires the trip to still be unassigned and the driver to still hold that offer. Because the offer expired and the trip may have gone to someone else, the update affects no rows, and the driver is told the trip is no longer available.

Q13. How does the payment step stay safe from double charges?

The trip service emits a TripCompleted event and the payment service charges using the trip id as an idempotency key. Redelivered events or retries find the existing charge and do nothing new.

Key takeaways

• Separate ephemeral, high-rate location data (in memory) from durable trip and payment data (database).
• Driver pings are about 250,000 writes per second at our scale but only around 100 MB of live state.
• Geospatial indexes divide the map into cells: geohash, quadtree, S2 or H3. Search the cell plus neighbours, then filter by real distance and rank by road ETA.
• Matching can be greedy or batched; batching improves global pickup times in dense areas.
• Prevent double assignment with atomic compare-and-set reservations, leases and conditional updates.
• Model the trip as a state machine with conditional transitions and published events.
• Partition by city; surge and ETA are separate services fed by the same location stream.
• Hand payments to a payment service with idempotency keys.

Next lesson

Continue with Design a notification system.