mvcc-impl

A pedagogical MVCC (Multi-Version Concurrency Control) database engine in Rust, inspired by PostgreSQL's internals.

Design

Each key has a version chain (a Vec<Version>). Each Version records:

Field	Meaning
value	The stored value (None for tombstone-only versions)
created_by (xmin)	Transaction ID that created this version
deleted_by (xmax)	Transaction ID that logically deleted this version

Transactions acquire a snapshot of all active transactions at begin() time. Reads walk the version chain newest-first, returning the first version whose creator is visible per Snapshot Isolation rules:

1. Own writes are always visible
2. Only committed transactions are visible
3. Transactions with a higher ID (started later) are invisible
4. Transactions that were active in the reader's snapshot are invisible

A version is considered deleted if its deleted_by is set and that deleter is visible to the reader.

API

Method	Description
Database::new()	Create an empty database
db.begin()	Start a new transaction, capturing a snapshot
db.read(txn, key)	Read the latest visible version of a key
db.write(txn, key, value)	Write a new version (first-writer-wins conflict detection)
db.delete(txn, key)	Logically delete the latest visible version
db.commit(txn)	Mark transaction as committed
db.abort(txn)	Mark transaction as aborted
db.gc()	Garbage-collect unreachable versions

Garbage Collection

gc() computes a horizon — the minimum transaction ID across all active transactions and their snapshot contents. Versions are removed when:

• Their creator was aborted, or
• Their deleter is committed AND has an ID older than the horizon (no active transaction can see the undeleted version)

Conflict Detection

Write-write conflicts use first-writer-wins: if the latest version of a key was created by a different, still-active (non-aborted) transaction, the write or delete fails.

Tests

cargo test

25 tests covering read, write, delete, snapshot isolation, write-write conflicts, abort semantics, and garbage collection.