Optimistic concurrency control

Deep dive

How it works

In: a transaction's reads and writes on shared records · Out: commit, or abort and retry · State: a 64-bit TID word per record (version plus lock bit); per transaction a read set and a write set · Cost: |W| CAS operations plus |R| loads at commit, order of tens of ns per item without contention.

Each record has a 64-bit TID word: a version number plus a lock bit.

1. Read: load the TID (spin while it is locked), read the value, re-load the TID. If it is unchanged, the value is consistent: record (record, tid) in the read set. This is a seqlock read.
2. Write: buffer (record, value) in the write set.
3. Commit:
   1. Lock every write-set record in a global order (by address), so two committers cannot deadlock.
   2. Validate: each read-set record must have the TID we saw and must not be locked by another transaction.
   3. Choose the new TID, greater than every TID read or overwritten.
   4. Write the values, then store the new TID, which also clears the lock bit (release).
4. On a validation failure, unlock and abort. The caller retries.

Serialization point: the moment all write locks are held. Every read validated after that point was still current then.

Code

use std::sync::atomic::{AtomicU64, Ordering::*};

const LOCK: u64 = 1 << 63;

pub struct Record { tid: AtomicU64, val: AtomicU64 }
impl Record { pub fn new(v: u64) -> Self { Record { tid: AtomicU64::new(0), val: AtomicU64::new(v) } } }

pub struct Txn<'a> { reads: Vec<(&'a Record, u64)>, writes: Vec<(&'a Record, u64)> }

impl<'a> Txn<'a> {
    pub fn new() -> Self { Txn { reads: Vec::new(), writes: Vec::new() } }

    pub fn read(&mut self, r: &'a Record) -> u64 {
        if let Some(&(_, v)) = self.writes.iter().find(|(w, _)| std::ptr::eq(*w, r)) { return v; }
        loop {
            let t1 = r.tid.load(Acquire);
            if t1 & LOCK != 0 { std::hint::spin_loop(); continue; }
            let v = r.val.load(Acquire);
            if r.tid.load(Relaxed) == t1 { self.reads.push((r, t1)); return v; } // stable snapshot
        }
    }

    pub fn write(&mut self, r: &'a Record, v: u64) {
        match self.writes.iter_mut().find(|(w, _)| std::ptr::eq(*w, r)) {
            Some(w) => w.1 = v,
            None => self.writes.push((r, v)),
        }
    }

    pub fn commit(mut self) -> Result<u64, ()> {
        self.writes.sort_by_key(|(r, _)| *r as *const Record as usize); // global lock order
        let mut max_tid = 0;
        for (r, _) in &self.writes {
            loop {
                let t = r.tid.load(Relaxed);
                if t & LOCK == 0 && r.tid.compare_exchange_weak(t, t | LOCK, Acquire, Relaxed).is_ok() {
                    max_tid = max_tid.max(t);
                    break;
                }
                std::hint::spin_loop();
            }
        }
        let valid = self.reads.iter().all(|(r, seen)| {
            let now = r.tid.load(Acquire);
            let mine = self.writes.iter().any(|(w, _)| std::ptr::eq(*w, *r));
            now & !LOCK == *seen && (now & LOCK == 0 || mine)
        });
        if !valid {
            for (r, _) in &self.writes { r.tid.fetch_and(!LOCK, Release); }
            return Err(()); // abort: caller retries
        }
        for (_, seen) in &self.reads { max_tid = max_tid.max(*seen); }
        let new_tid = max_tid + 1; // Silo also embeds an epoch number here
        for (r, v) in &self.writes {
            r.val.store(*v, Release);
            r.tid.store(new_tid, Release); // publish + unlock in one store
        }
        Ok(new_tid)
    }
}

Values here are one word. For larger records, copy the bytes between the two TID loads (a seqlock read) and write them while holding the lock.

Complexity and constants

• Execution: no shared writes at all. Reads cost two extra loads of a word that usually sits in the same cache line as the data.
• Commit: |W| CAS operations plus |R| loads. Order of tens of ns per item without contention.
• Abort probability ≈ 1 − e^(−λ·|R|·d) for write rate λ per item, read-set size |R| and duration d: linear while small, then it saturates. Retries add load and push it higher.
• With 2PL the "conflict cost" is waiting. With OCC it is redoing work, which is wasted CPU.

Efficiency

• Cost: execution makes no shared writes; a read costs two extra loads of a word usually in the data's cache line; commit is |W| CAS plus |R| loads. Contention shows up as aborts and retries, which burn CPU. Bound: wasted work and cache-line traffic.
• Levers:
  • version word in the data's cache line, validate the read set only — cheap validation — always
  • read-only transactions from a snapshot epoch — never validate or abort — read-heavy mixes
  • TIDs from a global epoch (advanced about every 40 ms) plus a per-thread counter (Silo) — no shared cache line written per transaction — many cores
  • back off with jitter, switch to locking after k aborts (MOCC-style) — avoids abort storms below single-threaded speed — hot keys
  • group commit — one log flush for many transactions — durable commits
• Naive → standard → state of the art:
  • lock every item up front · waiting even without conflicts
  • OCC with per-record version words · near-zero coordination at low contention
  • epoch-based TIDs with snapshot reads · Silo reported about 700k TPC-C transactions/s on 32 cores

Implementation notes

• Phantoms: validating records does not catch a new row inserted into a scanned range. Silo also validates the version numbers of the B-tree leaf nodes it scanned (node-set validation).
• TID generation without a global counter: Silo builds the TID from a global epoch (advanced about every 40 ms) plus a per-thread counter. No shared cache line is written per transaction.
• Read-only transactions: serve them from a recent snapshot epoch so they never abort.
• Memory reclamation: readers may hold pointers to records being deleted. Free them with epoch-based reclamation.
• Retry policy: back off with jitter. After k aborts, switch the transaction to pessimistic locking (MOCC-style) to bound tail latency.
• Application-level OCC: UPDATE t SET ..., version = version + 1 WHERE id = ? AND version = ?. Zero rows affected means a conflict: reload and retry.

Pitfalls

• Validating without first locking the write set lets two transactions validate at the same time and both commit (lost update).
• Locking the write set in transaction order instead of a global order deadlocks under spinning.
• ABA: if a version can return to an old value, validation passes wrongly. TIDs must increase strictly per record.
• Long-running analytics inside OCC transactions starve. Run them on snapshots instead.
• Abort storms at hot keys collapse throughput below single-threaded speed. Monitor the abort rate and keep a fallback.

Variants and alternatives

In production

• Databases: FoundationDB, SQL Server In-Memory OLTP (Hekaton), Silo and DBx1000 (research engines).
• Cluster control planes and coordination: etcd transactions (compare revision), Kubernetes API (resourceVersion).
• Cloud storage and web APIs: DynamoDB conditional writes, HTTP ETags with If-Match.
• Application frameworks: JPA/Hibernate @Version.

Implementations

Sources

• H. T. Kung, J. Robinson, On Optimistic Methods for Concurrency Control, ACM TODS, 1981. paper
• S. Tu, W. Zheng, E. Kohler, B. Liskov, S. Madden, Speedy Transactions in Multicore In-Memory Databases, SOSP, 2013. paper
• X. Yu, A. Pavlo, D. Sanchez, S. Devadas, TicToc: Time Traveling Optimistic Concurrency Control, SIGMOD, 2016. paper
• T. Wang, H. Kimura, Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores, VLDB, 2016. paper
• J. Zhou et al., FoundationDB: A Distributed Unbundled Transactional Key Value Store, SIGMOD, 2021. paper