CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Who loads (20 minutes)

Write the steps of a read in cache-aside and in read-through. Mark who reads the database in each.

Done when: two numbered lists with the loader marked.

Hint

In cache-aside the application code holds the database call.

Easy 2: Match the write pattern (20 minutes)

Choose write-through, write-back or write-around for: a like counter, a password change, a log of old orders, a user's profile name. Give one reason for each.

Done when: four choices, each with a reason.

Hint

Ask what loss is acceptable and how often the item is read.

Easy 3: Count the writes (20 minutes)

A counter is updated 1,200 times per minute. Count database writes per minute with write-through, with write-back flushing every 20 seconds, and with write-around.

Done when: three counts.

Hint

Write-back count = minutes × 60 ÷ flush interval.

Medium

Medium 1: Two writers (30 minutes)

Write the timeline of two writers setting a value to 5 and to 9 under update-the-cache, so that the cache ends with the wrong value. Then show the same timeline under delete-the-cache, and say what the cache holds at the end.

Done when: two timelines with the final database and cache values.

Hint

Delay one writer's cache step until after the other's.

Medium 2: The reader race (30 minutes)

Write the five-step timeline in which a reader stores an old value after a writer has deleted the key. Say how long the wrong value stays with a TTL of 5 minutes, and name one change that narrows the window.

Done when: a timeline, a time bound and one change.

Hint

The reader reads the database before the writer's update and stores after the delete.

Medium 3: Sizing the saving (30 minutes)

A service has 4,000 reads per second and 40 writes per second on the same data. Reads use cache-aside with a 95 percent hit ratio. Writes delete the key. Compute database reads per second. Then compute extra misses per second if each write deletes a key that is read 20 times per second on average.

Done when: a baseline database read rate and an extra miss rate.

Hint

Database reads = 4,000 × 0.05. Extra misses = deletes per second, one per deleted key.

Hard

Hard 1: Design for a shopping cart (45 minutes)

Choose read and write patterns for a shopping cart. State the loss you will accept, the TTL, what happens if the cache dies, and how a user on two devices sees one cart.

Done when: a chosen pattern pair, a failure plan and a two-device explanation.

Hint

Think of what the user sees after the cache is cleared.

Hard 2: Write-back with safety (45 minutes)

Design a write-back buffer for 20,000 counter updates per second that must lose at most 1 second of data after a crash. Choose the flush interval, the extra safety mechanism and the database write rate. Compare with write-through at 20,000 writes per second.

Done when: a flush interval, a safety mechanism and two write rates.

Hint

Updates per flush = 20,000 × interval. A log on disk bounds the loss.

Hard 3: Cache during a database outage (50 minutes)

A read-through cache in front of a database serves 8,000 reads per second at a 90 percent hit ratio. The database goes down for 5 minutes. Describe what happens with and without serving expired entries. Compute how many requests fail in each case, assuming expired entries cover 70 percent of the previously missed keys.

Done when: two failure counts and a statement of the staleness accepted.

Hint

Misses per second = 8,000 × 0.10. Outage seconds = 300.