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

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

🗂️ धडा 06 — Caching आणि memoization: scoreboard लक्षात ठेवतो

📍 तुम्ही इथे आहात: 12 पैकी धडा 06 · मागे: lesson-05-memory · पुढे: lesson-07-io-batching

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

धडे 01–05, अधिक caching: आधीच काढलेले उत्तर ठेवून द्या, म्हणजे पुढच्या request ला ते जवळजवळ फुकट मिळते. Memoization म्हणजे एखाद्या function चे results cache करणे; जागा मर्यादित असताना LRU cache सर्वात अलीकडे वापरलेली उत्तरे ठेवतो; आणि cache उपयोगी आहे की नाही हे hit ratio ठरवतो. perf/demo.py मधले caching() आणि perf/sim.py मधले fib_plain, fib_memo, LRU, request_stream आणि cached_cost.

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

पालक सारखे results office मध्ये येत राहतात: "कतरिनाची वेळ काय होती?" 🙋‍♀️

प्रत्येक वेळी ऐश्वर्या मागच्या खोलीत जाते, निकालांचे मोठे पुस्तक उघडते, पान शोधते, आणि परत येते. यात 50 seconds जातात.

मग ती दाराजवळ एक छोटा scoreboard लावते. 📋 ती शोधलेले प्रत्येक उत्तर board वर लिहिते. पुढच्या वेळी कोणी तोच प्रश्न विचारला, तर ती फक्त board वाचते: 1 second.

प्रश्न board वर असेल, तर तो hit आहे. ✅
नसेल, तर तो miss आहे — पुन्हा मोठ्या पुस्तकाकडे. ❌

Board वर फक्त 100 नावांसाठी जागा आहे. तो भरल्यावर, ज्या नावाबद्दल सर्वात जास्त काळ कोणीही विचारले नाही ते ती पुसून टाकते. बहुतेक पालक त्याच काही अंतिम फेरीतल्या धावपटूंबद्दल विचारतात, म्हणून छोटा board खूप प्रश्नांची उत्तरे देतो.

एक धोका: मोठ्या पुस्तकात एखादी वेळ दुरुस्त झाली, तर कोणी update करेपर्यंत board अजूनही जुनी वेळ दाखवतो. 🕰️

🗺️ आकृती

flowchart LR
    ask["🙋 2000 lookups<br/>500 runners, a few popular"] --> board{"📋 on the board?<br/>LRU of 100"}
    board -->|"hit 44.9%"| fast["1 ms"]
    board -->|"miss"| book["📚 the back room<br/>50 ms, then write it on the board"]
    fast --> avg["average 28.0 ms<br/>(no cache: 50 ms)"]
    book --> avg
    fib["fib(25): 242,785 calls"] -->|"lru_cache"| memo["26 calls"]

🗺️ काढलेली आकृती + एक lab: https://school-edh.pages.dev/performance/lesson-diagrams.html#l06

❓ काय

