Design a query cache · Dev Handbook

Define use cases and constraints

Use cases (in scope)

User sends a search request that results in a cache hit.
User sends a search request that results in a cache miss.
Service has high availability.

Constraints and assumptions

Traffic is not evenly distributed; popular queries should almost always hit.
Fast lookups; low latency between machines.
Limited memory: must decide what to keep and what to expire; cache millions of queries.
10 million users, 10 billion queries/month.

Usage

~270 bytes per entry (query 50, title 20, snippet 200).
2.7 TB/month if all 10 billion queries are unique and all are stored.
4,000 requests/second.

Sketch the high-level design

Fig 1A miss joins index results with documents

Inspect one part at a timeQuery

Query
A client reaches the web server and Query API.
Hit
The API can return a result from memory cache.
Miss
Query the reverse index for IDs and the document service for snippets.
Result
Join the data into a result and apply the cache policy.

A cache hit avoids the index/document join.

How to read this model

A query console beside a fast result drawer and document archive. The object is a teaching analogy. Inspecting a part highlights its role; it does not execute or simulate the software. Cabinet trays are records, workpieces are data, and latches are checks. Unless an explanation states a quantity, compartments and sample workpieces do not denote data counts. Part dimensions are not a quantitative scale.

Define the core components

Popular queries are served from a memory cache (Redis/Memcached) to cut read latency and spare the reverse index and document services. Limited capacity → use LRU to expire old entries.

Query API parses the query (remove markup, tokenize, fix typos, normalize).
On a hit: move the entry to the front of the LRU list and return it.
On a miss: query the reverse index and document services, then store the result at the front of the cache.

When to update the cache

Update when page contents change, a page is added/removed, or page rank changes. The simplest approach is a TTL (cache-aside). See cache for the trade-offs.

Scale the design

Fig 2Distribute cache ownership by key

Inspect one part at a timeEntry

Entry
DNS, CDN, a load balancer, and web servers precede the Query API.
Ownership
A consistent hashing rule routes keys across Cache shards 1, 2, and 3.
Miss path
Cache misses query the reverse-index and document-service clusters.
Membership
When nodes change, only the key ranges reassigned by the hashing rule move.

Consistent hashing limits key movement when cache membership changes; it does not prevent every miss.

How to read this model

A routing console beside range-independent cache drawers and an index archive. The object is a teaching analogy. Inspecting a part highlights its role; it does not execute or simulate the software. Cabinet trays are records, workpieces are data, and latches are checks. Unless an explanation states a quantity, compartments and sample workpieces do not denote data counts. Part dimensions are not a quantitative scale.

Scaling the cache cluster

Three options for distributing the cache across machines:

Option	Trade-off
Each machine has its own cache	Simple, low hit rate
Each machine has a full copy	Simple, wastes memory
Shard the cache across machines	More complex, best option

Shard with machine = hash(query), using consistent hashing to minimize data movement on rebalance.

Additional talking points

SQL scaling patterns, NoSQL, caching levels: see database and cache.