Pharos - Searching Nearby Drivers on Road Network at Scale

This post introduces Pharos as the next-generation solution for real-time K-nearest neighbor (KNN) search of nearby drivers based on routing distance or ETA. It addresses the limitations of the previous system, Sextant, by incorporating OpenStreetMap graphs for road networks and using 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. The architecture is described with its Proxy, Node, and Model layers, emphasizing load balancing, fault tolerance, and fast recovery. The driver storage mechanism, including snapping LatLon pairs to road segments and using ARTs for indexing, is detailed. Synchronization during concurrent driver updates and nearby requests is also explained.