Pharos - Searching Nearby Drivers on Road Network at Scale

Summary

Ride-hailing allocation requires identifying nearby drivers based on actual routing distance and estimated time of arrival rather than straight-line haversine distance. Grab developed Pharos, a distributed in-memory spatial microservice that evaluates road networks to match fast-moving drivers with pick-up requests. The system partitions OpenStreetMap road graphs by city and vehicle vertical while indexing driver positions and edge-based nodes using Adaptive Radix Trees. To locate candidates, Pharos projects driver coordinates onto road segments as phantom nodes and runs Incremental Network Expansion to compute isochrone reaches. Read-write concurrency is managed by switching tree root snapshots, allowing concurrent reads while updates produce new roots for subsequent lookups.

Takeaways

1. 1

   Pharos maintains bi-directional indexing with two Adaptive Radix Trees—Driver ART and EBN ART—offering higher throughput for numerical keys and lower memory overhead compared to hash tables.

2. 2

   Off-road GPS coordinates are mapped to the road graph via snapping, projecting positions onto nearby Edge Based Nodes to create in-memory phantom nodes.

3. 3

   Concurrent query reads and driver location updates operate without interference by providing active queries with fixed tree root snapshots while modifications generate new root pointers.