# Location Tracking System Low-Level Design

Source: https://www.techinterview.org/post/3233467307/lld-location-tracker/
Updated: 2026-04-17 · techinterview.org

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

  - Store geofence definitions: Geofence(geofence_id, name, type ENUM(CIRCLE,POLYGON), center_lat, center_lng, radius_m, polygon_coords JSON)

  - For each location update: determine which geofences the device is currently inside (point-in-polygon test)

  - Compare to the device's previous geofence set: if newly inside → ENTRY event; if no longer inside → EXIT event

  - 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](https://www.techinterview.org/post/3233460273/uber-interview-guide-2026-dispatch-systems-geospatial-algorithms-and-marketplace-engineering/).

Lyft system design covers real-time location tracking for drivers. Review patterns for [Lyft interview: driver location tracking system design](https://www.techinterview.org/post/3233460306/lyft-interview-guide-2026-rideshare-engineering-real-time-dispatch-and-safety-systems/).

Airbnb system design covers geolocation and proximity queries. See design patterns for [Airbnb interview: geolocation and proximity search design](https://www.techinterview.org/post/3233460279/airbnb-interview-guide-2026-search-systems-trust-and-safety-and-full-stack-engineering/).