QuorumWiki
Play
How-to guides

Design a key-value store for a search engine

Design a query cache in front of a search backend for a system design interview: LRU eviction, TTL, sharding the cache, hot queries, and what Quorum teaches.

A query cache sits between the web servers and the search backend and answers repeat searches from memory. Key it by the normalized query, evict the least recently used entries, and expire each one after a short TTL so results do not go stale for long. When one node cannot hold the hot set, split the keys across several cache nodes by hash.

This is one of the questions in the System Design Primer, and its solution for the query cache is worth reading next to this page.

Requirements#

Functional:

  • A search that was seen recently returns from the cache.

  • A search that was not seen goes to the backend, and the answer is stored.

  • Popular queries stay cached, and rare ones may fall out.

Non-functional:

  • Lookups take about a millisecond, so the cache must live in memory.

  • The service stays up when a cache node dies. Missing the cache is slow, and it must never be an error.

  • Results can be a few minutes old, but a deleted page should not show up for hours.

Estimate the load#

Assume 10 billion searches a month and 2.5 million seconds in a month.

  • Average rate: 10B / 2.5M is 4,000 searches a second. Peak at three times the average is 12,000.

  • Traffic is skewed. Assume 50 million distinct queries draw 90% of searches, and the rest are one-offs.

  • Entry size: the normalized query is about 50 bytes, and a page of ten titles and snippets is about 2 KB. So 50M entries are about 100 GB.

  • Backend load: at a 90% hit rate, the backend sees 10% of 12,000, or 1,200 a second at peak. Raise the hit rate to 95% and it sees 600.

One Redis node holds a few tens of gigabytes comfortably, so 100 GB means four or five nodes. The backend savings matter more than the memory bill.

The design#

Query normalization#

Before any lookup, the Query API lowercases the text, strips markup, trims spaces, and fixes obvious typos. "Cheap Flights NYC" and "cheap flights nyc " should hit the same key. Every query you fold together raises the hit rate for free.

The cache#

The Query API checks a memory store such as Redis or Memcached. A hit returns at once. A miss asks the search backend, writes the result under the key, and returns it. That is cache-aside, and the application owns the logic. If a cache node is down, the call falls through to the backend.

LRU eviction#

Memory is finite, so the cache drops the entry untouched for longest. The classic build is a hash map from key to a node in a doubly linked list. A read moves its node to the head, and an insert at capacity removes the tail. Both operations take constant time. Redis approximates this by sampling a few keys, which is cheaper and close enough.

TTL and invalidation#

Search results change when pages change or ranks shift, and the cache cannot know. Give each entry a TTL of a few minutes. Popular queries refresh often because they expire often, and rare ones barely matter. For urgent removals, such as a takedown, publish a delete for the affected keys.

Sharding the cache#

Hash the query key and send it to one of N nodes. Plain modulo reshuffles almost everything when N changes, so use consistent hashing, which moves only about 1/N of the keys. See sharding for the general case. Put a replica behind each shard if losing a node's keys would swamp the backend.

Where it breaks#

A popular entry expires. Ten thousand requests for the same trending query miss at once and all hit the backend. Let one request rebuild the entry while the others wait or take the stale copy, and add jitter to TTLs. See cache stampede protection.

A cold cache. After a restart or a deploy, the hit rate is zero and the backend takes full load. Warm the cache from the previous day's top queries before sending traffic. See cache warming and tiered caching.

A hot shard. One celebrity query is one key on one node. Replicate hot keys or keep a small local cache in each Query API server. See hot keys and hot shards.

Eviction churn. A crawler walks through millions of unique queries and pushes real hot entries out. Do not cache queries that were seen only once.

Build it in Quorum#

The first board shows the read path. It puts a Cache in front of the Database, and the Cache's default strategy is cache-aside with a TTL and a size. Look at how the Database load drops as the hit ratio rises.

Drag to pan. Hold Ctrl or Cmd and scroll to zoom.

At 1.50k Users the Simulation solves this Design to Apdex 1.00, p99 217 ms, 0.0% errors and $1.28/s Burn.
WhereSettingValueWhy
App ServerInstance sizesmallSmall gives the app two vCPUs, enough to run code while the data tier does its own work.
CacheCache strategyasideThe app fills the Cache on a miss and writes straight to the Database, so the Cache holds only what someone has read.
CacheTTL (seconds)60An entry lives for a minute, which keeps most hot reads as hits and bounds how stale an answer can get.
CacheInstance sizesmallMemory decides how much of the hot set fits. A Cache too small for it misses even on popular rows.
DatabaseInstance sizesmallSmall gives the Database two vCPUs, so the figures below reflect the Cache and not a starved Database.

