Origin

  • 2PL: invented 1976 at IBM (9:50).
  • OCC: invented 1981 at CMU by Prof. H. T. Kung — who was a networking person, not a database person, which is why the phase names are odd. He later left for Harvard (9:50, 10:57).

The core idea: private workspaces

  • On BEGIN, the DBMS allocates a private workspace for the transaction (8:18).
  • Every read and every write is copied into that workspace; no other transaction can look inside it while it runs. Writes therefore need no locks on the global tuples (8:36).
  • At commit, the workspace is compared against the global database / other transactions to detect conflicts since the transaction started (9:06).
  • If no conflicts, the changes are installed into the global database and become visible (9:37).

What the "private workspace" actually is

  • At this level of abstraction: a memory space the transaction can read/write, in practice backed by the buffer pool — but the protocol does not care (12:47, 13:04).
  • It must still be thread-safe / latched: multiple threads can execute queries on behalf of the same transaction and touch the same buffer (15:05).
  • Memory cost is real, but "there is no free lunch": either you maintain a lock table for a billion tuples, or you copy a billion tuples (13:27).
    • Delta copying mitigates it — copy only the modified attribute, not the whole tuple. This is what CMU Project 4 asks students to implement (13:27).
    • PostgreSQL does not do this: it copies the entire tuple regardless of how many attributes changed, though it does not copy on reads (14:02).

The three phases

graph LR
    B["BEGIN — allocate private workspace"] --> R["1. READ phase<br/>reads/writes go to private workspace"]
    R --> V["2. VALIDATION phase<br/>timestamp assigned HERE, check conflicts"]
    V -->|pass| W["3. WRITE phase<br/>install changes, set WTS on tuples"]
    V -->|fail| A["ABORT"]
  1. Read phase — the transaction reads and writes, but everything is copied from the global state into the private workspace. Subsequent reads of an already-copied object read the private copy, which is what guarantees repeatable reads (11:20, 19:38).
    • Copying on read is optional: if you don't need repeatable reads, skip it (19:38).
  2. Validation phase — entered on COMMIT. This is where the timestamp is assigned — transactions do not get timestamps when they arrive. The system checks for conflicts against transactions that completed in the past or are running right now (11:48, 12:10).
  3. Write phase — changes are applied to the global database and each touched tuple's write timestamp (WTS) is set to the committing transaction's timestamp (12:10).

Worked example (T1 starts first, T2 commits first)

  • Each record in the global database carries (object, value, WTS); the initial WTS is 0 (14:20).
  • T1 begins, reads A → copies A plus its WTS into its workspace (15:29).
  • T2 begins, reads A → its own copy (15:51).
  • T2 commits first, so T2 gets timestamp 1 even though T1 arrived first — arrival order no longer equals commit order (16:19, 16:39).
  • T2 is read-only → no conflict, write phase does nothing, workspace is discarded (16:53).
  • T1 writes A in its workspace with WTS = ∞, because it has no timestamp yet (17:17).
  • T1's next read of A hits its own workspace copy — repeatable reads (17:45).
  • T1 validates, gets timestamp 2, passes (T2 is gone), overwrites the ∞ with 2, installs the change (18:01, 18:17).
  • Equivalent 2PL execution: both take shared locks on A (compatible), T2 commits, T1 upgrades to exclusive — same outcome (19:06).

Open implementation questions flagged

  • Indexes vs. workspaces: if an index points at the global database, a transaction must additionally check whether the record ID it found is already in its own read/write set (19:59).
  • Repeatable read defined: read the same value, read it again immediately, get the same value (22:02).
  • Systems that don't guarantee it exist — PostgreSQL's default gives read committed (22:16).