13.2 OCC, Timestamp Ordering, and Application Concurrency Strategies

A high-concurrency registration system doesn’t want all transactions to queue up waiting for locks. So, you’re tasked with evaluating an approach where transactions execute first, commit, and then validate their outcomes.

---

Metadata Card

• Prerequisites: 13.1 Two-Phase Locking, Lock Granularity, and Deadlock Diagnosis
• Keywords: OCC, Validation, Timestamp Ordering, Thomas Write Rule, CAS, Idempotent Retries
• Code Languages: Pseudocode, SQL

---

Pessimistic concurrency coordinates conflicts before execution begins. Optimistic concurrency allows transactions to work in private state first, validating their consistency only upon commit. Timestamp ordering establishes a logical sequence upfront and rejects operations that violate that sequence. These aren’t competing technologies ranked by age; they’re different trade-offs suited to specific workloads.

OCC's Three Phases

Classic Optimistic Concurrency Control (OCC) divides transactions into three phases:

1. Read: Read from a shared database, accumulate modifications in a private workspace, and record the read set RS(T) and write set WS(T);
2. Validation: Check whether dependencies with overlapping transactions allow the selected serial order;
3. Write: Atomically publish the write set if validation succeeds; otherwise, abort.

The exact formulation depends on whether forward or backward validation is chosen, whether the validation point is treated as a serializability point or a commit point, and whether read and write phases can overlap. A set of set-based formulas cannot be directly copied into a general OCC algorithm without being anchored to a specific time interval.

Intuitively, "serializing by validation order" means that when transaction Tj performs validation, it must check whether any earlier-validated overlapping transaction Ti has written to any object that Tj has already read. If the write phase overlaps, additional checks are required to detect dangerous cross-operations between write sets and between Ti’s write set and Tj’s subsequent reads. Actual implementation must ensure that no concurrent writes occur between validation and write, which could go undetected.

When OCC Is Superior

OCC eliminates long-lived blocking and deadlocks, it does not eliminate all synchronization. Operations such as metadata validation, write set publication, and version reclamation still require coordination.

It is best suited for:

• Low conflict probability;
• Short transactions with low cost of failure recovery;
• Workloads with high read volume but limited write sets;
• Hotspots that can be partitioned, queued, or avoided.

It is not ideal for workloads where long-running computations reveal hotspots later. There is no universal threshold (such as "conflict rate exceeds X% and 2PL becomes better") that applies across all scenarios. The crossover point depends on transaction duration, hotspot distribution, validation overhead, core count, and retry strategies. Empirical benchmarking is required.

Application Version Numbers Are a Narrowed Optimistic Check

UPDATE account
SET balance = :new_balance,
    version = version + 1
WHERE account_id = :account_id
  AND version = :expected_version;

This is equivalent to a compare-and-swap operation on a single row. It can detect that "the row has changed since it was read," but it does not automatically protect against:

• Invariants across multiple rows;
• Newly added or deleted rows within a predicate scope;
• Out-of-band writes that do not include version conditions;
• Side effects caused by repeated operations outside of a transaction.

If a business decision depends on multiple rows, all such dependencies must be explicitly validated, or an alternative approach such as Serializable isolation, explicit locking, or a model expressible through database constraints must be adopted.

Basic Timestamp Ordering

Timestamp Ordering (TO) assigns a logical timestamp to each transaction TS(T), ensuring conflicting operations follow a consistent order. Each data item X maintains:

• read_ts(X): the maximum transaction timestamp of any transaction that successfully read X;
• write_ts(X): the maximum transaction timestamp of any transaction that successfully wrote X.

Basic rules:

read(T, X):
    if TS(T) < write_ts(X): abort T
    else read X; read_ts(X) = max(read_ts(X), TS(T))

write(T, X):
    if TS(T) < read_ts(X): abort T
    if TS(T) < write_ts(X): abort T
    else write X; write_ts(X) = TS(T)

This approach prevents transactions from forming waiting cycles due to data locks, thus avoiding lock-based deadlocks. However, it may cause older transactions to repeatedly be aborted. Implementation must preserve or update the priority of retried transactions to prevent starvation.

Thomas Write Rule Only Relaxes Outdated Writes

When TS(T) < write_ts(X) is encountered, the basic TO (Transaction Order) is halted. The Thomas Write Rule can ignore this outdated write because, in chronological order, it would have been overwritten by a more recent write anyway.

This rule applies only to specific write sequences and does not circumvent read dependency conflicts involving TS(T) < read_ts(X). It extends only to the view serializability scope, not to the claim that "all old writes can safely be discarded." Commit states, recovery, and versioning must remain consistent with the overall protocol design.

Multi-Version Timestamp Ordering

A multi-version TO maintains multiple versions of X, each tagged with a write timestamp. Transactions read the latest version of write_ts <= TS(T), so older transactions do not immediately fail simply because a newer version already exists.

The cost is shifted to:

• Version indexing and visibility determination;
• Active timestamp tracking;
• Retention and eventual removal of versions no longer accessible;
• Long-running transactions blocking garbage collection.

This bears familial resemblance to MVCC, but having multiple versions does not automatically imply the system uses a specific commit validation strategy, write conflict resolution rules, or SQL isolation semantics.

Implement Concurrency Strategies as Engineering Interfaces

When selecting a protocol, first write down five key items:

1. Invariants depend on single lines, multi-line, or predicate ranges;
2. How the system behaves when conflicts occur, do we wait, fail immediately, or fail on commit?
3. Which errors are retryable and where are the retry boundaries?
4. How do external side effects outside transactions become idempotent?
5. Which metrics should be monitored to detect when the strategy fails?

Recommend monitoring at least: lock wait times, deadlock rate, 40001/version conflict rate, distribution of transaction retries, number of long-running transactions, hotspot key distribution, and final failure rate. Relying solely on average throughput will mask tail latency caused by contention.

Scheme Comparison

Dimension	2PL / Locking	OCC	Timestamp Ordering
Conflict Handling Timing	Wait before or during access	Validate before commit	Check operation order on each execution
Primary Failure Modes	Waiting, deadlock victim	Validation failure, rollback	Termination due to out-of-order violation
Performance in Low-Conflict Scenarios	Lock management overhead	Generally superior	Depends on metadata and versioning costs
Behavior Under High Hotspots	Queuing, but manageable	Rollback amplification	Older transactions may be frequently terminated
Core Operational Metrics	Blocking chains, lock duration	Abort and retry rates	Abort rates, starvation, version cleanup

Real databases often blend these mechanisms: snapshot reads paired with write locks, optimistic validation used with short critical sections, and timestamps combined with multi-versioning. When choosing among them, rely on product documentation and reproducible experiments, do not infer overall behavior from a single paradigm label.

Section Checkpoint

• Can explain why OCC still requires atomic validation and publication.
• Can describe what a single version number can detect and what it cannot detect.
• Can apply the basic TO read-write rules step by step, and distinguish when the Thomas Write Rule applies.
• Can unify deadlock, serialization failure, and version conflicts under a bounded retry interface.

The next chapter will discuss how indexing, logging, recovery, and concurrency control must be reevaluated when all data resides in memory, rather than simply removing disk-related code.