system-design-primer
exercise

Key-value store

Design a key-value store for a search engine — a cache that returns results for a query it has seen recently, and evicts what it has not.

constraints and assumptions
  • High volume of repeated queries
  • Sub-millisecond reads
  • Least-recently-used eviction
  • Results expire when stale
  • Cache misses fall through to the index
  • High availability
work it in four steps
in short

A user sends a search request; the cache returns the result if it holds one, otherwise the query runs against the index and the result is added to the cache.

The whole design is one decision made well: what to keep and what to throw away.

read: Cache
from the primer — step 1: outline use cases and constraints

Gather requirements and scope the problem. Ask questions to clarify use cases and constraints. Discuss assumptions.

Without an interviewer to address clarifying questions, we'll define some use cases and constraints.

Use cases

We'll scope the problem to handle only the following use cases

  • User sends a search request resulting in a cache hit
  • User sends a search request resulting in a cache miss
  • Service has high availability

Constraints and assumptions

State assumptions

  • Traffic is not evenly distributed
    • Popular queries should almost always be in the cache
    • Need to determine how to expire/refresh
  • Serving from cache requires fast lookups
  • Low latency between machines
  • Limited memory in cache
    • Need to determine what to keep/remove
    • Need to cache millions of queries
  • 10 million users
  • 10 billion queries per month

Calculate usage

Clarify with your interviewer if you should run back-of-the-envelope usage calculations.

  • Cache stores ordered list of key: query, value: results
    • query - 50 bytes
    • title - 20 bytes
    • snippet - 200 bytes
    • Total: 270 bytes
  • 2.7 TB of cache data per month if all 10 billion queries are unique and all are stored
    • 270 bytes per search * 10 billion searches per month
    • Assumptions state limited memory, need to determine how to expire contents
  • 4,000 requests per second

Handy conversion guide:

  • 2.5 million seconds per month
  • 1 request per second = 2.5 million requests per month
  • 40 requests per second = 100 million requests per month
  • 400 requests per second = 1 billion requests per month
sourcedonnemartin/system-design-primer / solutions/system_design/query_cache/README.mdsyncedsynced from donnemartin/system-design-primer@master · 2026-08-16
full solution in the primer ↗