I ‘m not this is the correct platform to ask architecture related question, actually I have a webapplication developed in nodejs & typescript hosted in AWS, and the backend is mongodb and my requirement is to include a search box with wild card & auto suggest search functionality so when I start typing on the text box, it will autosuggest just like we do in google search, so how would I achieve this, querying everytime to mongodb will be kind of slow and if 100’s of user start doing that, then my application might start dangling so need your suggestion.
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?
Note: Earlier I posted the same question on stack overflow, but after reading some guidelines, thought it’s appropriate to open question here instead.