Proximity Service

Find nearby places

Design a service that, given a location and a radius, returns the nearby businesses in a category, sorted by distance, from a catalog of hundreds of millions of places.

Overview

A proximity service answers one question: which places are near this point? A user opens a map app and asks for coffee within 500 meters; the service returns the cafes inside that circle, closest first.

The catalog changes slowly (a business opens or moves a few times a year) while searches arrive thousands of times a second. So this is a read-heavy problem, and the interesting part is the index. An ordinary B-tree index sorts one value. Location is two values, latitude and longitude, and a B-tree on both can only use the first one efficiently. The design is about turning a two-dimensional search into a few cheap lookups.

Questions to ask first

How many places, and where? — 200 million businesses worldwide, dense in cities, sparse elsewhere
How many searches? — 50 million daily users, 10 searches each
What radius? — 0.5 km to 20 km, chosen by the user
How fresh must changes be? — A new or moved business shows up within minutes, not instantly
Do objects move? — No; places are fixed. Moving drivers are a different problem
How are results ranked? — By distance, with a category filter; relevance ranking is out of scope

What you will be able to do

Explain why a plain index on latitude and longitude is not enough.
Encode a point as a geohash, pick a length for a radius, and explain the nine-cell search.
Compare geohash, quadtree, S2, H3 and an R-tree index, and pick one.
Size the index and show that it fits in memory.
Keep searches fast while businesses are added and moved.

Key concepts

Geohash
Nine-cell search
Haversine distance
Bounding box
Quadtree
S2 cells
H3 hexagons
Read replicas
Cache by cell

Functional requirements

Return businesses within a radius of a point, optionally filtered by category
Sort results by distance and return the distance with each one
Page through results when there are many
Let owners add, move and remove a business
Return one business's details by ID

Non-functional requirements

Searches answer in under 200 ms at p99 (a target we chose)
Searches stay up 99.99% of the time; business edits may be briefly unavailable
A change to a business shows in search within a few minutes
No place inside the radius is missed because of how the map is divided
The index scales with more searches by adding copies, not by redesigning

Interview questions

Why not just put an index on latitude and longitude?
Walk me through a nearby search with geohash.
Why nine cells and not just the user's cell?
Geohash or quadtree?
Does the index need to be sharded?
How do new and moved businesses reach the index?
How is this different from finding nearby drivers?
What is S2 or H3, and when would you pick one?