CSE Roadmap

Core tier · about 4 hours · 7 parts

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.