CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 8 of 8 · 3 min read

Exercises

Easy

Easy 1: Replication or partitioning (20 minutes)

For each need, say replication, partitioning or both: survive a machine failure, store 40 TB on machines of 4 TB, serve 10 times more reads of the same data, take 10 times more writes.

Done when: four answers with reasons.

Hint

Replication copies, partitioning splits.

Easy 2: Find the partition (20 minutes)

Four partitions hold hash ranges 0-24, 25-49, 50-74, 75-99. Give the partition for keys with hashes 7, 25, 61, 99 and 50.

Done when: five partition numbers.

Hint

Find the range that holds each hash.

Easy 3: Spot the hot spot (20 minutes)

Say whether each key choice creates a hot spot, and why: order id counting upwards with range partitioning, user id hashed, country code with range partitioning when 70 percent of users are in one country, timestamp first for sensor writes.

Done when: four verdicts with reasons.

Hint

Look for keys that grow in order or cluster.

Medium

Medium 1: Capacity under skew (30 minutes)

12 nodes can each take 3,000 writes per second. One partition gets 25 percent of all writes, and the other 11 share the rest evenly. Compute the highest total write rate before a node saturates.

Done when: a rate and the saturated node.

Hint

The saturating node limits the total: 3,000 ÷ 0.25.

Medium 2: Fix the sensor key (30 minutes)

2,000 sensors send one reading a second each, with 20 partitions. Compute writes per partition for timestamp-first keys with one partition per hour, and for sensor-first keys. Then state the cost of a query for all sensors in the last hour.

Done when: two per-partition rates and one query cost.

Hint

With sensor-first keys, writes per partition = 2,000 ÷ 20.

Medium 3: Split a hot key (30 minutes)

A key gets 24,000 writes per second, and a partition limit is 4,000. Compute the fewest sub-keys. How many reads does a full read need? State when you would stop splitting.

Done when: a count of sub-keys, a read cost and a stopping rule.

Hint

Sub-keys needed = 24,000 ÷ 4,000, rounded up.

Hard

Hard 1: Partition a messaging app (45 minutes)

Design the partitioning of a messaging app: key, hash or range, how conversations are kept together, the query "latest 50 messages of a conversation", and the hot conversation case (a group chat with 100,000 people). Give numbers.

Done when: a key, two query costs and a hot-conversation plan.

Hint

Keep one conversation on one partition.

Hard 2: Size the cluster (45 minutes)

A data set will grow to 80 TB in two years, with 30,000 writes per second at peak. A node holds 4 TB and does 2,500 writes per second, with 3 copies of each partition. Work out the partitions, nodes and copies per node, with a margin of 30 percent.

Done when: counts with working and the margin shown.

Hint

Partitions by size = 80 ÷ 4. Partitions by writes = 30,000 ÷ 2,500. Take the larger, then add 30 percent.

Hard 3: Compare schemes on one workload (50 minutes)

For an order system (orders have id, user, time, status), compare key-range on time, hash on order id, and hash on user id with time sorted inside. For the queries "an order by id", "a user's orders in a month" and "all orders yesterday", give partitions touched. Choose one and defend it.

Done when: a 3 × 3 table of partitions touched and a decision.

Hint

A date range with time-first keys touches only the partitions in range, but all writes hit one.