The problem: reads
A large chat app starts using Snip for every link its users share, and traffic grows a hundredfold. From the estimate in 01.05 Back-of-the-envelope estimation, that's about 350 new links and 35,000 redirects a second on average, and around 100,000 redirects a second at peak.
Adding app servers is easy now: they're stateless. But every redirect still asks the one database the same question, "where does this code go?", and the graphs show the primary at 90% CPU at peak, almost all of it from those lookups. Writes are fine. Reads are the problem.
There are two standard ways to take reads off a database. Most systems end up using both.
Fix 1: read replicas
A read replica is a copy of the database that receives every change from the primary and applies it. The app sends writes to the primary and reads to the replicas. Since replicas only serve reads, you can add more of them as read traffic grows. (The standby from 02.02 Split the database; scale up or out is built the same way; it just doesn't take traffic.)
The catch is that copying takes time. The primary commits a write, then sends it to each replica, which applies it a moment later. That delay is replication lag: usually milliseconds, but it can grow to seconds when a replica is busy. During it, a replica returns old data. For Snip, that breaks a requirement:
6 messages. Use Next and Back to follow them in order.
Text version
- Owner, friend → Snip app: POST /links — The owner creates a link.
- Snip app → Primary: INSERT x7Kp — Writes go to the primary, which saves the new link.
- Snip app → Owner, friend: 201 snip.link/x7Kp (reply) — The owner gets the short link and pastes it into a chat straight away.
- Owner, friend → Snip app: GET /x7Kp — A friend clicks it within a second. Reads go to a replica.
- Snip app → Replica: SELECT x7Kp — The replica hasn't applied the insert yet: it's a few hundred milliseconds behind.
- Replica → Snip app: not found (reply) (fails) — The replica says the code doesn't exist, so the friend sees a 404 for a link that was just created.
- Note over Primary and Replica: a moment later, the replica catches up
Snip promised "a new link works the moment it's created", so it needs a rule for this. The simplest one: if a replica says a code doesn't exist, ask the primary before answering 404. Real codes are almost always found on the replica, so only brand-new links (and mistyped ones) reach the primary. Other systems use "read your own writes": for a few seconds after a user writes, send that user's reads to the primary.
Fix 2: a cache
A cache keeps copies of frequently read data in memory, in a store like Redis or Memcached. Reading memory takes about 100 ns, while a database query costs a network round trip plus index and disk work (01.04 Numbers to know), and the cache can serve far more lookups per machine.
Snip uses the most common pattern, cache-aside: the app checks the cache first, and only on a miss asks the database and saves the answer in the cache.
4 steps. Use Next and Back to follow the request.
Text version
- A redirect for /x7Kp reaches one of the app servers.
- The app asks Redis for x7Kp. With a good hit rate, about 19 in 20 redirects end here, in well under a millisecond.
- On a miss, it reads a replica, then stores the answer in Redis with an expiry time so the next request for x7Kp is a hit.
- Only if the replica has never heard of the code does the app ask the primary, which covers links created in the last moment.
- Load balancer → Snip app
- Snip app → Redis: 1. get
- Snip app → Read replica: 2. on miss
- Snip app → Primary: 3. if not found
What makes a cache work is the hit rate, the share of reads it answers. At 100,000 redirects a second:
| Hit rate | Reads that reach the database |
|---|---|
| 80% | 20,000 a second |
| 95% | 5,000 a second |
| 99% | 1,000 a second |
Snip is close to ideal for caching. Links never change once created (editing is out of scope), so cached answers are never wrong. And clicks are lopsided: a small share of links, the ones shared today, get most of the traffic. If 10 million links are clicked on a busy day, at 500 bytes each that's about 5 GB, which fits in one cache server's memory.
What a cache costs
- Stale data. The cache is a copy; when the original changes, the copy is wrong until it's updated or expires. Snip mostly avoids this because links don't change. When something does change (an owner deletes a link, say), the usual move is to delete the cache entry, not overwrite it, and let the next read fill it from the database. Give every entry an expiry time (a TTL) as a safety net.
- Cold starts. A cache that restarts empty sends every read to the database at once. 06.05 Stampedes and request coalescing covers how to soften that.
- Missing keys. Requests for codes that don't exist always miss. Someone scanning random codes goes straight past the cache. Caching "not found" for a short time helps.
- One more system to size, monitor and keep available.
Which first?
| Read replicas | Cache | |
|---|---|---|
| Best for | Many different queries: dashboards, searches, reports | The same small set of keys read again and again |
| Freshness | Behind by the replication lag | Behind until expiry or deletion |
| App changes | Send reads to a different address | Check cache, fill on miss, delete on change |
| Capacity per machine | A database server's worth | Far more simple lookups per machine |
Snip uses both: Redis for redirects, which are one key lookup repeated endlessly, and a replica for the owners' dashboard and stats queries, which vary too much to cache well.
ChangeAdd a cache for redirects and a read replica
Text version
Change: Add a cache for redirects and a read replica
Added: Redis, Read replica.
New connections: Snip app → Redis (redirects); Snip app → Read replica (reads); Primary → Read replica (copies).
Seen in production
Memcache
Facebook's paper describes memcache as a "demand-filled look-aside cache" in front of MySQL, serving billions of requests per second. On a write, the web server updates the database and then deletes the cache entry rather than updating it, because deletes are safe to repeat. For keys prone to stampedes, a mechanism they call leases cut the peak database query rate from 17,000 to 1,300 a second.
What we foundThe same cache-aside pattern, with delete-on-write, scaled to billions of requests a second.
Scaling Memcache at Facebook (NSDI 2013)usenix.org ↗Snip serves 100,000 redirects a second at peak and the cache hit rate drops from 99% to 95% after a deploy. What happens to the reads reaching the database?
Recap
Interview questions
Your database is overloaded with reads. What are your options, and how do you choose?
What is replication lag, and how can it cause bugs?