Putting caching to work on real systems

1 Our caching toolkit — a quick recap

A cache is a small, fast store that keeps copies of data so we don't have to re-fetch or re-compute it from a slow source (like a database) every time. We've spent two sessions on the details; here we line up the tools we'll reach for today so the case studies read smoothly.

Tool 1 — Eviction (from Session 3)

A cache has limited memory, so when it fills up it must evict (kick out) something to make room. The rule it uses is an eviction policy:

Tool 2 — Write & invalidation strategies (from Session 4)

The second half of caching is keeping the cache honest when the underlying data changes. If we update the database but the cache still serves the old copy, we've served stale data. The strategies:

And to fight staleness directly, we invalidate — explicitly delete or refresh a cache entry when its source changes — or we lean on TTL to let entries expire on their own. We also met the classic dangers: the thundering herd (many requests stampede the DB the moment a hot key expires) and the hot key problem (one key so popular it overloads a single cache node). Remember the consistency mapping: write-through → immediate consistency; TTL / write-around → eventual consistency.

2 Do we always want a cache? & the 5-step design process

Do we always want to cache? Not always.

A cache is not a free win you sprinkle on everything. It is a deliberate design decision with real trade-offs. Let's be honest about both sides.

The 5-step process for designing a cache

Whenever a system-design question calls for a cache, walk these five steps in order. Every case study below is just this checklist applied.

1. Establish the need for caching. Don't cache reflexively — show why the slow path hurts.
2. Determine the type of cache. Local (lives on each app server) vs Global (a separate shared cache tier). If global, then also decide Single vs Distributed. (Single/Distributed is only a question for global caches — a local cache is automatically "distributed" across your app servers.)
3. Identify the eviction algorithm. Just use LRU.
4. Identify the invalidation algorithm, based on (a) your consistency requirements and (b) the complexity of the data/query.
5. Think about the load balancer — consistent hashing vs round robin.

3 Case study: the Scaler Code Judge

The Code Judge is a service that "judges" your code submission. When you submit a solution for a DSA problem on Scaler, it takes your code and runs it through hundreds of test cases to decide whether it's correct. Let's design its cache with the 5-step process.

Step 1 — Establish the need

What does the app server need to evaluate a submission?

• User info — auth, whether they've already solved this, whether they're part of the course, …
• Problem info — topic, total score, memory limit, time limit, number of test cases, …
• The code submission made by the user
• Test case data — the input file and the expected output file

How large can this data be?

100 testcases × (10^6 integers / testcase) × (8 bytes / integer)
  = 100 × 10^6 × 8 bytes
  = 800 MB
  ≈ 1 GB        (for the input file; the output file is similar)

Scaler has ~3,000 problems
  3000 problems × (1 GB testcase data / problem)
  = 3 TB of testcase data in S3

How many problems are solved on a given day? Around 100–200 different problems — we run multiple batches in parallel, each solving the current (or last) class's problems, and the batches overlap in timeline.

The need: do we want to transfer 1 GB of test-case data over the network for every submission request? Absolutely not. Hence — we need a cache.

Step 2 — Type of cache: Local vs Global

Local cache wins. Each app server caches some test cases on its own local HDD:

• The request comes to the app server.
• It hits SQL to fetch user/problem info (small data).
• If the problem's test cases are already on this server's HDD, use them — no network overhead.
• If not cached, download from S3, save locally on the HDD, then use them.
• Any subsequent request for the same problem now reads from the HDD.

POST /evaluate-submission

fn check_solution(request):
    pid = request.solution.problem_id
    uid = request.auth_token.uid
    user_info, problem_info = fetch_from_SQL(user_id, pid)

    if not file_exists(`{pid}_in.txt`):          // caching logic
        download_from_s3(url='s3.hld-bucket-com/testcases/{pid}_in.txt',
                         save_to='/users/scaler/testcases/{pid}_in.txt')
        download_from_s3(url='s3.hld-bucket-com/testcases/{pid}_out.txt',
                         save_to='/users/scaler/testcases/{pid}_out.txt')
        // saves the files on the local HDD

    // these reads are from the local HDD
    inputs = read_file(`/users/scaler/testcases/{pid}_in.txt`)
    expected_outputs = read_file(`/users/scaler/testcases/{pid}_out.txt`)

    return evaluate(solution.code, inputs, expected_outputs)

