In-memory MVCC: timestamps as locks, and the design-space price list

What does MVCC look like when the disk-era assumptions are deleted? Hekaton (SIGMOD ’13) answers with one design — no locks, no latches, no pages; Wu & Pavlo’s VLDB ’17 evaluation answers with the whole design SPACE, benchmark-backed prices attached. Read Hekaton first (a design), then Wu/Pavlo (the menu).

Hekaton — MVCC with no locks, no latches, no pages

The version record is self-describing, like a postgres tuple but timestamp-based:

 ┌──────────┬─────────┬──────────────┬─────────┐
 │ begin_ts │ end_ts  │ index links  │ payload │
 └──────────┴─────────┴──────────────┴─────────┘
 live version: end_ts = ∞
 during update: end_ts = writer's txn-id (acts as the write lock!)
 visibility: begin_ts ≤ my_read_ts < end_ts

Key moves to internalize:

1. Txn-ids double as locks. Storing a txn-id in end_ts is the write-write conflict check: a second writer sees a txn-id there and aborts/waits. One CAS = lock + version link. (Bit-smuggling again — the id/timestamp distinction is one bit.)
2. Commit processing, not commit point. At commit, get commit_ts, then validate (serializable = re-check read set unchanged + rescan scan predicates), then write log, then fix up all your begin/end_ts fields from txn-id → commit_ts. Readers who hit a txn-id must chase the txn’s state — visibility can depend on an in-flight commit (commit dependencies, taken instead of blocking).
3. Indexes point at version chains; lock-free hash + Bw-tree (topic 9’s protagonists) — MVCC and lock-free structures co-designed.
4. Cooperative GC: any thread that walks past a version older than the oldest active read_ts unlinks it. No vacuum process; the workload cleans itself in proportion to how much it reads.

The visibility test is one range check — except either field may still hold a txn-id, and then the reader chases the writer’s state:

#![allow(unused)]
fn main() {
fn visible(v: &Version, read_ts: u64, txns: &TxnTable) -> bool {
    let begin = match v.begin_ts {
        Stamp(ts) => ts,
        TxnId(id) => match txns.state(id) {
            Committing { commit_ts } => commit_ts, // take a commit DEPENDENCY:
            _ => return false,                     // I abort if the writer does
        },
    };
    let end = match v.end_ts {
        Stamp(ts) => ts,       // superseded at ts
        TxnId(_) => u64::MAX,  // being updated — still the latest for readers
    };
    begin <= read_ts && read_ts < end
}
}

Contrast postgres on every axis: ts vs xid+clog+hint-bits; validation vs SIREAD; cooperative GC vs vacuum; new-to-old chains vs t_ctid old-to-new.

Wu/Pavlo — the menu with prices (VLDB ’17)

They implement every combination in one system and measure. The axes:

The meta-lesson (their words, roughly): everyone argues about CC algorithms, but version storage and GC decide throughput. Storage layer > protocol. (The RUM triangle strikes again.)

Questions for notes.md

1. Hekaton’s end_ts-as-lock: write the CAS-based first-writer-wins in pseudocode. Your mvcc.rs does the same check where? (Point at the line once implemented.)
2. Delta storage wins for writes; append-only N2O for reads. Which is a GraphBLAS delta matrix (topic 20)? So M8’s “copy-on-write + deltas” sits where in the Wu/Pavlo taxonomy — and what does their data predict about its read path?
3. Logical vs physical index pointers: FalkorDB’s node ids ARE logical indirection into matrices. What does that make “index management” cost for a graph MVCC — which updates still have to touch indexes?
4. Cooperative GC in proportion to reads: what happens to a write-only hot key that nobody reads? (Wu/Pavlo call this out — find the fix.)
5. Predict, then check §6 of Wu/Pavlo: at 40 cores, high contention, what ruins MVOCC — validation aborts or timestamp allocation?

Done when

You can fill the 5-axis table from memory and place postgres, Hekaton, and your M8 design in it — one row each.

References

Papers

• Diaconu, Freedman, Ismert, Larson, Mittal, Stonecipher, Verma, Zwilling — “Hekaton: SQL Server’s Memory-Optimized OLTP Engine” (SIGMOD 2013) — ~1.5 h; the version format and commit processing sections carry it
• Wu, Arulraj, Lin, Xian, Pavlo — “An Empirical Evaluation of In-Memory Multi-Version Concurrency Control” (VLDB 2017) — ~1 h; read it as a menu with prices, the tables and §6 graphs carry the message