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
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How does PostGIS handle geofencing queries efficiently?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”PostGIS uses an R-tree spatial index (GIST index) that stores bounding boxes of geometric objects in a hierarchical tree. For ST_DWithin (is point within radius), the R-tree prunes the search space from 100K geofences to ~10 candidates in O(log n), then does exact distance calculation on those candidates. Without the index, every query would be O(n) — scanning all 100K fences. Always create a GIST index on geometry columns used in spatial queries.”}},{“@type”:”Question”,”name”:”What is a geohash and how does it help with geofencing?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A geohash encodes a (lat, lng) coordinate as a string where longer strings represent smaller areas. The hierarchical property: all points in an area share the same prefix. For geofencing: encode each geofence’s center as geohash prefixes at multiple precision levels. For a device at a location, compute its geohash prefix and find all geofences whose cells overlap. This reduces candidates from all 100K fences to only those geographically nearby. Redis GEOSEARCH implements this using geohash internally.”}},{“@type”:”Question”,”name”:”How do you detect enter vs exit events for a moving device?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Maintain per-device state: a set of fence_ids the device is currently inside (stored in Redis as a set per device_id). On each location update: compute the set of fences containing the new position. Compare with the stored previous set. Fences in new but not old = ENTER events. Fences in old but not new = EXIT events. Update the stored set. Set TTL on the Redis key (e.g., 24h) to clean up state for inactive devices automatically.”}},{“@type”:”Question”,”name”:”How do you scale to 1 million location updates per 30 seconds?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”That is ~33K updates/second. Ingest via Kafka — devices publish location events to a topic partitioned by device_id (so the same device’s updates are ordered). Consumer workers pull from Kafka partitions, each handling a geographic shard of devices. Each worker maintains a local cache of geofences for its region. Geofence data is loaded into memory at startup (~100K fences × ~200 bytes = ~20MB) — easily fits in RAM for in-memory lookup without DB queries on the hot path.”}},{“@type”:”Question”,”name”:”How do you handle GPS inaccuracy in geofencing?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”GPS accuracy on mobile devices ranges from 3m (clear sky) to 50m (urban canyon). Two strategies: (1) Add a buffer to geofence boundaries — instead of triggering at the exact boundary, trigger when confidence is high (device is clearly inside or clearly outside). (2) Use accuracy_m from the location update: if the device is within accuracy_m of the fence boundary, defer the enter/exit event until the next update provides a clearer signal. This prevents false triggers from GPS noise near fence edges.”}}]}
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.