Single vs Distributed?

N/A — single vs distributed only applies to global caches. A local cache is automatically "distributed," because there are multiple app servers each holding their own slice.

Step 4 — Invalidation algorithm

(We'll cover eviction in Step 3 below; invalidation is the meaty part here.) Invalidation is only relevant when the data changes. So: can test cases change?

• Adding a new problem is not a data update.
• But test-case data for an existing problem can absolutely be updated — our problem setters aren't gods. The editorial solution might have been wrong (fix the solution + the expected output), or the test cases weren't "tight enough" (e.g. the problem needed O(n log n) but the tests let O(n²) pass), so we fix both the input and expected-output files.

How often? Extremely rarely — say one update per problem per year on average. So can we just ignore this edge case?

What consistency do we need?

Imagine that mid-contest we realise some test cases are wrong. The problem setters create new test cases, upload them to S3, and we announce to all participants: "test cases for P3 are updated — please resubmit."

So we need immediate consistency, which points straight at write-through. But let's explore the other options first — just for learning.

Why TTL fails here

With TTL, each downloaded file gets an expiry. If a request comes before expiry, use the cached copy; otherwise delete it and re-fetch from S3.

fn check_solution(solution):
    pid = solution['problem_id']
    user_info, problem_info = fetch_from_rds(pid)

    if file_exists(`{pid}_in.txt`):
         if read_last_updated_at(`{pid}_in.txt`) < now() - (1 hour):
              // downloaded more than 1 hour ago — stale!
              delete_file(`{pid}_in.txt`)     // TTL invalidation

    if not file_exists(`{pid}_in.txt`):          // caching logic
        download_from_s3([`{pid}_in.txt`, `{pid}_out.txt`])
        // saves on the local HDD

    inputs = read_file(`{pid}_in.txt`)           // reads from local HDD
    expected_outputs = read_file(`{pid}_out.txt`)

    return evaluate(solution.code, inputs, expected_outputs)

What's the ideal TTL? Walk the options:

• 1 week / 1 day / 10 hours — by the time the TTL expires the contest is over; the updated test cases never took effect.
• 1 hour / 10 min / 1 min — for the few minutes after the announcement the old test cases are still in use. Bad user experience.
• 10 s / 1 s — every minute the TTL expires and each app server re-downloads 5–10 GB from S3. With 1,000 code-judge app servers that's 5 TB of data transfer per minute. The miss rate is too high — it defeats the entire purpose of caching.

Surely there's a sweet spot? No — there is absolutely no sweet spot. Every value is a bad experience in some way.

Why write-around and write-back also fail

• Write-around: same problem as TTL — you'd have to decide how often the CRON job runs, and again there's no ideal value.
• Write-back: stupid here — it leads to data loss, and with a local cache you'd have to write to all 1,000 app servers on every write.

Write-through… but cleverly (versioned filenames)

Can we update 1 GB files across hundreds of app servers + S3 atomically? Absolutely not. Maintaining atomicity across 2 servers is already insanely hard and slow; across 100s it's impossible — at least one will fail and you'd have to roll back the other 99, and you'd be limited by the slowest server (brutally slow writes). So we do something smarter:

• Version the test-case files by putting a timestamp in the filename: p1_input.txt ⇒ p1_input_2025-03-16_08:00.txt.
• The normal cache works as before, with one change: when a request arrives, the SQL DB (queried for user + problem info anyway) also returns the current input/output filenames for this problem. If those files are on the HDD, use them; if not, fetch from S3 and use them.
• For invalidation, the problem setter uploads the new files (new timestamp) to S3, then updates the filename in the SQL DB. These two writes don't have to be atomic — upload to S3 first, and only if that succeeds update the filename in SQL. (If the new file is in S3 but SQL isn't updated yet, no harm — the new file simply isn't used yet.)
• Any request after the SQL entry is updated gets the new filename, the app server sees it lacks those files on its HDD, fetches them from S3, and uses them. Immediate consistency, achieved.

fn check_solution(request):
    pid = request.solution.problem_id
    uid = request.uid
    user_info, problem_info = fetch_from_rds(uid, pid)

    input_file_name  = problem_info.input_file_name    // version comes from SQL
    output_file_name = problem_info.output_file_name

    if not file_exists(input_file_name):               // caching logic
        download_from_s3([input_file_name, output_file_name])
        // saves on the local HDD

    inputs           = read_file(input_file_name)      // reads from local HDD
    expected_outputs = read_file(output_file_name)

    return evaluate(solution.code, inputs, expected_outputs)

Step 3 — Eviction algorithm

LRU eviction, on each app server. The operating system already maintains read/write timestamps for every file, so we just use those: find all files in the folder, and when we're out of space, delete the least-recently-used one.

fn check_solution(solution):
    pid = solution['problem_id']
    user_info, problem_info = fetch_from_rds(pid)

    file_name = problem_info['file_name']    // version from the SQL DB

    if not file_exists(`{file_name}_in.txt`):              // caching logic
        if get_folder_size('.') > 100GB:
             delete(get_oldest_accessed_at_file('.'))     // LRU eviction
        download_from_s3([`{file_name}_in.txt`, `{file_name}_out.txt`])
        // saves on the local HDD

    inputs           = read_file(`{file_name}_in.txt`)    // reads from local HDD
    expected_outputs = read_file(`{file_name}_out.txt`)

    return evaluate(solution.code, inputs, expected_outputs)

Step 5 — Load balancer

Recall the mental model: why do we have more than one server? Here it's because evaluation is heavy compute, not because the working set must be sharded — so round robin is the answer, with each app server acting independently. But let's prove the alternatives are worse.

Why we can't just multi-thread the code judge

Normally you handle concurrent requests with multi-threading. Is that a good idea here? No — we cannot multi-thread the code judge, because code evaluation is a CPU-bound task.

In the code judge, evaluating a single request takes ~5 seconds, during which the app server is fully occupied and can't take another request. Therefore we want each request to go to the next available server — which is exactly round robin routing.

4 Case study: the Scaler Contest Leaderboard

The leaderboard is a paginated rank list. For each rank it shows the user's details and, for each contest problem, the problem details plus the user's score and submission details. Users ask two things: "show me page 23" and "show me my rank." Let's run the 5-step process.

The situation & the numbers

A 3-hour contest, 100,000 participants, 5 problems.

Total submissions
  = 1 submission / (participant × problem) × 5 problems × 100,000 participants
  = 500,000 submissions during the entire contest

Average submissions per second
  = 500,000 / 3 hours
  = 500,000 / (3 × 3600 s)
  = 500,000 / 10,000 s
  = 50 submissions / second

Peak load (start & end of contest run hotter)
  = 2× average
  = 100 submissions / second

Those 100 submissions/sec are evaluated by the code judge (previous case study). For each one, the code judge writes the final verdict/score to SQL. From that collective data we must compute and show the leaderboard.

Step 1 — Establish the need

How do we compute the rank list?

We gather, by joining ~10 tables:

• What contest is running (contests table)
• Which users participate (join of users, contests, contest_participants)
• Which problems are in the contest (join of problems, contests, contest_problems)
• What submissions users made (join of users, user_submissions, problems, contest_problems)

Then we GROUP BY user_id, compute each user's final score (from individual submission scores, number of incorrect attempts, time taken, …), and sort by final score. The sorted list is our rank list.

How much data, and how slow?

500,000 submissions, each ~100 bytes (problem id, score, time taken, verdict, user id, contest id, …)
  total = 100 bytes × 500,000 = 50 MB

50 MB isn't "large" as storage, but it's a lot to pull in a single query — and we're joining 10s of tables. Even with indexes, that fetch takes 1–2 seconds. Since this is heavy compute, say it takes ~5 seconds to fetch + compute the rank list once.

Requests / second
  = (20 views / user / 3 hours) × 100,000 users
  = 2,000,000 views / 3 hours
  = 2,000,000 / 10,000 s
  = 200 views / second

Step 2 — Type of cache

Local vs Global

What does a result look like? A simple JSON page:

[
    {rank: 1, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] },
    {rank: 2, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] },
    {rank: 3, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] },
    {rank: 4, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] }
]

