Design a nearby places service

I would index places by geohash cell and keep the whole index, about 50 GB, in memory on replicated nodes. A search converts the user's point into a 5-character cell, which is about 4.9 km wide and covers a 2 km radius together with the 8 neighbouring cells. The service reads each cell's entries from a cache, or from an index replica on a miss. It then removes places outside the true radius, applies category and open-now filters, ranks by distance and rating, and returns a page with a cursor.

In a dense city that is about 21,600 candidates for 1,260 real hits, which is cheap to filter in memory. I cache cell entries, not final results, so many users share the cache and filters stay current. Reads scale by adding replicas, six for the 11,600 searches a second peak, and by sharding by prefix if the index grows. Owners write to a places database, the source of truth.

A queue and an updater apply each change to the index within minutes, using a version number so repeats are harmless. The trade-off is a few minutes of delay on edits, in exchange for fast, independent read and write paths.

These numbers are assumptions for the exercise, not facts about a real system:

• 200 million places worldwide. Each result entry (id, position, name, category, rating, hours) takes about 250 bytes, and a full details record about 1 KB.
• 100 million searches a day, with a peak of 10 times the average. A typical radius is 2 km.
• One index replica serves about 2,000 searches a second.
• Dense city areas hold about 100 places per square kilometre, and owners make 1 million edits a day.

The arithmetic:

Searches per second

100M ÷ 86,400 s ≈ 1,157

≈ 1,160/s, 11,600/s at a 10x peak

Index size

200M × 250 B

50 GB, small enough to hold in memory on a few nodes

Index replicas for peak

11,600/s ÷ 2,000/s per replica = 5.8

6 copies of the index

Candidates in a dense city

3 × 3 cells of ≈ 24 km² = 216 km²; × 100 places per km²

≈ 21,600 places to filter

Places inside a 2 km radius

π × 2² ≈ 12.6 km²; × 100 places per km²

≈ 1,260 places, about 6% of the candidates

Edit rate

1M ÷ 86,400 s ≈ 11.6

≈ 12/s, easily handled asynchronously

A geohash turns a latitude and longitude into a short string by repeatedly halving the map and recording left or right, up or down. Each extra character adds 5 bits of precision and shrinks the cell. Places that share a prefix share an area, so the index is just a table from a cell string to the list of places inside it. Near the equator, the cell sizes are roughly:

• 4 characters: 39 km by 19.5 km.
• 5 characters: 4.9 km by 4.9 km.
• 6 characters: 1.2 km by 0.6 km.
• 7 characters: 150 m by 150 m.

Pick the precision from the radius. Choose the level where the cell's shorter edge is at least the radius. Then the cell holding the user plus its 8 neighbours always covers the circle, because the circle can reach at most one radius past the edge of the user's cell. For 2 km that is 5 characters. For a larger radius, go one level coarser or add a second ring of neighbours: a 5 × 5 block at 5 characters reaches at least 9.8 km from any point in the middle cell.

Why the 8 neighbours. Two points can be a few metres apart and fall in different cells with different prefixes. A search that reads only its own cell would miss places just over the border. Neighbour cells are computed by a small library function.

Wasted candidates. The 3 × 3 block covers about 216 km², and the circle only 12.6 km². In a dense city that is about 21,600 candidates for 1,260 true hits. That is fine for in-memory work, because the exact distance check removes the extras. Smaller cells with more lookups waste less but cost more calls. Both are sound choices, and what matters is saying why.

Dense and empty cells. A city centre cell may hold far more places than a rural one. If a cell grows past a limit, say 5,000 entries, store it as its child cells one level down. A quadtree does this natively: it splits any square with too many places into four. It adapts to density, but it is a pointer structure held in memory, harder to store, shard and update. Geohash strings work in any key-value store, sort in an ordinary index and shard by prefix, which is why I would start there.

The cell lookup returns candidates, not answers. The search service finishes the job in memory, in this order.

• Exact distance. Compute the real distance of each candidate to the user. For a few kilometres, a flat-earth approximation is accurate enough. Beyond that, use the haversine formula. Drop places outside the radius.
• Filters. Keep the right category. For open now, store opening hours as a weekly bit pattern in 15-minute slots, which is 7 × 96 = 672 bits or 84 bytes, together with the place's time zone. The service converts now to the place's local time and checks one bit.
• Rank. Sort by distance for the default view. For a blended view, use a weighted score of closeness, rating and the number of reviews. Use a smoothed rating, such as a Bayesian average, so one five-star review does not beat a thousand good ones.

With about 1,260 places in the radius, a full sort is cheap. To return only the first page, a heap that keeps the best 20 is even cheaper.

Why not cache final results. Radius, category, position and the moment all change the answer, so a cache of final results would almost never hit. Cache the raw entries of each cell instead, which every nearby user shares, and run filtering and ranking per request. Open now is evaluated at request time, so it is always right.

Paging. Offset paging breaks when results move between requests, giving repeats and gaps. Use a cursor: the sort key of the last item shown, such as its score and id. The next request returns the items after that key. For stable ordering across pages, the first request can keep the ranked list of ids for five minutes under a token, and later pages read slices of it.

Reads. The index is small, 50 GB, and it is read far more than it is written. That suits replication more than sharding. Run 6 copies behind a router, and add copies as traffic grows. If the data outgrows one node, shard the index by geohash prefix, say the first 2 or 3 characters, and give busy city shards more replicas. A router sends a query to the shard that owns its cells. A query that touches two shards near a border sends two requests and merges them.

The cell cache. Key it by cell string and store the cell's entries, with a TTL of about five minutes. Hot cells, such as city centres, hit all day. A cold cell is one extra read from the index. The cache also keeps search working for a few minutes if an index replica fails.

Edits are slow on purpose. The places database is the source of truth. An owner's save writes there, and the owner sees it at once because the owner's own page reads from the database. The change is then published on a queue, and the index updater applies it. Reads tolerate minutes of delay, and an edit rate of about 12 a second is trivial. Avoiding a synchronous write to the index keeps owners fast and keeps the index independent of the database's health.

Updates must be safe to repeat. Each change carries a version number from the places database. The updater applies it only if the version is newer than the entry's, so a duplicate or out-of-order message does no harm. If a place moves, the updater removes it from the old cell and adds it to the new one. Then it clears the cache for just those cells.

Repairs. Over time the index can drift from the database, for example after a bug. Rebuild it in the background from the database into a fresh copy and swap it in. This is also how a new field or a new cell precision rolls out safely.