Loading...
Low latency: Request-to-match must complete in under 3 seconds. Riders abandon the app if matching takes longer, research shows abandonment rates double for every additional second of wait.
This 3-second budget includes spatial query, ETA computation for multiple candidates, driver notification via push, and the driver's acceptance tap. The system-controlled portion (everything except the driver's decision) must complete in under 1 second.
High throughput: The system handles millions of location updates per second globally. At peak, 500K concurrent drivers each sending GPS every 3 seconds means 170K writes per second just for location.
This write throughput exceeds most traditional database systems. It is comparable to IoT telemetry ingestion, not typical web application traffic.
Eventual consistency: Driver location can be 3-5 seconds stale since drivers send updates periodically. This is acceptable for matching because a driver moves at most 50 meters in 3 seconds at city speeds, well within the margin of error for "find nearby drivers."
However, not all data tolerates eventual consistency. Ride assignments must be strongly consistent to prevent double-booking. The system uses a hybrid consistency model: eventual for location, strong for ride state.
High availability: 99.99% uptime, which allows only 52.6 minutes of downtime per year. A rider stranded at 2 AM because the system is down is unacceptable, this is a service people depend on for physical transportation, not just digital convenience.
Every component needs redundancy: Redis replicas, multiple Kafka brokers, PostgreSQL standby, and at least two instances of every service behind a load balancer.
Horizontal scalability: The system must scale linearly as Uber expands to new cities without re-architecting. Adding a new city should mean deploying capacity, not rewriting code.
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
The numbers reveal why naive "scan all drivers" fails. 500K active drivers each sending GPS every 3 seconds equals 170K location writes per second. A ride request must search through these, and a full table scan will not finish in 3 seconds.
Start with the user base: 100 million registered riders, 5 million registered drivers. But registered users are not the same as active users. At peak hours (Friday evening, Saturday night), roughly 500K drivers are concurrently active (online and accepting rides), and 200K riders are concurrently looking for or on rides. Total rides completed: 2 million per day globally, averaging 23 rides per second with peaks reaching 200 per second during rush hour in major cities.
Location updates: This is the dominant write workload. 500K drivers / 3-second interval = 170K writes per second at worst case. Each update carries roughly 100 bytes (driver ID, lat, lon, heading, speed, timestamp). That is 17 MB per second of raw location data, or 1.5 TB per day just for GPS pings. In practice, adaptive update frequency (covered in Trade-offs) reduces this by 30-40% since stationary and highway drivers ping less often, but design for the worst-case baseline.
Ride requests: 200 per second at peak. Each request triggers a spatial query (find nearby drivers in the H3 k_ring), ETA computation for the top candidates using a routing engine, and a push notification to the selected driver. The spatial query must return in under 10ms to stay within the 3-second total budget for the entire matching cycle.
Live driver locations (Redis): 500K drivers at roughly 100 bytes each for the metadata hash, plus cell set membership overhead = approximately 50 MB total. This fits comfortably in a single Redis instance (typical Redis handles 10+ GB). The data is ephemeral with a 30-second TTL since a driver who has not pinged in 30 seconds is likely offline or unreachable.
Trip history (PostgreSQL): Each trip record is roughly 2 KB (rider ID, driver ID, pickup/dropoff coordinates, timestamps for each lifecycle event, fare breakdown, surge multiplier, status, rating). At 2 million trips per day, that is 4 GB per day or about 1.5 TB per year. Indexed on rider_id for "my past rides" and driver_id for "my trip history" and earnings reports.
Location history (Cassandra): Raw GPS pings retained for analytics, route reconstruction, and dispute resolution ("the driver took a longer route"). At full rate: 170K writes per second at 100 bytes = 17 MB per second, or roughly 1.5 TB per day. Storing every ping long-term is wasteful, sampling at 10% (one ping every 30 seconds instead of every 3 seconds) reduces this to 150 GB per day while preserving enough resolution for route reconstruction. Partitioned by driver ID and date with a 90-day TTL for automatic expiry.
Each WebSocket location message is roughly 100 bytes on the wire. At 170K messages per second, inbound bandwidth for location alone is 17 MB per second, or roughly 1.5 TB per day. This is manageable for modern infrastructure, but it means the Location Service fleet collectively handles more sustained throughput than most web applications see in peak bursts.
Outbound bandwidth during trips: each active ride pushes driver location to the rider every 2 seconds at roughly 200 bytes per message. With 200K concurrent rides, that is 100K messages per second outbound, or 20 MB per second. The total bidirectional bandwidth is roughly 37 MB per second sustained.
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
POST /rides: Rider requests a ride. Body includes pickup coordinates, destination coordinates, and ride type (standard, premium, XL). Returns ride ID, estimated fare, and surge multiplier. The server creates a trip record in PostgreSQL with status "requested" and triggers the matching pipeline asynchronously. The response returns immediately so the rider sees a loading screen rather than waiting for the full matching cycle.
PATCH /rides/:id/accept: Driver accepts a ride offer. Body includes driver ID. The server atomically marks the driver as unavailable in Redis (so no other ride request can claim this driver) and transitions the trip to "matched" in PostgreSQL. Returns trip details, rider pickup coordinates, and optimal route to the pickup point.
PATCH /rides/:id/status: Updates ride status through lifecycle states: driver_en_route, arrived_at_pickup, trip_in_progress, completed, cancelled. Each transition is validated server-side against a state machine to prevent invalid jumps.
For example, a ride cannot go from "requested" directly to "completed" without passing through "matched" and "trip_in_progress." This server-side enforcement is essential because multiple clients (rider app, driver app, admin dashboard) can trigger status changes.
GET /rides/:id: Returns current ride details including driver location, ETA, fare estimate, and status. Polled by riders during the pickup phase and used by customer support for dispute resolution.
GET /rides/:id/eta: Returns updated ETA for both pickup and destination. Recalculated based on driver's current position and live traffic data. During the pickup phase, this endpoint is polled by the rider app to show "Your driver is X minutes away." During the trip phase, it shows remaining time to destination.
POST /drivers/:id/availability: Driver toggles online or offline. When going online, the driver's location is added to the spatial index and the WebSocket location stream begins. When going offline, the driver is removed from the spatial index and the WebSocket connection is gracefully closed. This endpoint must be idempotent since network issues may cause duplicate requests, toggling online twice should not create duplicate entries in the spatial index.
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
Five services, one spatial index. The architecture separates concerns by access pattern: Location Service handles high-throughput writes, Ride Service handles transactional operations, and Matching Service handles CPU-intensive spatial queries. Kafka sits in the middle, decoupling producers from consumers so a slow analytics pipeline never blocks real-time matching.
The key insight: the critical path (driver GPS to Redis to matching) must be as short as possible. Everything else (history storage, surge computation, analytics) runs asynchronously off the same event stream.
High-Level Architecture: Driver GPS to Location Service to Redis, Rider request to Ride Service to Matching to Notification
Each service owns a specific data store and exposes well-defined APIs. No service directly reads another service's database, all inter-service communication happens via APIs or Kafka events.
Location Service: Stateless service behind a WebSocket load balancer. Receives driver GPS pings, validates coordinates (rejects impossible jumps, a new position more than 200km/h equivalent from the last known location is discarded as a GPS glitch), computes the H3 cell at resolution 9, and writes the updated position to Redis. Publishes each update to a Kafka topic for downstream consumers: Cassandra for location history, Surge Pricing Service for supply tracking, and analytics pipelines. This is the highest-throughput service at 170K messages per second. Because it is stateless, scaling is straightforward, add more instances behind the load balancer.
Ride Service: Manages the entire trip lifecycle in PostgreSQL. Creates trip records on ride request, enforces state machine transitions (requested, matched, driver_en_route, arrived_at_pickup, trip_in_progress, completed, cancelled), calculates and stores fare at trip completion, and exposes trip history for both riders and drivers. This is the only service with write access to the trips table, preventing data corruption from concurrent modifications by multiple services.
Matching Service: The brain of the system and the most architecturally interesting component. On a ride request, it queries Redis for drivers in the rider's H3 cell and neighboring cells via k_ring, filters for availability, computes ETA for the top candidates using a routing engine, and offers the ride to the best match. Handles the atomic driver claim via Redis SETNX to prevent double-assignment. If a driver rejects or times out, it automatically offers to the next candidate. The Matching Service is CPU-bound (ETA computation) rather than I/O-bound, so it scales differently from the other services.
Notification Service: Pushes ride offers to drivers (FCM/APNs), sends trip updates to riders, and handles SMS fallback when push notifications fail. Rate-limited to prevent notification storms during surge events. Implements priority levels: ride offers are highest priority (time-sensitive), trip updates are medium, and promotional messages are lowest.
Surge Pricing Service: Consumes location events from Kafka (driver supply per cell) and ride request events (rider demand per cell). Computes the supply/demand ratio per H3 cell over a rolling 2-minute window. When demand exceeds supply by a configurable threshold, it sets a surge multiplier (1.2x, 1.5x, 2.0x, etc.) that the Ride Service reads when calculating fare estimates. The multiplier is stored in Redis for fast access and decays automatically when demand normalizes.
Level Expectations
Mid-level: Identify the five services and explain why location data lives in Redis instead of PostgreSQL.
Senior: Explain why Kafka decouples the location ingestion path from analytics, how matching is a separate service to scale independently of trip CRUD, and why surge pricing is computed per H3 cell.
Staff: Discuss consistent hashing for Redis spatial partitioning across regions, two-level indexing (coarse city-level then fine H3-cell-level), and Redis memory capacity planning for 500K drivers across 70+ countries.
In an interview, the Matching Service is the most discussion-worthy component. It sits at the intersection of spatial indexing, real-time data, and distributed coordination, all the elements that make this system architecturally interesting.
Leading with how matching works (spatial query, ETA ranking, atomic driver claim) demonstrates both systems thinking and algorithm knowledge. Most candidates describe the service decomposition; the ones who stand out explain the matching algorithm in detail.
Two flows define this system, and they have opposite characteristics.
The location update flow runs 170K times per second, is write-heavy, and must be fire-and-forget so it never blocks the driver app. A dropped or delayed GPS ping is tolerable, the next one arrives in 3 seconds.
The ride request flow runs 200 times per second at peak, is read-heavy against the spatial index, and must complete within 3 seconds including driver notification and response. A failed ride request directly impacts revenue and rider trust. These opposing requirements explain why the two flows share infrastructure (Redis, Kafka) but follow entirely different code paths.
This is the revenue-critical path. Every second of latency here directly impacts rider experience and conversion rate.
Ride Request Flow: Rider to Ride Service to Matching to Redis to Driver Notification to Accept
The total latency budget is 3 seconds, but most of that is driver decision time. Here is how each millisecond is spent:
Step 1: Rider sends request (0ms): Rider taps "Request" in the app. The client sends POST /rides with pickup and destination coordinates to the API Gateway.
Step 2: Trip created (50ms): Ride Service creates a trip record in PostgreSQL with status "requested" and returns a ride ID to the rider immediately. The rider sees "Finding your driver."
Step 3: Spatial query (60ms): Ride Service calls Matching Service. Matching computes the rider's H3 cell and runs k_ring(center, 1) to get 7 cells. Queries Redis SMEMBERS on each cell set. Returns candidate driver IDs. This takes under 10ms.
Step 4: Filter and rank (150ms): For each candidate, Matching reads the driver hash from Redis to check availability. Computes ETA for the top 20 candidates using a routing engine. Sorts by ETA. Total: roughly 50ms for ETA calculation per batch.
Step 5: Offer to driver (200ms): Matching sends the ride offer to the top-ranked driver via Notification Service. The driver has 15 seconds to accept.
Step 6: Driver accepts (1-15s): Driver taps "Accept." The server atomically marks the driver as unavailable in Redis (SETNX on a lock key) and transitions the trip to "matched" in PostgreSQL.
Step 7: Rider notified (1-15.5s): Rider receives driver details, vehicle info, and ETA. The WebSocket trip update stream begins pushing driver location every 2 seconds.
If the driver rejects or times out after 15 seconds, the system offers to the next-ranked driver. After 3 rejections, it expands the search to k_ring(center, 2), 19 cells instead of 7. The latency budget breakdown: trip creation (50ms), spatial query and filtering (100ms), ETA computation (100ms), notification delivery (500ms), driver decision (up to 15s). The system-controlled portion completes in under 1 second; the rest is driver response time.
Why this sequential offering approach? Broadcasting to multiple drivers simultaneously would lead to race conditions, multiple drivers accepting the same ride. Sequential offering with atomic claiming (SETNX) ensures exactly one assignment per ride while giving the nearest driver first priority.
While the ride request flow is the revenue path, the location update flow is the data foundation that makes everything else possible.
Driver Location Update: GPS Ping to Validation to H3 Cell to Redis Update to Kafka
This flow is optimized for throughput and resilience. Each step is designed to be as fast as possible and to tolerate downstream failures gracefully.
Step 1: GPS ping: Driver app sends lat, lon, heading, speed, and timestamp via WebSocket every 3 seconds.
Step 2: Validate: Location Service checks for impossible jumps. If the new position implies movement faster than 200km/h from the last known position, the update is discarded. This catches GPS glitches (which can place a phone on the wrong continent), deliberate spoofing, and stale cached locations from the device. Additionally, coordinates outside valid ranges (latitude outside -90 to 90, longitude outside -180 to 180) are rejected.
Step 3: Compute H3 cell: The validated coordinates are converted to an H3 index at resolution 9 (roughly 0.1 square kilometers per cell). This is a pure mathematical function, no network call, no database lookup, just coordinate-to-cell conversion in microseconds.
Step 4: Update Redis: The driver's metadata hash is updated with the new coordinates and timestamp. If the H3 cell changed from the previous update, the system executes SREM on the old cell set and SADD on the new cell set.
Cell changes happen on roughly 5-10% of updates since most 3-second movements stay within the same cell at city driving speeds. This means 90% of updates only touch the driver's hash, a single Redis command instead of three.
Step 5: Publish to Kafka: The location event is published to a Kafka topic for downstream consumers: Cassandra (location history), Surge Pricing Service (supply tracking), and analytics. This is fire-and-forget from the Location Service's perspective, if Kafka is slow, the driver's live location in Redis is still current.
The entire update path completes in under 5ms for the critical portion (validation + Redis write). Kafka publishing happens asynchronously. This means a driver's location in the spatial index is updated within 5ms of the GPS ping arriving, fast enough that the matching system always sees near-real-time positions.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Redis holds the real-time driver map, the data structure that makes sub-second matching possible. The key design decision is how to organize drivers for spatial lookup.
Each H3 cell (resolution 9, roughly 0.1 square kilometers) maps to a Redis set containing driver IDs. Key pattern: cell:89283082e73ffff with members like driver_42, driver_789. When a driver moves to a new cell, the system removes them from the old set (SREM) and adds to the new one (SADD). Most updates (90-95%) stay within the same cell since a driver moves at most 50 meters in 3 seconds at city speeds.
Driver metadata lives in a separate hash per driver. Key: driver:42 with fields lat, lon, heading, speed, available (boolean), and last_update (timestamp). This hash is updated on every GPS ping and read during matching to filter available drivers and compute ETA.
The TTL on driver metadata is 30 seconds. If a driver stops sending pings (lost connectivity, app killed, phone died), their data expires automatically, removing them from matching consideration without any explicit cleanup job. This is elegant, the index is self-healing. No cron job needed to clean up stale drivers; Redis's built-in TTL mechanism handles it.
While Redis handles the real-time spatial data, PostgreSQL stores the transactional, permanent records that need ACID guarantees.
The trips table is the transactional core: id (UUID), rider_id (foreign key), driver_id (foreign key, nullable until matched), status (enum: requested, matched, driver_en_route, arrived_at_pickup, trip_in_progress, completed, cancelled), pickup_lat, pickup_lon, dropoff_lat, dropoff_lon, fare (calculated at completion), surge_multiplier (captured at request time), created_at, updated_at, completed_at. Indexed on rider_id for "my past rides" view, driver_id for driver earnings, and (status, created_at) for operational dashboards showing active ride counts.
The riders table stores profile data: id, name, email, phone, rating, payment_method_id, created_at. The drivers table adds vehicle-specific fields: license_plate, vehicle_make, vehicle_model, vehicle_color, vehicle_type (standard, premium, XL). These are classic relational data with referential integrity requirements, which is why PostgreSQL fits better than a NoSQL store.
Partition key: (driver_id, date). Clustering key: timestamp descending. Columns: lat, lon, heading, speed. TTL: 90 days.
This schema lets you efficiently query "all locations for driver X on date Y" for route reconstruction during dispute resolution. The compound partition key ensures each day's data for a driver lives in one Cassandra partition, keeping reads fast and partition sizes bounded (roughly 28K rows per driver per day at full resolution, or 2.8K at 10% sampling).
Write throughput matters most here. 170K writes per second at full rate, or 17K at 10% sampling. Cassandra handles this with its append-only, LSM-tree storage engine. No reads are needed on the write path, every GPS ping is an insert, never an update.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
"How do you find nearby drivers?", this is the real interview question hidden behind the system design prompt. Everything else (REST APIs, database schema, service decomposition) is standard. The spatial indexing strategy is what makes this problem uniquely interesting.
A naive scan of 500K drivers is O(N) per request. At 200 requests per second, that is 100 million distance calculations per second, impossible to sustain. Spatial indexing makes it O(1) by pre-partitioning geographic space so each query only examines the drivers in a small area, typically a few dozen candidates instead of half a million.
Three main approaches exist for partitioning geographic space. Each makes different trade-offs between simplicity, uniformity, and adaptivity.
Geospatial Indexing: Geohash rectangles vs H3 hexagons vs Quadtree adaptive cells
Geohash: Encodes coordinates as a base-32 string where a shared prefix indicates proximity. At resolution 7, each cell is roughly 150 meters on a side. Implementation is simple: truncate the geohash string for coarser resolution, prefix-match for nearby cells, and use standard string comparisons for proximity checks. The problem: rectangular cells have 8 neighbors at two fundamentally different distances. The 4 edge neighbors share a full cell side and are closer. The 4 corner neighbors share only a single point and are roughly 40% farther away. This means "find all neighbors" returns cells at inconsistent distances, potentially missing the truly closest driver because they are in a corner cell that is geometrically farther than an edge cell.
H3 (Hexagonal Hierarchical Spatial Index): Uber's open-source hexagonal grid system. Resolution 9 gives cells of roughly 0.1 square kilometers. The critical advantage: hexagons have exactly 6 neighbors, all equidistant from the center cell. There is no edge-versus-corner problem because every neighbor shares an edge. The k_ring function returns the center cell plus k rings of neighbors: k_ring(center, 1) returns 7 cells, k_ring(center, 2) returns 19, k_ring(center, 3) returns 37. The resolution hierarchy allows multi-scale indexing, resolution 7 for city-level analytics, resolution 9 for block-level matching.
Quadtree: Recursively subdivides space into 4 quadrants. When a cell contains more drivers than a threshold (say 50), it splits into 4 sub-cells. Dense areas (downtown) end up with small cells; sparse areas (suburbs) get large ones. This adaptive density is the main advantage, you do not waste granularity on empty suburbs or lose precision in crowded downtowns. The cost: rebalancing as drivers move adds complexity. Each cell split or merge requires updating the tree structure, which is harder to distribute across Redis nodes than a fixed grid like H3. In a distributed system, the tree becomes shared mutable state, a coordination headache.
H3 Nearby Search: Rider cell to k_ring expansion to Redis query to ETA ranking
H3 provides a fixed, precomputed grid, no rebalancing needed, ever. Cell IDs are deterministic functions of coordinates, meaning any service can independently compute a cell ID without querying a central authority. Equidistant neighbors make "search nearby" queries fair in all directions. The resolution hierarchy allows coarse-to-fine search: start at resolution 7 (city-level) for surge pricing, drill down to resolution 9 (block-level) for matching. Uber built and open-sourced H3 specifically for this class of geospatial problems.
With the spatial index in place, the matching algorithm is straightforward. It runs on every ride request and completes in under 100ms for the system-controlled portion:
The atomic claim uses Redis SETNX on key claim:ride_id:driver_id. If the key already exists, another matching instance claimed this driver first. The loser retries with the next candidate. Conflicts are rare (under 1%) because the probability of two ride requests targeting the same driver in the same millisecond is low.