How large is one page? (100 bytes / entry) × (10 entries / page) = 1 KB / page. Since each request only needs to fetch ~1 KB, we can happily use a global cache (unlike the code judge, where each request needed 1 GB).

Single vs Distributed

Total rank-list data
  = (100 bytes / entry) × 100,000 users
  = 10 MB        ← tiny!

10 MB fits on a single cache server. 200 queries/sec is nothing — a single Redis server can handle up to 100,000 read requests/sec. The per-request network transfer is just 1 KB (≈ 200 Kbps of bandwidth total). So the ideal here is a single global cache server (e.g. Redis).

Step 4 — Invalidation algorithm

What consistency do we need?

Immediate consistency is always nice to have, but is it critical here? When a user submits, their "true" rank changes. Eventual consistency would mean the leaderboard shows old ranks for some time (say 10 min) even though the true ranks moved. Is that the end of the world? No. It won't cause a bad user experience. So eventual consistency is good enough.

How long is "eventual"?

How much delay can we afford — 10 hours? 1 hour? 10 min? 1 min? 10 s? 100 ms? In practice, Scaler invalidates the rank list every 30 minutes, and nobody has ever complained.

Both TTL and write-around give eventual consistency. Which to use?

What exactly does Redis store? (the schema)

Two query types: "show me page 23" and "show me my rank." So we store the data twice — keyed by page and keyed by user:

