CSE Roadmap

Common tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Ping or heartbeat (20 minutes)

Say whether each is a ping or a heartbeat: a load balancer asking a server "are you up"; a worker sending "I'm alive" every 2 seconds; a monitor checking a database port; a leader telling followers its term.

Done when: four labels.

Hint

A ping is asked for; a heartbeat is volunteered.

Easy 2: Safety or liveness (20 minutes)

Label each statement: "never two leaders"; "an election finishes eventually"; "no node votes twice in one term"; "the cluster is never leaderless for more than a minute".

Done when: four labels with one reason each.

Hint

Safety is about bad things not happening; liveness is about good things arriving.

Easy 3: Majority sizes (20 minutes)

Compute the majority and the number of failures tolerated for 3, 5 and 7 nodes.

Done when: a table of three rows.

Hint

Majority is more than half. Failures tolerated equals nodes minus majority.

Medium

Medium 1: Trace an election (30 minutes)

Seven nodes, leader 1 crashes in term 3. Node 6 times out first. Nodes 2, 3 and 4 vote for 6, node 5 voted for 7 already, and node 7 is a candidate too. Compute votes and the outcome. What term is it?

Done when: a vote count, a result and a term number.

Hint

Count votes, including the candidate's vote for itself. Need 4 of 7.

Medium 2: Tune the timeout (30 minutes)

Heartbeats arrive every 500 ms. A pause of 3 s happens about once a day. Pick an election timeout and justify it with false alarm rate and failover time. Give the random range.

Done when: a number, a range and a two-line trade-off.

Hint

The timeout should be longer than the common pause or you will elect on every pause.

Medium 3: Lease timeline (30 minutes)

A lease has TTL 12 s and is renewed every 4 s. A worker freezes at second 9 after renewing at second 8. When does the key expire? When can another worker take over? When is the earliest the frozen worker could be wrong about holding it?

Done when: three times and a short reason.

Hint

Expiry is the last renewal plus the TTL.

Hard

Hard 1: Split vote probability (45 minutes)

Three followers time out with a random delay uniform in [150, 300] ms and a vote request takes 20 ms to reach everyone. Estimate how often two timeouts fall within 20 ms of each other. Explain how widening the interval helps.

Done when: a rough estimate and a conclusion about the interval.

Hint

Two timeouts clash when they are close together within the vote delay.

Hard 2: Design a job leader (45 minutes)

Design the leader for a nightly report job across 4 machines using etcd or ZooKeeper. Give the key, the TTL, the renewal rule, the fencing token use and what the job does when it loses the lease.

Done when: a written design with five parts.

Hint

The job should stop writing when it cannot renew.

Hard 3: Leader at scale (50 minutes)

A single leader handles 5,000 writes per second but the product needs 40,000. Propose a design with a leader per partition. Give the partition count, how leaders are placed, and what happens when one leader fails.

Done when: a design with numbers and a failure story.

Hint

40,000 divided by 5,000 is at least 8 leaders, so plan for more.