I've found Apache Solr the best approach to building a flexible, fast auto-complete service. Solr can spit results back in json so it's dead easy to write a simple API wrapper in whatever language you're using (go, python, ruby).<p>You can then stick Varnish in front of the whole lot if the search space is relatively static and not ridiculously huge.