Cache — आधीच काढलेल्या किंवा आणलेल्या उत्तरांचा छोटा, जलद साठा. आधी cache ला विचारणे आणि फक्त miss झाल्यावरच हळू स्रोताकडे जाणे याला cache-aside pattern म्हणतात.
Memoization — function चे results त्याच्या arguments नुसार cache करणे. Python मध्ये ते built in आहे: functools.lru_cache(maxsize=...) आणि functools.cache (आकाराची मर्यादा नाही). ते फक्त pure functions साठीच योग्य आहे: तेच arguments, तेच उत्तर, कोणतेही side effects नाहीत.
Hit ratio — hits ÷ सगळे lookups. सरासरी खर्च साधारण hit ratio × hit cost + (1 − hit ratio) × miss cost असतो. 1 ms चा hit आणि 50 ms चा miss असेल, तर 45% hit ratio सुमारे 28 ms देतो — चांगले, पण 1 ms पासून खूप दूर.
Eviction — cache भरल्यावर काय विसरायचे. LRU (least recently used) सर्वात जास्त काळ न वापरलेली entry विसरतो. इतर: LFU (least frequently used), FIFO, random.
Skew — खरे traffic असमान असते: काही keys ना बहुतेक requests मिळतात. म्हणूनच छोट्या cache चा hit ratio चांगला असू शकतो. Lab चा stream key ⌊500 × u³⌋ निवडतो (u random), म्हणून कमी क्रमांकाच्या "अंतिम फेरीतल्या धावपटूंबद्दल" खूप जास्त वेळा विचारले जाते.
शिळेपणा आणि invalidation — cache मधले उत्तर जुने असू शकते. तुम्ही एकतर प्रत्येक entry ला TTL (time to live) देता आणि तेवढ्या काळापर्यंतचा शिळेपणा स्वीकारता, किंवा स्रोत बदलल्यावर entry delete/update करता (हे ऐकण्यापेक्षा अवघड आहे).
Cache stampede — एखादी लोकप्रिय entry expire होते आणि शेकडो requests एकदम miss होऊन सगळ्या हळू स्रोतावर आदळतात. उपाय: एका request ला refresh करू द्या आणि बाकीच्या थांबतील किंवा जुनी value घेतील, आणि TTLs मध्ये थोडा random jitter जोडा.

Machines दरम्यानचे caches — अनेक servers पुढचे CDNs आणि shared caches — हे Scaling school मध्ये आहेत.

🤔 का

कारण सर्वात स्वस्त काम म्हणजे जे तुम्ही वगळता ते. साधे recursive fib(25) तेच उप-प्रश्न लाखो वेळा पुन्हा करते; cache प्रत्येकाला एकाच गणनेत बदलतो. पण cache म्हणजे memory सुद्धा आहे (धडा 05), चुकीचा data देण्याचा एक नवा मार्ग, आणि restart नंतर warm up करावी लागणारी आणखी एक गोष्ट. आधी आणि नंतर hit ratio मोजा; 5% hit ratio असलेला cache बहुतांश खर्चच असतो.

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

perf/sim.py मधले fib_plain(n) आपल्या calls CALLS["fib"] मध्ये मोजते; fib_memo(n) तेच recursion functools.lru_cache मध्ये गुंडाळते आणि उत्तर आणि खरे cache_info() परत देते. LRU(cap) हा OrderedDict वर बांधलेला छोटा least-recently-used cache आहे, जो hits आणि misses मोजतो. request_stream() 500 keys वर जोरदार skew सह 2000 seeded lookups बनवते, आणि cached_cost(cap, stream, hit_ms, miss_ms) hit ratio आणि प्रत्येक request चा simulated सरासरी खर्च परत देते.

🧪 करून पाहा

python3 perf/demo.py caching
python3 - <<'EOF'
import sys; sys.path.insert(0, "perf"); import sim
for n in (10, 20, 25, 30):
    sim.CALLS["fib"] = 0; sim.fib_plain(n); plain = sim.CALLS["fib"]
    sim.CALLS["fib"] = 0; sim.fib_memo(n); memo = sim.CALLS["fib"]
    print(f"fib({n:>2}): plain {plain:>9,} calls · memoized {memo:>3}")
s = sim.request_stream()
for miss_ms in (5, 50, 500):
    r, cost = sim.cached_cost(100, s, miss_ms=miss_ms)
    print(f"cache of 100, a miss costs {miss_ms:>3} ms → hit ratio {r:.1%} · average {cost:6.1f} ms")
EOF

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

caching हे छापते:

── fib(25) = 75025: plain recursion does the work 242,785 times · memoized (lru_cache) 26 times (23 cache hits)
── parents look up results: 2000 requests over 500 runners, a few asked for far more often · a hit costs 1 ms, a miss 50 ms
   LRU cache of  10 → hit ratio 15.4% · average 42.5 ms per request
   LRU cache of  50 → hit ratio 33.0% · average 33.9 ms per request
   LRU cache of 100 → hit ratio 44.9% · average 28.0 ms per request
   LRU cache of 250 → hit ratio 67.7% · average 16.8 ms per request

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

