CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Size the cluster (20 minutes)

Data is 2 billion pairs of 2 KB, kept in 3 copies, on nodes with 2 TB usable. Add 33 per cent headroom. How many nodes?

Done when: you write 12 TB for 3 copies, 6 nodes without headroom, and 8 with it.

Hint

2,000,000,000 × 2 KB is 4 TB per copy.

Easy 2: Choose N, W, R (20 minutes)

For N = 3, say whether each setting gives strong consistency: (W=1,R=1), (W=2,R=2), (W=3,R=1), (W=1,R=3), (W=2,R=1).

Done when: five answers: no, yes, yes, yes, no.

Hint

Strong consistency needs W + R greater than N.

Easy 3: CP or AP (20 minutes)

For a bank balance, a social media like count, a shopping cart and a seat booking, say CP or AP with a reason.

Done when: four rows with a choice and a reason each.

Hint

Which is worse, a wrong answer or no answer?

Medium

Medium 1: Compare vector clocks (30 minutes)

For each pair say ancestor, descendant or conflict: ([A,1]) and ([A,2]); ([A,2],[B,1]) and ([A,2],[B,2]); ([A,1],[B,2]) and ([A,2],[B,1]); ([A,3]) and ([B,1]).

Done when: four answers: ancestor, ancestor, conflict, conflict.

Hint

A clock is an ancestor if every counter is at least as big.

Medium 2: Trace a quorum (30 minutes)

N = 3, W = 2, R = 2. A write goes to copies 1 and 2 and copy 3 is slow. Then a read reaches copies 2 and 3. Show that the read sees the new value, and what the read does about copy 3.

Done when: a table with each copy's value and version, and a note about read repair.

Hint

Copy 2 is in both the write set and the read set.

Medium 3: Draw the node (30 minutes)

Draw one node with its commit log, memory cache, SSTables and Bloom filter, and number the steps of a write and of a read.

Done when: one diagram with both paths numbered.

Hint

The commit log comes before the cache on a write.

Hard

Hard 1: Simulate gossip (60 minutes)

Write a program with 20 nodes, each sending its heartbeat table to 3 random nodes every second. Stop one node, and measure how many seconds until all others mark it down.

Done when: a plot or table of detection time over 20 runs, and a note on how it changes with 100 nodes.

Hint

Pick random peers with a seeded generator.

Hard 2: Merkle comparison (60 minutes)

Build a Merkle tree over 16 buckets. Change 2 keys on one replica. Find the differing buckets by comparing trees, and count the hash comparisons used.

Done when: the program prints the two differing buckets and the number of hash comparisons, which should be well below the cost of comparing every key.

Hint

Compare the root first and go down only where hashes differ.

Hard 3: Mock interview (60 minutes)

Answer "design a key-value store" aloud in 35 minutes and mark yourself on the four steps. List two missed topics.

Done when: a recording, a score on each step, and two named gaps.

Hint

Use the four-step framework as a checklist.