AP Exams (Advanced Placement) · System Design
Caching
A fast copy of a CampusClip mapping — hits, write paths, staleness, and where the copy sits after scale-out.
The midterm short code is opened again and again. This topic is the fast copy of that one mapping: when an open hits, when it misses, what a teacher's write must do to the copy, and why an in-process map fails the moment CampusClip has two hosts.
- AP Exams (Advanced Placement)
- Medium level
- 5 concepts
- 1 practice questions
1Why CampusClip caches a mapping
The midterm notice is one short code. Hundreds of students open it. Without a cache, every open asks the store for the same long URL. A cache is a small, fast copy of that mapping sitting closer to CampusClip than the store is. The first open after a miss fills the cache; later opens for the same code can be answered from the copy.
A cache does not make the store optional. It makes repeated reads cheaper. If the mapping is missing from the cache (a miss), CampusClip still loads it from the store. If the teacher changes the long URL, the copy can be wrong until CampusClip invalidates or overwrites it — that is the next concepts.
Figure. Student hits CampusClip. A hit is answered from the cache. A miss (dashed) goes to the store, then the cache is filled.
What a cache is for
- Hot keya3k9 is opened many times; the store would repeat the same lookup.
- CopyKeep code → URL in fast memory beside CampusClip.
- MissIf the copy is absent, load the store, then fill the cache.
Store lookups saved by the cache
The midterm code a3k9 is opened 200 times. The first open is a miss that reads the store and fills the cache; every later open for the same code is a hit. How many store lookups happen with the cache, versus without it, and how many are saved?
- without a cache: one store lookup per open, times 200200 store lookups
- with a cache: 1 miss fills it, the other 199 opens hit1 store lookup
- lookups saved = 200 - 1199
Pro tip. The saving grows with reuse of the same hot key; a code opened only once would save nothing, because that single open is the miss that fills the cache.
The midterm short code is opened 200 times. A cache helps because
- Later opens can reuse one store lookup instead of doing 200
- It replaces the need to store the mapping at all
- It raises host capacity from 20/s to an industry-typical rate
The cache holds a copy of a mapping the store still owns. It does not invent a new capacity number.
2Hit versus miss
A hit means the cache already has the short code. CampusClip returns the stored long URL without asking the store. A miss means the code is absent (never seen, or evicted, or invalidated). CampusClip then loads the store, answers the student, and — on the usual read path — writes the mapping into the cache so the next open can hit.
Hit rate is hits / (hits + misses) on the opens you counted. We will not invent a "typical" hit rate. If 9 of 10 opens for a3k9 hit, the hit rate on that sample is 0.9. A different sample can differ. The store still owns the mapping; a high hit rate only says the copy was useful on those opens.
| Outcome | Cache has the code? | CampusClip does |
|---|---|---|
| Hit | Yes | Reply from the copy; store is not asked |
| Miss | No | Load the store, reply, then fill the cache |
Average open time from a hit rate
On a stated sample of 10 opens of a3k9, 9 hit the cache and 1 misses. A cache hit answers in 1 ms; a miss reads the store and then fills the cache, costing 20 ms. What is the average open time on this sample?
- hit rate on the sample = 9 / (9 + 1)0.9
- average = 0.9 x 1 ms + 0.1 x 20 ms0.9 + 2.0 ms
- average open time2.9 ms
Pro tip. Weight each outcome by its share on a stated sample; a single miss still costs 20 times a hit here, so the miss term dominates even at a 0.9 hit rate. Do not quote 2.9 ms as universal, it is this sample's number.
An open for a3k9 finds nothing in the cache. CampusClip should
- Load the store, answer, and fill the cache
- Answer with a made-up URL so the student is not blocked
- Delete the store row because the cache is the source of truth
A miss is the store's job. Inventing a URL is not a cache policy. The store remains the source of truth on this path.
3Cache write paths
Reads are only half the story. When a teacher pastes a new link, or changes the long URL behind a3k9, CampusClip must decide what the cache and the store each see. Three write paths show up in first-course designs: cache-aside (write the store, then invalidate or update the cache), write-through (write cache and store together), and write-back (write the cache first and flush the store later).
Write-back is fastest on the teacher's paste and can lose an unflushed mapping if the cache node dies. CampusClip's short-code table is a mapping students will follow — losing a paste is the wrong risk. Cache-aside or write-through fits that table. Write-back can wait for something CampusClip can afford to lose, such as a click counter.
How a cache-aside write runs
- Write the storeThe long URL is saved in the source of truth first.
- Fix the cacheInvalidate (or update) the cache entry so the next open is not stale.
- Next readA miss reloads the new mapping; a hit only happens after the cache is filled again.
| Strategy | Write goes to | Strength | Risk |
|---|---|---|---|
| Cache-aside | Store first; cache filled on read miss | Simple; cache holds hot keys | Stale if invalidation is skipped |
| Write-through | Cache and store together | Cache stays coherent with the store | Write latency includes both |
| Write-back | Cache first; store later | Fast writes | Crash can lose unflushed writes |
A teacher changes the long URL behind a3k9. Losing that write on a cache crash is unacceptable. Which strategy fits?
- Cache-aside or write-through — the store is written before or with the cache
- Write-back — acknowledge in cache and flush later
- Never write the store; the cache is enough
The mapping must survive a cache-node crash, so the store is written on the critical path. Write-back is the loss-window path.
4Staleness after a write
Stale means the cache still holds the old long URL after the store has a new one. That happens when CampusClip writes the store and forgets to invalidate the cache, or when two hosts each have their own copy and only one was updated. The student then follows a3k9 to the old document.
TTL (time to live) is a clock on the copy: after N seconds the entry is treated as a miss. TTL bounds how long staleness can last; it does not make the copy correct. Invalidation on write is what makes the next open miss and reload. Use both if you want a safety bound plus a correct next read — and say the TTL you chose; we will not invent a "standard" TTL.
Figure. After a write, the store has the new long URL. If the cache is not invalidated it still holds the old one, so a hit sends the student to the old document. TTL bounds how long that can last; it does not make the copy correct.
How a mapping goes stale
- WriteTeacher updates the store to a new long URL.
- ForgetThe cache still holds the old URL.
- StudentA hit returns the old document until invalidate or TTL expiry.
CampusClip wrote a new long URL to the store but left a3k9 in the cache. The next student open that hits the cache
- Follows the old URL until invalidate or TTL expiry
- Automatically sees the new URL because the store is source of truth
- Deletes the short code
A hit never asks the store. Source of truth does not help a request that did not go there. Invalidation or TTL is what ends the stale hit.
5Where the cache sits
CampusClip can keep a cache in the same process (a map in memory), beside the app (a small key-value process the hosts share), or on the student's client (the browser remembering a redirect). In-process is fastest and dies with the host — after scale-out, host S1's map is invisible to S2, so S2 misses and hits the store. A shared cache beside the app is what scale-out usually wants for the short-code table.
A client cache of a 302 can skip CampusClip entirely on the next open. That is fine for a stable midterm link and wrong if the teacher just changed the URL and you needed every student to see the change now. Placement is a consistency choice, not a brand of software.
Figure. After scale-out, both CampusClip hosts talk to one shared cache. An in-process map on S1 would not help S2.
| Where | Who shares it | Dies with |
|---|---|---|
| In-process map | Only that CampusClip host | That host |
| Beside the app (shared) | Every host behind the balancer | The cache process |
| Student client | That student's browser | That client's storage |
CampusClip now runs on S1 and S2. The code → URL map still lives only in each process. After S1 caches a3k9, an open that the balancer sends to S2
- Misses S2's map and loads the store
- Hits S1's map automatically
- Cannot be redirected until S1 is the only host again
In-process memory is not shared. S2 has its own empty map. A shared cache beside the app is what would make S2 hit.
Notes
- A cache is a fast copy of a hot mapping. The store remains the source of truth.
- Hit: answer from the copy. Miss: load the store, then fill the cache.
- Cache-aside writes the store then invalidates; write-through writes both; write-back writes the cache first.
- Stale means the copy is old after a store write. TTL bounds the window; invalidation ends it.
- In-process caches do not survive scale-out; a shared cache beside the app does.
Formulas
- Hit rate = hits / (hits + misses) on a stated sample — not a universal constant.
Exam traps & shortcuts
- Read-heavy + same keys → cache. Write that must survive a crash → do not use write-back for that key.
- If two hosts disagree after a write, you forgot invalidation or you cached in-process.
Reference tables
CampusClip short-code table. Durability first; speed second.
| Question | Answer for the mapping table |
|---|---|
| Source of truth? | The store |
| Write path? | Cache-aside or write-through — not write-back |
| After a write? | Invalidate (TTL is only a bound) |
| After scale-out? | Shared cache, not an in-process map |
Recap
A copy, a miss path, and a write that must not lie.
- Why
- Repeated opens of a3k9 should not each hit the store.
- Hit / miss
- Hit answers from the copy. Miss loads the store and fills the cache.
- Writes
- Aside = store then fix cache; through = both; back = cache first (loss window).
- Stale
- Old copy after a store write. Invalidate; TTL only bounds the window.
- Where
- In-process dies at scale-out. Share the cache beside the app.
Practise Caching
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 1 exam-style questions on this topic, with explanations
- A 3-question practice set that ends the chapter
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device