Part 5 of 5 · 4 min read
Exercises
Easy
Easy 1: Name what timestamp ordering assigns (15 minutes)
State what timestamp ordering assigns to each transaction, and when.
Done when: a unique timestamp assigned when the transaction begins is correctly described.
Hint
A unique timestamp, assigned at the moment the transaction begins.
Easy 2: Name the three phases of optimistic concurrency control (15 minutes)
Name the three phases of optimistic concurrency control in order.
Done when: the read phase, the validation phase, and the write phase are all correctly named in order.
Hint
The read phase, the validation phase, and the write phase.
Easy 3: State what Thomas' write rule does differently (15 minutes)
State, in one sentence, how Thomas' write rule treats an outdated write differently from plain timestamp ordering.
Done when: ignoring the outdated write instead of rejecting the whole transaction is correctly described.
Hint
It ignores the outdated write rather than rejecting the entire transaction that issued it.
Medium
Medium 1: Decide the outcome of an out-of-order write under plain timestamp ordering (25 minutes)
Under plain timestamp ordering, transaction A, with an earlier timestamp, attempts to write a row that a later-timestamped transaction B has already read. Determine the outcome.
Done when: transaction A being rejected, since its write would violate the required timestamp order relative to B's earlier read, is correctly concluded.
Hint
Transaction A is rejected, since its write would violate the required order relative to B's already-completed, later-timestamped read.
Medium 2: Decide the outcome of the same write under Thomas' write rule (25 minutes)
Under Thomas' write rule, transaction A's write, timestamped earlier, arrives after transaction B's write, timestamped later, to the same row, with no intervening read. Determine the outcome.
Done when: A's outdated write being simply ignored, rather than transaction A being rejected outright, is correctly concluded.
Hint
A's outdated write is simply ignored under Thomas' write rule, since it would never have been visible to any reader once B's newer write landed.
Medium 3: Decide when optimistic concurrency control detects a conflict (30 minutes)
A transaction under optimistic concurrency control reads a row, computes a new value, and another transaction commits a conflicting change to that same row before this transaction's own commit. Determine at what point this conflict is detected.
Done when: the validation phase, immediately before this transaction's own commit, is correctly identified as when the conflict is detected.
Hint
The validation phase, which happens immediately before this transaction's own attempted commit.
Hard
Hard 1: Explain why Thomas' write rule only applies to write-write conflicts (30 minutes)
Explain why Thomas' write rule, ignoring an outdated operation rather than rejecting it, applies specifically to a write arriving after a newer write, and not to a write arriving after a newer read.
Done when: the explanation correctly notes an outdated write really would never be visible to any reader once a newer write has already landed, making it safe to discard, whereas a write arriving after a newer read would actually change a value that reader already observed, which cannot simply be ignored without breaking correctness.
Hint
An outdated write really would be immediately overwritten and never seen by any reader once a newer write exists, making it safe to discard; but a write landing after a newer read would change a value that read already relied upon, which cannot be ignored without producing an incorrect result for that reader.
Hard 2: Compare restart costs between timestamp ordering and optimistic concurrency control (35 minutes)
Explain why a workload with very frequent conflicts would likely perform worse under optimistic concurrency control than under locking, even though both can guarantee serializability.
Done when: the explanation correctly notes optimistic concurrency control only detects conflicts at validation, after a transaction has already done its read-phase work, so frequent conflicts mean frequent wasted work and restarts, whereas locking would have made a conflicting transaction wait instead, avoiding the wasted computation.
Hint
Since optimistic concurrency control only checks for conflicts at the validation phase, after read-phase work is already done, frequent conflicts mean that work is frequently wasted and transactions frequently restarted, while locking instead makes a conflicting transaction wait, avoiding that wasted computation.
Hard 3: Choose a protocol for a stated workload (40 minutes)
A workload consists of many short transactions that very rarely conflict with each other, each doing a modest amount of read-phase computation. Decide whether optimistic concurrency control or locking is likely the better fit, and explain why.
Done when: optimistic concurrency control is reasonably chosen, with the explanation correctly citing the rarity of actual conflicts meaning few costly restarts, while avoiding lock acquisition and waiting overhead on every single transaction, which could otherwise be unnecessary cost for a workload with little real contention.
Hint
Optimistic concurrency control is a reasonable fit here, since real conflicts are rare, so restarts are infrequent and cheap overall, while the workload also avoids the lock acquisition and waiting overhead that locking would impose on every transaction regardless of whether a conflict was ever going to occur.