Real-Time Geospatial Tracking

Live location for vehicles, couriers and fleets

Design a system that takes in a steady stream of GPS positions from a million moving devices, shows each one live to the people watching it, and fires an event when a device enters or leaves a zone.

Overview

A tracking system answers one question over and over: where is this thing now? Phones and vehicle trackers send a GPS position every few seconds. The system keeps the newest one, shows it live to whoever is watching (a customer waiting for a delivery, a dispatcher with a map of a city), and raises an event when a device crosses into or out of a zone, such as an airport pickup area or a warehouse yard.

The design is shaped by three features. First, the writes are many, small and short-lived: a new position makes the previous one useless for the live view, so the hot data is one row per device that is overwritten all day. Second, every write has readers waiting for it, so the system is really a fan-out system. Third, GPS is noisy and networks reorder packets, so a naive design moves cars backwards and fires false zone events.

This topic focuses on ingest, fan-out and geofencing. Finding the drivers nearest a point is covered in the Uber topic, and indexing fixed places in the Proximity Service topic.

Questions to ask first

How many devices report at once? — 1 million at peak
How often do they report? — Every 4 seconds while moving, every 30 seconds when parked
Who watches? — Customers watch one device; dispatchers watch an area of a map
How fresh must the watcher's view be? — Under 1 second from arrival to screen (a target we chose)
What are zones? — Circles and polygons, up to about 100,000 of them
How long is history kept? — 90 days, for route replay and disputes

What you will be able to do

Size the write and fan-out load from the device count and report interval.
Keep only the newest position per device, even when packets arrive late or twice.
Fan positions out to per-device and per-area watchers without queues that grow.
Fire each geofence enter and exit once, despite GPS jitter.
Store months of tracks cheaply and replay them.

Key concepts

Latest position only
Per-device ordering
Sequence numbers
Geospatial index
Pub/sub fan-out
Conflation
Point in polygon
Geofence hysteresis
Time-series history
Adaptive reporting

Functional requirements

Accept position updates (latitude, longitude, accuracy, speed, heading, device time) from devices
Return the latest position of one device, or of many devices in one call
Push live positions to watchers of one device, or of an area of the map
Create circle and polygon zones, and emit an event when a device enters or leaves one
Store every device's track for 90 days and replay it for a time range
Tell each device how often to report, based on whether it is moving

Non-functional requirements

A position reaches its watchers within 1 second of arriving, at p99 (a target we chose)
Zone events fire within 2 seconds of the position that caused them
A late or repeated position never replaces a newer one
Each zone crossing produces one event, not a burst of enter and exit events
Only watchers allowed to see a device receive its position
Ingest keeps working when history storage or geofencing is slow

Interview questions

Why not write every position to a relational database?
How do you push positions to watchers?
How do you handle out-of-order and duplicate updates?
How does geofencing scale to 100,000 zones?
How do you stop a geofence from flapping?
What happens when a watcher reconnects?
How do you reduce battery and server cost?
Who may see a device's location?