fib(10): plain       177 calls · memoized  11
fib(20): plain    21,891 calls · memoized  21
fib(25): plain   242,785 calls · memoized  26
fib(30): plain 2,692,537 calls · memoized  31
cache of 100, a miss costs   5 ms → hit ratio 44.9% · average    3.2 ms
cache of 100, a miss costs  50 ms → hit ratio 44.9% · average   28.0 ms
cache of 100, a miss costs 500 ms → hit ratio 44.9% · average  275.9 ms

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

Memoization ने घातांकी (exponential) कामाचे रेषीय (linear) कामात रूपांतर केले: fib(30) 2,692,537 calls वरून 31 वर आले. Lookup cache साठी, 10 slots नीच 15.4% requests पकडल्या, कारण traffic skewed होते, पण cache दुप्पट केल्याने hit ratio कधीच दुप्पट झाला नाही. आणि 500 ms च्या miss सह, 44.9% hit ratio असूनही सरासरी 275.9 ms उरते: जेव्हा misses महाग असतात, तेव्हा miss path सुद्धा जलद असायला हवा.

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

घड्याळ, database किंवा बदलणारी कोणतीही गोष्ट वाचणाऱ्या function वर @lru_cache
method वर @lru_cache: cache self ला जिवंत ठेवतो (अल्पायुषी objects साठी memory leak)
आकाराची मर्यादा नसलेला cache — functools.cache कायम वाढत राहतो
TTL नाही आणि invalidation नाही, म्हणून दुरुस्त केलेला result कधीच दिसत नाही
प्रत्येक user ची pages एका shared key खाली cache करणे — एका user ला दुसऱ्याचा data दिसतो
profiling करण्याआधीच cache जोडणे; हळू भाग पुन्हा पुन्हा होणारे काम नसूही शकतो

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

खऱ्या account वर — Redis सह cache-aside, TTL सह:

import json, redis
r = redis.Redis(host="cache.school.internal")
def best_lap(runner_id):
    key = f"best_lap:{runner_id}"
    hit = r.get(key)
    if hit is not None:
        return json.loads(hit)
    value = db_best_lap(runner_id)                  # the slow source
    r.set(key, json.dumps(value), ex=60)            # expire after 60 s
    return value

Redis तुमच्यासाठी ठेवत असलेला hit ratio तपासा:

redis-cli INFO stats | grep -E 'keyspace_hits|keyspace_misses'
redis-cli CONFIG SET maxmemory-policy allkeys-lru   # evict least recently used keys when full

Python process मध्ये, मर्यादित memo:

from functools import lru_cache
@lru_cache(maxsize=1024)
def house_of(bib: int) -> str: ...
print(house_of.cache_info())      # hits, misses, maxsize, currsize

🏭 Production मध्ये हे का महत्त्वाचे आहे: प्रत्येक cache साठी, त्याचा hit ratio आणि त्याची miss latency chart करा, आणि त्याचा data किती शिळा असू शकतो ते लिहून ठेवा. कोणीही न मोजलेला cache म्हणजे फक्त अंदाज.

⏭️ पुढे

Misses "मागच्या खोलीत" गेले. तिथली प्रत्येक फेरी म्हणजे वेळ खाणारे एक हस्तांतर (hand-off). पुढे: I/O — N+1 queries, batching आणि buffering.

git checkout lesson-07-io-batching

🗂️ Lesson 06 — Caching & memoization: the scoreboard remembers

📍 You are here: Lesson 06 of 12 · Previous: lesson-05-memory · Next: lesson-07-io-batching

📦 What's in this branch