contest:3:page:1  →  "[
    {rank: 1, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] },
    {rank: 2, user_id: ..., user_name: ..., problems: [{1: ...}, {...}, ...] },
    ... 10 entries
]"

contest:3:user:377  →  {rank: 1, user_id: 377, user_name: ..., problems: [...] }

Total data in Redis = 10 MB (pages) + 10 MB (per-user) = 20 MB — each user's entry is stored twice. Serving a request for user 1234 on page 23:

pageEntries = redisClient.get("contest:3:page:23")
myRank      = redisClient.get("contest:3:user:1234")
return MakeLeaderboardTable(pageEntries, myRank)

contest:3:institution:IIT-B  →  {institute_name: ..., users: [{rank: 1, user_id, ...}, {...}, ...]}

Step 3 — Eviction algorithm

20 MB of data per contest — no eviction needed. We store this for every live contest. How many run in parallel at once? Max ~10 (usually 1–2). That's ~200 MB total — still no eviction.

Once a contest ends the rank list can't change (no new submissions), so we just dump it into the SQL DB and stop caching it (post-contest views drop and nothing needs recomputing). Eviction rule: once the contest ends (after ~24 hours), dump the leaderboard data into SQL.

Step 5 — Load balancer (for the cache)

There's no LB for the cache — it's a single Redis server. And if it crashes, there's no data loss, because the cache holds no "real" data. We just restart it; the CRON job runs automatically after 10 minutes (or we force it to run once the cache is back up).

5 Deep dive: Redis & naming technologies in interviews

What is Redis?

Redis is by far the most popular solution for caches (and key-value databases). It is a very fast, in-memory, key-value database.

• Fast because: it's written in C; it's single-threaded (uses async-IO instead of threads — threads need locks, which are extremely slow, and threads have high overhead because context switching is slow); and it has lots of low-level optimizations.
• In-memory: uses RAM; by default stores nothing on disk. RAM is ~100,000× faster than disk for random access. (Optional, off by default: disk persistence — which reduces write speed.)
• Key-value: no complex joins, no indexes, no complex queries, no search. Think of it as a hashmap in memory.
• Powerful primitives: complex datatypes (sorted sets, bloom filters, custom types) and powerful atomic operations (e.g. increment).
• Database: technically a database, but mostly used as a global cache (single or distributed).

So what should you actually say? Something like: "We'll use a single global cache server here — a fast, in-memory key-value cache, something like Redis or Memcached or similar." And if pushed to "choose one / how would you choose":

• "I've worked with Redis before, so I might prefer that."
• "But I'd check what other teams/projects use — if my team already uses X extensively, I'd use X to benefit from their expertise and existing infra."
• "I'd weigh cost (maybe Memcached is ~2× cheaper than Redis), the load each can handle, and the features each offers."
• "I'd research before choosing one."

Bonus: a leaderboard with Redis sorted sets

Beyond the CRON/write-around design above, Redis's sorted set (type ZSET) is a classic alternative for "always-sorted" rankings — it keeps members ordered by a numeric score with O(log N) inserts and rank lookups. The commands all start with Z:

# Add or update a player's score
ZADD leaderboard 980 user:42
ZINCRBY leaderboard 20 user:42       # bump user 42 by 20

# Top 10, highest first, with scores
ZREVRANGE leaderboard 0 9 WITHSCORES

# What is user 42's rank? (0-based; REV = highest is rank 0)
ZREVRANK leaderboard user:42

# One player's score
ZSCORE leaderboard user:42

# Page 2 (ranks 11-20)
ZREVRANGE leaderboard 10 19 WITHSCORES

This turns "give me the top N" and "what's my rank?" into single O(log N) commands instead of an O(N) DB scan — handy when you want immediate updates rather than a 30-minute CRON recompute.

6 Case study: the Social Media Newsfeed

A newsfeed (Twitter/X timeline, Instagram feed) shows a user the recent posts of everyone they follow, newest first. The central design question is when do we assemble each user's feed — at the moment a post is created, or at the moment a user opens the app? These are the two fan-out strategies.

Fan-out on write (push model)

Fan-out on write means: the instant a user posts, we push a copy of that post into the precomputed feed (a cached timeline) of every follower. When a follower opens the app, their feed is already built — just read it.

• Reads are blazing fast — the feed is precomputed and cached, so opening the app is one cheap lookup. This matters because reads vastly outnumber writes (people scroll far more than they post).
• Writes are expensive — one post triggers many cache writes (one per follower).

Fan-out on read (pull model)

Fan-out on read means: do nothing special when posting. When a user opens the app, pull the latest posts from everyone they follow and merge them on the fly.

• Writes are cheap — a post is saved once, full stop.
• Reads are expensive — every feed open must gather and merge posts from possibly hundreds of followees, every time.

The celebrity / hot-key problem

The reverse is also bad: if we used pure fan-out on read for everyone, every single feed-open would have to pull from the celebrity (and everyone else) live — slow reads for the entire platform. Neither pure strategy wins alone.

The hybrid approach (what real systems do)

Production systems (this is famously roughly how Twitter's timeline works) combine both:

• Normal users → fan-out on write. A user with a few hundred followers can afford to push their post into all those cached feeds cheaply.
• Celebrities / hot accounts → fan-out on read. We do not push their posts. We mark them as "celebrity" once their follower count crosses a threshold.
• At read time, merge. When you open the app, you read your precomputed feed (full of normal-user posts pushed to you) and pull-in the recent posts of the few celebrities you follow, merging them by time.

This gives us the best of both: cheap reads for the common case (no 50-million-write storms when a celebrity posts), and fast feeds because only a handful of celebrity pulls are merged in at read time, not hundreds of ordinary followees.

# Fan-out on write: a normal user "alice" posts (id 9001)
for follower in followers(alice):          # skip if alice is a celebrity
    LPUSH feed:{follower} 9001             # prepend the new post id
    LTRIM feed:{follower} 0 799            # cap the cached feed at 800

# Read time: build Bob's timeline (hybrid merge)
ids   = LRANGE feed:bob 0 49              # precomputed page (normal followees)
celeb = recent_posts_of(celebrities_followed_by(bob))   # pulled live
feed  = merge_by_time(ids, celeb)[:50]   # combine & sort newest-first

★ Putting it all together

Three very different products, one toolkit and one 5-step process. Here's the one-paragraph story tying them together:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original class notes / handout (Google Doc) — open the shared class material for this session.
• Class handout: "[SST-2028] Caching Case Studies".

Redis — mandatory reading (everyone)

• Try Redis online (onecompiler.com/redis) — run Redis commands in the browser.
• Redis quick start.
• Redis cheatsheet.

Redis — optional (mandatory for SDE-2+)

• Redis University tutorial.
• Redis docs.
• Eviction policies & Cluster mode (Google Doc).

Papers, docs & deep dives

• Redis Sorted Sets documentation — the data structure for an always-sorted leaderboard (ranked, range queries by score).
• System Design Primer — Facebook newsfeed / fan-out — push vs pull fan-out patterns behind the social media newsfeed.
• Kafka: a Distributed Messaging System for Log Processing (original paper) — the log/queue model underpinning newsfeed fan-out pipelines.
• Redis key eviction policies (LRU/LFU) — how the caching layer decides what to drop, tying back to the toolkit recap.