# Pharos - Searching Nearby Drivers on Road Network at Scale

[Grab](https://yomu.fyi/company/grab) · Hao Wu · Dec 22, 2020

**Type:** Problem & solution

## 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.

## Context

Ride-hailing platforms need to allocate fast-moving drivers in real time based on actual routing distance and estimated time of arrival across road networks, where straight-line distance approximations yield suboptimal matches and longer passenger wait times.

## Approach / What changed

Grab built Pharos, a distributed in-memory spatial microservice that partitions OpenStreetMap road graphs by city and vehicle vertical, indexes driver locations using Adaptive Radix Trees, snaps coordinates to road segments as phantom nodes, and performs Incremental Network Expansion to resolve routing-based K-nearest-neighbour queries.

## Takeaways

- 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.
- 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.
- 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.

**Tags:** [Architecture](https://yomu.fyi/topic/architecture), [Microservices](https://yomu.fyi/topic/microservices), [Reliability](https://yomu.fyi/topic/reliability), [Scalability](https://yomu.fyi/topic/scalability), [Search](https://yomu.fyi/topic/search)

[Read original post](https://engineering.grab.com/pharos-searching-nearby-drivers-on-road-network-at-scale)