The primer’s use cases and estimates (4,000 requests per second, 2.7 TB a month if nothing were evicted), the LRU cache, Memcached versus Redis, and pipelining.
What you will learn
State the query cache's use cases and assumptions as the primer does.
Estimate its entry size, monthly volume and request rate.
Build an LRU cache from a hash table and a linked list, and choose between Memcached and Redis.
The problem
The primer's version of this question is Design a key-valuecache 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.
270 B×10×109=2.7 TB per month
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.
10×400=4,000 requests per second
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., 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)what its symbols mean, 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 memorycaches. 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, lists, sets, sorted sets, Redis hashes 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". Send commands in batches (the documentation suggests about 10,000) and read each batch's replies, so the server does not have to keep unbounded replies in memory.
Users1× instanceWeb server (reverseproxy)2× instancesQuery API5× instancesMemory cache2× instancesReverse Index Service2× instancesDocument Service2× instancesUsers1× instanceWeb server (reverseproxy)2× instancesQuery API5× instancesMemory cache2× instancesReverse Index Service2× instancesDocument Service2× instances
Figure 1
The primer’s query cache: the Query API answers from the memory cache, and on a miss from the Reverse Index Service and the Document Service.
Follow one search. The web server passes it to the Query API, which parses and normalizes the query and looks it up in the memory cache. On a hit the cache returns the results and moves the entry to the front of its LRU list. On a miss the Query API asks the Reverse Index Service for the matching documents and the Document Service for their titles and snippets, then stores the results in the cache. The Query API is counted at the lab’s 1,000 requests a second a server for the primer’s 4,000 a second, plus one spare, and the cache at 12,000 a second a node, plus one spare. Only misses reach the two services, and the primer gives no hit ratio, so each is drawn with one server and a spare.
Users: 1 × Users
Web server (reverse proxy): 2 × Load balancer
Query API: 5 × App server
Memory cache: 2 × Cache
Reverse Index Service: 2 × App server
Document Service: 2 × App server
Users sends requests to Web server (reverse proxy)
Web server (reverse proxy) sends requests to Query API
Query API sends requests to Memory cache
Query API sends requests to Reverse Index Service
Query API sends requests to Document Service
Key takeaways
At 270 bytes an entry, 10 billion queries a month would be 2.7 TB if all were kept, so the cache must evict and expire; 10 billion a month is about 4,000 a second.
Normalize queries first, so equivalent queries share one entry; read cache-aside, and expire entries with a TTL.
A hash table finds an entry in O(1)what its symbols mean and a doubly linked list keeps recency order, so the least recently used entry is always at the tail.
Memcached stores bytes in slab classes; Redis stores typed values on a mostly single-threaded core; pipelining hides round-trip time.