CSE Roadmap

Common tier · about 3 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Name the design (20 minutes)

Name the routing design in each case: clients talk to a load balancer that sends to any node and the node forwards; clients hold a copy of the map and call the owner; a separate tier of machines forwards to data nodes.

Done when: three names.

Hint

Who makes the routing decision in each?

Easy 2: The two layers (20 minutes)

A store uses hash mod 64 to find the partition and a table for partition to node. A node is added. Which layer changes, and which stays?

Done when: a statement for each layer.

Hint

The key-to-partition rule does not depend on the node count.

Easy 3: Forward share (20 minutes)

A cluster has 12 nodes and clients send each request to a random node. What share of requests need a forward? How many extra hops per second at 6,000 requests a second?

Done when: a share and a hop count.

Hint

A random node owns 1 in 12. The rest need a forward.

Medium

Medium 1: Compare the paths (30 minutes)

With 0.4 ms per hop and 1.5 ms of processing, compute the time for the three designs when the map is right. For any-node routing with 8 nodes compute the average.

Done when: four times.

Hint

Map right: client to owner uses 2 hops. A router uses 4.

Medium 2: Failover cost (30 minutes)

A partition gets 80 writes a second. Failure detection takes 15 seconds and routers learn the new map 2 seconds after the election, which takes 3 seconds. Compute the writes affected and the retries needed with one retry per failed write.

Done when: a write count and a retry count.

Hint

Affected time = detection + election + notification.

Medium 3: Gossip rounds (30 minutes)

500 nodes use gossip where every node that knows tells 3 random nodes per round. Estimate the rounds until nearly all know, with growth by a factor of 4 per round at first.

Done when: a round count with the working.

Hint

Each round multiplies the number of knowing nodes by about 4.

Hard

Hard 1: Stale router (45 minutes)

A router misses the notification of a partition move and keeps using the old map. Describe step by step what happens to a read and a write for that partition, with the old owner's behaviour, the retry and the router's recovery. Compute the extra latency and the writes at risk if no retry exists.

Done when: a numbered flow and two numbers.

Hint

The old owner must reject, not apply, writes for a partition it gave away.

Hard 2: Design the control plane (45 minutes)

Design the config store and routers for a 100-node store with 1,000 partitions: how many config store nodes, what is stored, who subscribes, what the routers do if the config store is unreachable, and how a split of the network is handled.

Done when: a design with counts and failure behaviours.

Hint

A coordination service usually runs 3 or 5 nodes.

Hard 3: Pick the routing style (50 minutes)

A mobile app uses a sharded store through a public API. Compare any-node, routing tier and smart client for it. Choose, and defend the choice with latency, security, upgrade and failure arguments.

Done when: a comparison and a defended choice.

Hint

A public API cannot expect clients to hold internal maps.