Geofencing Service#

Q: How does a geofencing service detect entry and exit events?

Each location update runs a point in polygon test against fences the user is subscribed to. State per fence is tracked as inside or outside, and an event fires only when the boolean flips.

Q: What spatial index is best for geofencing?

R-trees handle arbitrary polygons well, while S2 or H3 cell coverings let you prune candidates fast by intersecting the user's cell with cells touching each fence. Most production systems combine both.

Q: How do you avoid spam events at fence boundaries?

Apply hysteresis with two boundaries: a tighter enter polygon and a looser exit polygon. Combine with a dwell timer so brief crossings caused by GPS noise do not fire alerts.

Q: How does a geofencing service scale to millions of fences?

Shard fences by region or by H3 cell. Each shard owns a subset of fences and processes updates whose location falls inside the shard's bounding cells, keeping per-update fanout small.

Q: How are geofence events delivered to consumers?

Events publish to a queue then fan out to webhooks and push notifications with at least once delivery. Idempotency keys on the consumer prevent duplicate side effects on retry.

Problem statement (interviewer prompt)

Design a geofencing service: register polygonal fences for millions of users / vehicles. Stream location updates and emit ENTER / EXIT / DWELL events to webhook + push consumers. Avoid event spam at fence boundaries (hysteresis) and tolerate noisy GPS.

flowchart LR
  D([Device])
  LOC[Location Update]
  GIDX[(Geofence Index<br/>R-tree / S2)]
  EVT([Event Generator])
  HOOK[Webhooks / Push]
  D --> LOC --> GIDX --> EVT --> HOOK

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class D client;
    class LOC,HOOK service;
    class GIDX datastore;
    class EVT compute;

flowchart TB
  subgraph Sources
    DEV([Devices / phones])
    VEH[Vehicles]
    DRONE[Drones / IoT]
  end

  subgraph Ingest
    LB
    ING([Location ingest])
    BATCH[Batch + dedup]
  end

  subgraph Geofences[Fence registry]
    REG[Fence Registry]
    REGDB[(Fences DB<br/>polygon / circle / multipoly)]
    IDX[(Spatial index<br/>R-tree / S2 / H3)]
    SUB[Subscriptions per fence]
  end

  subgraph Eval[Evaluation Engine]
    MATCH[Point-in-polygon test]
    HYS[Hysteresis<br/>avoid bounce]
    STATE[(Per-device per-fence state)]
    DEBOUNCE[Debounce / dwell]
    EVTGEN[Enter / Exit / Dwell event]
  end

  subgraph Delivery
    BUS[[Kafka events]]
    WH[Webhook delivery]
    PUSH((APNS / FCM))
    INAPP[In-app realtime]
    DLQ[(DLQ)]
  end

  subgraph Ops
    METR[Metrics]
    AUDIT[Audit]
    ML[Pattern detection]
  end

  Sources --> LB --> ING --> BATCH
  BATCH --> MATCH --> Eval
  Eval --> STATE
  Eval --> EVTGEN --> BUS
  Geofences --> MATCH
  IDX --- MATCH
  BUS --> WH
  BUS --> PUSH
  BUS --> INAPP
  WH --> DLQ

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class DEV client;
    class VEH,DRONE,BATCH,REG,SUB,MATCH,HYS,DEBOUNCE,EVTGEN,WH,INAPP,AUDIT,ML service;
    class REGDB,IDX,STATE,DLQ datastore;
    class BUS queue;
    class ING compute;
    class PUSH external;
    class METR obs;

Index for point-in-polygon#

R-tree on bounding boxes is the classic.
Modern: S2 / H3 cell coverings; a fence covers a set of cells.
Lookup: cell of the device → fences whose covering contains it → exact PIP test.

Hysteresis#

Avoid event spam when device sits on the border.
Require N consecutive INSIDE updates to fire ENTER; same for EXIT.
Dwell event after T minutes inside.

Delivery#

At-least-once webhooks with retry + DLQ.
Idempotency by (device, fence, event_id).

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Pub/Sub & message brokers	topics, consumer groups, delivery semantics	pub-sub-pattern
`HLD`	Idempotency & retries	safe re-execution, backoff + jitter	idempotency-retries
`HLD`	Observability	metrics, logs, traces, SLOs	observability
`HLD`	Geo indexing	Geohash, Quadtree, S2, H3, R-tree	geo-indexing

Quick reference#

Functional#

Register polygonal / circular fences.
Watch devices; emit ENTER / EXIT / DWELL events.
Deliver via webhook / push / in-app.
Per-device per-fence state.

Non-functional#

p99 event latency < 5 s.
Tens of millions of fences; 100M+ devices.
99.9% delivery for webhooks.

Capacity#

Location updates: millions/s.
Per update: index lookup + state update + maybe event emit.

Schema#

fences(id, owner, geometry, type, attrs)
subscriptions(fence_id, target, type)
device_state(device_id, fence_id, in_or_out, last_changed)

Trade-offs#

Server-side vs client-side geofencing: client saves bandwidth and battery (OS APIs); server centralizes business logic. Hybrid common.
R-tree vs S2/H3 cells: cells parallelize beautifully across shards; R-tree better for small fence counts.
At-most-once vs at-least-once with idempotency: usually at-least-once.

Refs#

Esri / PostGIS spatial indexing; Uber H3 docs; Mapbox / Radar geofencing platform docs; ByteByteGo "Design geofencing".

FAQ#

How does a geofencing service detect entry and exit events?#

Each location update runs a point in polygon test against fences the user is subscribed to. State per fence is tracked as inside or outside, and an event fires only when the boolean flips.

What spatial index is best for geofencing?#

R-trees handle arbitrary polygons well, while S2 or H3 cell coverings let you prune candidates fast by intersecting the user's cell with cells touching each fence. Most production systems combine both.

How do you avoid spam events at fence boundaries?#

Apply hysteresis with two boundaries: a tighter enter polygon and a looser exit polygon. Combine with a dwell timer so brief crossings caused by GPS noise do not fire alerts.

How does a geofencing service scale to millions of fences?#

Shard fences by region or by H3 cell. Each shard owns a subset of fences and processes updates whose location falls inside the shard's bounding cells, keeping per-update fanout small.

How are geofence events delivered to consumers?#

Events publish to a queue then fan out to webhooks and push notifications with at least once delivery. Idempotency keys on the consumer prevent duplicate side effects on retry.