Problems / Caching, hard
Asked at Google and Amazon. Every keystroke runs a prefix query on the full-text search index. Suggestions must come back within 80 ms at p99, and at 8 s a news event raises traffic by half.
Unlock it once for 25 credits; everything inside it is free (runs, changes, Submit, results, hints). Sign in with Google to start; new accounts get free credits.
Success ≥ 99.9%, p99 ≤ 80 ms and Apdex ≥ 0.95, for at most $28,000 a month.
Like a coding problem, a solution has to pass every case, not just the one it was built for. Submit in the lab runs all 3; 1 of them are hidden until then.
40,000 requests a second for 20 seconds: 97% suggest (reads), 3% log (writes).
What each component does in this design, and what calls it. The simulator mimics each one from these settings.
| Component | Its job here | Settings |
|---|---|---|
| Load balancerLoad balancer | Traffic enters here.Calls Suggest API.Layer 4 balancers route by IP and port; layer 7 balancers read HTTP and can route by path or header. | – |
| Suggest APIApp service | Load balancer forwards to it.Calls Full-text index (prefix queries).Little's law: throughput ≈ concurrency ÷ latency. 200 slots at 50 ms serve about 4,000 req/s. | 16 replicas × 100 slots · timeout 400 ms |
| Full-text index (prefix queries)Search index | Suggest API calls it.Search engines build an inverted index: each word points to the documents that contain it. | 512 slots |