mvcc-snapshot-isolation-txn

Answer

The MVCC engine (mvcc_engine.js) implements snapshot isolation with these components:

1. Timestamp Oracle — Lock-Free Global Counter

A simple monotonic counter (++this._counter) that provides strictly increasing timestamps for both transaction begin and commit events. No locks needed because JavaScript's single-threaded execution model makes increment operations atomic.

2. Version Chain Per Key

Each key maintains an array of (txnId, beginTs, endTs, value) tuples sorted by beginTs descending (most recent first). A version is: - beginTs: the commit timestamp when this version was created - endTs: the commit timestamp when this version was superseded (or Infinity for the latest/live version) - Visible to a transaction with snapshot S iff beginTs ≤ S < endTs

3. Lock-Free Commit Protocol

The commit() method is fully synchronous (no await points), making it atomic:

1. Read-only fast path: if no writes were performed, commit immediately — no conflicts possible
2. Obtain commit timestamp from the oracle
3. Write-write conflict detection (first-committer-wins): for each key in the write-set, find the latest committed version. If its beginTs > our transaction's beginTs, another transaction committed a write to this key after our snapshot was taken → abort
4. Install versions: supersede the previous version (set its endTs to our commit timestamp) and prepend our new version
5. Garbage collect old versions

4. Write-Write Conflict Detection

Uses the first-committer-wins rule for snapshot isolation. Two concurrent transactions (their intervals [beginTs, commitTs] overlap) that write to the same key: the second one to commit sees the first one's version with beginTs > its own beginTs and aborts.

5. Garbage Collection

After every commit and abort, removes versions where endTs < the oldest active transaction's beginTs. Such versions are invisible to all active snapshots. The latest version (endTs = Infinity) is never removed.

// Core commit logic — lock-free, synchronous, atomic
commit(txn) {
    if (txn.status !== 'active') return false;

    // Read-only: instant commit
    if (!txn.isReadWrite) { /* ... */ return true; }

    const commitTs = this._oracle.next();

    // Write-write conflict detection
    for (const [key] of txn.writes) {
        const chain = this._chains.get(key);
        if (chain && chain.length > 0) {
            for (const v of chain) {
                if (this._committed.has(v.txnId)) {
                    if (v.beginTs > txn.beginTs) {  // conflict!
                        // abort
                        return false;
                    }
                    break;
                }
            }
        }
    }

    // Install versions
    for (const [key, value] of txn.writes) {
        // supersede previous version
        for (const v of chain) {
            if (this._committed.has(v.txnId)) {
                v.endTs = commitTs;
                break;
            }
        }
        // add new version
        chain.unshift(new Version(txn.id, commitTs, Infinity, value));
    }

    this._garbageCollect();
    return true;
}

// GC: remove versions invisible to all active snapshots
_garbageCollect() {
    let oldestActive = Infinity;
    for (const [, txn] of this._activeTxns) {
        if (txn.beginTs < oldestActive) oldestActive = txn.beginTs;
    }
    for (const [key, chain] of this._chains) {
        const newChain = chain.filter(v => v.endTs >= oldestActive);
        // ... update map
    }
}