Location Tracking System Low-Level Design

Requirements

• Track real-time location of mobile assets (drivers, delivery couriers, field workers)
• 1M active devices sending location updates every 4 seconds
• Query nearby assets within a radius in <100ms
• Store location history for trip replay and analytics
• Detect geofence entry/exit events

Data Flow

Device (GPS ping every 4s) → Location API → Redis Geo (live location)
                           → Kafka        → Cassandra (location history)
                                          → Geofence Service (zone events)
                                          → Analytics Pipeline

Live Location Storage: Redis Geospatial

Redis stores live locations using the Geo API (internally a sorted set with geohash scores):

# Update device location
GEOADD locations {lng} {lat} {device_id}

# Find all devices within 5km of a point
GEORADIUS locations {lng} {lat} 5 km ASC COUNT 20

# Get location of specific device
GEOPOS locations {device_id}

# Distance between two devices
GEODIST locations {device_id_1} {device_id_2} km

At 1M active devices: GEOADD throughput = 250K writes/second. Redis handles this easily (single-threaded, ~1M ops/second). Memory: ~100 bytes per member → 100MB for 1M devices. GEORADIUS runs in O(N+log(M)) where N is results and M is total members.

Stale Location Filtering

Devices go offline without explicit deregistration. Maintain a Redis hash alongside: HSET device_meta {device_id} last_update {epoch_ms}. When querying nearby devices: filter out devices with last_update > 30 seconds ago (they are offline). Alternatively, use Redis EXPIREAT on each device’s geo entry — but GEOADD doesn’t support TTL on individual members. The metadata hash approach is cleaner.

Location History: Cassandra

CREATE TABLE location_history (
    device_id  UUID,
    trip_id    UUID,
    recorded_at TIMESTAMP,
    lat        DOUBLE,
    lng        DOUBLE,
    speed_kmh  FLOAT,
    heading    SMALLINT,
    PRIMARY KEY (device_id, recorded_at)
) WITH CLUSTERING ORDER BY (recorded_at DESC);

Partition by device_id — all locations for a device on the same node. Clustering by recorded_at DESC for efficient “latest N locations” queries. Write throughput: Cassandra handles 250K writes/second with proper replication (RF=3). Retention policy: keep 90 days in Cassandra (hot), archive to S3/Parquet after 90 days (cold).

Geofencing

A geofence is a geographic boundary (polygon or circle) that triggers an event on entry or exit. Implementation:

1. Store geofence definitions: Geofence(geofence_id, name, type ENUM(CIRCLE,POLYGON), center_lat, center_lng, radius_m, polygon_coords JSON)
2. For each location update: determine which geofences the device is currently inside (point-in-polygon test)
3. Compare to the device’s previous geofence set: if newly inside → ENTRY event; if no longer inside → EXIT event
4. Publish ENTRY/EXIT events to Kafka for downstream processing

Point-in-polygon test (ray casting algorithm): O(n) where n is polygon vertices. For circles: distance to center <= radius. Store device’s current geofences in Redis hash: HSET device_geofences {device_id} {json_set_of_geofence_ids}.

Spatial Indexing for Geofence Lookup

For each location update, finding which geofences contain the point: checking all geofences O(G) is too slow for large G. Spatial index: R-tree (spatial index for rectangles/polygons) or H3 hexagonal grid. H3 approach: convert each geofence to a set of H3 cells at resolution 9 (~0.1km²). Build an inverted index: H3_cell → [geofence_ids]. For each location update: convert device location to H3 cell, look up geofence_ids, verify each with exact point-in-polygon test. Reduces candidates from all geofences to those overlapping the device’s H3 cell.

Key Design Decisions

• Redis Geo for live spatial queries — purpose-built for radius queries, O(log n) per query
• Cassandra for location history — high write throughput, time-series partitioning by device_id
• Kafka as the async path — Cassandra writes and geofence checks never block the location API
• H3 spatial index for geofencing — reduces candidate geofences from O(G) to O(1) expected

Uber system design is the canonical location tracking interview topic. See common questions for Uber interview: real-time location tracking system design.

Lyft system design covers real-time location tracking for drivers. Review patterns for Lyft interview: driver location tracking system design.

Airbnb system design covers geolocation and proximity queries. See design patterns for Airbnb interview: geolocation and proximity search design.