Lessons 01–05, plus caching: keep an answer you already worked out, so the next request gets it for almost nothing. Memoization is caching the results of a function; an LRU cache keeps the most recently used answers when space is limited; and the hit ratio decides whether a cache helps at all. caching() in perf/demo.py and fib_plain, fib_memo, LRU, request_stream and cached_cost in perf/sim.py.

🧒 Explain like I'm 5

Parents keep coming to the results office: "What was Katrina's time?" 🙋‍♀️

Each time, Aishwarya walks to the back room, opens the big results book, finds the page, and walks back. That takes 50 seconds.

Then she puts up a small scoreboard by the door. 📋 Every answer she looks up goes on the board. Next time someone asks the same question, she just reads the board: 1 second.

If the question is on the board, that is a hit. ✅
If not, it is a miss — back to the big book. ❌

The board only has room for 100 names. When it is full, she rubs out the name nobody asked about for the longest time. Most parents ask about the same few finalists, so a small board answers a lot of questions.

One danger: if a time is corrected in the big book, the board still shows the old time until someone updates it. 🕰️

🗺️ Diagram

flowchart LR
    ask["🙋 2000 lookups<br/>500 runners, a few popular"] --> board{"📋 on the board?<br/>LRU of 100"}
    board -->|"hit 44.9%"| fast["1 ms"]
    board -->|"miss"| book["📚 the back room<br/>50 ms, then write it on the board"]
    fast --> avg["average 28.0 ms<br/>(no cache: 50 ms)"]
    book --> avg
    fib["fib(25): 242,785 calls"] -->|"lru_cache"| memo["26 calls"]

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

❓ What

Cache — a small, fast store of answers you already computed or fetched. Asking the cache first and going to the slow source only on a miss is the cache-aside pattern.
Memoization — caching a function's results by its arguments. Python has it built in: functools.lru_cache(maxsize=...) and functools.cache (no size limit). It only makes sense for pure functions: same arguments, same answer, no side effects.
Hit ratio — hits ÷ all lookups. The average cost is about hit ratio × hit cost + (1 − hit ratio) × miss cost. With a 1 ms hit and a 50 ms miss, a 45% hit ratio gives about 28 ms — better, but far from 1 ms.
Eviction — what to forget when the cache is full. LRU (least recently used) forgets the entry unused the longest. Others: LFU (least frequently used), FIFO, random.
Skew — real traffic is uneven: a few keys get most of the requests. That is why a small cache can have a good hit ratio. The lab's stream picks key ⌊500 × u³⌋ (u random), so low-numbered "finalists" are asked far more often.
Staleness and invalidation — a cached answer can be out of date. You either give each entry a TTL (time to live) and accept staleness up to that long, or delete/update the entry when the source changes (harder than it sounds).
Cache stampede — a popular entry expires and hundreds of requests miss at once and all hit the slow source. Fixes: let one request refresh while others wait or get the old value, and add a little random jitter to TTLs.

Caches between machines — CDNs and shared caches in front of many servers — are covered in the Scaling school.

🤔 Why

Because the cheapest work is the work you skip. Plain recursive fib(25) repeats the same sub-questions hundreds of thousands of times; a cache makes each one a single computation. But a cache is also memory (lesson 05), a new way to serve wrong data, and one more thing to warm up after a restart. Measure the hit ratio before and after; a cache with a 5% hit ratio is mostly cost.

🔧 How (in this repo)

fib_plain(n) in perf/sim.py counts its calls in CALLS["fib"]; fib_memo(n) wraps the same recursion in functools.lru_cache and returns the answer and the real cache_info(). LRU(cap) is a small least-recently-used cache built on OrderedDict, counting hits and misses. request_stream() makes 2000 seeded lookups over 500 keys with a strong skew, and cached_cost(cap, stream, hit_ms, miss_ms) returns the hit ratio and the simulated average cost per request.

🧪 Try it

