Timestamp ordering and optimistic control

Locking makes a transaction wait when it meets a conflict. Timestamp ordering and optimistic control never make it wait; they abort it instead. Timestamp ordering gives every transaction a timestamp when it starts and keeps the schedule equivalent to the serial order of those timestamps. Each item remembers the largest timestamps that have read and written it, and an operation that arrives too late, after a younger transaction has used the item in a conflicting way, aborts its transaction, which restarts with a new timestamp. Optimistic control lets a transaction run without any checks, keeping its writes in a private copy, and validates at commit that no conflicting transaction got in its way; a transaction that fails validation restarts. Applications use the same idea with a version column on each row.

Two timestamps on every item

Each item Q carries R-TS(Q), the largest timestamp of any transaction that has read it, and W-TS(Q), the timestamp of the transaction that wrote it last. A larger timestamp means a younger transaction. For a transaction T:

The simulator applies the rules to one schedule. R5(A) means the transaction with timestamp 5 reads A:

"""Basic timestamp ordering, step by step. Every transaction gets a timestamp when it starts; every item keeps
R-TS, the largest timestamp that has read it, and W-TS, the timestamp of its last write. An operation that
arrives too late aborts its transaction. Set THOMAS = True to apply Thomas's write rule instead.

Notation: R5(A) means the transaction with timestamp 5 reads A, W7(B) that the one with timestamp 7 writes B.
"""
import re

SCHEDULE = "R5(A) R7(A) W7(A) R5(B) W5(A) R9(B) W7(B) W9(B)"
THOMAS = False


def run(schedule, thomas):
    rts, wts, aborted = {}, {}, set()
    for token in schedule.split():
        op, ts, item = re.fullmatch(r"([RW])(\d+)\((\w+)\)", token).groups()
        ts = int(ts)
        if ts in aborted:
            print(f"  {token:6} skipped: T{ts} was aborted")
            continue
        r, w = rts.get(item, 0), wts.get(item, 0)
        if op == "R":
            if ts < w:
                aborted.add(ts)
                verdict = f"abort T{ts}: a younger transaction (T{w}) already wrote {item}"
            else:
                rts[item] = max(r, ts)
                verdict = "read"
        elif ts < r:
            aborted.add(ts)
            verdict = f"abort T{ts}: a younger transaction (T{r}) already read {item}"
        elif ts < w and thomas:
            verdict = f"ignored: T{w} already wrote a newer value of {item} (Thomas's write rule)"
        elif ts < w:
            aborted.add(ts)
            verdict = f"abort T{ts}: a younger transaction (T{w}) already wrote {item}"
        else:
            wts[item] = ts
            verdict = "written"
        state = "  ".join(f"{i}: R-TS {rts.get(i, 0)}, W-TS {wts.get(i, 0)}" for i in sorted(set(rts) | set(wts)))
        print(f"  {token:6} {verdict}")
        print(f"         {state}")
    return aborted


print("basic timestamp ordering" + (" with Thomas's write rule" if THOMAS else ""))
gone = run(SCHEDULE, THOMAS)
print("aborted:", ", ".join(f"T{t}" for t in sorted(gone)) or "none", "(each restarts later with a new timestamp)")

basic timestamp ordering
  R5(A)  read
         A: R-TS 5, W-TS 0
  R7(A)  read
         A: R-TS 7, W-TS 0
  W7(A)  written
         A: R-TS 7, W-TS 7
  R5(B)  read
         A: R-TS 7, W-TS 7  B: R-TS 5, W-TS 0
  W5(A)  abort T5: a younger transaction (T7) already read A
         A: R-TS 7, W-TS 7  B: R-TS 5, W-TS 0
  R9(B)  read
         A: R-TS 7, W-TS 7  B: R-TS 9, W-TS 0
  W7(B)  abort T7: a younger transaction (T9) already read B
         A: R-TS 7, W-TS 7  B: R-TS 9, W-TS 0
  W9(B)  written
         A: R-TS 7, W-TS 7  B: R-TS 9, W-TS 9
aborted: T5, T7 (each restarts later with a new timestamp)

T5 tried to write A after T7, a younger transaction, had read it: in the timestamp order T5 comes first, so T7 should have read T5’s value, and it is too late for that, so T5 aborts. T7’s write of B fails the same way because T9 had already read B. No transaction ever waited, so no deadlock is possible. The price is that both aborted transactions must restart, and with new, larger timestamps, because with their old ones they would fail the same check again.

Thomas’s write rule changes one case: a write that arrives after a younger transaction’s write is skipped instead of aborting the writer, because in the timestamp order it would be overwritten anyway (Thomas: A Majority Consensus Approach). It keeps some transactions alive that basic timestamp ordering would abort. Strict timestamp ordering makes a transaction wait to read or overwrite a value until its writer has committed or aborted, which keeps schedules recoverable. Multiversion timestamp ordering keeps old versions, so that a late read finds the value it should see instead of aborting.

Optimistic control in three phases

Kung and Robinson split every transaction into three phases (On Optimistic Methods for Concurrency Control):

The read phase does all the work, reading from the database and writing only into a private copy. The validation step at commit checks for conflicts. Backward validation compares a transaction with those that committed while it ran; forward validation compares it with those still running. The write phase copies the private writes into the database. Optimistic control pays off when conflicts are rare, because then almost every transaction passes validation and nobody ever waited for a lock.

Optimistic locking with a version column

