Imagine a post office sorting room the size of a continent. Five hundred million letters arrive at different addresses and they keep moving - a letter picked up, rerouted, dropped off, moved again - every few seconds. A customer walks up and asks: “Give me every letter that’s within two kilometers of this spot, right now.” And you have to answer in ten milliseconds.

That is the geospatial proximity problem. It sits at the core of Uber driver search, Yelp restaurant discovery, Doordash courier dispatch, Airbnb map views, and fleet management systems worldwide. The naive approach - store latitude and longitude in a relational database and run a distance formula against every row - collapses immediately. A full table scan over 500 million rows takes seconds even with a B-tree index, because distance is a two-dimensional relationship and B-trees are one-dimensional structures. They can answer “latitude between 37.5 and 38.0” efficiently, but they cannot answer “distance from point within radius” without fusing two orthogonal range scans and post-filtering millions of candidates.

The second naive approach - a standard 2D spatial index like PostGIS with an R-tree - works well up to tens of millions of static entities. The problem here is not query latency on the read side; R-trees are excellent at range queries. The problem is the write side. When 500 million entities are moving and each one sends a GPS update every 3 to 5 seconds, you’re absorbing roughly 100 to 160 million location writes per second at peak. Every write invalidates an entry in the spatial index. R-trees are not designed for that mutation rate. The index becomes a bottleneck and its benefit on the read side evaporates.

The fundamental tension is: write velocity versus query freshness versus read latency. We want to absorb tens of millions of location updates per second, keep the proximity index fresh enough that a query returns entities that are actually still nearby, and answer any given query in under 10ms. We need to solve for index write throughput, index read performance, and query precision vs recall simultaneously - accepting some approximation on the write side to stay within latency budgets on the read side.

Requirements and Constraints

Functional Requirements

• Answer “find all entities within Y km of (lat, lon)” for configurable Y (0.5 km to 50 km)
• Support entity types: drivers, couriers, restaurants, POIs, users
• Accept location updates from moving entities (drivers, couriers) every 3 to 10 seconds
• Return results sorted by ascending distance from the query point
• Support entity metadata retrieval (name, type, status) in the same response

Non-Functional Requirements

• Query latency: p99 under 10ms, p50 under 3ms
• Write throughput: sustain 100 million location updates per second at peak (500M entities x 1 update per 5 seconds)
• Entity count: 500 million active entities globally
• Availability: 99.99% uptime (less than 53 minutes downtime per year)
• Location freshness: query results must reflect entity positions within the last 5 seconds
• Result accuracy: return all entities within the radius (recall 100%) with acceptable false positive rate under 5% (pruned in post-filter)

Constraints and Assumptions

• Entities are distributed globally but density is concentrated in urban areas (power law distribution)
• Static POIs (restaurants, stores) vastly outnumber moving entities - different update cadence
• We do not need to store historical location trails (that is a separate analytics system)
• Cross-entity-type queries are out of scope - each entity type has its own index namespace
• The system is eventually consistent on writes: a newly moved entity may briefly appear in its old cell for up to one index update cycle (100 to 200ms)

High-Level Architecture

The architecture separates the read path (proximity queries) from the write path (location updates) with different latency and throughput profiles. Think of it as two independent conveyor belts running at different speeds that share the same warehouse floor - the fast read belt and the high-volume write belt never block each other.

The API Gateway handles authentication, rate limiting, and routes queries to the Query Service and updates to the Location Ingestion Service. The Query Service receives a (lat, lon, radius) triple, encodes the query point into a Geohash cell, expands to neighboring cells, fetches candidate entity IDs from the Geohash Index in Redis, runs a Haversine distance filter to prune false positives, then hydrates entity metadata from Cassandra. The entire read path touches only in-memory Redis and a Cassandra multi-get - no disk seeks in steady state.

The Location Ingestion Service receives GPS pings, writes them to a Kafka topic partitioned by geohash prefix, and returns immediately. A Flink stream processor consumes from Kafka, applies last-write-wins coalescing within 100ms windows per entity, and produces a deduplicated batch to the Index Updater. The Index Updater applies atomic SREM old_cell / SADD new_cell operations in Redis, updating the spatial index without a full rewrite of the entity’s record.

The Entity Store (Cassandra) holds full entity metadata and the precise lat/lon for Haversine post-filtering. It is written by the Index Updater alongside the Redis cell membership change. The Result Cache (Redis with 500ms TTL) sits in front of the Query Service for repeated identical queries - common in dense areas where many users query the same cell simultaneously.

Component Deep Dives

The Geohash Index

The Geohash index does one job: given a geohash cell string, return the set of entity IDs currently inside that cell.