Books Deep-Read · System Design Interview Vol 2 · Ch 1
System Design Interview Vol 2 · Ch 1 · Alex Xu & Sahn Lam · 2022
You tap "restaurants near me" and, within a second, the app has picked the few dozen around you out of two hundred million. This chapter asks: how is that actually done? The answer is slightly counter-intuitive — the hard part is not the searching. It is assigning the Earth street numbers ahead of time.
The system never measures distance. It does not take your coordinates and compare them, one by one, against two hundred million shops. It carved the planet into cells long ago and gave each cell a number. When you tap the button it asks only two questions: which cell are you in, and who else is in it?
A location is two numbers — one north–south, one east–west. Databases are excellent at lining things up by one number, the way a dictionary is sorted by spelling. They are bad at looking things up by two numbers at once. It is like asking a library for every book whose title falls between A and C and whose spine is between 3 and 5 centimetres thick: each clue narrows things down, but reconciling the two piles means going through them book by book. Do that across two hundred million shops and it is unusably slow.
① Fold the Earth in half, and write down the folds. Cut the world in two, then in two again, and again. Each cut adds one more character to the cell's number. More characters, smaller cell. The magic is this: if two numbers start the same way, the two places are close — the pair of coordinates has been squeezed into a single string, and the database is back to the one thing it does best, lining things up by a single key.
② The radius is not for measuring; it is for picking a cell size. Looking for something within 500 metres? Use small cells. Within 20 kilometres? Switch to big ones. The cells shrink the candidates from two hundred million to a few hundred; real distances get computed at the very end.
③ Grab the neighbours too. You are quite possibly standing at the edge of your cell, with the best place in the one next door. So the system never queries only your cell — it takes your cell plus the eight around it, pools the shops from all nine, and then sorts.
There are two schools of cutting. One cuts the whole world into cells of equal size — simple, and when a shop opens or closes you edit one row. The other cuts more finely wherever the shops are dense — fine downtown, one huge cell over the desert — so each query returns a more even number of candidates, at the cost of having to recompute a whole region whenever a shop changes.
And one more honest line: cells are square and the range you want is round. The nine-cell block inevitably scoops up shops that are actually outside your radius, so at the end you still have to measure each one and throw the strays away.
"Find things near me" is not a search problem, it is a street-numbering problem: flatten the pair of coordinates into a single one-dimensional number ahead of time, so the database can use the old tricks it is good at — sorted lookup and prefix matching. Everything else is housekeeping around edges and around fitting a circle into squares.
Want the mechanisms, the notation and the diagrams? → Switch to the deep read
You think "restaurants near me" is a search problem. It is a dimensionality-reduction problem: from start to finish this chapter does one thing — squeeze the two-dimensional pair (latitude, longitude) into a one-dimensional key (a geohash string, or S2's 64-bit integer) so that B-tree indexes, key-value stores and caches — tools that only know how to line things up by a single key — become usable again. Along the way it drops two counter-intuitive conclusions: the radius is not a query parameter, it is an index-precision dial; and the data is only tens of gigabytes while read traffic is 5,000 QPS, so the answer is replicas, not shards.
wx4g". B-tree indexes are built for this.This is the opening chapter of Volume 2 and the first of the book's geo trilogy: Ch1 Proximity Service (shops that never move) → Ch2 Nearby Friends (people whose position changes every few seconds) → Ch3 Google Maps (road graphs and navigation). All three share the same spatial index; what changes is how often the data updates — which makes this chapter the foundation the other two are built on. In the real world it is the "Nearby" tab of Yelp or Google Maps, and any feature that means "find things by location".
Start with the scale (the book's own numbers): 100 million daily active users and 200 million businesses. Assume five searches per user per day and search QPS = 100M × 5 ÷ 86,400 ≈ 5,000. Functionally only three things are required: return businesses given (longitude, latitude, radius); let owners add, delete and update their business, with no requirement that the change be visible immediately (tomorrow is fine); let customers view business details.
The crux hides in "what happens if you don't solve it". The naive answer is one line of SQL: WHERE lat BETWEEN … AND lng BETWEEN …. It will not run over 200 million rows, and the reason is not a missing index — it is that two indexes cannot be combined: the database generally picks one, say latitude, producing a thin band that wraps the entire globe, then checks longitude row by row. The intermediate set runs to millions of rows, and this question's latency budget is a few hundred milliseconds. So proximity in two dimensions has to be encoded into some one-dimensional key before the query ever arrives.
The obvious first fix is a uniform grid: chop the map into fixed-size squares and record which square each shop sits in. That does achieve the reduction, but the counts per cell are wildly uneven — one cell over Manhattan holds tens of thousands of shops, one over the Pacific holds none.
Every solution that actually works has the same shape: halve the plane recursively, and write down which side each cut fell on, in order. Two-dimensional proximity then lives in the prefix of a one-dimensional key — the longer the shared prefix, the more cuts put the two points on the same side, and the closer they are.
Geohash is the standard implementation of that knife: the longitude and latitude ranges are halved alternately, one bit per cut, and the bit string is encoded five bits at a time into base32 characters — so every extra character shrinks the cell to roughly 1/32 of its area. Concretely: length 4 is about 39 km × 20 km, length 5 about 4.9 km × 4.9 km, length 6 about 1.2 km × 0.6 km.
"Radius → precision" therefore becomes a lookup table. The book's mapping is 0.5 km → 6, 1 km → 5, 2 km → 5, 5 km → 4, 20 km → 4. This is exactly what "the radius is an index-precision dial, not a query parameter" means: you do not compute distances with it, you pick a cell size with it, cutting the candidate set from 200 million to a few hundred and leaving real distance to the last step.
The book names two traps, both of which must be handled on the spot:
① The boundary problem. Two points can be metres apart and still fall on opposite sides of a cut, with completely different prefixes — in the worst case, across the equator or the prime meridian, the very first character differs. So "same prefix ⇒ nearby" holds, but the converse, "different prefix ⇒ far apart", is false. The fix is blunt: query your own cell plus the eight around it, nine in total.
② Not enough results. Too few businesses inside the radius (out in the suburbs, or after an "open now" filter). The fix is equally blunt: drop the last character of the code, which enlarges the cell about 32-fold, and query again; drop another if that is still not enough.
Geohash cells are cut to fit the Earth; quadtree cells are cut to fit the data: start from the whole map, and whenever a square holds more than a threshold of businesses (the book uses 100), split it into four, recursing until every leaf holds at most 100. Manhattan ends up split very deep; the Pacific needs a single node. Candidate counts come back naturally even, and it supports "the k nearest businesses" out of the box — geohash only answers "who is in this cell", so k-nearest means expanding ring by ring yourself.
The key difference: it is not a table in a database but a tree each LBS server builds in its own memory at startup. The book's memory arithmetic: 200M businesses ÷ 100 = 2 million leaf nodes, internal nodes about a third of that, roughly 670,000; each leaf stores 100 business ids of 8 bytes, i.e. 800 bytes, for a total of about 1.71 GB — which one machine holds comfortably.
The whole cost lands on updates: adding or removing a business changes the tree's shape, and doing that live means locking and is hard to get right. The book's choice is to rebuild the entire tree nightly and roll it out gradually, taking a small batch of servers out of rotation at a time to rebuild and return them — because building a tree over 200 million businesses takes minutes, during which that machine cannot serve. Which also explains the requirement that "business updates need not take effect immediately": that concession is exactly what buys this design.
S2 is Google's spherical grid library and takes a third road: project the sphere (rather than treating the map as a plane) onto the six faces of a circumscribed cube, then thread a Hilbert curve — a path that folds back on itself, visits every cell, and keeps neighbouring cells adjacent along the curve — so each cell gets a 64-bit integer cell id. The goal is the same reduction as geohash; the knifework is just more careful, done on the sphere and so free of the distortion of flattening the Earth.
Its distinctive power is region cover: any shaped area — an administrative district, a delivery zone — can be covered by a set of cells of varying size, big ones filling the middle, small ones hugging the edge. That makes geofencing questions ("has this user entered that irregular area?") simple. The cost is that both the concept and the implementation are far heavier — not something you derive at a whiteboard.
The schema is surprisingly plain: a business table for details, and a geospatial_index table with exactly two columns — geohash and business_id — where one shop in one geohash is one row. The query is WHERE geohash IN (those nine cells).
Then the book makes a call that runs against everything Volume 1 taught: this table does not need sharding at all. Two columns, 200 million rows, tens of gigabytes — one decent machine holds it. The real pressure is 5,000 QPS of reads, not capacity. So the answer is read replicas: writes go to the primary, reads fan out to N replicas, and read throughput scales linearly with machines. Capacity and traffic are two separate dials; do not reach for sharding to turn the traffic one.
The cache layer hides a detail that is very easy to get wrong: the cache key must be the geohash, never the user's coordinates. User coordinates carry six decimal places and change with every step; used as a key they give you a hit rate of exactly zero. A geohash is a cell, and everyone inside it shares one answer — one line's difference between a cache that is decoration and a cache that carries the load. Two things get cached: geohash → list of business ids and business_id → business details.
The architecture therefore grows into two almost unrelated paths: a read path (user → LBS → Redis → index read replicas) and a write path (owner → business service → primary → asynchronous replication to the replicas). The LBS is stateless and read-only, scaled out for peak; owner writes are low enough in QPS to ignore. The "my edit isn't visible yet" caused by replication lag falls squarely inside what the requirements already allow.
Table 1 · What separates the four approaches
| Approach | Mechanism | Strength | Honest cost |
|---|---|---|---|
| 2D range query | index lat and lng separately, BETWEEN in SQL | no extra machinery | the two indexes cannot be combined; millions of intermediate rows; unusable at 200M |
| Uniform grid | fixed-size squares, store the cell id | simplest to build | wildly uneven counts, and cell ids carry no notion of nearness |
| Geohash | recursive halving + base32; prefix means proximity | simple, easy to update, radius queries directly | the boundary problem (take 9 cells); fixed cell size still floods dense areas |
| Quadtree | recursive quartering by density, leaves ≤ 100 | even counts, k-nearest for free | lives in memory, must be built; updates are brutal — nightly rebuild plus staged rollout |
| S2 | sphere + Hilbert curve → 64-bit integer | covers arbitrary regions, good for geofencing | heaviest in concept and implementation; not whiteboard material |
Table 2 · The final two: geohash vs quadtree
| Geohash | Quadtree | |
|---|---|---|
| Where it lives | a table in a database or key-value store | each server's memory (about 1.71 GB here) |
| Difficulty | low — a library and one indexed column | you build the tree and own its lifecycle |
| Adding or removing a shop | delete a row / insert a row | reshapes the tree; live updates need locking, so in practice a nightly rebuild |
| Cell size | fixed once precision is chosen | adapts to density |
| k-nearest | not directly; expand ring by ring | native |
| When to pick it | businesses change often and you need radius queries — the chapter's default | density is extreme and you must answer "the nearest k" |
Table 3 · Why this question does not shard
| Sharding | Read replicas (the chapter's choice) | |
|---|---|---|
| Solves | one machine cannot hold it | one machine cannot read it fast enough |
| The facts here | 2 columns × 200M rows ≈ tens of GB — one machine is plenty | 5,000 QPS of reads, essentially no writes |
| Cost | cross-shard queries, rebalancing, hot shards — all paid for nothing | replication lag — which the requirements already permit |
Compressed into one rule: businesses change and you need radius queries → geohash; density is lopsided and you need k-nearest → quadtree; you must cover irregular regions or do geofencing → S2. And whichever index you pick, the last step is unavoidable: once the candidates come back, you must compute real distances and sort — cells only cut 200 million down to a few hundred; they do not produce the answer.
The value of this question is that it demonstrates a general move: when the query's dimensions and the index's structure do not match, reduce the dimensions rather than replace the database. The same move recurs everywhere — full-text search reduces documents to an inverted list of terms, vector search reduces high-dimensional vectors to LSH buckets. Geohash is just the geographic instance of it.
In an interview, volunteering "this should not be sharded, it should be replicated" and "the cache key has to be the geohash, not the coordinates" is worth far more than reciting the encoding rules — both show that you are computing load rather than reciting a design.
① In one line: "find things near me" is not a search problem but a dimensionality-reduction problem — flatten coordinates into one key so ordinary indexes and caches work again.
② The scale that frames it: 100M DAU, 200M businesses, search QPS ≈ 5,000, latency budget in the hundreds of milliseconds.
③ Naive SQL dies because two indexes cannot be combined: filter millions of rows on one dimension, then check the other row by row.
④ Geohash = recursive halving + base32; length 4 ≈ 39 km, 5 ≈ 4.9 km, 6 ≈ 1.2 km, each extra character shrinking the area to about 1/32.
⑤ The radius is the precision dial, not a distance parameter: look up the length, take the nine-cell block, and only then compute real distance.
⑥ Two unavoidable traps: boundaries (take the eight neighbours) and too few results (drop the last character and widen).
⑦ The quadtree adapts to density and gives k-nearest for free, at the cost of ~1.71 GB resident in memory and brutal updates — nightly rebuild plus staged rollout.
⑧ Two counter-intuitive engineering calls: the index table takes read replicas, not shards (tens of GB fit; the pressure is reads); and the cache key must be the geohash, not the coordinates, or the hit rate is zero.