Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: Allowed or not (20 minutes)
A write of x = 1 runs from t = 10 to t = 30. Say whether each read is allowed in a linearizable system: starts 5 ends 8 returns 0; starts 12 ends 15 returns 1; starts 18 ends 20 returns 0; starts 31 ends 33 returns 0.
Done when: four answers with reasons.
Hint
A read starting after a completed write must see it.
Easy 2: Name the model (20 minutes)
Name the weakest model that satisfies each story: bank balance; page view counter; replies never before questions; every replica applies the same order.
Done when: four names.
Hint
Counters can lag. Money cannot.
Easy 3: Serializable or linearizable (20 minutes)
For each need, say which property helps: stop write skew; always read the latest value of one key; both together.
Done when: three answers.
Hint
One is about transactions and the other about recency.
Medium
Medium 1: Quorum trace (30 minutes)
n = 5, w = 3, r = 3. A write has reached nodes 1, 2 and 3 only so far (it is not finished). Client A reads nodes 1, 4, 5. Client B reads nodes 2, 3, 4 later. Work out the values each reads. Is there a case that breaks linearizability? Explain.
Done when: read sets, values and a verdict.
Hint
Count which nodes hold the new value in each read set.
Medium 2: Pick a model (30 minutes)
Choose a model for each: a chat message list, a shopping cart, a seat reservation, a profile photo URL, a leaderboard. Give a reason and the failure you accept.
Done when: five rows.
Hint
Ask what the user sees if the value is a bit old.
Medium 3: Partition behaviour (30 minutes)
Two data centres lose their link for 10 minutes. For single-leader and multi-leader setups, say what users in each data centre can do. Where is the leader?
Done when: a table of two setups by two sites.
Hint
The side without the leader cannot write in a single-leader setup.
Hard
Hard 1: Fix the thumbnail bug (45 minutes)
A photo service writes a file, then sends a queue message, and the resizer sometimes reads an old file. Propose three fixes: a linearizable store, passing a version in the message, and a retry rule. Compare.
Done when: three fixes with a trade-off each.
Hint
A version number in the message tells the resizer which file it needs.
Hard 2: Unique usernames at scale (45 minutes)
Design username registration for 20 million users in two regions. Keep names unique. Describe the store, what happens when the inter-region link breaks, and a looser alternative.
Done when: a design, a failure story and an alternative.
Hint
A single linearizable store for names needs a consensus group.
Hard 3: Causal feed (50 minutes)
Design a social feed where replies never appear before the post they answer, without making the whole store linearizable. Say what you store with each post, how a replica decides to hold a reply back, and what the cost is.
Done when: a design with fields, a hold rule and one cost.
Hint
Store the id of the post each reply depends on.