Problem RestatementProblem
Design a service that answers: "show me places near me". Given a user's location (latitude and longitude), a radius, and optional filters or text ("pizza", "open now", rating 4+), return the top K places sorted by a mix of distance and quality. Examples include Yelp, Google Maps nearby, or restaurant search in Uber Eats.
Places change rarely, but searches happen constantly. So this is a read-heavy problem, and the main question is how to find nearby points quickly.
RequirementsRequirements
1.1 Functional
- Search by location + radius (or "nearest K").
- Optional text query and filters (category, price, rating, open now).
- Return ranked results with distance.
- Business owners add and update places (changes can take a few minutes to show).
1.2 Non-Functional
- Low latency: under ~100 ms.
- High read throughput, peaks at meal times.
- Global coverage: very dense cities and empty countryside.
1.3 Scale Estimates
- 200M places worldwide × 1 KB ≈ 200 GB of place data.
- 100M daily users × 5 searches = 500M searches/day ≈ 6K/sec, peak ~30K/sec.
- Writes (new or updated places): a few hundred per second. Tiny in comparison.
1.4 API Design
GET /v1/search?lat=12.97&lng=77.59&radius=2000&q=pizza&open_now=true&limit=20&cursor=
[{ place_id, name, lat, lng, distance_m, rating, ... }]
GET /v1/places/{id}POST /v1/places,PATCH /v1/places/{id}(owners)
High-Level ArchitectureArchitecture
2.1 Overview
- Search Service: turns the location into a set of map cells, fetches candidates, filters and ranks them.
- Geo index: maps cells to place IDs. It fits in memory on each search server, or lives in a search engine with geo support (Elasticsearch/OpenSearch geo queries).
- Place DB: full place details (SQL or document store), fronted by a cache.
- Indexer: listens to place changes and updates the index.
2.2 Architecture Diagram
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
U["User app"] --> LB["Load balancer"]
LB --> SS["Search Service"]
SS --> GI[("Geo + text index - replicated")]
SS --> C[("Place details cache")]
C --> DB[("Places DB")]
O["Business owners"] --> PS["Place Service"]
PS --> DB
PS --> K[("Change events")]
K --> IX["Indexer"]
IX --> GIHow to Find Nearby Points
Scanning 200M places for each query is impossible, so we split the map into cells.
Geohash: encode a location as a short string. Nearby places share a prefix. For example,tdr1 is a ~20 km × 20 km area and tdr1y is ~5 km. For a 2 km search:
- Compute the user's geohash at a precision where cells are about the size of the radius.
- Take that cell plus its 8 neighbors. A place just across a cell border can be closer than one inside the same cell.
- Get all places in those 9 cells, compute the exact distance, and keep those within the radius.
Google's S2 and Uber's H3 are cell systems with similar ideas and better shapes. Any of these is fine in an interview if you explain the neighbor-cell trick.
Key FlowsFlows
4.1 Search
- Compute the covering cells for the circle.
- Get candidate place IDs from the index for those cells, applying filters there if possible (category, open now).
- For text queries, intersect with a text match (an inverted index on names, categories and dishes).
- Rank:
score = w1 × relevance + w2 × rating + w3 × popularity − w4 × distance. - Fetch details for the top 20 from the cache and return them with a cursor for the next page.
4.2 Updating a place
The owner edits hours or a location → Place DB → change event → indexer updates the cell entry. A delay of a minute or two is acceptable.
Deep Dive A — Finding the places near a pointDeep dive
200 million places, a latitude and longitude, and a radius. The index that answers this decides everything about latency.
A bounding box over latitude and longitude columns
Convert the radius into a box and query lat BETWEEN ... AND lng BETWEEN ....
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["lat 37.77, lng -122.41, 2 km"] --> BOX["lat between a and b AND lng between c and d"]
BOX --> I1["B-tree on lat - 4M rows in range"]
BOX --> I2["B-tree on lng - 6M rows in range"]
I1 --> X["Intersect two huge sets, then filter by real distance"]
I2 --> XThere is no single index for two independent dimensions. The database narrows on one column and scans the rest, so a query in a dense area touches millions of rows to return twenty. It works at ten thousand places and falls apart long before two hundred million.
Fixed grid cells or geohash
Turn the two dimensions into one key: divide the world into fixed cells, store each place's cell id, and index that. A search reads the user's cell and its neighbours — one indexed lookup over a few hundred rows.
This is the right idea and it has one flaw, which is that the world is not evenly populated. A cell size tuned for Manhattan holds a handful of places and forces wide neighbour scans across Montana; a size tuned for Montana returns 5,000 places for a single cell downtown. One number cannot fit both.
Cells that adapt, with a cap and an expanding ring
Use a structure whose resolution follows density — a quadtree that splits a cell once it holds more than N places, or multi-resolution cells (S2, H3) chosen per query.
%%{init: {"look":"handDrawn","handDrawnSeed":7,"theme":"base","fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","themeVariables":{"fontFamily":"Virgil, \"Segoe Print\", \"Comic Sans MS\", cursive","fontSize":"16px","primaryColor":"#fff4e6","primaryBorderColor":"#1e1e1e","primaryTextColor":"#1e1e1e","secondaryColor":"#e7f5ff","tertiaryColor":"#ebfbee","lineColor":"#1e1e1e","textColor":"#1e1e1e","mainBkg":"#fff4e6","nodeBorder":"#1e1e1e","clusterBkg":"#f8f9fa","edgeLabelBackground":"#ffffff","classText":"#1e1e1e"}}}%%
flowchart LR
Q["Query point + radius"] --> RES["Pick a resolution from local density"]
RES --> CELLS["Read the ring of cells covering the radius"]
CELLS --> DENSE{"Enough candidates?"}
DENSE -->|"too many"| CAP["Cap candidates per cell - let ranking decide"]
DENSE -->|"too few"| GROW["Widen to the next ring or coarser cells"]
CAP --> RANK["Rank by distance, rating, open now"]
GROW --> RANKBoth extremes now have an answer:
- Dense: cap the candidates taken from each cell and let ranking do the work. Nobody scrolls past the first twenty pizza places, so scanning 5,000 to sort them is wasted effort.
- Sparse: widen the ring until there are enough results, or switch the promise from "within 2 km" to "the nearest twenty" — an empty result page is worse than a slightly farther restaurant.
The index stays small — place id, cell, and a few filter fields is roughly 50 bytes, so 200M places fit in about 10 GB of memory — which means it can simply be replicated onto every search server rather than queried over the network.
Deep Dive B — Scaling and cachingDeep dive
- The geo index for 200M places (ID + cell + a few filter fields ≈ 50 bytes) is ~10 GB, which fits in memory. Replicate it on many search servers to scale reads.
- For even more scale, shard by region (e.g., by country or large geohash prefix). Queries near a border ask two shards.
- Cache popular queries by (rounded location cell + query + filters) for a few minutes. Lunchtime "pizza near downtown" repeats a lot.
- For a delivery app, also filter by "does this restaurant deliver to this address" and rank by estimated delivery time. These need live data (courier supply, kitchen load), which comes from a fast store.
Trade-offs & AlternativesTrade-offs
| Decision | Choice | Why | Alternative |
|---|---|---|---|
| Index | Geohash cells + neighbors | Simple, works with key-value stores | Quadtree: adapts to density, in-memory only |
| Engine | Search engine with geo + text | One query for location and keywords | Separate geo and text services: more merging |
| Scale | Replicate index, shard by region | Reads scale linearly | Single DB with a spatial index (PostGIS): fine for small scale |
| Freshness | Async indexing (minutes) | Cheap, reads stay fast | Synchronous: slower writes, rarely needed |
Common Follow-up QuestionsFollow-ups
- "Why not just use SQL with latitude/longitude ranges?" A bounding-box query on two columns can't use one index efficiently at this scale. Geo cells turn it into a simple key lookup.
- "Moving objects like drivers?" That's different: locations change every few seconds, so keep them in an in-memory geo index updated from a stream (see the ride-hailing design).
- "Personalization?" Add user features (cuisines you order, price level) to the ranking step.
Wrap-UpWrap-up
Split the map into cells (geohash, quadtree, S2 or H3), search the user's cell plus its neighbors, then filter by exact distance. Combine with text search and filters, rank by relevance, rating and distance, and fetch details from a cache. Replicate the in-memory index for reads, shard by region at global scale, and expand the search area where places are sparse.