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.