CSE Roadmap

Core tier · about 3 hours · 6 parts

Part 6 of 6 · 3 min read

Exercises

Easy

Easy 1: Name the letter (20 minutes)

Name the ACID letter being violated in each case: a crash leaves half an order saved; two clients both read 5 and both write 6 for an increment; committed data vanishes after a power cut; total debits no longer equal total credits.

Done when: four letters with a reason each.

Hint

Atomicity, isolation, durability, and the application's invariant.

Easy 2: Single or multi (20 minutes)

Say whether a single-object operation is enough or a multi-object transaction is needed: increase a view counter, move money between accounts, change a user's name stored in one document, update a product price copied into 3 documents.

Done when: four answers with reasons.

Hint

If more than one record must change together, use a transaction.

Easy 3: Retry or not (20 minutes)

Say whether to retry each error: a deadlock, a unique constraint violation, a timeout during failover, an out-of-memory error from overload.

Done when: four answers with how you would retry.

Hint

Transient errors are worth retrying, permanent ones are not.

Medium

Medium 1: Write the transaction (30 minutes)

Write the transaction (in pseudocode) for placing an order with 2 lines that also reduces stock and checks stock is not negative. Say which invariant you protect and which letter protects what.

Done when: pseudocode, an invariant and a letter-by-letter note.

Hint

Check stock inside the transaction, and abort if it would go negative.

Medium 2: Backoff schedule (30 minutes)

Design a retry plan with a first delay of 50 ms, doubling, 6 tries and up to 25 percent random extra. Compute the shortest and longest total wait.

Done when: two totals with the working.

Hint

With 6 tries there are 5 waits: 50, 100, 200, 400, 800 ms before the random extra.

Medium 3: Counter race (30 minutes)

Two clients each add 1 to a counter that is 10, with read, add, write. Write three interleavings, one giving 12 and two giving 11. Then show how an atomic increment or compare-and-set fixes it.

Done when: three timelines and the fix.

Hint

Both read the old value before either writes.

Hard

Hard 1: The lost acknowledgement (45 minutes)

A payment service commits and the reply is lost. Design the full flow with an idempotency key: the table, the check, the response to a retry, key expiry and the case where two retries arrive at once.

Done when: a table design, a flow and the concurrent-retry rule.

Hint

A unique constraint on the key makes concurrent retries safe.

Hard 2: Durability budget (45 minutes)

Your database writes to local disk and replicates asynchronously to one follower. List three ways committed data can be lost, give a protection for each, and say what you would still accept as risk.

Done when: three losses, three protections and a risk statement.

Hint

Think of async replication, a power cut, and silent corruption.

Hard 3: Do you need a transaction (50 minutes)

A like button increases a counter and adds a row to a "likes" table. Design it first with a transaction, then without one using a different approach (for example, derive the count). Compare cost, failure behaviour and correctness.

Done when: two designs and a comparison table.

Hint

A derived count removes the need for the second write.