Partitioning and Availability

In one line: the partitioning choice here deliberately rejects the locality that the entire chapter has been building toward. Understanding why is the sharpest reasoning in the design.

Two ways to partition

With 20% annual growth in mind, the number of places will increase. We can partition data on the following basis:

Scheme	Detail
By region	Split locations into regions based on zip codes. All locations belonging to a region are stored on a single node. If a region becomes popular during tourist season, it can affect performance — numerous queries on one server result in slow response times
By `PlaceID`	Partition on `PlaceID` instead of region to avoid query overload in popular seasons or rush hours. A key-value store maps `PlaceID` to the server holding it

So, we'll opt for partitioning based on places. Moreover, we'll also use caches for popular places.

This deliberately destroys locality — and that is the point

Stop and notice how strange this is against everything before it.

Ten lessons have argued that proximity queries need spatial locality. The quadtree exists to put nearby places near each other. Then the partitioning scheme scatters places across servers by ID, which is essentially random with respect to geography.

Two places on the same street land on different servers. A search for cafes near you fans out across the whole fleet.

That looks like it undoes the work — and it is the right call. Here is the reasoning:

Region partitioning creates hotspots you cannot escape. Lesson 2's requirement was explicit about lunch hours and tourist seasons. If Manhattan's places live on one node, that node absorbs every Manhattan query. During lunch it saturates while a node holding rural Montana idles. You cannot add capacity usefully, because the load is intrinsically concentrated on one key range.

ID partitioning spreads the hot region across the fleet. Manhattan's 50,000 places scatter over every server, so a Manhattan traffic spike is absorbed by all of them. The hotspot dissolves.

The cost is a fan-out per query, which is affordable because the index is small and in memory. A scatter-gather over several servers, each answering in microseconds, is cheap. The aggregator from Lesson 6 already exists to merge the results.

Trading locality for load distribution is correct when the load is skewed and the per-shard query is cheap. Both conditions hold here.

This is the same reasoning as the sharded-counters pattern — deliberately scattering a hot counter across shards and paying a fan-out to read it — and the same as consistent hashing scattering adjacent keys. Locality concentrates load. When load concentration is the failure mode, scatter on purpose.

But the quadtree cannot be partitioned by PlaceID, and the design conflates two things

Here is a real tension the design does not resolve.

A quadtree is inherently spatial. Its leaves are geographic cells; splitting requires knowing which places share a region. You cannot distribute a quadtree by PlaceID — the structure would be meaningless.

So what is actually partitioned by PlaceID? Look at what "the key is the PlaceID and the value contains the server in which that place is stored." That is place records — rows in the relational database.

And Lesson 12's availability section describes the quadtree differently: "QuadTrees are built on a server, so we can use the server ID as a key to identify the server on which the QuadTree is present."

So there are two distinct schemes and the lesson runs them together:

	Partitioned by	Why
Place records (the database)	`PlaceID`	Spread hot regions across servers
QuadTrees (the index)	Geography, necessarily	The structure is spatial

Which means the hotspot problem is not actually solved for the index. A quadtree covering Manhattan is still a quadtree covering Manhattan, and it still absorbs Manhattan's lunch rush.

What handles it is the next section — replication. The Manhattan tree exists on several servers, and read traffic spreads across the replicas. That is a legitimate answer, but it is replication doing the work, not partitioning, and the lesson credits partitioning.

Being able to separate these is a genuinely strong interview move: "partitioning by ID helps the record store; for the spatial index, geography is forced, so hotspots are handled by replicating hot subtrees more heavily — and I'd replicate adaptively by load rather than uniformly."

Availability through replication

Consider a scenario in which multiple people within the same radius submit a search request. If we have a single QuadTree, it'll affect availability. So we replicate our QuadTrees across multiple servers. This allows us to distribute read traffic and reduce response time. QuadTrees are built on a server, so we can use the server ID as a key to identify the server on which the QuadTree is present. The value is the list of places that the QuadTree holds. The key-value store makes it easier to rebuild the QuadTree if we lose it.

