uber

A rider opens the app, types "SFO Airport" as the destination, and sees "$24.50, ~23 min." This estimate appears before they commit to the ride. Let's build the pricing flow.

The Problem

Fare depends on the actual driving route, not the straight-line distance between two points. A 10km straight line might be 15km of road with turns, highway ramps, and one-way streets. Straight-line pricing would consistently undercharge for complex routes and overcharge for highway trips.

Route Calculation via Routing Service

The Ride Service sends the pickup and destination coordinates to a Routing Service. The Routing Service models the road network as a weighted graph: intersections are nodes, road segments are edges, weights are expected travel times. A shortest-path algorithm (Dijkstra or A* variant) finds the fastest route and returns the total distance and estimated duration.

The rider sees the estimate and taps "Confirm." The system creates a ride request with status SEARCHING and begins the matching process.

The architecture at this stage is straightforward: the Rider App sends a fare estimate request through the API Gateway to the Ride Service. The Ride Service calls the Routing Service for route distance and duration, computes the fare, and stores the trip record in the Trip DB. Two services, one database.

✅ NFR addressed: Basic fare estimation working

❌ Still missing: No way to find nearby drivers — a SELECT * scanning all 2M online drivers is unacceptable. No real-time tracking. No trip lifecycle management.

The rider confirmed the ride. The system needs to answer: "Which available drivers are near this rider?" and assign the best one.

The Problem

The naive approach queries the driver database directly:

With 2 million online drivers and no spatial index, this query calculates distance for every row. Standard B-tree indexes on latitude or longitude alone don't help — they narrow one dimension but still scan thousands of candidates in the other. At 1,000 ride requests per second during peak, each full-scan query holds a connection for hundreds of milliseconds, exhausting the connection pool.

Geospatial Index for Nearby Search

Instead of scanning all drivers, organize driver locations in a geospatial index that groups nearby drivers together. We use geohash-based spatial indexing: encode each driver's coordinates into a string where nearby locations share a common prefix.

When a rider requests a ride:

1. Compute the rider's geohash at the search precision (e.g., precision 6, roughly ~1km-scale cells)
2. Query the rider's cell and all 8 neighboring cells — the 9-cell search pattern handles drivers near cell boundaries
3. Filter to available drivers only, compute actual distances, remove any beyond the maximum search radius
4. Rank remaining candidates by distance from the rider's pickup point

If the initial search returns too few candidates (common in suburban areas), expand to a coarser geohash precision (~5km × 5km cells). Keep expanding until enough candidates are found or the maximum radius is reached.

Send Offer and Match

With a ranked list of nearby available drivers, the Matching Service sends a ride offer to the nearest candidate via their WebSocket connection: "New ride request, pickup at X, destination Y. Accept?"

The driver has a timeout window (e.g., 15 seconds) to respond:

• Accept: The ride transitions to MATCHED. The rider is notified with driver details and ETA.
• Decline or timeout: The system tries the next candidate on the list.

If all candidates decline, expand the search radius and try again. If no driver is found after all retries, notify the rider: "No drivers available."

⚠️ A critical correctness problem exists here: what if two ride requests simultaneously try to assign the same driver? This double-dispatch problem is covered in the Deep Dive section.

The architecture now adds three components. The Matching Service receives ride requests and queries the Geospatial Index (in-memory) for nearby available drivers. It sends ride offers to drivers through the Connection Service, which maintains WebSocket connections to Driver Apps.

✅ NFRs addressed: Sub-second geospatial lookup (geohash index), driver matching via offer/accept flow

❌ Still missing: No pipeline for ingesting 500K GPS updates/sec — who populates the geospatial index? No real-time rider tracking. No double-dispatch prevention. No trip lifecycle management.

The ride is matched. The rider is watching their phone, waiting for the driver's car icon to appear and move toward them. This requires two things: a pipeline to ingest driver GPS updates at massive scale, and a way to push those updates to the rider's device in real-time.

The Problem

Two million online drivers send GPS coordinates every 4 seconds. That's roughly 500,000 writes per second at peak — potentially bursty without client-side jitter. And during an active trip, each location update must reach the rider's phone within seconds.

WebSocket Connections

Both rider and driver apps maintain a persistent WebSocket connection to a Connection Service. WebSocket provides a bidirectional channel: the driver sends location updates upstream, receives ride offers downstream. The rider sends ride requests upstream, receives tracking updates downstream.

Location Ingestion Pipeline

Every 4 seconds, each online driver's app sends a location update over their WebSocket connection: {driver_id, lat, lng, timestamp, heading, speed}. The Location Service receives these updates and splits them into two paths:

