CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 4 min read

Exercises

Easy

Easy 1: Hit ratio (20 minutes)

A cache logs 46,000 hits and 4,000 misses in an hour. Compute the hit ratio and the miss ratio. How many reads reached the database per second, on average?

Done when: two ratios and a per-second figure.

Hint

Hit ratio = hits ÷ (hits + misses). An hour has 3,600 seconds.

Easy 2: Average read time (20 minutes)

A cache answers in 2 ms and a database in 40 ms. Compute the average read time at hit ratios of 70, 90 and 98 percent, using the formula with the wasted lookup on a miss.

Done when: three averages with the working.

Hint

Average = hit × cache + miss × (cache + database).

Easy 3: Good or poor candidate (20 minutes)

Judge each as good, poor or doubtful for a cache, with one reason: a list of country names, the current balance of a bank account, the top 10 products of the week, a one-time password, a user profile page.

Done when: five verdicts, each with a reason from the four tests.

Hint

Check the read-to-write ratio and staleness first.

Medium

Medium 1: Database load (30 minutes)

A service gets 25,000 reads per second. The database handles 3,000 reads per second at most. Find the lowest hit ratio at which the database copes. Then find how many reads per second reach it at 95 percent.

Done when: a minimum hit ratio and a load figure at 95 percent.

Hint

Reads reaching the database = total × miss ratio. Set that equal to 3,000.

Medium 2: Size the cache (30 minutes)

A catalogue has 50 million items of 1 KB. Assume 10 percent of items get 90 percent of reads. Compute the total size, the hot set size and the cache size that would serve about 90 percent of reads. Say what happens if the cache is half that size.

Done when: three sizes and a statement about the smaller cache.

Hint

Hot set = 10 percent of the total size. Half the hot set serves a smaller share.

Medium 3: Staleness window (30 minutes)

A product price is cached with a TTL of 120 seconds. It changes once. Compute the longest time a reader can see the old price, and how many page views show the old price at 50 views per second. Propose a TTL that limits the old views to 1,000, and the cost in database reads per minute for that key.

Done when: two figures for the 120-second TTL, a new TTL and a read-rate comparison.

Hint

Stale views = seconds × views per second. New TTL = 1,000 ÷ 50 seconds.

Hard

Hard 1: Where should the cache live (45 minutes)

A page needs 12 values for each request. Compare three places for the cache: inside the application, a cache server in the same data centre, and a distant server. Compute the read time for all 12 values at each place using the table in section 3, and the same for a database on a spinning disk. Then state which place you would choose and what it costs.

Done when: four totals and a choice with its trade-off.

Hint

Multiply the per-read cost by 12 for each place.

Hard 2: A cache that does not help (45 minutes)

A system logs 1 million requests, and 700,000 of them ask for keys never seen before in the log. Compute the best possible hit ratio for an unlimited cache. Explain what share of misses comes from first requests (called cold misses), and suggest two changes that could still reduce database load.

Done when: a maximum hit ratio, the cold-miss share and two changes.

Hint

A first request for a key can never be a hit, however large the cache is.

Hard 3: Cache or index (50 minutes)

A query scans a table of 20 million rows and takes 2 seconds. It is called 500 times per minute with 40 different parameter values. Compute the time saved per minute with a cache that has a 95 percent hit ratio (assume the cache read costs nothing). Then describe how an index on the filtered column might change the picture, and when you would still want the cache.

Done when: a time-saved figure, a discussion of the index and a decision rule.

Hint

Misses per minute = 500 × 0.05. Each miss costs 2 seconds.