6

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

2
  • @DocBrown Thanks! deleted the post on stack overflow Nov 5 '18 at 9:56
  • Did you ever get an answer to this to your satisfaction? I was just looking into this myself.
    – Miao Liu
    Feb 2 '20 at 4:23
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.