Caching in system design series: 1. Multi-level cache and counters · 2. Rate limiting
The posts on cache-aside and cache incidents cover one cache tier in front of a database. This post looks at the system level: which tiers caches live in, how much one Redis can take, and two counter case studies that come up a lot in interviews.
1. Where caches live
Key idea: each tier caches a different kind of data and is invalidated differently. Pick the tier by asking “how stale can this data be, and who is allowed to see it?”
| Tier | What it caches | How it’s refreshed | Notes |
|---|---|---|---|
| Client (browser, app) | Responses, images, static files | Cache-Control, ETag |
The server can’t delete it, only wait for it to expire |
| CDN | HTML/JS/CSS, images, video | TTL, purge via API, hashed file names | Close to users, cuts origin bandwidth |
| Reverse proxy (Nginx) | Static files, public GET responses | TTL, proxy_cache_bypass |
Absorbs requests before the app |
| Local cache in the service | Config, catalogs, small hot data | Short TTL, invalidation events | Fastest (ns), one copy per instance |
| Remote cache (Redis) | Query results, computed results, shared data | Cache-aside, TTL | Shared by all instances, costs ~0.5 ms of network |
| Database | Buffer pool, page cache | Self-managed | MySQL 8.0 removed the query cache |
Two common tricks:
- File names with a content hash (
app.3f9a1c.js) + a 1-year TTL: you never need to purge the CDN; new content means a new name. - Local + remote (near cache): Caffeine in the JVM with a TTL of a few seconds in front of Redis, for extremely hot keys. The cost: each instance can be a few seconds stale.
2. Three jobs and their cost
Key idea: a cache isn’t only for fast reads. It also works as a buffer and as a place to share data, and each role has its own risks.
- Speeding up: read from RAM instead of disk and recomputation.
- Buffering: a place to hold data temporarily before passing it to another component, for example collecting counter increments and writing them to the DB in batches. A buffer is not a cache: data in a buffer doesn’t exist anywhere else yet, so if you lose it, it’s really gone. A message queue is a durable buffer.
- Sharing data: instances share sessions, results or replies. For example, request-reply over Kafka uses Redis as a “reply pool” so whichever instance receives the reply can hand it to the instance that’s waiting; the full analysis is in the request-reply over Kafka case study.
The shared costs: data inconsistent with the source, RAM, and network bandwidth (big values). Redis in particular: one thread processes commands, so a slow command (KEYS, values of several MB) blocks every client; Pub/Sub with a huge number of channels makes UNSUBSCRIBE CPU-heavy.
3. How much one Redis can take
Key idea: use the numbers below to work out node counts in an interview, and remember the real limit is usually single-threaded CPU and value size, not RAM.
| Metric (one instance, ordinary hardware) | Reference value |
|---|---|
SET |
~50,000 commands/s |
GET |
~80,000 commands/s |
| Number of keys | ~250 million in practice (2³² ≈ 4.3 billion in theory) |
| Recommended RAM | ≤ 32 GB (fork during snapshots, startup time and replica sync) |
| Connections | maxclients defaults to 10,000, bounded by file descriptors |
Pipelining (sending many commands in one go) pushes throughput to a few hundred thousand commands/s. Measure with redis-benchmark or k6 using real payloads. Redis Cluster splits keys into 16,384 slots across several masters; details in Redis persistence, replication and Cluster.
4. Case study: counters for a social network
Key idea: counting likes/comments/shares/views on posts and followers of users at 1 million QPS: keep the counters in Redis, keep the source of truth for “who liked what” in the DB, and sync asynchronously.
Requirements. Functional: like, comment, share and view counts for posts; post, follower and following counts for users. Non-functional: accurate (no double counting), fast, highly available, not lost on restart. Scale: 1 billion users, 200 million DAU, 1 million QPS.
Estimates. Assume the 1M QPS is ~900K counter reads (each post on the feed shows 4 numbers) and ~100K writes (mostly views, fewer likes). Posts whose counters must stay hot: say 500 million posts from the last 30 days × 4 counters.
The simple design: one post_count table. A SELECT by post_id is fine, but UPDATE post_count SET like_count = like_count + 1 WHERE post_id = ? when a viral post gets 10,000 likes/s means 10,000 transactions fighting over one row: row locks queue up behind each other, and a node manages only a few hundred TPS of this kind. Two patches:
- Batching: accumulate in memory, then
UPDATE ... + 37every second. Fewer writes, but a service now holds state, and a crash loses what wasn’t written. - A queue in front of the DB: likes go into Kafka, and a consumer batches and writes. More durable, but the displayed number lags by a few seconds.
A better answer: Redis as the counter.
- Accurate:
HINCRBY post:{id} like 1is one atomic command, no race. - Fast: reads and writes in RAM; Cluster to spread 1M QPS (~15–20 masters at 50–80K commands/s, plus replicas for reads).
- Saves RAM: use small hashes instead of a separate key per counter. Hashes with few fields are stored as a very compact listpack; grouping 1,000 posts into one hash (
cnt:{post_id / 1000}with field{post_id}:like) cuts the per-key overhead. - Large data: old posts few people view go to a cold tier: Redis Enterprise auto-tiering (RAM + SSD) or Pika (Redis-protocol compatible, stores on disk with RocksDB), or keep them only in the DB and reload on demand.
flowchart LR
U[User like] --> API[Like service]
API -->|INSERT ... ON CONFLICT DO NOTHING| DB[(post_like)]
API -->|if a new row was inserted: HINCRBY| R[(Redis counters)]
R -->|job every 5 s, batched| DB2[(post_count)]
F[Feed service] -->|HMGET| R
Durability, hot keys and reconciliation
- Durability: Redis with AOF
everysec(loses at most ~1 s on a crash). A periodic job reads counters that changed (posts marked “dirty” in a SET) and writes them topost_countin batches; if Redis loses data, reload frompost_countand recount frompost_likefor hot posts. - Hot keys: one viral post makes one slot hot. Split the counter into N sub-keys (
post:{id}:like#0..#15), pick one at random on each write, and sum the N keys on read (or cache the total locally for a few seconds). Or batch increments in service memory for 100 ms before callingHINCRBY. - Reconciliation: a nightly job compares
count(*)frompost_likewith the counter for a sample of posts and fixes any drift. - Followers: same model; a unique
follow(follower_id, followee_id)table is the source of truth, and the counter lives in Redis.
5. Case study: unread broadcast notification counts
Key idea: when a notification goes to everyone, don’t increment 10 million counters; each user only stores “which notification I’ve read up to”, and the unread count is computed when needed.
Requirements. Show the number of unread broadcast notifications (promotions, system announcements); computed on the server, not the frontend. Accurate, low latency. 10 million users.
- Option 1, a counter for every user: each broadcast does
INCR unread:{user}for 10 million users. That’s 10 million commands; at ~50K commands/s it takes ~200 s per broadcast (or a few seconds with pipelining and many nodes), and most users never even open the app. - Option 2, a pointer per user: broadcasts have increasing IDs (stored in a ZSET or a
broadcasttable). Each user storeslast_read_id. Unread count = the number of broadcasts withid > last_read_id(ZCOUNT broadcasts (last_read +inf), or simplylatest_id − last_read_idif the IDs are contiguous. When the user reads them all, move the pointer. The client fetches this number when the app opens or polls it periodically.
Option 2 costs one number per user and O(log n) per read. The only catch: targeted broadcasts (sent only to VIP users) need filtering by group, for example one broadcast ZSET per segment.
6. Five small problems solved with Redis
Key idea: many “fast, low-memory” requirements have a tailor-made Redis data structure; spotting the right one is half the answer.
| Problem | Structure | Key idea |
|---|---|---|
| Read-compute-write races between many clients | Lua script (or WATCH/MULTI) |
Lua runs atomically, simpler and faster than WATCH optimistic locking |
| Scheduling a job (cancel an order after 15 minutes) | ZSET, score = run time | A worker runs ZRANGEBYSCORE to fetch due jobs; see the ride auto-cancel case study |
| Counting unique visitor IPs per day, error < 5% | HyperLogLog | 12 KB per counter regardless of element count, 0.81% standard error |
| Tagging books by genre, finding books that are both “Fiction” and “Adventure” | Bitmap | One bitmap per genre indexed by book_id; intersect with BITOP AND |
| A public “is this username taken?” API, without probing traffic hammering the DB | Bloom filter | “Not present” is certain; “present” may be slightly wrong, and only then ask the DB |
Exercises
Exercise 1: Sizing Redis for counters
Task: 500 million hot posts, 4 counters each (like, comment, share, view). How much RAM if each counter is its own string key? What if you group them in hashes of 1,000 posts? How many nodes if each node uses 25 GB?
Solution to Exercise 1
- Separate keys: each small string key costs ~70–90 bytes (dictEntry, the key’s SDS, robj, allocator overhead). 2 billion keys × ~80 B ≈ 160 GB, plus ~1.3× fragmentation ≈ 210 GB → 9 nodes of 25 GB. It’s also past the practical “250 million keys per instance”, so you need ≥ 8 nodes just for the key count.
- Hashes of 1,000 posts (field
{post_id}:{type}, 4,000 fields/hash): that exceeds the default listpack threshold (hash-max-listpack-entries 128), so group smaller: 32 posts/hash = 128 fields. Each listpack field is ~15–20 bytes → 2 billion × ~18 B ≈ 36 GB, plus hash key overhead (15.6 million keys × ~100 B ≈ 1.6 GB) ≈ 40 GB → 2 nodes, plus replicas. - Conclusion: small hashes save ~5× RAM. The cost: no per-counter TTL (per-field TTL only arrived in Redis 7.4), and readers must know how to compute the hash key.
- Throughput: 1M QPS still needs ~15–20 masters, so the node count is decided by CPU, not RAM. That’s worth saying out loud in an interview.
Remember
- Name the six cache tiers, what each caches and how it’s refreshed.
- Tell a cache from a buffer, and why losing a buffer means really losing data.
- State the limits of one Redis and use them to work out node counts.
- Design an accurate like counter: a unique source of truth in the DB, the counter in Redis, hot-key handling.
- Explain the “read up to here” pointer for broadcast notifications.
Interview questions
Mid
Why not count likes with UPDATE count = count + 1 on the database?
Every like on a post fights for the lock on the same row, so a viral post turns into a lock queue and a node manages only a few hundred updates/s on that row.
Alternatives: increment in Redis (atomic, in RAM) and write to the DB in batches; or batch through a queue and then write. The source of truth for “who liked” stays in the DB with a unique constraint.
How do a cache and a buffer differ?
A cache holds a copy of data that already exists at the source, so if it’s lost you read it again; a buffer holds data that hasn’t reached its destination yet, so if it’s lost it’s really gone.
That’s why a buffer needs durability (a queue, AOF) or an accepted, bounded loss, while a cache only needs a TTL and a refresh strategy.
Can single-threaded Redis have race conditions?
Each single command is atomic, but a sequence of reading on the client, computing, then writing still races between clients.
Put that sequence into a Lua script, or use WATCH/MULTI (retry when the key changes). Lua is usually simpler and faster.
Senior
Design like/view counters for 1 billion users at 1 million QPS.
Likes: a unique post_like table as the source of truth, Redis hashes holding the counters, a batching job writing post_count. Views: only need to be approximate, count in Redis (HLL if you need unique viewers), possibly sampled.
Redis Cluster with ~15–20 masters for 1M QPS, small hashes to save RAM, cold posts on a disk tier. Hot keys: split the counter into sub-keys or batch increments in the service for 100 ms. Durability: AOF everysec + reload from the DB, and nightly reconciliation.
How do you count unread broadcast notifications for 10 million users?
Store a last_read_id pointer per user and count the broadcasts with a larger id, instead of incrementing 10 million counters on every send.
O(1) writes when sending a broadcast, O(log n) reads with ZCOUNT. For segmented broadcasts, keep one ZSET per segment and sum over the user’s segments.
When do you use a local JVM cache instead of Redis?
When the data is small, read extremely often, and can be a few seconds stale: config, catalogs, super-hot keys.
A local cache (Caffeine) reads in ns, costs no network, and survives Redis going down. In exchange, every instance has its own copy, invalidating all of them at once needs pub/sub or a short TTL, and it uses heap (which affects GC). The common combination: a local 5 s TTL in front of Redis.
How do you check whether a username exists on a public API without probing traffic taking down the DB?
A Bloom filter (RedisBloom BF.EXISTS) in front of the DB: answer “not taken” right away when the filter says no; only ask the DB when the filter says “maybe”.
Add per-IP rate limiting. Size: 100 million usernames at a 1% false positive rate needs ~120 MB. A Bloom filter can’t delete elements; if usernames get deleted, use a Cuckoo filter or rebuild it periodically.
Useful phrases for interviews
- “Each cache tier has its own invalidation story.”
- “We never purge the CDN because file names carry a content hash.”
- “A near cache with a five-second TTL absorbs the hottest keys.”
- “A viral post turns its counter into a hot key.”
- “Counters are flushed to the database write-behind every few seconds.”
- “The like table is the source of truth, Redis only holds the count.”
- “Incrementing ten million counters is a fan-out we can avoid.”
- “Each user keeps a read pointer into the broadcast stream.”
- “A Bloom filter has false positives but never false negatives.”
- “HyperLogLog gives a cardinality estimate within one percent.”
Notes based on the System Design course (Ronin Engineer), rewritten in my own words.