Cache cache cache. Pre-cache, serve slightly stale cache, write your own data structures to store cache data in special ways.

The obvious method is to use mem-cached, but beyond that, nothing seems to be standardized. Use every trick you can think of.