Partitioning and Updating the Trie

In one line: the update strategy here — replace the whole structure rather than edit it — is the right answer to a read-optimized index, and the design gives two versions of it.

Partitioning by prefix range

A single server cannot handle billions of daily queries or store all prefixes in memory. The trie can be partitioned by prefix ranges — one server stores "A" through "M," another "N" through "Z." Each maintains a replica for durability. However, simple range partitioning can lead to unbalanced load because some prefixes occur far more frequently than others.

Range partitioning is required here — hashing would destroy the structure

Worth stating why the obvious alternative is unavailable.

Every other chapter in this module partitioned by hash — of a hostname, a user ID, a place ID — because hashing distributes evenly. Here you cannot, and the reason is the same property that made the trie the right structure in the first place.

Hashing destroys prefix relationships. If "UNIV" and "UNIVERSAL" hash to different servers, then answering "UNIV" requires consulting every server, because completions could be anywhere. The whole point of a trie is that a prefix and its completions are structurally adjacent, and hashing scatters exactly that adjacency.

HASH:   "UNIV" -> server 7, "UNIVERSAL" -> server 3   -> query must fan out to ALL
RANGE:  "UNIV" and "UNIVERSAL" both in N-Z            -> one server answers

So range partitioning is not a choice made for balance — it is forced by the query pattern, and the imbalance is the price.

When your structure depends on key adjacency, you must partition by range, and you inherit the key distribution's skew. The Yelp chapter reached the same conclusion about geography; here the skewed dimension is the alphabet.

The skew is severe, and the design names it without sizing it

"Some prefixes occur far more frequently than others" understates it. Letter-initial distribution in English is heavily non-uniform — a handful of letters begin a large share of words, and query distributions are more skewed still because of brand names and common terms.

An A–M / N–Z split is close to the worst possible choice: it assumes the alphabet's midpoint is the traffic midpoint, which it is not.

Three better approaches, none of:

Split by observed load, not by letter. Measure query volume per prefix and choose boundaries that equalize traffic — so a hot letter becomes its own partition and a dozen cold ones share a server. Same instinct as that building block's non-uniform segments: partition on the quantity that drives cost, not on the one that is easy to divide.

Split at deeper prefixes for hot regions. Rather than one server for "S", give "SA–SL" and "SM–SZ" their own servers. The trie's structure supports this naturally, since any node can be a partition boundary.

Replicate hot partitions more. The design already has a secondary per range; hot ranges warrant more, and this is the cheapest fix because Lesson 2 established the whole index is only 60 GB.

That last one is worth emphasizing: the index is small enough that replication is nearly free, so load-based replication is a better lever than clever partitioning here.

ZooKeeper for the prefix-to-server mapping, and it is the same component as everywhere else

The design's own question — where the mapping lives and who routes requests — is answered: "we use a cluster manager like ZooKeeper to store the mapping between clusters."

Correct, and it is the fifth appearance of this component in the module: the Google Maps key-value store mapping segments to servers, Quora's primary-replica mapping, Twitter's service registry, WhatsApp's connection registry.

The properties are always identical: small, read by everyone, changed rarely, and must be immediately correct when it does change.

Every partitioned system needs one small, strongly-consistent place that says where things live — and it is always separate from the store holding the things.

Updating offline

Updating the trie in real time for every query is resource-intensive and slows down read requests. Instead, we update the trie offline. We log queries and frequencies to a hash table, aggregate at regular intervals, then update the trie.

A MapReduce job processes the logs periodically (e.g. every 15 minutes), calculates phrase frequencies, and stores results in a database such as Cassandra.

Offline updates are forced by the precomputed top-k, not just by write volume

The stated reason is that real-time updates would slow reads. True, and there is a stronger structural reason from Lesson 4.

Because each node stores a precomputed list of top suggestions, a single frequency change can invalidate the stored lists of every ancestor node:

UNIVERSITY's count rises
  -> may change the top-10 at "UNIVERSIT"
  -> and at "UNIVERSI", "UNIVERS", "UNIVER", "UNIVE", "UNIV", "UNI", "UN", "U"

So one increment potentially touches the whole path to the root, and popular queries sit under short prefixes where the lists are most contested.

At Lesson 2's rate — hundreds of thousands of queries per second — that is not an optimization problem, it is impossible. Materializing answers into a structure makes incremental updates expensive by construction, which is the standard cost of the materialize-versus-compute trade.

Hence: batch the increments, recompute the affected lists in bulk, and publish the result. The 15-minute interval is the staleness the design accepts in exchange, and it is affordable because Lesson 1 established that top suggestions change slowly.

Two swap strategies, and they differ in resource cost

Replica replacement: create a copy of the trie on each server, update it offline, then switch traffic to the new version, discarding the old.

Primary-secondary swap: maintain a primary for traffic and a secondary for updates. After updating the secondary, swap roles.

Both are atomic pointer swaps rather than in-place mutation, which is the key property: readers never observe a half-updated trie, and no locking is needed on the read path.

The second is better for the reason in that last row: after a swap, the previous primary still holds the last-known-good trie. If the new one is broken — a bad aggregation, a corrupted build — you swap back instantly.

Keeping the previous version live is what turns a deployment into something reversible, and it costs only memory, which Lesson 2 showed is not scarce here.

This is copy-on-write at the level of a whole data structure, and it is the same instinct as that building block's quadtree splits and every blue-green deployment: build the new thing beside the old one, then switch a pointer.

The routing step, and what it needs to know

Incoming queries hit a load balancer, which forwards to an application server. The server routes the request to the appropriate trie shard based on the prefix.

Straightforward, with one detail worth naming: routing requires only the first character or two, since the partition boundaries are prefix ranges. So the application server makes the decision without any lookup into the trie itself — a range comparison against a ZooKeeper-held map.

That keeps the routing decision at microseconds, which matters against Lesson 1's budget where the entire response must fit in 200 ms including the network round trip.

Route on the shortest prefix that determines the partition, so routing costs a comparison rather than a lookup.

Updating in place would mean locking nodes on a structure read billions of times a day. Building a new copy and swapping it in means readers never contend with writers — the cost is holding two tries in memory during the swap.

Next: the assembler that builds it.