Low Level Design: Geo-Fencing Service – Tech Interview Dot Org

Geo-Fencing Service: Low Level Design

Data Model

GeoFence Table

GeoFence
--------
id              BIGINT PK
name            VARCHAR(255)
type            ENUM('circle','polygon')
center_lat      DOUBLE          -- circles only
center_lng      DOUBLE          -- circles only
radius_meters   INT             -- circles only
geom            GEOGRAPHY(POLYGON)  -- PostGIS, used for all shapes
owner_id        BIGINT
trigger_on      ENUM('enter','exit','both')
active          BOOLEAN
created_at      TIMESTAMPTZ

Circles are also stored as polygon geometries (approximated as a 64-point polygon) to unify spatial queries, but center_lat, center_lng, and radius_meters are retained for a fast Haversine pre-filter before invoking PostGIS.

Event Table

FenceEvent
----------
id              BIGINT PK
fence_id        BIGINT FK
device_id       BIGINT
event_type      ENUM('enter','exit')
occurred_at     TIMESTAMPTZ

GeoFenceSubscription Table

GeoFenceSubscription
--------------------
id              BIGINT PK
fence_id        BIGINT FK
callback_url    TEXT
secret          VARCHAR(64)     -- HMAC signing key for webhook payloads
created_at      TIMESTAMPTZ

Location Update Ingestion

API Endpoint

POST /locations
Content-Type: application/json

{
  "updates": [
    { "device_id": 42, "lat": 37.7749, "lng": -122.4194, "ts": 1700000000 },
    ...
  ]
}

Accepts 1–10 location updates per device per second. Updates are written to a Kafka topic location-updates for async fence evaluation, keeping the HTTP response fast. The ingestion service validates coordinate ranges and rate-limits per device.

Fence Evaluation Pipeline

Spatial Query

-- Find all active fences containing the new device location
SELECT gf.id, gf.trigger_on
FROM geofence gf
WHERE gf.active = TRUE
  AND gf.owner_id IN (/* fences relevant to this device */)
  AND ST_Within(
        ST_SetSRID(ST_MakePoint(:lng, :lat), 4326)::geography,
        gf.geom
      );

Spatial Index

CREATE INDEX idx_geofence_geom ON geofence USING GIST (geom);

The GiST index enables a bounding-box pre-filter so PostGIS only runs the precise ST_Within check against a small candidate set. For circle fences, a Haversine distance check runs first as an additional pre-filter before the PostGIS call.

State Tracking and Debounce

To prevent false events from GPS jitter, a device's inside/outside state per fence is tracked in Redis:

Key:   fence_state:{fence_id}:{device_id}
Value: { "state": "inside", "since": 1700000000 }
TTL:   300s

An enter event is only fired when the device has been continuously inside the fence for >30 seconds. An exit event is only fired when the device has been continuously outside for >30 seconds. This debounce window is configurable per fence.

Webhook Delivery

When a confirmed enter/exit event is written to FenceEvent, the system looks up all GeoFenceSubscription rows for that fence and enqueues a webhook delivery task:

POST {callback_url}
X-Signature: HMAC-SHA256(secret, payload)
Content-Type: application/json

{
  "fence_id": 101,
  "device_id": 42,
  "event_type": "enter",
  "occurred_at": "2024-01-01T12:00:00Z"
}

Delivery uses exponential backoff with up to 5 retries. Failed deliveries are logged for manual inspection.

Scalability Notes

Fence evaluation workers consume from the Kafka location-updates topic and scale horizontally.
Active fence sets per device are cached in Redis to avoid per-update DB lookups.
PostGIS runs on a read replica; writes go to primary.
Very high-volume deployments can shard by geographic region using a geohash prefix.

{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What database is best for storing geo-fence geometries?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “PostgreSQL with the PostGIS extension is the standard choice. PostGIS adds the GEOGRAPHY type and spatial functions like ST_Within, plus GiST indexes that enable fast bounding-box pre-filtering before precise polygon checks.”
}
},
{
“@type”: “Question”,
“name”: “How do you prevent false enter/exit events from GPS jitter in a geo-fencing system?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Use a debounce window: only fire an enter event if the device has been continuously inside the fence for more than 30 seconds, and only fire an exit event if it has been continuously outside for more than 30 seconds. Track the device's state and the timestamp it last changed in Redis.”
}
},
{
“@type”: “Question”,
“name”: “How do you scale a geo-fencing service to millions of devices?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Write location updates to a Kafka topic and process them with horizontally scaled fence evaluation workers. Cache active fence sets per device in Redis to avoid per-update database queries. Use a read replica for PostGIS spatial queries and shard by geographic region (geohash prefix) for very high volumes.”
}
},
{
“@type”: “Question”,
“name”: “How are circle geo-fences handled differently from polygon geo-fences?”,
“acceptedAnswer”: {
“@type”: “Answer”,
“text”: “Circles are stored as approximated polygon geometries (e.g., 64-point polygon) in the GEOGRAPHY column so that all fences use the same ST_Within query path. Additionally, the circle's center coordinates and radius are stored separately to enable a fast Haversine pre-filter that eliminates obviously distant points before the PostGIS call.”
}
}
]
}