Real-time Driver Location and Routing Search

Grab has evolved its driver location management and search capabilities with Pharos, a system designed for high-volume, real-time K-nearest neighbor (KNN) search based on routing distance or ETA. This builds upon previous efforts like Sextant, which used haversine distance, by incorporating OpenStreetMap graphs for road networks and employing Incremental Network Expansion (INE) for more accurate routing calculations. Pharos utilizes Adaptive Radix Trees (ART) for efficient in-memory storage of driver spatial data and metadata, supporting frequent driver position updates and real-time KNN queries. The architecture is layered into Proxy, Node, and Model components for load balancing, fault tolerance, and fast recovery. Driver locations are snapped to road segments and stored using ARTs for efficient indexing and retrieval. The system handles concurrent driver updates and nearby requests through ART root synchronization and garbage collection.