Design a Geofencing Alert Service

Design a service that watches a large fleet of moving devices against a large set of registered geofences (circles and polygons) and fires enter/exit alerts in near real time. A tenant defines geofences; when one of their devices crosses a boundary, the tenant's webhook is called once.

Operating context. Devices post location pings through a mobile SDK. You are sizing for tens of millions of devices reporting roughly every 30 to 60 seconds and millions of active geofences, some densely clustered (an airport, a stadium) and some vast (a whole city). An alert should fire within a couple of seconds of the ping that crossed the boundary. The system is multi-tenant and each tenant sees only their own geofences and devices.

Out of scope. The mobile SDK's battery/sampling behavior, the downstream notification channels (push/email/SMS delivery), the geofence-authoring UI, and per-tenant billing. Assume those are owned by other teams.

What to produce. A high-level architecture covering: the location-ping ingest path, how geofences are spatially indexed so each ping is matched against only nearby candidates, the point-in-geofence test for circles vs polygons, how per-device inside/outside state is tracked to detect a genuine transition, exactly-once alert emission and webhook fan-out, how you partition work (by device vs by geo cell) and handle dense hot cells, and the failure modes. Sketch the components and the flow of a single ping to an alert; we will probe specifics in checkpoints.