python3 perf/demo.py caching
python3 - <<'EOF'
import sys; sys.path.insert(0, "perf"); import sim
for n in (10, 20, 25, 30):
    sim.CALLS["fib"] = 0; sim.fib_plain(n); plain = sim.CALLS["fib"]
    sim.CALLS["fib"] = 0; sim.fib_memo(n); memo = sim.CALLS["fib"]
    print(f"fib({n:>2}): plain {plain:>9,} calls · memoized {memo:>3}")
s = sim.request_stream()
for miss_ms in (5, 50, 500):
    r, cost = sim.cached_cost(100, s, miss_ms=miss_ms)
    print(f"cache of 100, a miss costs {miss_ms:>3} ms → hit ratio {r:.1%} · average {cost:6.1f} ms")
EOF

✅ Verify — what you should see

caching prints:

── fib(25) = 75025: plain recursion does the work 242,785 times · memoized (lru_cache) 26 times (23 cache hits)
── parents look up results: 2000 requests over 500 runners, a few asked for far more often · a hit costs 1 ms, a miss 50 ms
   LRU cache of  10 → hit ratio 15.4% · average 42.5 ms per request
   LRU cache of  50 → hit ratio 33.0% · average 33.9 ms per request
   LRU cache of 100 → hit ratio 44.9% · average 28.0 ms per request
   LRU cache of 250 → hit ratio 67.7% · average 16.8 ms per request

Your snippet prints:

fib(10): plain       177 calls · memoized  11
fib(20): plain    21,891 calls · memoized  21
fib(25): plain   242,785 calls · memoized  26
fib(30): plain 2,692,537 calls · memoized  31
cache of 100, a miss costs   5 ms → hit ratio 44.9% · average    3.2 ms
cache of 100, a miss costs  50 ms → hit ratio 44.9% · average   28.0 ms
cache of 100, a miss costs 500 ms → hit ratio 44.9% · average  275.9 ms

🏁 What you just proved

Memoization turned exponential work into linear: fib(30) went from 2,692,537 calls to 31. For the lookup cache, 10 slots already caught 15.4% of requests, because the traffic was skewed, but doubling the cache never doubled the hit ratio. And with a 500 ms miss, even a 44.9% hit ratio leaves an average of 275.9 ms: when misses are expensive, the miss path still needs to be fast.

⚠️ Common mistakes

@lru_cache on a function that reads the clock, the database or anything that changes
@lru_cache on a method: the cache keeps self alive (a memory leak for short-lived objects)
a cache with no size limit — functools.cache grows for ever
no TTL and no invalidation, so a corrected result is never seen
caching per-user pages under a shared key — one user sees another's data
adding a cache before profiling; the slow part may not be repeatable work at all

🏭 In production

On a real account — cache-aside with Redis, with a TTL:

import json, redis
r = redis.Redis(host="cache.school.internal")
def best_lap(runner_id):
    key = f"best_lap:{runner_id}"
    hit = r.get(key)
    if hit is not None:
        return json.loads(hit)
    value = db_best_lap(runner_id)                  # the slow source
    r.set(key, json.dumps(value), ex=60)            # expire after 60 s
    return value

Check the hit ratio Redis keeps for you:

redis-cli INFO stats | grep -E 'keyspace_hits|keyspace_misses'
redis-cli CONFIG SET maxmemory-policy allkeys-lru   # evict least recently used keys when full

In a Python process, a bounded memo:

from functools import lru_cache
@lru_cache(maxsize=1024)
def house_of(bib: int) -> str: ...
print(house_of.cache_info())      # hits, misses, maxsize, currsize

🏭 Why this matters in production: for every cache, chart its hit ratio and its miss latency, and write down how stale its data may be. A cache nobody measures is a guess.

⏭️ Next

The misses went to "the back room". Every trip there is a hand-off that costs time. Next: I/O — N+1 queries, batching and buffering.

git checkout lesson-07-io-batching

← Previousmemory Next →io batching

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