CSE Roadmap

Core tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Choose the place (20 minutes)

Choose in-process, shared, replicated or distributed for: a list of 200 country names, session data for 1 million users, live seat availability, the top 100 products. Give one reason for each.

Done when: four choices with reasons.

Hint

Ask how big the data is and how often it changes.

Easy 2: Database reads from in-process caches (20 minutes)

A key is cached in each of 120 application servers with a TTL of 20 seconds. Compute the database reads per minute for this key, and compare with a shared cache that reloads it once per TTL.

Done when: two numbers.

Hint

Reads per minute = servers × 60 ÷ TTL.

Easy 3: Mod N moves (20 minutes)

With hash mod N, about what share of keys move when N goes from 4 to 5, and from 20 to 21? Compare with consistent hashing at the same steps.

Done when: four shares.

Hint

Mod N: about N ÷ (N + 1) of keys move. Consistent hashing: about 1 ÷ (N + 1).

Medium

Medium 1: Size a cluster (30 minutes)

The hot set with spare room is 200 GB. A node has 64 GB with 75 percent usable for data. Traffic is 900,000 reads a second and a node does 150,000. Compute the nodes needed for memory and for throughput, and choose a final count with failure room.

Done when: two node counts and a final choice with a reason.

Hint

Nodes for memory = hot set ÷ usable memory per node, rounded up.

Medium 2: Add a node (30 minutes)

A ring has 8 nodes and 4,000,000 keys. Compute the keys moved when a ninth node joins using consistent hashing and using mod N (about 8/9 of keys move). Say what the database sees in each case if all moved keys miss once.

Done when: two key counts and a database load comment.

Hint

Consistent hashing moves about 4,000,000 ÷ 9 keys.

Medium 3: Two-layer cache (30 minutes)

A service has 100 servers. Each keeps a local cache with a 3-second TTL in front of a shared cache. A hot key gets 200,000 reads a second in total. Compute reads reaching the shared cache with and without the local layer, assuming each server reloads the key once per TTL.

Done when: two rates and the staleness cost.

Hint

With the local layer: 100 servers ÷ 3 seconds.

Hard

Hard 1: Cache outage plan (45 minutes)

A site has 80,000 reads a second, a 96 percent hit ratio and a database limit of 5,000 reads a second. The shared cache fails. Design a plan with local caches, load shedding and a refill. Show the database load at each step and what users see.

Done when: a numbered plan with loads and a user-visible effect.

Hint

Misses now are 80,000 × 0.04. The outage adds the former hits.

Hard 2: Replicated or distributed (45 minutes)

A game server has 30 processing units. It holds a 50 MB item catalogue changed weekly, and 6 GB of player inventories changed every second. Choose a cache type for each, with the memory used in total, the update traffic, and the failure behaviour.

Done when: two choices with memory, traffic and failure notes.

Hint

Replication copies the data to every unit. Distribution stores it once.

Hard 3: Draw the full cache design (50 minutes)

Draw the cache layout for an online shop with 100 application servers: local caches, a shared cluster with consistent hashing, the database, and the miss path. Mark every number: TTLs, nodes, hit ratios, database load. State what you would watch.

Done when: a labelled drawing, a numbers table and a list of signals.

Hint

Keep your numbers consistent with the earlier modules.