Design a Proximity Service

Given a user's latitude, longitude and an optional radius, return businesses within that distance. Business owners can add, update or delete their listings, but those changes do not need to appear in search results instantly; it is acceptable for them to show up the next day. Customers can also open a business's detail page.

Non-functionally, search should be fast, the service must be highly available during traffic spikes in dense areas at peak hours, and user location must be handled with privacy laws like GDPR and CCPA in mind. The defining characteristic is the read/write ratio: searches vastly outnumber edits, which shapes every storage decision that follows.

Assume 100 million daily active users who each run about 5 searches a day, and 200 million businesses. Search QPS is 100M x 5 / 86,400. Rounding a day to 100,000 seconds for easy maths gives 500M / 100,000 = 5,000 QPS; the exact figure is about 5,800, so plan for roughly 5k average with headroom for several times that at peak.

Storage for business records is small: even at 1 KB each, 200M businesses is 200 GB, which fits on one well-provisioned database with read replicas. The geospatial index is smaller still, since it only needs an ID and coordinates per business. So the design challenge is query efficiency over 2D data, not capacity.

Split the system into two services with very different profiles. The location-based service is read-only, stateless and handles the hot path: given a location and radius, find business IDs. It scales horizontally and benefits greatly from caching. The business service handles owner writes and customer detail-page reads; writes are low volume and can go to a primary database while reads hit replicas.

The API is small: GET /v1/search/nearby?latitude=&longitude=&radius= returns a paged list of businesses, and GET/POST/PUT/DELETE /v1/businesses/{id} manages listings. Because the data model is read-heavy, a primary-plus-read-replicas relational setup is a sensible default; replication lag of a few seconds is irrelevant given the next-day freshness requirement. The interesting part is how the location service finds candidate IDs quickly.

The obvious query is WHERE lat BETWEEN a AND b AND lng BETWEEN c AND d. Even with an index on each column, the database must take the set of rows within the latitude band and the set within the longitude band and intersect them. Each band is a strip spanning the entire planet, containing far more rows than the small square we want, so the intersection is expensive. A B-tree index orders data in one dimension; it cannot directly answer a two-dimensional range.

Every serious geospatial index therefore maps 2D space into one dimension or into a tree. The simplest idea is an evenly divided grid: chop the world into equal squares and index businesses by square. It fails because business density is wildly uneven: a square in midtown Manhattan holds thousands of entries while one in the Pacific holds none. We want small cells where data is dense and big cells where it is sparse.

Geohash recursively halves longitude and latitude, interleaving one bit from each, and encodes the resulting bit string in base32. Each extra character subdivides the cell, so a longer geohash means a smaller area and two points sharing a long prefix are usually close. That turns a 2D lookup into a string-prefix lookup, which ordinary indexes and key-value stores handle well. Precision is chosen from the radius: a 6-character hash is about 1.2 km by 0.6 km, length 5 is roughly 4.9 km square, and length 4 is about 39 km by 19.5 km.

Geohash has two boundary problems. Two points can be metres apart yet share no prefix if they straddle a cell edge, such as the equator or prime meridian; and points with a long shared prefix can still lie in different cells. The standard fix is to query the user's cell plus its eight neighbours, then filter by exact distance. If too few results come back, drop a character to widen the area and repeat.

A quadtree recursively splits a square into four children until each leaf holds at most some threshold, say 100 businesses. Dense cities get deep, small leaves and empty oceans stay as big leaves, exactly the adaptivity grids lacked. It is an in-memory structure built when a server starts. With 200M businesses and 100 per leaf there are about 2M leaves and roughly 0.67M internal nodes; at about 832 bytes per leaf (100 IDs of 8 bytes plus bounds) and 64 bytes per internal node, the tree is around 1.7 GB, which fits comfortably in RAM. Building it is O(n log n) and takes minutes, so servers must be rolled out gradually and updates are typically applied by nightly rebuilds.

Google S2 projects the sphere onto a cube and maps each face to a one-dimensional Hilbert curve, which preserves locality well: points close on the curve are close in space. It supports arbitrary regions (geofences) and a region coverer that approximates a circle with cells of mixed sizes. It is powerful but harder to explain in an interview than geohash or a quadtree.

Geohash is easy to implement, works on any database and updates are trivial (delete and insert one row), but it cannot adapt cell size to density. Quadtrees adapt naturally and support 'return the k nearest' queries well, but they are in-memory, slow to rebuild and awkward to update in place. S2 is the most precise and flexible but the most complex. For an interview, geohash with Redis or a quadtree in each LBS instance are both defensible.

Caching fits well because the data changes slowly. Cache geohash -> list of business IDs at each supported precision, and cache business_id -> business object separately so detail pages and search results share it. Caching on raw coordinates is useless because users' coordinates almost never repeat exactly. Deploy LBS and caches in multiple regions near users for latency and to keep location data within legal jurisdictions. Filters such as 'open now' or 'restaurants only' are applied after fetching the small candidate set.

Because the location service is stateless and its index is either in Redis or rebuildable, failures are mostly a capacity question: keep enough replicas per region that losing one does not overload the rest, and stagger quadtree rebuilds so a fleet never cold-starts at once. If the business database primary fails, writes pause briefly while a replica is promoted, but searches keep working from replicas and caches.

The lasting lesson is that geospatial search is an indexing problem: transform two dimensions into something a one-dimensional structure can range-scan, accept a boundary fix such as neighbour cells, and over-fetch candidates before an exact distance filter. Everything else is standard read-heavy scaling.