🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

📌 धडा 05 — Caching: वाचणाऱ्याजवळ प्रती

📍 तुम्ही इथे आहात: 18 पैकी धडा 05 · मागे: lesson-04-data-model · पुढे: lesson-06-load-balancing

📦 या ब्रँचमध्ये काय आहे

धडे 01–04, आणि भाग 2 चा पहिला बांधणीचा ठोकळा: cache. प्रती कुठे राहू शकतात (browser, CDN, app, database), cache किती मोठा हवा (hit-ratio वक्र), आणि प्रती पुरेशा ताज्या कशा राहतात (cache-aside, write-through, TTL, invalidation). design/blocks.py मधील LRUCache आणि zipf_stream() वेगवेगळ्या आकारांच्या caches मधून 20,000 feed reads चालवतात; design/demo.py मधील cache() वक्र छापते.

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

दररोज सकाळी शेकडो पालक कार्यालयात येतात आणि विचारतात: "वर्ग 3A च्या सूचना काय आहेत?" कारकून मागच्या मोठ्या नोंदवहीकडे जाते, 3A ची पट्टी शोधते, आणि त्या वाचून दाखवते. पुन्हा. पुन्हा. तेच उत्तर, शेकडो वेळा.

म्हणून दीपिका कार्यालयाच्या दाराजवळ एक छोटा सूचना फलक 📌 लावते. कारकून सर्वात जास्त विचारल्या जाणाऱ्या वर्गांची प्रत तिथे लावते. आता बहुतेक पालक फलक वाचतात आणि निघून जातात. एखादा वर्ग फलकावर नसेल तेव्हाच कारकून नोंदवहीकडे जाते — आणि मग तोही फलकावर लावते.

फलक लहान आहे. तो भरला की, जागा करण्यासाठी कारकून सर्वात जास्त काळ कोणीही न पाहिलेली प्रत (least recently used) काढते.

दीपिकाला दोन अडचणींची तयारी करावी लागते:

जुन्या प्रती. शिक्षिकेने 3A साठी नवी सूचना post केली की फलकावरची प्रत जुनी होते. म्हणून एकतर कारकून ती लगेच काढते, किंवा प्रत्येक प्रतीवर "8:05 पर्यंत वैध" अशी टीप (TTL) असते आणि त्यानंतर ती बदलली जाते.
फलक किती मोठा? काही खूप लोकप्रिय वर्गांना बहुतेक प्रश्न येतात. लहान फलकसुद्धा बरेच पकडतो. दुप्पट मोठा फलक थोडेसेच जास्त पकडतो.

🗺️ आकृती

flowchart LR
    ph["📱 app<br/>browser / phone cache"] --> cdn["🌍 CDN<br/>edge copies"]
    cdn --> api["🔌 API servers"]
    api -->|"1 get"| rc[("📌 Redis<br/>cache-aside")]
    rc -.->|"hit: answer"| api
    api -->|"2 miss: read"| db[("🐘 database<br/>+ its buffer cache")]
    api -->|"3 put, TTL 60 s"| rc
    post["✍️ new notice"] -->|"delete key 'feed:3A'"| rc
    curve["📈 hit ratio<br/>1% of classes → 33.8%<br/>10% → 64.0% · 50% → 83.1%"]

🗺️ काढलेली आवृत्ती + एक lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l05

❓ काय

