Inserting Places and Ranking Them

In one line: these are the two write paths, and both are made cheap by the same fact — writes are rare. The daily rating rebuild in particular is a decision worth defending rather than apologizing for.

Inserting a new place

We insert a new place into the database as well as into our QuadTree. We find the segment of the new place if the QuadTree is distributed on different servers, and then we add it to that segment. We split the segment if required and update the QuadTree accordingly.

The split is one sentence in the design and the most expensive operation in the design

"We split the segment if required and update the QuadTree accordingly" hides a good deal of work. Unpacked, a split means:

Create four children and partition the 501 places among them by quadrant.

Rewire neighbour links. From Lesson 10, leaves are connected so a search can walk to neighbours. The old leaf's neighbours must now point at whichever of the four children borders them — and that requires geometric reasoning about each neighbour, whose own cells may be at different depths. This is the maintenance cost of stored adjacency that Lesson 10 flagged.

Propagate to replicas. From Lesson 12, each tree lives on a leader and two followers. A structural change is not a value update — followers must apply the same restructuring.

Handle concurrent reads. Searches are traversing this tree while it is being restructured. A reader that has descended to the old leaf mid-split may find a node that no longer exists.

That last one is the genuinely hard part and the design does not address it. The standard resolutions are copy-on-write — build the four children, then swap the parent's pointer atomically so readers see either the old leaf or the new subtree, never a half-state — or a brief lock on the affected subtree.

Copy-on-write is the better fit given the ratio: readers never block, and at five splits a day the extra allocation is irrelevant.

Which brings the real point: this is expensive, and it is completely fine, because Lesson 3's estimate says five new places arrive per day. Five expensive operations daily against 60 million searches is nothing.

An operation's cost only matters multiplied by its frequency. A design that made insertion cheap by making search harder would be strictly worse here. Recognizing which side of the ratio you are on is what tells you where complexity is affordable.

Splits are the mechanism that keeps the tree adapted — and they are irreversible

Worth noticing what the split accomplishes beyond making room. It is how the tree tracks a changing world.

A neighbourhood that gentrifies gains restaurants; its leaf splits; the cells there get finer. The structure follows the data without anyone re-planning the partitioning. That is the promised benefit of Lesson 9's rule, delivered incrementally.

But there is no merge operation anywhere in the design. A neighbourhood that empties out leaves four sparse children where one leaf would do.

Over years, that means the tree only ever gets deeper, accumulating structure for density that no longer exists. It is a slow degradation rather than a bug — Lesson 11 showed internal nodes cost 0.1% of memory, so a somewhat over-split tree wastes little space. The real cost is deeper traversals and more searches straddling boundaries.

The natural fix is already in the design: Lesson 6's periodic rebuild — "this process repeats periodically, e.g. monthly." A full rebuild from the database produces an optimally shaped tree and discards accumulated over-splitting.

That is a clean division of labour worth naming: incremental updates keep the index correct, periodic rebuilds keep it well-shaped. The Distributed Search chapter made exactly the same split between incremental indexing and batch reindexing, and for the same reason — incremental operations preserve correctness but degrade structure.

Keeping the average rating current

Search results show an average rating, and recomputing it per query — averaging every review of every candidate — is hopeless. There are three answers and the middle one is usually right.

Store the running sum and count on the place row and update them as part of the review write. The average is then a division, available for free on every read.

The correctness detail is concurrency: two reviews landing together can both read the old count and write back, losing one. Either take an optimistic lock and retry, or express it as a single atomic statement that increments in place rather than read-modify-write.

Worth volunteering here: given roughly a thousand reads per write, review throughput is on the order of one write per second. That is small enough that a message queue and an async aggregation service would be over-engineering — recognizing when not to add a component is a stronger signal than adding one.

One review per user, enforced where it cannot be bypassed

An application-level check is a race by construction — the gap between the read and the write is exactly where the duplicate slips through. A composite unique constraint makes the second insert impossible regardless of how many application servers are running.

The general rule: enforce a data constraint as close to the persistence layer as you can. Application checks express intent; only the database enforces it.

Ranking popular places

We need a service rating calculator that calculates the overall rating of a service. We can store a place's rating in the database and in the QuadTree, along with its ID, latitude, and longitude. The QuadTree returns the top 50 or 100 popular places within the given radius. The aggregator service determines the actual top places and returns them to the user.

Note: We don't expect the rating to be updated within hours, as such frequent changes in QuadTrees or databases can be expensive. We update them once a day, when the load is minimal.

The rating lives in the index so ranking does not need a database round trip

Storing the rating in the quadtree is a denormalization, and the reason is specific.

Without it, ranking would require: find candidate IDs in the tree, fetch all of them from the database, sort by rating, keep 20. With hundreds of candidates across several servers, that is a large fetch to discard most of.

With it, each quadtree server sorts locally and returns only its top 50 to 100. The database is then queried for the final small set.

WITHOUT rating in tree:  tree -> hundreds of IDs -> DB fetch all -> sort -> 20
WITH rating in tree:     tree -> sort locally -> top 100 -> aggregator -> DB fetch 20

Push the filter to where the data is. Same principle as predicate pushdown in query engines, and as distributed search's per-shard top-k.

The over-fetch — 50 to 100 per server to produce 20 — is the standard price of distributed ranking, for the reason Lesson 6 gave: no server can know whether its 20th-best beats another server's 5th-best, so each must send enough that the merged result is correct.

Note the cost of this denormalization, though: the rating now lives in two places, and both must be updated. That is precisely why the rebuild has to touch the tree as well as the database.

Updating ratings once a day is the right call, and the reasoning generalizes

"We don't expect the rating to be updated within hours, as such frequent changes in QuadTrees or databases can be expensive."

At first reading this sounds like a compromise. It is not — it is correct, and for a reason stronger than cost.

A rating is an aggregate over many reviews, so any single review barely moves it. A place with 500 reviews averaging 4.2 receives a 5-star review; the average moves by about 0.0016. Updating the index for that is spending real work to change a displayed value by nothing.

The update is not one write. Changing a rating means writing the database row, updating the in-memory tree, propagating to replicas, and potentially reordering results. Per review, at 1 million reviews a day, that is 11 write amplifications per second across a replicated in-memory structure — for changes invisible to users.

Batching converts random writes into a sequential job. One nightly pass recomputes every affected place's average and applies the updates in bulk, when load is minimal.

So the daily cadence follows from a property of the data: when a value changes by less than its own noise, updating it in real time is waste.

The right way to say this in an interview is as a staleness budget. The question is not "how fast can we update?" but "how stale can this be before anyone notices?" For an aggregate rating over hundreds of reviews, a day is well inside the noise. For the review text, which Lesson 2 discussed, a user should see their own submission immediately — different data, different budget.

One refinement worth offering: the daily job should be incremental, processing only reviews since the last run. Lesson 5 noted the schema has no timestamps, which makes that impossible — so the job must currently reprocess everything. That is the concrete cost of the missing time dimension.

What the finalized design adds

We introduced caches to store popular places. This allows us to fetch the places much faster. Moreover, we added a rating calculator that sorts places by rating.

Two additions, and the cache is the more interesting.

Popular places are a small, heavily-skewed set — a famous restaurant is fetched thousands of times more often than an average one. That is the textbook case for caching, and it composes well with everything else: the quadtree finds which places, the cache supplies what they are without a database read.

It also pairs neatly with the daily rating rebuild. Because ratings change once a day, cached place records can be held with a long TTL and invalidated by the nightly job. Slow-changing data is easy to cache — the same reason CDNs found static assets easier than dynamic ones.

Next: checking the design against its requirements.