阅读中文版本

Build an MVCC Snapshot Store

A multi-version concurrency control store that gives each transaction a consistent snapshot, writes create new versions, and garbage collection reclaims versions invisible to all live snapshots.

mvcc-snapshot-store/
├── src/store.ts
├── src/transaction.ts
├── src/gc.ts
├── tests/mvcc.test.ts
└── package.json

const tx = {id: nextId(), snap: now()};

return versions.find(v => v.begin <= tx.snap && (v.end === null || v.end > tx.snap));

versions.push({val, begin: commitTs, end: null}); prev.end = commitTs;

versions = versions.filter(v => v.end === null || v.end > oldestSnapshot);

Project overview

A store that locks on read blocks writers, and a store that locks on write blocks readers. A multi-version store does neither: it keeps multiple versions of each key, so a reader sees a consistent snapshot and a writer creates a new version without overwriting the old. The reader and the writer do not interfere, because they access different versions.

The snapshot isolation is the guarantee. A transaction that begins at a timestamp sees the store as of that timestamp, regardless of concurrent writes. A write that commits after the snapshot is invisible to the transaction, because its begin-timestamp is after the snapshot. The transaction sees a consistent view, not the latest, and the consistency is what makes the isolation useful.

The multi-version storage is the mechanism. Each key has a list of versions, each with a value, a begin-timestamp, and an end-timestamp. A read finds the version visible at the snapshot, which is the one whose begin is at or before the snapshot and whose end is after or null. A write creates a new version and sets the end of the previous, so the old version is still visible to transactions with an earlier snapshot.

The garbage collection is what bounds the version count. A version whose end is older than the oldest live snapshot is invisible to every transaction, so it can be removed. GC runs in the background and reclaims these versions, so the version list does not grow forever.

The value of this project is the read-no-lock, not the versioning. Keeping multiple versions is a storage trick; letting a reader proceed without locking while a writer writes is the part worth learning, because that is what makes MVCC the concurrency control of choice for high-throughput stores.

What you will build

The project delivers five capabilities, each driven by a test:

• Snapshot isolation per transaction
• Multi-version storage
• Write-create-new-version
• Garbage collection of old versions
• Read-no-lock

Each key has a list of versions, each with a value, a begin-timestamp, and an end-timestamp. A transaction reads the version visible at its snapshot timestamp. A write creates a new version and updates the end-timestamp of the previous version. GC removes versions whose end-timestamp is older than the oldest live snapshot.

Architecture and data model

The store is a map from key to a list of versions. A version is a value, a begin-timestamp, and an end-timestamp, where the end is null for the current version and a timestamp for a superseded one. The timestamps are from a monotonic clock, which is a counter incremented on every commit, so they are unique and ordered.

A transaction begins by getting a snapshot timestamp from the clock. The snapshot is the clock value at begin, which defines what the transaction sees. A read finds the version of the key whose begin is at or before the snapshot and whose end is after the snapshot or null. This is the version that was current at the snapshot, and it is the consistent view the transaction sees.

A write in a transaction creates a new version on commit, not on write. The write is buffered in the transaction, and on commit the new version is created with a begin-timestamp of the commit time, and the previous version end is set to the commit time. The buffering ensures an aborted transaction does not create versions, and the commit timestamp ensures the new version is visible only to transactions that begin after the commit.

The GC removes versions whose end is older than the oldest live snapshot. The oldest live snapshot is the minimum snapshot timestamp of all live transactions, which is tracked by the store. A version whose end is older than this is invisible to every live transaction, because every transaction has a snapshot after the end, so the version is not visible. GC removes these versions, bounding the version list.

The GC runs in the background, so it does not block transactions. A GC that runs in the foreground would block reads and writes, which defeats the purpose of MVCC. A background GC that scans the version lists periodically is the right design, because it reclaims space without blocking.

The snapshot isolation is not serializable. Two transactions that read overlapping keys and write based on the reads can produce a write skew, where each transaction writes based on a snapshot that does not see the other write, and the result is inconsistent. Serializable isolation requires conflict detection, such as SSI, which is out of scope, because snapshot isolation is the common case and the write skew is a known limitation.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• An understanding of snapshot isolation

The dependencies cover the core needs:

• node:crypto (built-in) — Transaction id generation

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

mvcc-snapshot-store/ is organized so each concern is testable in isolation:

mvcc-snapshot-store/
├── src/store.ts
├── src/transaction.ts
├── src/gc.ts
├── tests/mvcc.test.ts
└── package.json

Phase 1: Begin transaction

Assign a transaction id and a snapshot timestamp from a monotonic clock.

const tx = {id: nextId(), snap: now()};

The snapshot timestamp defines what the transaction sees.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Read at snapshot

Read the version of the key whose begin-timestamp is at or before the snapshot and end-timestamp is after.

