LESSON 25.3
Tracking moving objects
Ingesting location updates from millions of devices, in-memory grids for nearby queries, keeping the index fresh as things move, geofencing, and how often devices really need to report.
7 min read
Geohashes and quadtrees index places that stay put. Ride-hailing, delivery and fleet tracking index things that move every few seconds. The challenge shifts from query structure to write rate and freshness.
The write rate
Start with the numbers:
- 1 million active drivers, one update every 4 s
- 250,000 updates/s
- Each update about 100 bytes
- 25 MB/s inbound
- Useful lifetime of one update
- a few seconds
Writing that into a B-tree spatial index on disk means a quarter of a million index updates a second for data that's worthless moments later. Instead, keep live locations in memory and treat history as a separate, append-only stream.
An in-memory grid
- Divide the map into cells (geohash prefix, S2 or H3 cells of roughly 1 km).
- Keep two maps in memory: cell to set of drivers and driver to (cell, position, timestamp).
- On each update, compute the new cell. If it changed, remove the driver from the old cell's set and add it to the new one; always update the position.
- A nearby query reads the rider's cell and its neighbors, then sorts the candidates by actual distance.
Redis has geo commands built on geohash-sorted sets that do this for a single node. At larger scale, partition the grid by region or cell range across many servers, and route updates and queries to the owner of each cell.
Freshness and expiry
A driver who loses signal shouldn't keep showing up as available. Each entry carries a timestamp, and entries older than a threshold (say 30 seconds) are ignored by queries and swept out periodically. If a grid server restarts, it rebuilds within seconds simply from new updates; live location doesn't need to survive restarts, because it will be stale anyway.
How often to report
The update interval is a trade-off between accuracy, battery and server load. Adaptive reporting helps: report more often while moving fast or on an active trip, less often when parked, and immediately on significant events (a turn, arrival). Clients can also skip an update if they've moved less than a few meters.
Geofencing
Geofencing flips the question: not "what's near this point?" but "which fences contain this device?", and specifically when it enters or leaves one.
Fence index by cell
- Each update checks only fences touching its cell
- Large fences cover many cells
Pick it when: Many fences, many devices.
Exact polygon test
- Precise
- Expensive per test
Pick it when: Only on the few candidate fences from the cell lookup.
Store each device's current set of fences, compare after every update, and emit an event only when membership changes. Add a small hysteresis (require a couple of consistent readings) so GPS jitter at a boundary doesn't fire enter and exit alerts back and forth.
Try it
Ride Matching HLD
Design live driver tracking and nearby search.