Cache — एक जलद, लहान store, जो ज्यांचे खरे घर हळू आहे अशा data च्या प्रती ठेवतो (database, दुसरी service, जड आकडेमोड).
Hit / miss / hit ratio — hit म्हणजे cache मध्ये सापडले; miss खऱ्या घरी जातो. Hit ratio = hits ÷ सगळे reads. प्रत्येक miss म्हणजे एक database read.
Cache कुठे राहू शकतो (वाचणाऱ्याच्या सर्वात जवळचा आधी):
- browser / app — Cache-Control: max-age=30; तुम्हाला काहीच खर्च नाही, पण तुम्ही तो delete करू शकत नाही.
- CDN (CloudFront) — वाचणाऱ्याजवळ edge वर प्रती; pages, चित्रे, public याद्यांसाठी सर्वोत्तम.
- application cache (Redis, Memcached) — सगळे API servers मिळून वापरतात; "वर्ग 3A च्या सूचना" साठी नेहमीची जागा.
- database buffer — database ची स्वतःची memory; मोफत, पण ती तुम्हाला हळू query पासून वाचवू शकत नाही.
Hit-ratio वक्र — खरा traffic एकतर्फी (skewed) असतो: काही items ना बहुतेक reads मिळतात. म्हणून लहान cache मोठा वाटा पकडतो, आणि प्रत्येक जास्तीचा gigabyte कमी पकडतो. आकार ठरवणे म्हणजे एक वक्र — तो मोजा, आणि जिथे जास्त memory चा फायदा थांबतो तो बिंदू निवडा.
LRU (least recently used) — भरल्यावर, सर्वात जास्त काळापूर्वी वाचलेले काढून टाका.
Cache-aside (lazy loading) — app cache वाचतो; miss झाला तर database वाचतो आणि उत्तर cache मध्ये ठेवतो. सर्वात सामान्य pattern.
Write-through — प्रत्येक write cache आणि database दोन्हीकडे जातो, म्हणून लिहिलेल्या गोष्टींसाठी cache नेहमी गरम असतो. कोणीही न वाचणाऱ्या data साठी memory खर्च होते.
TTL (time to live) — N सेकंदांनंतर प्रत कालबाह्य होते. तुम्ही स्वीकारता तो सर्वात जास्त जुनेपणा, आकड्याच्या रूपात लिहिलेला.
Invalidation — write झाल्यावर key (feed:3A) delete करा, म्हणजे पुढचा read नवा data आणतो. Delete करा, update नाही: एकमेकांशी शर्यत लावणारे दोन updates जुनी value ठेवून जाऊ शकतात.

🤔 का

कारण धडा 02 म्हणाला प्रत्येक write मागे 100 reads आणि 3,507 req/s चा peak. Cache उत्तर देतो तो प्रत्येक read म्हणजे database ला न करावा लागणारा read, आणि त्याचे उत्तर दहाऐवजी सुमारे एका millisecond मध्ये मिळते. Read-heavy system साठी "read p99 < 200 ms" गाठण्याचा cache हा सर्वात स्वस्त मार्ग आहे. पण तो एक दुसरी प्रत जोडतो — आणि दोन प्रती एकमेकांशी जुळत नाहीत असे होऊ शकते. म्हणून रचनेतल्या प्रत्येक cache साठी दोन लिहिलेली उत्तरे हवीत: ती किती जुनी असू शकते? आणि ती कशाने delete होते?

🔧 कसे (या repo मध्ये)

design/blocks.py मधील zipf_stream(n, items) reads ची एक ठरलेली यादी बनवते, जिथे item i सर्वात लोकप्रिय item च्या सुमारे 1/(i+1) इतक्या वेळा विचारला जातो — काही वर्ग खूप लोकप्रिय, बहुतेक शांत. LRUCache(size) hits आणि misses मोजतो आणि भरल्यावर least recently used नोंद विसरतो. design/demo.py मधील cache() 5,000 वर्गांवरचे 20,000 reads त्यांपैकी 1%, 10% आणि 50% ठेवणाऱ्या caches मधून चालवते. Snippet वक्राचे आणखी बिंदू काढतो.

🧪 करून पाहा

python3 design/demo.py cache
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import LRUCache, zipf_stream
stream = zipf_stream(20_000, 5_000)
for size in (10, 50, 250, 500, 1_000, 2_500, 5_000):
    c = LRUCache(size)
    for k in stream: c.get(k)
    print(f"cache {size:>5} classes → hit ratio {c.hit_ratio():6.1%} · database reads {c.misses:>6,}")
top = sum(1 for k in stream if k < 50)
print(f"the 50 most popular classes get {top:,} of 20,000 reads ({top / 200:.1f}%)")
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

cache छापते:

── 20,000 feed reads over 5,000 classes (a few classes are very popular) through an LRU cache
   cache holds    50 classes (1% of them) → hit ratio  33.8%
   cache holds   500 classes (10% of them) → hit ratio  64.0%
   cache holds  2500 classes (50% of them) → hit ratio  83.1%
   a cache holding 1% of the classes already catches a third of the reads — sizing is a curve, measure it
   where: browser · CDN · API (Redis) · database buffer · invalidate on write or use a short TTL

तुमचा snippet छापतो:

cache    10 classes → hit ratio  14.9% · database reads 17,018
cache    50 classes → hit ratio  33.8% · database reads 13,240
cache   250 classes → hit ratio  55.0% · database reads  9,008
cache   500 classes → hit ratio  64.0% · database reads  7,203
cache  1000 classes → hit ratio  73.1% · database reads  5,382
cache  2500 classes → hit ratio  83.1% · database reads  3,375
cache  5000 classes → hit ratio  83.9% · database reads  3,212
the 50 most popular classes get 9,822 of 20,000 reads (49.1%)

🏁 तुम्ही आत्ताच काय सिद्ध केले

वक्र वाकतो: 10 वरून 500 वर्गांवर गेल्याने database reads 17,018 वरून 7,203 वर येतात; 2,500 वरून सगळ्या 5,000 वर गेल्याने फक्त आणखी 163 वाचतात. सगळे काही ठेवणारा cache सुद्धा 83.9% वर थांबतो — प्रत्येक वर्गाचा पहिला read नेहमी miss असतो. आणि 50 सर्वात लोकप्रिय वर्गांना 49.1% reads मिळतात, पण 50 जागांचा LRU फक्त 33.8% पकडतो: शांत वर्ग लोकप्रिय वर्गांना बाहेर ढकलत राहतात. आकार वक्रावरून ठरवा, "परवडेल तितका मोठा" यावरून नाही.

⚠️ नेहमीच्या चुका

TTL नाही आणि invalidation नाही असा cache — वाचणाऱ्यांसाठी कधीच update न होणारी सूचना
प्रत्येक पालकाचा data सामायिक key खाली cache करणे — एका पालकाला दुसऱ्या पालकाचे feed दिसते
write वर cache delete करण्याऐवजी update करणे (शर्यतींमुळे जुनी value राहते)
index नसल्याने हळू असलेल्या query पुढे cache — आधी index दुरुस्त करा (धडा 04)
अनेक वाचणाऱ्यांचा एकाच कालबाह्य key वर एकदम miss आणि सगळे database वर आदळतात (stampede) — Scaling शाळा पाहा
cache हीच एकमेव प्रत मानणे: Redis restart होतो; database हेच सत्य

🏭 प्रत्यक्ष वापरात

वर्गाच्या feed साठी cache-aside, API मध्ये (Python सारखा pseudo-code):

def class_feed(class_id):
    key = f"feed:{class_id}:v1"
    hit = redis.get(key)
    if hit: return json.loads(hit)
    rows = db.query("SELECT … FROM notices WHERE class_id = %s ORDER BY created_at DESC LIMIT 20", class_id)
    redis.set(key, json.dumps(rows), ex=60)          # TTL 60 s: the longest staleness we accept
    return rows

def post_notice(class_id, notice):
    db.insert(notice)                                  # the database first — it is the truth
    redis.delete(f"feed:{class_id}:v1")                # then invalidate

On a real account — कार्यालयासाठी एक लहान Redis (ElastiCache Serverless), आणि लक्ष ठेवायचा CloudWatch आकडा:

aws elasticache create-serverless-cache --serverless-cache-name notice-cache --engine redis
aws cloudwatch get-metric-statistics --namespace AWS/ElastiCache --metric-name CacheHitRate \
    --dimensions Name=CacheClusterId,Value=notice-cache --statistics Average --period 300 \
    --start-time 2026-09-21T00:00:00Z --end-time 2026-09-22T00:00:00Z

अधिक खोलात: Scaling शाळा, धडा 09 (Redis सह cache-aside, TTLs आणि stampede थांबवणे), आणि CDN caching साठी तिथले धडे 03–04.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक cache साठी TTL आणि invalidation चा नियम design doc मध्ये लिहा. "60 s पर्यंत जुने" हा product निर्णय आहे — तातडीच्या सूचनेसाठी 60 s चालेल का ते शाळेला विचारा (कदाचित चालणार नाही; तातडीच्या सूचना cache वगळू शकतात).

⏭️ पुढे

Cache आणि API अनेक servers वर चालतात. प्रत्येक request कोणत्या server ला जातो — आणि कोणता cache server कोणता वर्ग ठेवतो — हे कोण ठरवते?

git checkout lesson-06-load-balancing

📌 Lesson 05 — Caching: copies close to the reader

📍 You are here: Lesson 05 of 18 · Previous: lesson-04-data-model · Next: lesson-06-load-balancing

📦 What's in this branch

