Overview
Google Suggest was launched in 2004 as a 20% time project from Google engineer Kevin Gibbs. He developed the idea on a Google shuttle bus.
Design
- Use trie.
- Use cache (distributed cache)
Trie
Just make use of all keywords (including space) and build a trie out of it. Then you are good to go just search in Trie.
A comparison of speed between DB, Set and Trie can be found here. A lot of implementation code can be found here.
Memcached
Distributed caching + LRU replacement algorithm. Refer to [Design] Distributed Caching - memcached for more.