Timestamp ordering and optimistic concurrency

Why it matters

Locking makes transactions wait. Two other families of protocols avoid waiting by deciding the serial order in advance (timestamp ordering) or by checking for conflicts only at the end (optimistic concurrency control). They appear in exams alongside 2PL, inside real systems (validation-based engines, distributed databases, in-memory stores), and, in their simplest form, in nearly every web application as "optimistic locking" with a version column.

The idea

Timestamp ordering

Each transaction gets a unique timestamp when it starts, TS(Ti), and the protocol forces the schedule to be equivalent to running transactions in timestamp order. Each data item X records the largest timestamp of any transaction that has read it, R-TS(X), and that has written it, W-TS(X).

Transactions never wait, so there are no deadlocks; instead, transactions that arrive "too late" are aborted and restarted with a new timestamp. The Thomas write rule improves throughput: if a younger transaction already wrote X and nobody read Ti's would-be value in between, Ti's write is obsolete and can simply be skipped. That admits some view-serializable schedules that are not conflict serializable (the blind-write case from the serializability lesson). Basic timestamp ordering can produce unrecoverable schedules unless commits are delayed until the transactions read from have committed, so practical versions add that rule.

Optimistic concurrency control

Optimistic concurrency control (OCC) assumes conflicts are rare. Each transaction runs in three phases.

1. 1

   Read phase

   Execute the transaction, reading from the database and buffering all writes privately. Record the read set and write set.
2. 2

   Validation phase

   At commit, check whether any transaction that committed while this one ran wrote something this one read (or, depending on the scheme, overlaps with its write set). If so, abort and restart.
3. 3

   Write phase

   If validation passes, apply the buffered writes to the database. Validation and write happen atomically, typically in a short critical section.

Optimistic locking in applications

The same idea appears at application level: add a version column, read the row with its version, and update with a condition on it.

UPDATE accounts
SET balance = 450, version = version + 1
WHERE id = 42 AND version = 7;
-- 0 rows updated means someone else changed it: reload and retry, or report a conflict

It holds no locks while a user edits a form for minutes, which pessimistic locking (SELECT FOR UPDATE) cannot afford. HTTP's ETag with If-Match, from the System Design REST lesson, is the same pattern over an API.

Choosing among the families

Trade-offs

Pessimistic locking wastes time waiting when conflicts are rare; optimistic schemes waste whole transactions when conflicts are common, and can starve long transactions that keep losing validation. Timestamp ordering avoids deadlocks by design at the cost of restarts and timestamp bookkeeping on every item. Most production databases combine approaches: multiversioning for reads, locks for writes, and optimistic version checks in the application for long-running edits.

In an interview

Pick by contention: "Booking the last seat in a flash sale is high contention on one row, so I lock it briefly with SELECT FOR UPDATE inside a short transaction. Editing a product description in an admin form is low contention and slow, so I use a version column and reject stale saves with a conflict message." Then mention that OCC and timestamp schemes cannot deadlock.