CSE Roadmap

Common tier · about 4 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Single or multi (20 minutes)

Say whether single-leader or multi-leader fits better, with a reason: a bank ledger in one country, a calendar that works offline, an online shop with users on three continents and few shared records, a shared document edited by ten people.

Done when: four choices with reasons.

Hint

Ask whether users must write when the link to a far region is cut.

Easy 2: Quorum check (20 minutes)

For n = 5 with (w, r) = (3, 3), (4, 2), (2, 2) and (5, 1), say whether w + r > n and how many failed nodes writes and reads tolerate.

Done when: a four-row table.

Hint

Failed nodes tolerated for writes = n − w. For reads = n − r.

Easy 3: Pick the resolution (20 minutes)

Choose avoid, LWW, merge, CRDT or ask-the-user for: a like counter, a user's profile photo, a shared shopping list, a wiki page edited by two people at once.

Done when: four choices with reasons.

Hint

A counter and a set can merge. A photo needs one winner.

Medium

Medium 1: Latency gain (30 minutes)

Two regions are 150 ms apart. A checkout makes 4 sequential writes. Compute the checkout write time in the far region with a single remote leader (150 ms plus 5 ms each) and with a local leader (5 ms each). What do you give up?

Done when: two times and a trade-off.

Hint

Single remote leader = 4 × 155 ms.

Medium 2: LWW loses a write (30 minutes)

Two replicas have clocks that differ by 3 seconds. Write a timeline in which LWW keeps the earlier write, and say what the users see.

Done when: a timeline with timestamps and the final value.

Hint

Give the later write the smaller timestamp.

Medium 3: Read repair (30 minutes)

n = 5, w = 3, r = 3. Replicas 1, 2, 3 hold version 9 and replicas 4, 5 hold version 8. A read asks replicas 3, 4, 5. What does the client return, and which writes does read repair make? What if the read asks 1, 2, 3?

Done when: two read outcomes with repairs.

Hint

The client takes the highest version it sees, and writes it to stale replicas among those read.

Hard

Hard 1: Design a shopping cart (45 minutes)

Design a shopping cart on a leaderless store with n = 3. Choose w and r, and the merge rule when two devices change the cart at once. Show the "removed item comes back" bug and how your rule avoids it.

Done when: values for w and r, a merge rule, a bug timeline and a fix.

Hint

Merge the sets of added items, and track removals explicitly.

Hard 2: Sloppy or strict (45 minutes)

A store has 9 nodes, n = 3, w = 2, r = 2. A network split isolates 2 nodes from the other 7. Describe reads and writes for keys homed on the isolated nodes under a strict quorum and a sloppy quorum. Give the risk of stale reads in each and the repair steps.

Done when: a comparison table and a repair description.

Hint

A sloppy quorum accepts writes on stand-in nodes.

Hard 3: Choose the replication model (50 minutes)

A chat service has users on three continents and needs writes to work during a region outage. Compare single-leader with failover, multi-leader with home regions, and leaderless with quorums. Say which you choose, the conflict handling, the guarantees users get and the monitoring.

Done when: a three-way comparison, a choice, and a monitoring list.

Hint

Compare the loss on a region outage, the latency and the conflict risk.