Autosuggest at scale - trie sharding

Question

While reading on the design for autosuggest implementation on large scale systems (like google), I'm able to understand the usage of trie and how top "n" terms are stored at each node to quickly retrieve the list. However, I'm not able to get my head around the logic of efficient way of "sharding" the trie in a distributed system. Sharding on the first letter/first two letters isn't obviously a neat solution and I've read somewhere else on using a hash of the term - but that requires an aggregation server that pulls up results from all the servers and aggregate them. Doesn't sound like an efficient thing to do at "web" scale.

Would the ideal approach be something like calculating the actual density and breaking up the tree accordingly (sort of application managed shard/partitioning ?) - but think it would incur lots of maintenance and re-balancing?

Can someone advice or point me to any reference?

A related question to this - what if I wanted to store top "n" results for different time windows. Like, top 10 in last day, top 10 in last month, top 10 of all time. What's the best solution? - Store the pointer list at the tree node for each time window? What if the set of windows are not finite?

Thanks

Answer 1

Suppose you have stored prefix in different instances:

A-F
G-M
N-R
S
T-Z

1. if there are too many records under A-F instance, you can just re-partition and split it to A-D, E-F.
2. if there are too many records in S instance, you can add another load balancer in front of this instance, and split the instance to two, keeping SA-SM in one, and SN-SZ in another. For this use case you also change the config in overall load balancer so it can dispatch the traffic properly to the S-load balancer.