CSE Roadmap

Common tier · about 3 hours · 6 parts

Part 6 of 6 · 2 min read

Exercises

Easy

Easy 1: Define serializable (20 minutes)

Explain serializable isolation to a friend in three sentences, using the two-doctor story.

Done when: three sentences that mention "as if one at a time".

Hint

The result matches some serial order, not necessarily the real arrival order.

Easy 2: Match the recipe (20 minutes)

Match each phrase to serial execution, 2PL or SSI: "readers block writers"; "abort at commit"; "stored procedures"; "deadlock detection".

Done when: four matches.

Hint

Only 2PL blocks readers; only SSI aborts at commit.

Easy 3: Shared or exclusive (20 minutes)

Say which lock is taken: reading a balance; changing a balance; reading then changing it.

Done when: three answers, with the upgrade mentioned.

Hint

Read is shared, write is exclusive, read-then-write upgrades.

Medium

Medium 1: Throughput arithmetic (30 minutes)

A transaction takes 40 microseconds in memory and 2 milliseconds if it waits for the application once. Compute transactions per second on one thread for each. Then compute 6 partitions with no cross-partition work.

Done when: three numbers and one sentence about stored procedures.

Hint

Per second = 1,000,000 divided by microseconds per transaction.

Medium 2: Draw a deadlock (30 minutes)

Two transactions each update accounts X and Y, in opposite order. Draw a timeline that deadlocks. Then show a fix by ordering the locks the same way.

Done when: two timelines.

Hint

Opposite lock order is the cause.

Medium 3: SSI trace (30 minutes)

Two cashiers each read "total cash in the till is at least 100" and each withdraw 80 from different tills of one shared pool of 120. Trace SSI and say which transaction aborts and what the retry does.

Done when: a trace with the abort and the retry result.

Hint

The first commit wins; the second read a premise that changed.

Hard

Hard 1: Pick for a workload (45 minutes)

Pick a recipe for: a game leaderboard in memory, a bank ledger with mixed reads, a booking system with many hot rows. Justify with contention, latency and data size.

Done when: three picks with reasons and one risk each.

Hint

Hot rows hurt 2PL waits and SSI aborts alike.

Hard 2: Index-range lock (45 minutes)

A booking table has an index on (room, start_time). Describe which lock the search "room 7, 12:00 to 13:00" takes and which writes it blocks. Then describe the fallback with no index.

Done when: a description with one blocked and one allowed write, and the fallback.

Hint

The lock covers the index range, so other rooms are free.

Hard 3: Retry design (50 minutes)

Design the retry loop for a serializable transaction: which errors to retry, how many tries, waiting time, and how to keep side effects (such as sending an email) from happening twice.

Done when: a list of rules and a short pseudo-code loop.

Hint

Do side effects after the commit, with an idempotency key.