Lessons 01–04, plus the first building block of Part 2: the cache. Where copies can live (browser, CDN, app, database), how big a cache must be (the hit-ratio curve), and how copies stay fresh enough (cache-aside, write-through, TTL, invalidation). LRUCache and zipf_stream() in design/blocks.py run 20,000 feed reads through caches of different sizes; cache() in design/demo.py prints the curve.

🧒 Explain like I'm 5

Every morning, hundreds of parents walk to the office and ask: "What are the notices for class 3A?" The clerk walks to the big register at the back, finds the 3A tab, and reads them out. Again. And again. The same answer, hundreds of times.

So Dipika puts a small notice board 📌 by the office door. The clerk pins a copy of the most-asked classes there. Now most parents read the board and leave. The clerk walks to the register only when a class is not on the board — and then pins that one too.

The board is small. When it is full, the clerk takes down the copy nobody has looked at for the longest time (least recently used) to make room.

Two problems Dipika must plan for:

Old copies. When a teacher posts a new notice for 3A, the copy on the board is out of date. So either the clerk takes it down at once, or every copy has a "good until 8:05" note (a TTL) and is replaced after that.
How big a board? A few very popular classes get most of the questions. A small board catches a lot. A board twice as big catches only a little more.

🗺️ Diagram

flowchart LR
    ph["📱 app<br/>browser / phone cache"] --> cdn["🌍 CDN<br/>edge copies"]
    cdn --> api["🔌 API servers"]
    api -->|"1 get"| rc[("📌 Redis<br/>cache-aside")]
    rc -.->|"hit: answer"| api
    api -->|"2 miss: read"| db[("🐘 database<br/>+ its buffer cache")]
    api -->|"3 put, TTL 60 s"| rc
    post["✍️ new notice"] -->|"delete key 'feed:3A'"| rc
    curve["📈 hit ratio<br/>1% of classes → 33.8%<br/>10% → 64.0% · 50% → 83.1%"]

🗺️ Drawn version + a lab: https://school-edh.pages.dev/system-design/lesson-diagrams.html#l05

❓ What

Cache — a fast, small store that keeps copies of data whose real home is slower (a database, another service, a heavy calculation).
Hit / miss / hit ratio — a hit is found in the cache; a miss goes to the real home. Hit ratio = hits ÷ all reads. Every miss is a database read.
Where a cache can live (closest to the reader first):
- browser / app — Cache-Control: max-age=30; costs you nothing, but you cannot delete it.
- CDN (CloudFront) — copies at the edge near the reader; best for pages, pictures, public lists.
- application cache (Redis, Memcached) — shared by all API servers; the usual place for "notices of class 3A".
- database buffer — the database's own memory; free, but it cannot save you from a slow query.
The hit-ratio curve — real traffic is skewed: a few items get most reads. So a small cache catches a big share, and each extra gigabyte catches less. Sizing is a curve — measure it, then pick the point where more memory stops paying.
LRU (least recently used) — when full, remove what was read longest ago.
Cache-aside (lazy loading) — the app reads the cache; on a miss it reads the database and puts the answer in the cache. The most common pattern.
Write-through — every write goes to the cache and the database, so the cache is always warm for what was written. Costs memory for data nobody reads.
TTL (time to live) — a copy expires after N seconds. The longest staleness you accept, written as a number.
Invalidation — on a write, delete the key (feed:3A) so the next read loads the new data. Delete, do not update: two racing updates can leave the older value.

🤔 Why

Because lesson 02 said 100 reads for every write and a peak of 3,507 req/s. Every read the cache answers is a read the database does not do, and it is answered in about a millisecond instead of ten. A cache is the cheapest way to meet "read p99 < 200 ms" for a read-heavy system. But it adds a second copy — and two copies can disagree. So every cache in a design needs two written answers: how stale may it be? and what deletes it?

🔧 How (in this repo)

zipf_stream(n, items) in design/blocks.py makes a fixed list of reads where item i is asked about 1/(i+1) as often as the most popular one — a few classes are very popular, most are quiet. LRUCache(size) counts hits and misses and forgets the least recently used entry when full. cache() in design/demo.py runs 20,000 reads over 5,000 classes through caches holding 1%, 10% and 50% of them. The snippet draws more points of the curve.

🧪 Try it