1. Hot Path — Update the in-memory Geospatial Index. Compute the driver's geohash. Store the driver's position under that geohash key. If the driver moved to a new cell, remove from the old cell and add to the new one. This is what the Matching Service reads from. Typically low-millisecond latency per operation.

2. Cold Path — Persist location updates asynchronously for durability (trip history, analytics, dispute resolution). A message queue buffers updates; a consumer writes them to a time-series database in batches. No strict sub-second requirement, but keep end-to-end lag bounded (seconds to minutes).

The hot path handles the throughput challenge. The cold path handles the durability requirement. Neither needs to do both.

Location Relay to Rider

When a driver's location update arrives and the driver is on an active trip, the Location Service forwards it to the rider. But the rider is connected to a different Connection Service instance. How does the Location Service know which instance?

A connection registry (an in-memory key-value store) maps user_id → connection_service_instance. When a client connects, the Connection Service registers the mapping with a short TTL and periodic heartbeats. Any backend service that needs to push a message looks up the registry and routes to the correct instance.

Full flow: Driver App → Connection Service A → Location Service → [update index] → look up rider's connection → Connection Service B → rider's WebSocket → rider app renders position on map.

The rider sees the driver's position update every few seconds. The client interpolates between updates to produce smooth map animation.

Handling Disconnections

Mobile networks are unreliable. When a rider's WebSocket drops (tunnel, elevator), the system buffers recent events for each active trip. On reconnection, the client sends its last-seen event timestamp, and the server replays anything newer.

The architecture now adds four components. The Location Service receives GPS updates and splits them: the hot path updates the in-memory Geospatial Index, the cold path sends updates through a Message Queue to a Time-Series DB. The Connection Registry maps users to their Connection Service instance for cross-instance message routing.

✅ NFRs addressed: 500K writes/sec via in-memory index (high throughput), real-time driver-to-rider tracking via WebSocket (low latency), durable location history via async cold path

❌ Still missing: Trip state transitions are ad-hoc — no formal state machine. Side effects (notifications, payment) aren't reliably triggered. Double-dispatch still possible if two matching requests race on the same driver.

So far we've covered how the rider gets a fare estimate, how the system finds and matches a driver, and how location updates flow in real-time. Now we need to manage what happens after matching: the driver drives to the pickup, picks up the rider, drives to the destination, and completes the trip. Each phase has different rules and different data flowing to both parties.

The Problem

A ride involves many state changes: searching → matched → driver arrived → trip in progress → completed. Each transition triggers different side effects. When the driver is matched, the rider needs a notification. When the trip starts, fare metering begins. When it completes, payment is triggered. Without a formal state machine, these transitions become ad-hoc and error-prone — a missed notification, a fare that never starts metering, a payment that fires twice.

Trip State Machine

A trip moves through these states:

• SEARCHING — Rider requested, system is finding a driver
• MATCHED — Driver assigned, en route to pickup location
• ARRIVED — Driver reached the pickup, waiting for rider
• IN_PROGRESS — Rider picked up, driving to destination
• COMPLETED — Arrived at destination, fare calculated
• CANCELLED — Cancelled by rider or driver (rules depend on current state)

