STANDARDwalkthrough
Zipf's Law: The Cache Layers Above the Service
Search traffic is brutally skewed: query popularity follows a Zipf distribution, and prefixes inherit the skew with interest: every journey to "weather" walks through "w" and "we", the same few short prefixes that begin millions of other journeys. The consequence: the top ~100K prefixes (a fraction of a percent of 200M) serve on the order of half of all requests, and the top few million serve the overwhelming majority.
Layer one: the browser. Suggest responses carry Cache-Control (60-300s); a user backspacing and retyping "we" replays from local cache: zero network.
“That shape is a gift, and the design collects it with three cache layers before the service.”
Layer two: the CDN/edge. Suggestions for a given (prefix, locale) are identical for every user (personalization is deliberately layered client-side), so GET /suggest?q=we&locale=en is perfectly cacheable: the edge absorbs the Zipf head near the user at single-digit-ms latency.
Layer three: an in-process hot map on each serving node: the top ~1M entries pinned, skipping even the shard lookup. The arithmetic that makes interviewers nod: 700K/sec peak turns into ~200K/sec at origin after a 60-70% combined edge/browser hit rate, and the p99 for head prefixes is edge latency, not service latency.
Two sharp edges to name. TTL vs freshness: a 5-minute edge TTL delays trending suggestions by up to 5 minutes: acceptable for "weather", wrong for breaking news: so trending-eligible short prefixes get shorter TTLs (30-60s), a deliberate two-tier cache policy. And cache stampede: when a hot prefix's TTL expires at a busy edge, thousands of misses can hit origin simultaneously: request coalescing at the edge (one origin fetch per key) is the standard guard, the same mechanism the maps topic used for tile rollouts.
What if the interviewer asks: why not cache in Redis between service and edge? Usually redundant: the index is ALREADY in RAM on the serving nodes; adding Redis adds a hop, not speed.
Related concepts