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

1. Use trie.
2. 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.