CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Eviction or expiry (20 minutes)

For each case say whether eviction or expiry applies and why: a full cache receives a new entry, a session reaches 30 minutes of age, a one-time code is 5 minutes old, memory is at 100 percent.

Done when: four answers with a reason.

Hint

Eviction is about space, expiry is about age.

Easy 2: Trace LRU (20 minutes)

A cache of size 3 receives A, B, C, B, D, A, C. Trace LRU. List hits, misses and the entry evicted at each miss.

Done when: a table and a hit count.

Hint

Move an entry to the most recent end on every hit.

Easy 3: Pick a policy (20 minutes)

Choose LRU, LFU or FIFO for: a news front page, a list of the top 100 products, a log of recent events with no repeat reads. Give one reason each.

Done when: three choices with reasons.

Hint

Does the data repeat in time or in frequency?

Medium

Medium 1: LRU against FIFO (30 minutes)

Using a cache of size 3 and the sequence A, B, C, A, D, A, B, E, A, count the hits for LRU and for FIFO. Explain the difference.

Done when: two hit counts and an explanation.

Hint

FIFO ignores hits when choosing the victim.

Medium 2: TTL table (30 minutes)

A key is read 40 times a second and costs 80 ms to reload. Compute reloads per second and database time per second for TTLs of 2, 20 and 200 seconds. State which TTL you would choose when the business accepts 1 minute of staleness.

Done when: a three-row table and a choice with a reason.

Hint

Reloads per second = 1 ÷ TTL. Time = reloads × 0.08 seconds.

Medium 3: Size the cache (30 minutes)

The hot set is 8 million entries of 600 bytes, with 90 bytes of overhead, and 30 percent spare memory. Compute the memory. A machine has 8 GB. How many machines are needed if each can use 80 percent of its memory for the cache?

Done when: a memory figure in GB and a machine count.

Hint

Entries × (600 + 90) × 1.3, then divide by 6.4 GB per machine.

Hard

Hard 1: Defend against a scan (45 minutes)

A nightly report reads 5 million rows once each through the same cache of 1 million entries. Describe what happens to the hit ratio of the online traffic under LRU. Propose two ways to protect the hot set, and say what each costs.

Done when: an effect description and two protections with costs.

Hint

After 1 million scanned rows the old entries are gone.

Hard 2: Expiry wave (45 minutes)

At 08:00 a service starts and fills 2 million entries, all with a TTL of 1 hour. The database can serve 200 reloads per second at most. Compute how long the wave of reloads takes at 08:59:59 if every entry is read once at that time. Then choose jitter to keep the reload rate under 150 per second.

Done when: a wave duration, a jitter range and a resulting rate.

Hint

2,000,000 ÷ 200 reloads per second. Jitter range = 2,000,000 ÷ 150.

Hard 3: Design the eviction plan (50 minutes)

A site caches product pages (stable popularity), search results (change by the minute) and sessions (must not be evicted early). Propose cache areas, policies, TTLs and memory shares. Give the reasoning for each and the signals you would watch.

Done when: a table with three areas, policy, TTL, memory share and a list of signals.

Hint

Sessions may need a separate area or a store that is not a cache.