How will the leader-follower approach help us in replication?

We'll have a single leader and two followers. The leader will have the QuadTree and handle all the write requests. It'll update the followers about any change synchronously, so there'll be a chance of delay. The followers will handle all the read requests. If a follower dies, we'll choose another and replicate the data to it. If the leader is down, we'll choose any follower to step in as leader.

"Synchronously, so there will be a chance of delay" — these describe opposite designs

The sentence is self-contradictory, and untangling it matters because the two options have genuinely different consequences.

Synchronous replication: the leader waits for followers to acknowledge before confirming a write. Followers are never stale. The cost is write latency — every write waits for the slowest follower — and write availability, since a slow or dead follower blocks writes unless you degrade.

Asynchronous replication: the leader confirms immediately and propagates in the background. Writes are fast. The cost is staleness — a follower may briefly lack a write — and possible data loss if the leader dies before propagating.

"There'll be a chance of delay" describes staleness, which is the asynchronous failure mode. So the reasoning matches asynchronous while the word says synchronous.

For this system, asynchronous is clearly right, and the argument is the read-to-write ratio from Lesson 6. Writes are five places a day. Reads are 60 million searches. Optimizing writes at the cost of read staleness would be optimizing the rare path.

More importantly, the staleness costs nothing here. A new restaurant appearing in search results a second late is invisible. Compare a payment system, where reading a stale balance means a double spend — there, synchronous replication earns its cost. Here it does not.

The general rule: choose the replication mode by what staleness costs, not by which sounds safer. Lesson 2 already established that nothing in this domain is transactional.

Followers serving reads is what actually solves the hotspot

The most useful line is "the followers will handle all the read requests."

That means the leader does no read work at all, and read capacity scales with the number of followers. Since reads outnumber writes by millions to one, this is where nearly all capacity lives.

And it is the real answer to the hotspot problem the partitioning section claimed to solve. A tree covering a tourist region is geographically fixed — but you can put it on ten followers instead of two, and the spike divides.

That suggests a refinement the design does not make: replicate adaptively rather than uniformly. Three replicas everywhere is simple but wrong, since load is not uniform. Manhattan's subtree might warrant twenty replicas and rural Montana's one.

This is the same idea as CDNs's popularity-driven caching and distributed caching's hot-key handling. When load is skewed and data is small, replicate proportionally to load. At 12 GB total, extra replicas are nearly free — which is exactly why Lesson 11's small index matters here.

The key-value store as a rebuild log is a nice touch

"The key-value store makes it easier to rebuild the QuadTree if we lose it."

The in-memory tree is derived state. Its authoritative source is the place records, and the key-value store keeps serverID → the list of places that tree holds.

So recovery does not need to replay anything or copy a tree from a peer. Read the list, rebuild the structure, serve. For 500 places per leaf over a subtree, that is fast.

This is the standard pattern for rebuildable in-memory state and worth naming: do not back up the structure, back up the input that produces it. The structure is deterministic given the input, so persisting the input is sufficient and far simpler — no serialization format, no version compatibility between tree layouts.

The same instinct appears in distributed caching, where a cold cache refills from the database rather than being restored, and in distributed search, where an index segment is rebuilt from documents rather than repaired.

Key takeaway

The design deliberately sacrifices locality, partitioning place records by PlaceID rather than region, because region partitioning concentrates the lunch-hour and tourist-season load on one node — locality concentrates load, so scatter when concentration is the failure mode. But a quadtree cannot be partitioned by ID, since the structure is inherently spatial, so the index's hotspots are actually handled by replication, not partitioning — and replicating adaptively by load rather than uniformly is the refinement, made affordable by the index being only 12 GB. Replication should be asynchronous despite the design saying synchronous, because staleness costs nothing here and writes are five a day. And the tree is rebuilt from its inputs rather than restored — back up what produces the structure, not the structure.

Next: inserting new places and ranking by rating.