We use cookies for site analytics. Accept to help us understand how the site is used. See our Privacy Policy for details.
Geo-indexing, real-time matching, ETA prediction, and surge. The canonical geo-spatial design problem with hard real-time constraints.
Design the dispatch backend for a ride-share product. Riders open the app and request a ride; the system finds nearby drivers, picks one, notifies driver and rider, tracks the trip in real time, completes payment.
This is the canonical geo-spatial system design question. Strong candidates demonstrate fluency in spatial indexing (geohash, S2, H3), real-time location updates, matching algorithms, and the operational layer (ETAs, surge, fraud).
Asking these before diving into a solution is the difference between a "hire" and a "no signal" rating. Pick the questions whose answers would change your design.
Driver location updates
Match queries
Storage
Maps and routing
Two real-time tiers and one supporting tier.
Real-time location ingestion: drivers stream locations to the system every few seconds. Locations index into a spatial structure for nearby-search.
Real-time matching: rider requests match → spatial query → candidate drivers → ranking → assignment → notification.
Operational support: trip lifecycle (start, in-progress, end), pricing (surge), payment, ETA service, fraud detection, dispatcher analytics.
The hardest piece is the spatial indexing layer because it's both write-heavy (driver updates) and read-heavy (match queries) with low latency on both.
Receives driver location updates over persistent connection (WebSocket or QUIC). Validates, forwards to spatial index update pipeline.
In-memory sharded index of driver_id → location, indexed by spatial cell. Enables 'find drivers in cells covering 5km radius around (lat, lon).' Sharded by spatial region.
Stateless. Given a ride request: query spatial index for candidates, rank by ETA + driver acceptance probability + surge optimization, propose match to driver.
Tracks per-trip state machine (requested, assigned, picking up, in-trip, completed). Strongly consistent (DynamoDB conditional writes). Source of truth.
Real-time ETA computation. Uses live traffic, road graph, historical times. Called pre-request, during match selection, and continuously during pickup.
Per-city road graphs. Computes shortest-path with current traffic. Heavy precomputation (contraction hierarchies) + online traffic updates.
Per-region demand vs supply ratio. Computes surge multipliers. Updates drive surge map shown to drivers and riders.
Push notifications + in-app sockets to rider and driver. Match found, driver arriving, trip status updates.
Strongly consistent ledger of trip charges. Asynchronous payment processing post-trip. Decoupled from dispatch hot path.
The subsystems where the interview is actually decided. Skim if you're running short; own these if you want a strong signal.
The central data structure is a spatial index that supports "find all drivers within R meters of (lat, lon)" in milliseconds.
Geohash
Encode (lat, lon) as a base32 string where each character refines the cell. Prefix-shared strings = nearby cells.
S2 (Google)
Project Earth onto an inscribed cube; subdivide each face into a quad-tree. Each cell = 64-bit S2 cell ID.
H3 (Uber)
Hexagonal grid. Each cell is a regular hexagon at the chosen resolution.
Recommendation: H3 for new systems. Geohash for the simplest possible answer. S2 if you're integrating with Google's stack.
Index implementation
Sharding strategy
Shard the index by spatial region (city, country). All drivers in a city sit on the same cluster. Cross-shard queries are rare (airport pickups crossing boundaries).
Resolution choice
Match resolution to typical search radius. H3 res-9 hexagon is ~150m across - good for dense urban areas. Lower resolutions (larger cells) for rural areas.
2.5M location updates per second is heavy. Naive "update one row in DB per update" doesn't scale.
Update path
Write batching
At 2.5M updates/sec, updating 2.5M Redis keys/sec needs ~50-100 Redis nodes. Batch by cell - if many drivers update at once, batch their cell-membership changes into a single MULTI/EXEC. Cuts ops by 5-10x.
Conflation
If a driver sends multiple updates in flight (network jitter), only the latest matters. Conflate at the gateway: keep the latest in-memory, write at fixed rate (2 Hz). Reduces tail-load on Redis.
Persistence vs ephemeral
The spatial index is rebuildable from current driver state. Don't persist every update. Persist a snapshot every minute for fast recovery. Crash recovery: replay live updates from connected drivers.
Driver going offline
Active flag with TTL. Each location update refreshes the TTL (60 seconds). No update for 60 seconds → driver is removed from the index automatically. No explicit "offline" message required.
Privacy
Driver locations are PII. Encrypted in flight. Aggregated location (heatmaps) for analytics; raw location only retained as long as needed for support / forensics. Don't log raw locations to wide-access systems.
Naive: pick the driver with the shortest ETA. Real systems optimize multiple objectives.
ETA-only matching
Pick driver minimizing ETA-to-pickup. Simple. Works as v1.
Multi-factor ranking
Score = w1·(-ETA) + w2·driver_acceptance_rate + w3·driver_idle_time + w4·rider_score + w5·surge_optimality.
Pool / shared rides
Match multiple riders to the same driver if their routes overlap.
Batching matches
Naive matching is per-request. Better: collect requests in 1-2 second windows, solve a batch optimization over (riders × candidate drivers).
Match acceptance
Driver might decline. Two strategies:
Real systems: sequential by default, with parallel for low-acceptance markets.
ETA appears multiple times: pre-request preview, during match selection, during pickup, during trip. Each is a query against a real-time ML system.
Components of ETA
Routing graph
Per-city road network. Nodes = intersections, edges = road segments. Edge weight = expected travel time at time t.
Live traffic input
Speed observations from in-trip drivers ("probe vehicles"). At 10M concurrent drivers globally, the platform has the densest real-time traffic data anywhere.
ML refinement
Pure shortest-path × current speeds is a baseline. ML adds:
Continuous re-estimation
During pickup, ETA is recomputed every 30 seconds and pushed to the rider's app. Sets expectations and reduces cancellations.
ETA accuracy is a product KPI
"Driver arriving in 2 minutes" that turns into 8 minutes destroys trust. Internal accuracy targets: median error < 30 seconds, p95 error < 2 minutes. Monitored continuously.
Demand spikes (rain, sports event, surge in requests) outstrip supply. Surge pricing rebalances by raising fares to attract more drivers and discourage marginal demand.
Per-cell supply-demand ratio
Compute over ~5-minute rolling window: (active requests in cell) / (available drivers in cell). Above threshold → apply surge multiplier (1.2x, 1.5x, 2x, etc.).
Geographic granularity
Surge applies per cell (H3 resolution-7 or similar - few-km hexes). Adjacent cells can have different multipliers; smoothing prevents sharp boundaries that game the system.
Driver and rider visibility
Optimization horizon
Naive surge is short-term reactive. Modern systems forecast surge 15-30 minutes ahead and incentivize drivers to position preemptively.
Anti-gaming
Fairness considerations
Surge in low-income areas is regulated in some jurisdictions. Some platforms cap surge at certain levels for accessibility services. Surge during emergencies (hurricanes) is typically suspended and pre-positioned drivers compensate via base-fare boosts instead.
The economics
Surge is the price discovery mechanism. It's not just revenue extraction - it actively shifts driver supply to where demand is. Platforms that don't surge end up with hour-long waits.
Once a match is made, the trip enters a strongly consistent state machine. This is where the dispatch system intersects payment, fraud, and support.
State machine
Each transition is an atomic write to the trip orchestrator's DB (DynamoDB conditional update or relational DB with row lock). Listeners (notifications, payment, analytics) react to state-change events.
Why strong consistency here
The match assignment must be exclusive (one driver, one trip). Two riders being matched to the same driver simultaneously is a P0 bug.
Idempotency
Drivers and riders retry actions (network flakes). Every action carries a client-generated UUID; the orchestrator dedupes. Critical for payment to avoid double-charging.
Out-of-order events
"Driver arrived" and "driver started trip" can arrive out of order (network reordering). State machine validates allowed transitions and rejects invalid ones.
Failure recovery
Trip orchestrator outage during an active trip is bad. Solutions:
Lost-driver / lost-rider
GPS loss, dead phone. Detect prolonged silence; ping the other party. Allow rider to manually mark "ride completed" if driver is unreachable. Insurance / safety policies kick in.
Fraud detection
Trip patterns that suggest collusion (driver repeatedly accepts trips from a single rider with no actual movement) are flagged for review. Fraud detection runs offline; doesn't slow the dispatch hot path.
Spatial index choice
H3 is the modern winner for ride-share. Geohash works for the simplest possible system. S2 if you're already in Google's stack. The wrong choice doubles your matching latency or boundary-hop bugs.
Match latency vs match quality
Per-request matching is fast but locally-greedy. Batch matching produces better global solutions but adds 1-2 seconds latency. Most systems run per-request for premium products and small-batch for shared rides.
Driver location update frequency
4 seconds is the production sweet spot. 1 second drains driver phone batteries and overwhelms the location pipeline. 30 seconds makes ETAs inaccurate and matching stale.
ETA accuracy vs compute cost
Pure shortest-path × live traffic is fast and ~85% accurate. ML refinement adds 10-15% accuracy at significant compute cost. Worth it for the user trust win.
Surge: market-clearing vs user backlash
Aggressive surge maximizes short-term revenue and supply rebalancing. It also generates negative press and regulatory attention. Balance the algorithm with user-facing caps and transparent communication.
Multi-product support
A single dispatch backend supporting UberX, Pool, Eats, Reserve adds significant complexity (different objectives, different time horizons). Many platforms run separate dispatchers per product line for simpler service ownership.
Be ready for at least three of these. The first one is almost always asked.
Consistent hashing, eviction, replication, and what really happens when a single hot key takes down the cluster.
Five algorithms, three sharding strategies, one fail-open vs fail-closed decision. The bounded design that surfaces in every backend interview loop.
Reading is the floor. The interview signal is in walking through this live with someone probing follow-ups. Use the AI mock interview to practice talking through requirements, architecture, and trade-offs out loud.
Start an AI mock interview →