Each transition is performed atomically in a single database transaction (conditional state update + outbox insert). The Trip Service validates that the transition is legal (e.g., you can't jump from SEARCHING to IN_PROGRESS) and updates the record.

Reliable Event Publishing via Outbox Pattern

To reliably publish events after each transition, the service writes the event to an outbox table in the same database transaction as the state change. A separate process reads the outbox and publishes domain events (trip.matched, trip.started, trip.completed) to a message queue for downstream consumers. This avoids the dual-write problem where the DB update succeeds but the event publish fails.

Transition Side Effects

Idempotent Transitions

Network issues can cause duplicate transition requests. If the driver's app sends "arrived at pickup" twice due to a retry, the Trip Service handles this gracefully. Each transition checks the current state before applying. If the trip is already ARRIVED, a duplicate "arrived" request is a no-op. Side effects also need deduplication via idempotency keys or unique constraints in the outbox.

Double-Dispatch Prevention

When the Matching Service tries to assign a driver, it performs a conditional update with optimistic concurrency:

The version field prevents a subtle edge case: a driver going available → offered → available → offered in quick succession where a stale retry from the first cycle lands during the second. Without the version check, the retry would succeed because status is available again.

Fare Estimation vs Actual Fare

The estimated fare (from Step 1) uses expected route distance and time. The actual fare is calculated from metered distance and time after the trip completes. If the actual fare differs significantly (e.g., driver took a much longer route), the system can flag it for review or cap the fare at the estimate.

The final architecture adds three components. The Trip Service manages the state machine, writing each transition atomically to the Trip DB + Outbox. An outbox reader publishes domain events to the Message Queue. Event Consumers subscribe and handle side effects: notifications, payment, and analytics.

NFR Scorecard

Two million online drivers, each sending GPS coordinates every 4 seconds. That's roughly 500,000 writes per second at peak, with spikes during rush hour. A relational database doing 500K durable random writes per second on a single table would struggle — WAL/fsync overhead, index maintenance, and transaction coordination make this impractical.

Separating Hot and Cold Paths

The geospatial index for real-time matching doesn't need durability. If it crashes, connected drivers will send new updates within a few seconds — though mobile network conditions and reconnection delays mean full recovery may take longer. Replication or replay from a recent snapshot helps close this gap.

• Hot path: Driver → Location Service → in-memory geospatial index. Typically low-millisecond writes. This is what matching queries read from.
• Cold path: Location Service → message queue → batch consumer → time-series database. Writes in batches of thousands. No strict sub-second requirement, but keep end-to-end lag bounded for consumers like dispute resolution.

Sharding the Geospatial Index

Even in-memory, a single node handling 500K writes per second may hit CPU limits. Shard the index by geographic region: North America, Europe, Asia, etc. Each shard handles drivers in its region only.

Within a region, further partition by city or metro area. The sharding key is the driver's coarse geohash prefix (first 2-3 characters). Most proximity queries stay local to one shard. For riders near a shard boundary, fan out the query to the adjacent shard — handled by checking which shard owns each of the 9 neighboring cells.

Adaptive Update Frequency

Not all location updates are equally valuable:

• A driver parked at a rest stop doesn't need to report every 4 seconds
• A driver approaching a pickup needs frequent updates
• A driver on an active trip needs high frequency for rider tracking

Reduce reporting frequency when the driver is stationary or far from any ride request. Increase frequency during active trips. This can cut total update volume significantly without affecting matching quality.

Handling Stale Data

If a driver's app loses connectivity, their last-known position stays in the index. After a timeout (e.g., 30 seconds without an update), mark the driver as stale and exclude them from matching.

Rebuilding After Failure

If a geospatial index shard crashes, recovery options:

1. Wait for drivers to re-report — within one or a few reporting intervals, connected drivers send new updates. Simple, but creates a gap.
2. Replay from the message queue — the cold path queue has recent updates. Replay the last 30 seconds to rebuild faster.
3. Read replica — maintain a standby replica of each shard. On primary failure, promote the replica. Near-zero recovery time but doubles memory cost.

A common approach is replica promotion for fast failover, with client re-reporting as the natural steady-state recovery.

<discuss-with-ai-button title="Location Ingestion at Scale" context="Uber ingests ~500K GPS updates/sec from 2M online drivers. The hot path uses an in-memory geospatial index for real-time matching; the cold path persists to a time-series DB asynchronously. The index is sharded by geographic region." points='["Why can't a relational database handle 500K random writes/sec with durability guarantees?","How does the hot/cold path separation trade durability for throughput?","What happens if a geospatial index shard crashes during peak hours?","How does adaptive update frequency reduce load without hurting matching quality?","Compare geographic sharding vs consistent hashing for the geospatial index"]'>

Two riders request a ride at the same time. Both are near Driver A, the closest available driver for both. The matching service processes both requests concurrently. Without protection, both read Driver A's status as "available," both send an offer, and Driver A receives two ride requests.

Approach 1: Optimistic Concurrency Control (Recommended)

Add a version field to each driver record. The reservation operation is a conditional write:

This is optimistic because we assume conflicts are rare and handle them after the fact. In balanced markets, most drivers don't have two simultaneous offers — the conflict rate is low.

Note: WHERE status = 'available' alone prevents the basic race. The version field handles a subtler edge case: a driver goes available → offered → available → offered in quick succession, and a stale retry from the first cycle lands during the second.

Approach 2: Distributed Lock (Redis with TTL)

Acquire a lock on the driver ID before checking availability. Use an in-memory store with a TTL matching the offer window (e.g., 15 seconds). Only one matching request can hold the lock at a time.

Caveats: lock acquisition adds a network round-trip. If the lock holder crashes, you wait for the TTL to expire. Without a fencing token, edge cases can still produce double-dispatch. Under high concurrency, many requests queue on the same lock.

Recommendation: Use optimistic concurrency as the default. It's the simplest, requires no additional infrastructure, and performs well when conflicts are rare — which they are for ride matching. Mention distributed locks as an alternative if asked about higher contention.

Handling the Offer Window

The conditional update reserves the driver by setting status to offered. During the 15-second offer window, no other request can claim them. If the driver accepts, status transitions to en_route_to_pickup. If they decline or time out, status returns to available (with a new version number) and the next candidate is tried.

<discuss-with-ai-button title="Double-Dispatch Prevention" context="Two riders simultaneously try to book the same nearby driver. Without protection, both see the driver as available and both send an offer. Optimistic concurrency control with a version field prevents this race condition." points='["Why is optimistic concurrency preferred over distributed locks for ride matching?","What happens if a driver goes available→offered→available→offered rapidly and a stale retry arrives?","How does the single-writer pattern trade simplicity for availability?","What is the expected conflict rate in a balanced market vs a hotspot?","How do you handle the edge case where a driver's app crashes mid-offer?"]'>

The rider sees "Driver arriving in 4 minutes" and "Trip will take 23 minutes." These estimates affect the rider's decision to request and the driver's decision to accept. Inaccurate ETAs erode trust.

Approach 1: Straight-Line Distance

Calculate distance between two points, divide by average speed. Fast to compute. Limitation: ignores roads entirely. A 2km straight line might be 5km of winding streets.

Approach 2: Road Network Routing

Model the road network as a weighted graph: intersections are nodes, road segments are edges, weights are expected travel times. Shortest-path algorithm (Dijkstra or A*) finds the fastest route.

Raw edge weights come from speed limits, road type (highway vs residential), number of lanes. This gives a baseline ETA assuming free-flow traffic. Limitation: free-flow ETA is often wrong during rush hour. A 10-minute highway trip at 3am becomes 40 minutes at 5pm.

Approach 3: Traffic-Adjusted Routing (Recommended)

Adjust edge weights using real-time traffic data from multiple sources:

• Active drivers on the road — Drivers moving through the network report their speed via GPS updates. If 50 drivers on a highway segment average 20 km/h instead of the posted 100 km/h, that edge weight increases proportionally.
• Historical patterns — Traffic follows predictable patterns: rush hour, weekends, holidays. Historical data provides a baseline adjustment.
• External feeds — Traffic incidents, road closures, and construction from mapping data providers.

Pickup ETA vs Trip ETA

Learning from Completed Trips

After each trip, the system compares predicted ETA with actual travel time. This feedback loop improves future estimates. If the model consistently underestimates a road segment, the edge weight increases. ML models trained on millions of trips capture patterns that static routing misses: left turns at certain intersections take longer, school zones slow traffic at specific times.

Recommendation: Use traffic-adjusted routing. Road network graph with real-time edge weights from driver GPS data. Supplement with historical patterns for sparse-data scenarios. A bias toward slight overestimation creates a better UX than optimistic estimates that are frequently wrong.

The matching service found 5 nearby drivers sorted by distance. It sends an offer to Driver 1 (nearest). Driver 1 doesn't respond within 15 seconds. Now it tries Driver 2. Driver 2 declines. Driver 3 accepts — but in those 30 seconds, what has the rider experienced?

Approach 1: Sequential Cascading Offers

Try drivers one at a time, moving to the next on timeout or decline. Predictable and simple. Limitation: slow. If each candidate takes up to 15 seconds to time out, trying 5 drivers takes over a minute.

To speed this up, reduce the timeout window for subsequent candidates: First: 15s. Second: 10s. Third: 8s. Drivers who accept quickly are the ones you want.

Approach 2: Parallel Offers (Broadcast)

Send the offer to multiple drivers simultaneously. Accept the first response. The rider gets matched as soon as any driver accepts.

Limitation: if two drivers accept within milliseconds, one must be rejected. A two-phase offer/confirm flow or delayed navigation mitigates this.

Most production systems use a hybrid: send to 2-3 drivers simultaneously, accept the first, cancel the others.

Expanding Search Radius

If all candidates within the initial radius (~3km) decline, expand: 5km → 8km → maximum. The tradeoff: a driver 8km away means a long pickup time. Communicate the expected wait: "No nearby drivers. Expand search? Estimated pickup: 12 min."

Demand Queueing

During extreme demand (rainstorm, concert ending, New Year's Eve), every nearby driver may be occupied. Rather than "no drivers available," the system can queue the request and match as soon as a driver completes a nearby trip.

The rider sees: "High demand. Estimated wait: 5 min." When a nearby driver completes a trip, the system immediately offers them the queued request before they appear as "available" to new searches. This reduces wait time because drivers don't sit idle between trips.

This is where surge pricing intersects with matching: higher prices during demand spikes incentivize more drivers to go online and some riders to wait, naturally balancing supply and demand.

Recommendation: Use hybrid parallel offers (2-3 candidates) with decreasing timeout windows. Add demand queueing for peak periods. Communicate wait times transparently — riders prefer honest estimates over uncertain waiting.

The following topics contain open-ended architectural questions without prescriptive solutions. They are designed for staff+ conversations where you demonstrate systems thinking, trade-off analysis, and strategic decision-making.