Optimistic Concurrency Control

Introduction

Concurrency control is a fundamental problem in distributed systems and databases.
When multiple transactions execute simultaneously, the system must ensure that the result is equivalent to some serial execution, preserving isolation guarantees.
Two broad strategies exist: pessimistic approaches, which prevent conflicts by acquiring locks before accessing data, and optimistic approaches, which allow transactions to proceed without blocking and check for conflicts only at commit time.

Optimistic Concurrency Control (OCC) is built on the premise that conflicts between transactions are rare.
Rather than paying the overhead of locking on every access, OCC lets transactions read and write freely on local copies of data, then validates that no conflicts occurred before committing.
When contention is low, this yields higher throughput and lower latency than locking protocols.
When contention is high, the cost of aborted and retried transactions can make OCC perform worse than pessimistic alternatives.

The technique was formalized by Kung and Robinson in 1981, and its core ideas have since been adopted in systems ranging from in-memory databases (Silo, Hekaton) to distributed transactional stores (Google's Percolator, Google Spanner, CockroachDB).

How OCC Works

An OCC transaction proceeds through three distinct phases:

1. Read Phase

The transaction executes all of its read and write operations against a private workspace.
Reads fetch values from the database and record which objects were read (the read set).
Writes are performed on local copies of data objects, accumulated in a write set.
No locks are acquired, and no modifications are made to shared state.

2. Validation Phase

Before the transaction can commit, the system checks whether the transaction's execution is serializable with respect to other committed (or committing) transactions.
The key question is: did any other transaction modify data that this transaction read, or read data that this transaction intends to write, in a way that would violate serializability?

Validation typically assigns each transaction a numeric timestamp at the start of this phase.
The transaction is then checked against all transactions that committed (or are currently validating) with overlapping execution windows.

3. Write Phase

If validation succeeds, the transaction's write set is applied to the shared database atomically.
If validation fails, the transaction is aborted, its private workspace is discarded, and the transaction may be retried.

The critical design decision is the validation strategy.
Kung and Robinson described two variants: backward validation and forward validation.

Backward validation checks the committing transaction against all transactions that have already committed during its read phase.
If any committed transaction's write set intersects with the current transaction's read set, the current transaction must abort.

Forward validation checks the committing transaction against all currently active (still in their read phase) transactions.
If the committing transaction's write set intersects with any active transaction's read set, a conflict exists.
Forward validation offers more flexibility because the system can choose to abort either the committing transaction or the conflicting active one.

Walkthrough

Below is a step-by-step walkthrough illustrating the backward validation variant.
Consider three transactions, T1, T2, and T3, with assigned validation timestamps 1, 2, and 3 respectively.

Pseudocode for Backward Validation

function validate(T):
    // T is the transaction being validated
    // T.timestamp is assigned at the start of validation
    // committed_txns contains all transactions that committed
    //   while T was in its read phase (i.e., their timestamp < T.timestamp
    //   and their write phase overlapped with T's read phase)

    for each Tc in committed_txns where Tc.timestamp < T.timestamp:
        // If Tc wrote something T read, T's view may be stale
        if Tc.write_set ∩ T.read_set ≠ ∅:
            abort(T)
            return false

        // If Tc's write phase was not complete before T's read phase started
        // (i.e., there was temporal overlap), also check for write-write conflict
        if not (Tc.write_phase_end < T.read_phase_start):
            if Tc.write_set ∩ T.write_set ≠ ∅:
                abort(T)
                return false

    commit(T)    // Apply T.write_set to shared database
    return true

Concrete Example

Suppose we have data items X and Y with initial values X=10 and Y=20.

T1 begins, reads X (read set = {X}), and writes X=15 (write set = {X}).
T2 begins, reads X and Y (read set = {X, Y}), and writes Y=30 (write set = {Y}).

T1 enters validation first, gets timestamp 1.
No prior committed transactions exist, so T1 passes validation and commits.
X is now 15 in the database.

T2 enters validation, gets timestamp 2.
Backward validation checks T2 against T1:

• T1.write_set ∩ T2.read_set = {X} ∩ {X, Y} = {X} ≠ ∅

T2 must abort.
It read X during its read phase, but T1 committed a new value of X in the meantime.
T2's view of X is stale.
T2 is retried and will now read X=15.

This is the core mechanism.
No locks were ever held.
T2's abort is the price paid for optimism when a conflict actually occurs.

Validation Conditions (Kung-Robinson)

For a committing transaction Tj to be serializable after a previously committed transaction Ti, at least one of the following conditions must hold:

1. Ti completes its write phase before Tj starts its read phase. There is no overlap at all; serial execution is trivially preserved.

2. Ti completes its write phase before Tj starts its write phase, AND Ti's write set does not intersect Tj's read set. Ti may have been writing while Tj was reading, but Tj never read anything Ti changed.

3. Ti completes its read phase before Tj starts its write phase, AND Ti's write set does not intersect Tj's read set, AND Ti's write set does not intersect Tj's write set. Both transactions overlapped in their read phases, but there were no data dependencies between them in either direction.

If none of these conditions hold, Tj must be aborted.

OCC in Distributed Systems

Applying OCC in distributed settings introduces additional challenges:

Distributed Validation

When data is partitioned across nodes, the validation phase must coordinate across partitions.
A transaction that reads from partition A and writes to partition B needs both partitions to agree on the validity of the commit.
This typically requires a two-phase commit (2PC) protocol layered on top of OCC.

Google's Percolator uses this approach, combining OCC with 2PC over Bigtable, and using a centralized timestamp oracle (backed by Chubby) to assign globally monotonic timestamps.
Google Spanner takes a related but distinct approach, using TrueTime — a globally synchronized physical clock with bounded uncertainty — to assign commit timestamps with external consistency guarantees, without requiring a centralized oracle bottleneck.

Timestamp Assignment

Assigning globally consistent timestamps is itself a distributed systems problem.
Approaches include centralized timestamp oracles (simple but a potential bottleneck and single point of failure), Lamport clocks or hybrid logical clocks (which provide causal ordering), and synchronized physical clocks with bounded uncertainty (as in Spanner's TrueTime).

Starvation and Livelock

Under high contention, OCC can cause starvation.
A long-running transaction may be repeatedly aborted by shorter transactions that commit first.
Systems like Hekaton address this with adaptive strategies, falling back to pessimistic locking for transactions that have been aborted multiple times.
CockroachDB uses a "transaction contention" mechanism that can push conflicting transaction timestamps forward rather than always aborting.

Multi-Version Concurrency Control (MVCC) and OCC

Many modern systems combine MVCC with OCC.
MVCC maintains multiple versions of each data item, allowing readers to see a consistent snapshot without blocking writers.
OCC's validation phase can then check whether the snapshot a transaction read from is still consistent at commit time.
PostgreSQL's Serializable Snapshot Isolation (SSI), while not pure OCC, draws on similar principles by tracking read-write dependencies and aborting transactions that could produce non-serializable outcomes.

Trade-offs and When to Use OCC

OCC performs best when:

• Read-dominated workloads, where write conflicts are rare.
• Short transactions, that minimize the window for conflicts.
• Systems where the cost of locking (deadlock detection, lock manager overhead, reduced concurrency) exceeds the cost of occasional aborts.

OCC performs poorly when:

• Write contention is high, leading to frequent aborts and retries.
• Transactions are long-running, increasing the probability of conflict and wasting more work on each abort.
• Abort costs are non-trivial (e.g., transactions with side effects that are difficult to reverse).

A well-known result from Agrawal, Carey, and Livny (1987) demonstrated that under high contention, OCC with restart can perform significantly worse than two-phase locking.
The "wasted work" of aborted transactions compounds, and the retried transactions themselves cause further conflicts, creating a feedback loop.

Key Points

• OCC divides transaction execution into three phases: read (execute locally), validate (check for conflicts), and write (apply changes if valid).
• No locks are acquired during the read phase, enabling high concurrency when conflicts are infrequent.
• Backward validation checks the committing transaction against already-committed transactions; forward validation checks against currently-active transactions.
• The Kung-Robinson conditions provide a formal framework for determining whether two overlapping transactions can be serialized without conflict.
• In distributed settings, OCC must be combined with global timestamp assignment and atomic commit protocols like 2PC, adding complexity.
• Under high contention, OCC can degrade severely due to cascading aborts, making pessimistic or hybrid approaches preferable.
• Modern systems (Silo, Hekaton, CockroachDB) often blend OCC with MVCC and adaptive fallback mechanisms to balance throughput and contention handling.

References

H.T. Kung and John T. Robinson. "On Optimistic Methods for Concurrency Control." ACM Transactions on Database Systems, 6(2):213-226, June 1981.

R. Agrawal, M.J. Carey, and M. Livny. "Concurrency Control Performance Modeling: Alternatives and Implications." ACM Transactions on Database Systems, 12(4):609-656, December 1987.

Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. "Speedy Transactions in Multicore In-Memory Databases." Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP), 2013.

Daniel Peng and Frank Dabek. "Large-scale Incremental Processing Using Distributed Transactions and Notifications." Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2010.

Philip A. Bernstein and Nathan Goodman. "Concurrency Control in Distributed Database Systems." ACM Computing Surveys, 13(2):185-221, June 1981.