A friend has an interview at Google/Facebook recently and presented the trie as a solution. The interviewer pushed him forward using key-value database and avoid the trie.
Taking into account this, the statement at the beginning of the article “We can’t depend upon some database for this” is very strong. I don’t think reading data for one prefix from key-value database takes more than 20ms. I also assume that the answers for 99% prefixes we can get from the cache (2ms read latency). I guess supporting distributed trie is not trivial task and solution with the database is much cleaner.
Once a user clicks search with a query, we update counters for all prefixes for this query. I guess it should be fine if this fanout is async and we don’t get real time data (it doesn’t matter how much time write takes). Each prefix keeps top 10 suggestions. We read from the cache/database top 10 suggestion using just 1 query to cache/database that takes 2ms most of the time. This solution can be easily scaled and distributed. The only tricky part is how we do writes and fanout the query update.