python3 design/demo.py cache
python3 - <<'EOF'
import sys; sys.path.insert(0, "design"); from blocks import LRUCache, zipf_stream
stream = zipf_stream(20_000, 5_000)
for size in (10, 50, 250, 500, 1_000, 2_500, 5_000):
    c = LRUCache(size)
    for k in stream: c.get(k)
    print(f"cache {size:>5} classes → hit ratio {c.hit_ratio():6.1%} · database reads {c.misses:>6,}")
top = sum(1 for k in stream if k < 50)
print(f"the 50 most popular classes get {top:,} of 20,000 reads ({top / 200:.1f}%)")
EOF

✅ Verify — what you should see

cache prints:

── 20,000 feed reads over 5,000 classes (a few classes are very popular) through an LRU cache
   cache holds    50 classes (1% of them) → hit ratio  33.8%
   cache holds   500 classes (10% of them) → hit ratio  64.0%
   cache holds  2500 classes (50% of them) → hit ratio  83.1%
   a cache holding 1% of the classes already catches a third of the reads — sizing is a curve, measure it
   where: browser · CDN · API (Redis) · database buffer · invalidate on write or use a short TTL

Your snippet prints:

cache    10 classes → hit ratio  14.9% · database reads 17,018
cache    50 classes → hit ratio  33.8% · database reads 13,240
cache   250 classes → hit ratio  55.0% · database reads  9,008
cache   500 classes → hit ratio  64.0% · database reads  7,203
cache  1000 classes → hit ratio  73.1% · database reads  5,382
cache  2500 classes → hit ratio  83.1% · database reads  3,375
cache  5000 classes → hit ratio  83.9% · database reads  3,212
the 50 most popular classes get 9,822 of 20,000 reads (49.1%)

🏁 What you just proved

The curve bends: going from 10 to 500 classes cuts database reads from 17,018 to 7,203; going from 2,500 to all 5,000 saves only 163 more. Even a cache that holds everything stops at 83.9% — the first read of each class is always a miss. And the 50 most popular classes get 49.1% of reads, but a 50-slot LRU catches only 33.8%: the quiet classes keep pushing popular ones out. Size by the curve, not by "as big as we can afford".

⚠️ Common mistakes

a cache with no TTL and no invalidation — a notice that is never updated for readers
caching per-parent data under a shared key — one parent sees another parent's feed
updating the cache on write instead of deleting it (races leave the older value)
a cache in front of a query that is slow because it has no index — fix the index first (lesson 04)
many readers miss the same expired key at once and all hit the database (a stampede) — see the Scaling school
treating the cache as the only copy: Redis restarts; the database is the truth

🏭 In production

Cache-aside for the class feed, in the API (Python-like pseudo-code):

def class_feed(class_id):
    key = f"feed:{class_id}:v1"
    hit = redis.get(key)
    if hit: return json.loads(hit)
    rows = db.query("SELECT … FROM notices WHERE class_id = %s ORDER BY created_at DESC LIMIT 20", class_id)
    redis.set(key, json.dumps(rows), ex=60)          # TTL 60 s: the longest staleness we accept
    return rows

def post_notice(class_id, notice):
    db.insert(notice)                                  # the database first — it is the truth
    redis.delete(f"feed:{class_id}:v1")                # then invalidate

On a real account — a small Redis for the office (ElastiCache Serverless), and the CloudWatch number to watch:

aws elasticache create-serverless-cache --serverless-cache-name notice-cache --engine redis
aws cloudwatch get-metric-statistics --namespace AWS/ElastiCache --metric-name CacheHitRate \
    --dimensions Name=CacheClusterId,Value=notice-cache --statistics Average --period 300 \
    --start-time 2026-09-21T00:00:00Z --end-time 2026-09-22T00:00:00Z

Go deeper: the Scaling school, lesson 09 (cache-aside with Redis, TTLs and stopping a stampede), and lessons 03–04 there for CDN caching.

🏭 Why this matters in production: write the TTL and the invalidation rule into the design doc for every cache. "Stale for up to 60 s" is a product decision — ask the school if 60 s is acceptable for an urgent notice (it may not be; urgent notices can skip the cache).

⏭️ Next

The cache and the API run on many servers. Who decides which server gets each request — and which cache server keeps which class?

git checkout lesson-06-load-balancing

← Previousdata model Next →load balancing

This page is the lesson's README from the lesson-05-caching branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.