Naive Concurrency
Concept. A database runs many transactions at once, and the hard part is coordinating how they touch shared rows. The simplest rule, running one transaction at a time, keeps the data correct but leaves the server idle through every disk wait while the queue backs up. Drop the coordination to go faster and the opposite breaks: two writes to the same row overwrite each other, with no error raised. Concurrency control is the middle ground: run independent work in parallel, block only what would conflict.
Intuition. Mickey and Minnie both play song 42, which sits at 100. Run them one at a time and the play count correctly reaches 102, but everyone else is stuck behind one slow disk read. Drop the coordination and both read 100, both write 101, and one play disappears.
Naive way 1: run them one at a time
The simplest approach: never overlap. Run each transaction from start to finish before the next one begins.
# Serial: one transaction fully finishes before the next starts
for txn in queue:
txn.run() # no interleaving is even possible
Nothing interleaves, so nothing goes wrong. But it is slow, in two ways.
First, a transaction spends most of its time waiting on a disk read, which takes thousands of times longer than the computing around it.
Figure 1. One disk read (the dashed span between the two violet markers, its start and end) stalls the transaction far longer than the work around it. Under serial execution, nothing runs in that gap.
Second, because only one transaction runs at a time, that idle gap is pure waste, and a single long transaction blocks everyone behind it.
Figure 2. Serial execution wastes every wait. The violet blocks are transactions computing; the grey blocks are the server idle on disk. Because no one else may run in a gap, a long transaction (T2) stalls the whole queue: T3 and T4 wait far longer than their own work needs. The Ticketmaster on-sale would serialize into one slow line, even across unrelated rows.
Naive way 2: let them all run
To win back the parallelism, drop all coordination and let everything run at once. Two transactions on different rows never touch each other. Two on the same row collide: their reads and writes interleave, and the result depends on which one happens to write last.
# No coordination: read, change, write back
def play(song_id):
n = db.read(song_id, "play_count") # read the current count
db.write(song_id, "play_count", n + 1) # store one more
Nothing forces the read and the write to stay together. Slip another transaction between them and the data goes wrong, in more than one way.
Figure 3. Uncontrolled concurrency corrupts one row three different ways. In a lost update, two transactions both read 100 and both write 101, so one play disappears. In a dirty read, one transaction reads another's uncommitted write and the writer then aborts, so the reader acted on a value that never existed. In a stale read, a transaction reads the same row twice and a committed write in between makes its two reads disagree.
No error is raised. Every transaction reports success, and the database holds a number that no one-at-a-time run could ever produce.
The middle: concurrency control
Neither extreme is usable. Every real database aims for the middle.
Figure 4. Concurrency control sits between the two naive ends, overlapping only the actions whose order does not matter. Serial (Naive 1), on the left, is correct but has no throughput; free-for-all (Naive 2), on the right, has throughput but corrupts data. The rest of this section makes "order does not matter" precise, then builds the engines that deliver it.
Two questions remain, and the module takes them in order: what makes an interleaving correct, and how does an engine deliver it without serializing everything? The next page starts on the first, with the conflict graph the test is built on.