Design a Geofencing Service

Two-Phase Spatial Evaluation Flow

GPS updates flow from ingestion through spatial candidate queries, state transition evaluations (inside vs outside), and downstream event delivery. Hysteresis buffers prevent boundary flutter caused by noisy GPS readings.

The expensive part is not the polygon geometry math, because ray casting across 6 vertices completes in microseconds. The primary scalability challenge is narrowing 100M global geofences down to a handful of local candidates per location update, followed by tracking per-device state so enter and exit events fire exactly once. For the underlying stream processing architecture, see Stream Processing Basics.

Spatial Index: Two-Phase Filtering

Phase 1: Coarse filtering with spatial index (R-tree or Geohash)
  Each geofence has a bounding box → R-tree indexes these
  Query: "Which bounding boxes contain (lat, lng)?"
  Result: ~10-50 candidate geofences (from 100M → 50)
  Time: O(log N)

Phase 2: Precise point-in-polygon test (ray casting)
  For each candidate, ray from point to infinity
  Count intersections with polygon edges
  Odd → inside; Even → outside
  Time: O(V) per polygon (~300 operations → microseconds)

Total: < 1 ms per location update

Geofence Evaluation Engine: Processing 5M Updates/Sec

Architecture: Flink streaming application

Kafka Topic: location-updates (256 partitions by device_id)

Flink Job:
  1. Consume location updates
  2. Query spatial index (R-tree via sidecar)
  3. Get candidate geofences (10-50)
  4. Point-in-polygon check for each
  5. Compare with previous state (Redis lookup)
  6. If state changed → emit trigger event to Kafka

Scaling: Partition by geohash region, each worker loads only its region's fences

Dwell Detection: Preventing False Triggers

On ENTER: Start a dwell timer (e.g., 60 seconds)
  SET dwell_timer:{device}:{fence} 1 EX 60

On each update inside: check if timer expired → trigger DWELL event
On EXIT before expiry: delete timer → pass-through ignored

GPS Jitter handling: Hysteresis buffer
  Enter threshold: > 10m inside boundary
  Exit threshold: > 10m outside boundary
  Dead zone: within 10m → maintain current state

Event Bus Design (Kafka)

Topics:
  location-updates: partition key: device_id (high-volume GPS stream)
  geofence-triggers: partition key: geofence_id (exit and enter events)
  Partitions: 256 / 32; Retention: 48h / 7 days; RF=3

Producer events:
  location-updates: { device_id, lat, lng, accuracy_m, speed, timestamp }
  geofence-triggers: { device_id, geofence_id, event: enter|exit, timestamp }

Consumer groups:
  1. geofence-evaluator: Flink spatial join against R-tree index to emit triggers
  2. trigger-delivery: webhooks, push notifications, and SMS via Trigger Delivery Service
  3. event-store: append to ClickHouse for audit and analytics

Sync path: POST /location → Kafka location-updates → 202 (never block on evaluation)
Point-in-polygon query path: Geofence Query Service uses in-memory spatial index
DLQ: location-updates-dlq; alert when evaluator lag > 30s