Research this Design needs: Caching.

The second board turns on two stampede guards on the Cache, and it answers the popular-entry problem. Compare its caption with the unguarded version on Cache stampede protection.

Drag to pan. Hold Ctrl or Cmd and scroll to zoom.

At 4.00k Users the Simulation solves this Design to Apdex 0.96, p99 672 ms, 0.0% errors and $3.36/s Burn.
WhereSettingValueWhy
App ServerInstance sizemediumMedium gives the app four vCPUs, so the app tier is not the limit and the Database is what the guards change.
CacheTTL (seconds)10The same short TTL as before, so the difference below comes from the guards and not from a longer lifetime.
CacheCoalesce missesOnReaders that miss the same key wait on one fetch instead of each querying the Database. It matters most when the Cache is cold.
CacheEarly expirationOnA reader refreshes a key a little before it expires, at random, so keys leave the Cache one at a time and not all at once.
CacheInstance sizesmallMemory decides how much of the hot set fits. A Cache too small for it misses even on popular rows.
DatabaseInstance sizesmallSmall gives the Database two vCPUs, so the figures below reflect the Cache and not a starved Database.

Research this Design needs: Caching, Stampede protection.

The third board is a Database with several shards and a hash key. In the game the shards are Databases, not Cache nodes, but the effect on key spread is the one you would explain for a cache. See Sharding for what the key choice does.

Drag to pan. Hold Ctrl or Cmd and scroll to zoom.

At 3.80k Users the Simulation solves this Design to Apdex 0.97, p99 616 ms, 0.0% errors and $6.40/s Burn.
WhereSettingValueWhy
App ServerInstance sizelargeLarge, so the App Server is not the limit and the shards are.
DatabaseShards4Each shard is another copy of the Database, and writes divide across them.
DatabaseShard keyhashA hash of the user ID sends every user to one shard and spreads users evenly, so no shard runs hot.
DatabaseInstance sizesmallSmall for each shard, so a shard that takes too much of the load shows.

Research this Design needs: Sharding.

The last board puts a Search Engine beside the Database, the closest thing in the game to the backend behind your cache.

Drag to pan. Hold Ctrl or Cmd and scroll to zoom.

At 3.00k Users the Simulation solves this Design to Apdex 1.00, p99 246 ms, 0.0% errors and $3.60/s Burn.
WhereSettingValueWhy
App ServerInstance sizesmallSmall gives the app room to run the query it builds for each search.
DatabaseInstance sizesmallThe Database keeps the rows. Once a Search Engine is linked it stops answering searches.
Search EngineProductelasticsearchElasticsearch takes shards, replicas, and a heap choice when the index grows. Meilisearch is smaller and faster, but its results drift from the query as the index grows.
Search EngineRefresh interval1A new document is searchable within a second, so no search answers from an old index. A longer interval saves indexing CPU and returns staler results.

Research this Design needs: Full-text search, Full-text search.

Research Caching and Stampede protection to unlock the switches. The Cache stampede incident tests the cold-start case, and the Stampede Sandbox lets you run it yourself.

The game has no LRU list, no query normalization, no per-key invalidation, and no consistent-hash ring. A Cache has a size and a hit ratio, not individual entries.

Common questions#

How does an LRU cache work?#

It pairs a hash map with a doubly linked list. A lookup finds the node through the map and moves it to the head of the list, and when the cache is full the tail node is removed. Both steps take constant time.

How do you invalidate a search query cache?#

Mostly you do not. A short TTL of a few minutes lets every entry expire on its own, which is simple and good enough for ranked results. For urgent cases, delete the specific keys when the change is published.

How do you shard a cache across servers?#

Hash the key and map it to a node, preferably with consistent hashing so that adding a node moves only a small share of keys. Clients or a proxy such as Twemproxy do the routing.

What does the System Design Primer say about the query cache?#

The Primer scopes it to cache hits, cache misses, and high availability, with an LRU cache built from a hash table and a linked list. This page covers the same ground and adds the sharding and stampede cases.