🎓 A1Learner
🔍
0 of 42 lessons completed

Autocomplete: Sharding the Trie

Autocomplete scaling splits the stored tries across machines, so no single machine holds the whole alphabet. This lesson scales the design out: the trie is sharded by first letter, and each lookup visits one shard.

Terms land by first letter

The demo deals a fixed term list into three shards by first letter. The printout shows each shard's terms and how uneven the split already is.

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

for name in ["a-i", "j-r", "s-z"]:
    print(name, "holds", len(shards[name]), "terms:", shards[name])

A lookup visits one shard

The typed prefix pe belongs to one shard only, so only that shard is checked. The printout shows the 7 terms checked there against the 14 terms in the whole store.

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

typed = "pe"
name = shard_for(typed[0])
answer = [term for term in shards[name] if term.startswith(typed)]
print("shard visited:", name)
print("answer:", answer)
print("terms checked:", len(shards[name]))
print("terms in the whole store:", len(terms))

One store per language

The same typed prefix is answered from two language stores. The printout shows two different answers, which is why one shared store cannot serve both languages.

stores = {
    "english": ["mango", "maps", "market"],
    "spanish": ["madrid", "manzana", "mar"],
}
typed = "ma"
for language in ["english", "spanish"]:
    answer = [term for term in stores[language] if term.startswith(typed)]
    print(language, "answer for " + typed + ":", answer)

Example

terms = ["apple", "apricot", "banana", "cherry", "grape", "kiwi", "lemon", "mango", "peach", "pear", "plum", "quince", "strawberry", "watermelon"]
ranges = [("a-i", "a", "i"), ("j-r", "j", "r"), ("s-z", "s", "z")]

def shard_for(letter):
    for name, low, high in ranges:
        if low <= letter <= high:
            return name

shards = {"a-i": [], "j-r": [], "s-z": []}
for term in terms:
    shards[shard_for(term[0])].append(term)

for typed in ["ap", "ki", "pe", "st"]:
    name = shard_for(typed[0])
    answer = [term for term in shards[name] if term.startswith(typed)]
    print(typed, "-> shard", name, "->", answer)

Key points

  • Shard: one machine holding the tries for its range of first letters.
  • Shard key: the first letter of the typed prefix, which sends each lookup to exactly one shard.
  • Balance: in the demo the three shards hold 5, 7 and 2 terms, so first letters do not split the store evenly.
  • Limit, personalisation: the stored lists are the same for every user, because one list is precomputed per prefix.
  • Limit, language: each language needs its own trie and its own counts, because suggestions differ by language.

In this example, four typed prefixes are routed by their first letter and answered by their own shard. Each line shows the prefix, the shard it visited and the answer that shard returned.

Note

sharding by first letter keeps each lookup on one machine, at the cost of uneven shard sizes.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A user types ki. Which shard answers the lookup?