Applications use the same idea across requests, where a database transaction cannot stay open. Each row carries a version number. A client reads the row and its version, works on it, and writes back with an update that names the version it read and increments it. If somebody changed the row in between, the update matches no row, and the client must read again. Two app servers sell kettles from one row here; SQLite’s changes() reports how many rows the last statement changed (SQLite: changes()):

-- Optimistic locking with a version column. App servers A and B both read product 1: stock 10, version 1.
CREATE TABLE products (id INTEGER PRIMARY KEY, name TEXT NOT NULL, stock INTEGER NOT NULL,
                       version INTEGER NOT NULL);
INSERT INTO products VALUES (1, 'kettle', 10, 1);

-- A sells 3. Its update names the version it read, so it succeeds only if nobody changed the row since.
UPDATE products SET stock = 7, version = version + 1 WHERE id = 1 AND version = 1;
SELECT 'A' AS server, changes() AS rows_updated;

-- B sells 2 from the stock of 10 it read. Version 1 is gone, so its update matches no row.
UPDATE products SET stock = 8, version = version + 1 WHERE id = 1 AND version = 1;
SELECT 'B' AS server, changes() AS rows_updated;

-- Zero rows means a conflict: B reads again (stock 7, version 2) and repeats its update.
UPDATE products SET stock = 5, version = version + 1 WHERE id = 1 AND version = 2;
SELECT 'B, again' AS server, changes() AS rows_updated;
SELECT id, name, stock, version FROM products;

┌────────┬──────────────┐
│ server │ rows_updated │
├────────┼──────────────┤
│ A      │ 1            │
└────────┴──────────────┘
┌────────┬──────────────┐
│ server │ rows_updated │
├────────┼──────────────┤
│ B      │ 0            │
└────────┴──────────────┘
┌──────────┬──────────────┐
│  server  │ rows_updated │
├──────────┼──────────────┤
│ B, again │ 1            │
└──────────┴──────────────┘
┌────┬────────┬───────┬─────────┐
│ id │  name  │ stock │ version │
├────┼────────┼───────┼─────────┤
│ 1  │ kettle │ 5     │ 3       │
└────┴────────┴───────┴─────────┘

B’s first update changed no row, because A had already moved the version from 1 to 2. Without the condition on the version, B would have written stock 8 over A’s 7, and A’s sale would be lost. HTTP has the same check built in: a client sends the ETag it read in an If-Match header, and the server answers 412 Precondition Failed instead of overwriting a newer version (RFC 9110: HTTP Semantics).

Exercise

"""The read and write rules of basic timestamp ordering, with Thomas's write rule as an option.

Each item is a dict: "rts" is the largest timestamp that has read it, "wts" the timestamp of its last write.
"""


def read(ts, item):
    """Return "ok" (after updating item["rts"]) or "abort"."""
    return "ok"


def write(ts, item, thomas=False):
    """Return "ok" (after updating item["wts"]), "abort", or "ignore" for an obsolete write under Thomas's rule."""
    return "ok"

import re

from to_rules import read, write


def test_late_read_aborts():
    """A read after a younger transaction's write aborts"""
    item = {"rts": 0, "wts": 7}
    assert read(5, item) == "abort"
    assert item == {"rts": 0, "wts": 7}


def test_read_keeps_the_largest_timestamp():
    """R-TS keeps the largest reader's timestamp"""
    item = {"rts": 3, "wts": 2}
    assert read(5, item) == "ok" and item["rts"] == 5
    assert read(4, item) == "ok" and item["rts"] == 5


def test_write_after_younger_read_aborts():
    """A write after a younger transaction's read aborts, even under Thomas's rule"""
    assert write(7, {"rts": 9, "wts": 0}) == "abort"
    assert write(7, {"rts": 9, "wts": 0}, thomas=True) == "abort"


def test_obsolete_write():
    """An obsolete write aborts under basic ordering and is ignored under Thomas's rule"""
    item = {"rts": 1, "wts": 4}
    assert write(2, item) == "abort"
    assert write(2, item, thomas=True) == "ignore"
    assert item == {"rts": 1, "wts": 4}


def test_whole_schedule():
    """R5(A) R7(A) W7(A) R5(B) W5(A) R9(B) W7(B) W9(B): T5 and T7 abort"""
    items = {"A": {"rts": 0, "wts": 0}, "B": {"rts": 0, "wts": 0}}
    aborted = set()
    for token in "R5(A) R7(A) W7(A) R5(B) W5(A) R9(B) W7(B) W9(B)".split():
        op, ts, name = re.fullmatch(r"([RW])(\d+)\((\w)\)", token).groups()
        if int(ts) in aborted:
            continue
        result = read(int(ts), items[name]) if op == "R" else write(int(ts), items[name])
        if result == "abort":
            aborted.add(int(ts))
    assert aborted == {5, 7}

Timestamp ordering in depth: Thomas's rule, recoverability and starvation Pro: opens with a Pro, Premium or Ultimate pass

Optimistic control in depth: validation tests, contention and lost updates Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Timestamp ordering keeps the schedule equivalent to the serial order of start timestamps: a read after a younger write aborts, and so does a write after a younger read or write.
• Thomas’s write rule skips a write that a younger write has already made obsolete, instead of aborting.
• Optimistic control runs a transaction against a private copy and validates at commit; it suits rare conflicts.
• A version column, or an ETag with If-Match, gives applications optimistic locking across requests.