Requirements, estimates and the query cache

The problem

The primer's version of this question is Design a key-value cache to save the results of the most recent web server queries. A search service caches the results of popular queries in memory, so that it does not recompute them on every request.

Use cases (from the primer)

• A user sends a search request that results in a cache hit.
• A user sends a search request that results in a cache miss.
• The service has high availability.

Assumptions (from the primer)

• Traffic is uneven: "popular queries should almost always be in the cache".
• Lookups must be fast, with low latency between machines.
• Memory is limited, so the cache must decide what to keep and what to remove, while holding millions of queries.
• 10 million users, 10 billion queries a month.

---

Back-of-the-envelope estimates

Each entry maps a query to its results: query 50 bytes, title 20 bytes, snippet 200 bytes, so 270 bytes.

That is the size if every query were unique and all were kept. Memory is limited, so the cache must evict entries (lesson 2) and expire them.

using the primer's conversion of 400 requests per second ≈ 1 billion a month.

For scale, Facebook's memcache deployment "handles billions of requests per second and holds trillions of items" (Nishtala et al., NSDI 2013).

---

Reads and the LRU cache (from the primer)

The Query API parses the query: it removes markup, splits the text into terms, fixes typos, normalizes capitalization and converts it to boolean operations. Normalizing first means equivalent queries share one cache entry. Then the API checks the memory cache:

• Hit: move the entry to the front of the LRU list and return it.
• Miss: ask the Reverse Index Service and Document Service for the results, store them in the cache at the front of the list, and return them.

This is cache-aside (chapter 6). The cache itself is a hash table plus a doubly linked list: the table finds an entry in $O(1)$, and the list keeps entries in recency order, so the least recently used one is at the tail, ready to evict.

When to update. Cached results go stale when a page changes, is added or removed, or its rank changes. The primer's simplest answer is a TTL, a maximum time an entry may stay before it is refreshed.

---

Memcached or Redis

The primer names both as memory caches. Some differences that affect design:

• Memcached is a simple key-to-bytes store, with set, get and delete as its core operations. It manages memory with slab classes (lesson 2).
• Redis stores typed values (strings, hashes, lists, sets, sorted sets and others) and runs commands on a mostly single-threaded core. Its redis.conf says "Redis is mostly single threaded", with optional threaded I/O for network reads and writes.

Round trips and pipelining

A client that waits for each reply before sending the next command is limited by the round-trip time. Redis's documentation gives the example: with a 250 ms RTT, "even if the server is able to process 100k requests per second, we'll be able to process at max four requests per second". Pipelining sends many commands before reading the replies. It also cuts read() and write() system calls, so throughput "eventually reaches 10 times the baseline obtained without pipelining". Batch replies in groups (the docs suggest about 10,000 commands) so the server does not queue unbounded output.