Designing Real-time Car Tracking for Ride-Hailing Apps
This article breaks down the system design behind Uber's real-time car tracking, highlighting three core techniques: push messaging for efficient updates, spatial indexing with the H3 hexagonal grid for scalable driver discovery, and client-side prediction and correction for smooth animation despite network inconsistencies. It offers insights into how complex distributed systems are built to deliver seemingly simple user experiences.
Read original on Dev.to #systemdesignThe Challenge of Real-time Location Updates at Scale
Displaying moving cars in real-time on a map for millions of users requires a robust and scalable system. A naive approach of client-side polling for updates quickly becomes inefficient, consuming excessive battery, bandwidth, and server resources. Uber's system tackles this by moving from a pull-based (polling) to a push-based messaging architecture, ensuring updates are only sent when necessary and are relevant.
Push Messaging with RAMEN
Uber's internal real-time messaging platform, RAMEN, establishes long-lived connections (initially Server-Sent Events, later gRPC streams) to send updates. Key design considerations for RAMEN include:
- When to send: Only on meaningful changes (e.g., significant movement, not just a few meters).
- What to send: Small diffs or deltas instead of full state to minimize payload size.
- How to send: Utilizing persistent connections to reduce overhead compared to repeated HTTP requests.
Spatial Indexing with H3 Hexagonal Grid
To efficiently find nearby drivers among millions, Uber utilizes its open-source H3 library, a hierarchical hexagonal spatial index. This system divides the world into hexagonal cells, allowing the platform to track drivers within specific cell IDs. When a rider requests a car, the system only checks drivers in the rider's current cell and its immediate neighbors (a 'k-ring'), rather than computing distances to every driver globally. This approach scales with the local density of drivers, not the total number on the platform.
Why Hexagons over Squares?
Hexagonal grids provide a more uniform distribution of neighbors, as all six adjacent cells are equidistant from the center. This creates a smoother, more natural approximation of a circular search radius compared to square grids, which have neighbors at varying distances (edge vs. corner).
Client-Side Prediction and Correction
To ensure smooth car movement animation despite irregular network updates and GPS data, the client app employs two techniques: prediction (also known as dead reckoning) and correction. Prediction estimates the car's position between updates based on its last known speed, heading, and road context. When a new, real update arrives, a Kalman filter blends the predicted position with the measured position, giving more weight to the more reliable source. This prevents jarring 'teleportation' of the car icon, providing a fluid user experience.