Naive Concurrency
Concept. Concurrency control keeps shared data correct while transactions run together. 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.
I/O lag
An I/O operation takes time between its start and completion. The issuing transaction waits; the CPU can run other work during that interval.
Figure: I/O lag: reads and writes take timeTwo timelines show read start RS to read end RE, and write start WS to write end WE. Each start-to-end interval takes five time units in this example. Thin vertical lines mark the events and dashed spans show the wait. In practice, I/O can take millions of CPU cycles, depending on the device and operation.
Figure 1. I/O lag is the time from read start (RS) to read end (RE), or write start (WS) to write end (WE). Here it takes 5 time units. In practice, I/O can take millions of CPU cycles.
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
Serial execution prevents other transactions from using that waiting time. A long transaction blocks everyone behind it.
Figure: Naive Way 1: run one at a timeA server runs T1 and then T2. Short white compute blocks alternate with much longer gray disk read/write waits. The storage device handles the I/O while serial scheduling leaves the CPU idle instead of running another transaction. Broken arrows indicate compressed waiting time, not a measured duration. T3 and T4 cannot run during T2’s wait.
Figure 2. The disk handles reads and writes while serial execution leaves the CPU idle. The broken arrows compress the waiting spans; they do not represent measured durations. T3 and T4 cannot run while T2 waits, even when their work touches 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: Naive Way 2: run without coordinationThree side-by-side failure panels, each a tiny two-column schedule of T1 and T2 reading and writing one row with no coordination, time running top to bottom. Left, the lost update: both read 100, both write 101, so the count lands on 101 instead of 102. Middle, the dirty read: T1 writes 150, T2 reads it, then T1 aborts, so T2 acted on a value that never committed. Right, the stale read: T1 reads 20, T2 writes 30 and commits, T1 reads again and sees 30, disagreeing with itself inside one transaction. Each panel names its conflict type: write-write, write-read, read-write. Color key: red is the corrupted result each race produces, grey is the trace.
| Lost update | Dirty read | Stale read |
|---|---|---|
| play_count = 100 | balance = 100 | price = 20 |
| read → 100 | write 150 | read → 20 |
| read → 100 | read → 150 | write 30 |
| write 101 | ABORT | commit |
| write 101 | acts on 150 | read → 30 |
| lands on 101, not 102 | T2 used 150 | T1 saw 20, then 30 |
| one play silently vanishes | a value that never committed | two reads disagree in one txn |
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: How should transactions share the database?Three approaches: serial execution, uncoordinated execution, and concurrency control. Direct labels replace a safety-versus-performance axis.
Figure 4. Concurrency control overlaps independent work while ordering conflicting actions safely.
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.