CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Name the problem (20 minutes)

Name the problem in each case: 500 requests miss the same key at once, requests for ids that do not exist, all entries expire at midnight, one celebrity profile overloads a server, a price of 0 is cached for a day.

Done when: five names with one reason each.

Hint

Match each case to the checklist table.

Easy 2: Size the stampede (20 minutes)

A key is read 1,500 times a second and a reload takes 400 ms. Compute how many requests miss at expiry, and how many queries run with request coalescing.

Done when: two numbers.

Hint

Misses at once = reads per second × reload time in seconds.

Easy 3: Pick the fix (20 minutes)

For each problem in Easy 1, choose one fix and say what it costs.

Done when: five fixes with costs.

Hint

Use the checklist table.

Medium

Medium 1: Bloom filter saving (30 minutes)

An attacker sends 30,000 requests a second for keys that do not exist. A Bloom filter has a false positive rate of 0.5 percent. Compute the database reads per second with the filter and without. Name the cost of the filter.

Done when: two rates and a cost.

Hint

Reads with the filter = requests × false positive rate.

Medium 2: Jitter plan (30 minutes)

1,200,000 entries are filled in one hour with a TTL of 2 hours. The database can take 1,000 reloads per second on top of normal load. Compute the reload rate with no jitter spread over 1 minute, and choose a jitter range that keeps it under 1,000 a second.

Done when: a rate without jitter and a jitter range in seconds.

Hint

Without jitter, 1,200,000 ÷ 60. With jitter, entries ÷ spread seconds.

Medium 3: Cache loss (30 minutes)

A site has 60,000 reads a second at a 97 percent hit ratio on 8 cache nodes. Compute the database load normally, with one node lost (assume the lost node's share all misses), and with all nodes lost. State which load the database was sized for.

Done when: three loads and a sizing remark.

Hint

Normal load = 60,000 × 0.03. One node lost adds one eighth of the hits.

Hard

Hard 1: Hot key design (45 minutes)

A live event makes one key receive 500,000 reads a second. Each cache server handles 120,000 a second and there are 200 application servers. Design a local copy with a 2-second TTL and compute the reads reaching the cache server. Design key splitting with the least copies and compute the load per copy. Compare the staleness and the write cost.

Done when: two designs with loads, staleness and write cost.

Hint

Local copy reads = app servers ÷ TTL seconds. Copies needed = 500,000 ÷ 120,000, rounded up.

Hard 2: Protecting the database (45 minutes)

A database copes with 3,000 reads a second. The traffic is 50,000 reads a second at a 94 percent hit ratio. Design the protection for a cache outage using coalescing, load shedding and a warm-up. State how many reads a second you let through and what the rest receive.

Done when: a plan with numbers, a shed rate and a user-visible effect.

Hint

Misses now are 50,000 × 0.06. Outage means up to 50,000.

Hard 3: Audit a cache (50 minutes)

Take a cache design (any from this level) and walk through the checklist. For each of the six problems, write the trigger in your design, the number it would cause, the fix and the signal you would watch.

Done when: a six-row table with trigger, number, fix and signal.

Hint

Use real numbers from your own design, not the checklist numbers.