return versions.find(v => v.begin <= tx.snap && (v.end === null || v.end > tx.snap));

The read sees a consistent snapshot, not the latest write, so it is not affected by concurrent writes.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Write new version

Create a new version with the value and a begin-timestamp, and set the end-timestamp of the previous version.

versions.push({val, begin: commitTs, end: null}); prev.end = commitTs;

The new version does not overwrite the old, so concurrent readers still see the old.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Garbage collect

Remove versions whose end-timestamp is older than the oldest live snapshot.

versions = versions.filter(v => v.end === null || v.end > oldestSnapshot);

GC reclaims space from versions no transaction can see.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Begin two transactions, write in one, and assert the other still reads the old value; commit the writer and assert a new transaction reads the new value; run GC and assert old versions are reclaimed; assert concurrent reads do not block writes.

The snapshot test begins two transactions, writes in one, and asserts the other still reads the old value, proving the snapshot is consistent. The commit test commits the writer and asserts a new transaction reads the new value, proving the commit makes the write visible.

The abort test writes in a transaction and aborts, and asserts a new transaction reads the old value, proving the abort does not create versions. The GC test commits several writes, runs GC, and asserts old versions are reclaimed, bounding the version list.

The no-lock test runs a long read and a concurrent write and asserts neither blocks, proving the read-no-lock. The consistency test runs several concurrent transactions and asserts each sees a consistent snapshot, not a mix of versions.

The version-visibility test creates a version, begins a transaction, creates a new version, and asserts the transaction sees the old version, not the new. The GC-visibility test runs GC while a long transaction is live and asserts the versions the transaction sees are not reclaimed, proving GC respects live snapshots.

The write-skew test demonstrates the limitation: two transactions read overlapping keys, each writes based on the read, and the result is inconsistent, proving snapshot isolation is not serializable. This test documents the limitation, not a bug.

pnpm vitest run

Observability

Track the snapshot isolation per transaction rate, the mvcc resource usage, and the error count as the three primary signals for the mvcc-snapshot-store system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the multi-version storage alongside the snapshot isolation per transaction so a correlation is visible at a glance, because a rising multi-version storage with a stable snapshot isolation per transaction means the system is doing more work per unit, not that it is failing.

Log every begin transaction transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the mvcc identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the snapshot isolation per transaction error rate crossing a threshold, the mvcc utilization exceeding a percentage, and the multi-version storage latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The mvcc-snapshot-store system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Run one store per process, because the timestamps are from a process-local clock. A cross-process MVCC needs a shared clock, such as a TrueTime or a hybrid clock, which is a distributed system and out of scope. A single-process store is the right tool for a database that runs in one process.

Run GC in the background, so it does not block transactions. A GC that runs in the foreground blocks reads and writes, which defeats the purpose of MVCC. A background GC that runs on a schedule or when the version count exceeds a threshold is the right design.

Monitor the version count and the GC rate. A growing version count means GC is not keeping up; a high GC rate means the overwrite rate is high. Both are operator signals, not bugs.

Set the GC threshold from the transaction length. A GC that runs too often reclaims versions that a long transaction might still need, which is a bug; a GC that runs too rarely lets the version list grow, which is a memory problem. The threshold should be longer than the longest transaction, so a live transaction never loses a version it needs.

Do not use the store for serializable isolation. Snapshot isolation allows write skew, which is a known limitation. A store that needs serializable isolation requires conflict detection, such as SSI, which is a different algorithm and out of scope.

Security considerations

Treat every input to the mvcc-snapshot-store system as untrusted, because the snapshot isolation per transaction path is the one place an external caller controls what the system processes. Validate the input shape before any mvcc operation, and reject early with a clear error rather than letting a malformed input propagate into the begin transaction phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:crypto credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured mvcc-snapshot-store fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the snapshot isolation per transaction endpoint per caller, because an unbounded mvcc operation is a resource leak as much as a security problem. A caller that can trigger the read at snapshot path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the begin transaction logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The mvcc-snapshot-store system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the mvcc structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• No serializable isolation; snapshot isolation allows write skew.
• The version list per key grows; GC bounds it but not tightly.
• Single-process; cross-process MVCC needs a shared clock.

There is no serializable isolation. Snapshot isolation allows write skew, where two transactions read overlapping keys and write based on the reads, producing an inconsistent result. Serializable isolation requires detecting this conflict, such as with Serializable Snapshot Isolation (SSI), which is out of scope.

The version list per key grows. GC bounds it, but not tightly, because the GC threshold must be longer than the longest transaction, so some old versions are kept longer than necessary. A tighter bound requires tracking the exact snapshots that need a version, which is more memory and more complexity.

It is single-process. The timestamps are from a process-local clock, so two processes would have inconsistent timestamps, which breaks the snapshot isolation. A cross-process MVCC needs a shared clock, which is a distributed system and out of scope.