Geofencing System Low-Level Design

By /
⏱ 5 min read

What is Geofencing?

Geofencing defines virtual geographic boundaries (circles or polygons) and triggers actions when a tracked entity (user, vehicle, asset) enters or exits the boundary. Use cases: surge pricing when a driver enters a high-demand zone (Uber), store promotions when a customer walks near a retail location (Shopify), delivery zone validation, workplace attendance tracking. The core challenge: efficiently determining whether a moving point is inside any of potentially millions of geofences in real time.

Requirements

  • Create and manage geofences (circle or polygon) with metadata and associated actions
  • Process location updates from 1M active devices every 30 seconds
  • Detect enter/exit events with <5 second latency from when the device sends location
  • Query: which geofences contain point (lat, lng)?
  • Trigger webhooks/events when enter/exit is detected
  • Support up to 100K geofences globally

Data Model

Geofence(
    fence_id    UUID PRIMARY KEY,
    name        VARCHAR,
    type        ENUM(CIRCLE, POLYGON),
    center_lat  FLOAT,          -- for CIRCLE
    center_lng  FLOAT,
    radius_m    INT,            -- radius in meters for CIRCLE
    polygon     GEOMETRY,       -- PostGIS POLYGON for POLYGON type
    metadata    JSONB,          -- {'zone_type': 'surge', 'multiplier': 1.5}
    tenant_id   UUID,
    active      BOOL DEFAULT true
)

DeviceLocation(
    device_id   UUID NOT NULL,
    lat         FLOAT,
    lng         FLOAT,
    accuracy_m  INT,
    recorded_at TIMESTAMPTZ,
    -- only latest location stored per device (upsert by device_id)
    PRIMARY KEY (device_id)
)

FenceEvent(
    event_id    UUID PRIMARY KEY,
    device_id   UUID,
    fence_id    UUID,
    event_type  ENUM(ENTER, EXIT),
    lat         FLOAT,
    lng         FLOAT,
    created_at  TIMESTAMPTZ
)

Spatial Indexing with PostGIS and Geohash

Checking 100K geofences for every location update is O(100K) per update — too slow for 1M devices. Use spatial indexing:

-- PostGIS R-tree index for spatial queries
CREATE INDEX idx_geofence_geom ON Geofence USING GIST(
    ST_Buffer(ST_Point(center_lng, center_lat)::geography, radius_m)
);

-- Query: all geofences containing a point
SELECT fence_id FROM Geofence
WHERE ST_DWithin(
    ST_Point(:lng, :lat)::geography,
    ST_Point(center_lng, center_lat)::geography,
    radius_m
)
AND active = true;

Alternative: Geohash-based pre-filtering. Geohash divides the Earth into a hierarchical grid of cells. Encode each device’s location as a geohash prefix; find all geofences whose cells overlap. Redis supports geospatial commands:

# Index geofences in Redis
redis.geoadd('fences', lng, lat, fence_id)

# Find fences within 5km of device location
nearby_fences = redis.georadius('fences', device_lng, device_lat, 5, 'km')
# Then check exact containment against this small candidate set

Enter/Exit Event Detection

Enter/exit events require tracking previous state per device per fence:

DeviceFenceState(device_id, fence_id, inside BOOL, last_updated TIMESTAMPTZ)
-- Redis hash: HSET device_fence_state:{device_id} {fence_id} 1/0

def process_location(device_id, lat, lng):
    # 1. Find candidate fences near the location (spatial index)
    candidate_fences = get_nearby_fences(lat, lng, radius_km=50)

    # 2. For each candidate, check exact containment
    currently_inside = set()
    for fence in candidate_fences:
        if is_inside(lat, lng, fence):
            currently_inside.add(fence.fence_id)

    # 3. Compare with previous state
    previously_inside = redis.smembers(f'device_inside:{device_id}')

    entered = currently_inside - previously_inside
    exited  = previously_inside - currently_inside

    # 4. Emit events
    for fence_id in entered:
        emit_event('ENTER', device_id, fence_id, lat, lng)
    for fence_id in exited:
        emit_event('EXIT', device_id, fence_id, lat, lng)

    # 5. Update state
    redis.delete(f'device_inside:{device_id}')
    if currently_inside:
        redis.sadd(f'device_inside:{device_id}', *currently_inside)
        redis.expire(f'device_inside:{device_id}', 86400)

Key Design Decisions

  • PostGIS/R-tree for spatial queries — handles arbitrary polygons with O(log n) query performance
  • Two-step: spatial pre-filter + exact containment — reduces candidates from 100K to ~10 before exact check
  • Redis for device fence state — O(1) set operations for enter/exit detection; avoids DB reads on hot path
  • Process location updates via Kafka — decouples device ingestion from geofence evaluation; handles 1M/30s = 33K/s
  • Geohash prefix matching for sharding — route device updates to workers responsible for geographic regions

Geofencing and location-based service design is discussed in Uber system design interview questions.

Geofencing, surge zones, and location tracking design is in Lyft system design interview preparation.

Geographic search and geofencing system design is covered in Airbnb system design interview guide.

Scroll to Top