CSE Roadmap

Common tier · about 4 hours · 7 parts

Part 7 of 7 · 2 min read

Exercises

Easy

Easy 1: Quorums (20 minutes)

For groups of 3, 5 and 7 give the majority and the failures tolerated.

Done when: you write 2 and 1; 3 and 2; 4 and 3.

Hint

More than half.

Easy 2: Heartbeat load (20 minutes)

250,000 clients with a heartbeat every 10 seconds. Give the messages per second.

Done when: you write 25,000 per second.

Hint

250,000 / 10.

Easy 3: Token check (20 minutes)

A resource has seen token 57. Requests arrive with tokens 55, 57 and 58. Say which are accepted, if equal tokens are accepted.

Done when: you write 55 rejected; 57 and 58 accepted.

Hint

The resource keeps the highest token seen.

Medium

Medium 1: Trace the pause (30 minutes)

Client A gets token 12 and pauses. Client B gets token 13 and writes. A wakes up and writes. Write the steps with and without fencing.

Done when: two traces showing corruption without fencing and rejection with it.

Hint

Without a check, both writes land.

Medium 2: Data size (30 minutes)

400,000 entries with 2 KB each, and 3 copies of the log history of 2 GB. Give memory per replica and total disk across 5 replicas.

Done when: you write 800 MB per replica and about 10 GB (5 × 2 GB).

Hint

400,000 × 2 KB.

Medium 3: Timeout choice (30 minutes)

The session timeout is 6 seconds, and a client has a typical pause of 1 second but a rare pause of 15 seconds. Describe what happens in each case and what to change.

Done when: an answer that says the rare pause loses the session, and that fencing is needed.

Hint

A pause longer than the timeout loses the session.

Hard

Hard 1: Draw the election (60 minutes)

Draw the numbered election recipe with 4 candidates and show what happens when the leader and then candidate 2 fail.

Done when: two diagrams with the entry names and the watches.

Hint

Each candidate watches only the one just below it.

Hard 2: Add a read-only observer tier (60 minutes)

Design observers for 200,000 reads a second. Say how they get the log and what staleness clients may see.

Done when: a diagram, a staleness bound in milliseconds and a rule for clients that need fresh reads.

Hint

Observers do not vote.

Hard 3: Lock service API (60 minutes)

Write the API of a lock service: acquire, renew, release, with fencing tokens and errors. Give examples of client code that handles expiry.

Done when: an API list with errors and a client example that stops work when the lease is lost.

Hint

Every call should return the current token.