Storage Engines & DatabasesBuild a Simple Key-Value StoreHard

Multi-Version Concurrency Control (MVCC)

Master the fundamental concepts of build a simple key-value store through this focused micro-challenge.

~90 minutes Build a Simple Key-Value Store Ready to learn

Topic Overview

Multiple Versions Per Key

Multi-version concurrency control stores several values for one key tagged with sequence or timestamp. Readers observe a snapshot without blocking writers; writers append new versions. PostgreSQL heap tuples and RocksDB with column families use variants of this idea.

Version Chain Sketch

Map key to sorted list of (seq, value) pairs. Read picks latest version with seq <= read_snapshot.

c
Loading…

Garbage-collect versions older than oldest active snapshot
MVCC pairs naturally with LSM append-only writes
Conflicts detected at commit if snapshot rules violated
Track min_active_snapshot for retention policy

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement simplified MVCC get/put with snapshot reads. This exercise requires a reader at snapshot S not to see writes committed after S.

Implementation Task

Write a C program that implements a simplified MVCC key-value store.

Requirements:

Define a Version struct: value (int), commit_ts (int), next (pointer to older version)
Define a KeyEntry struct: key (int), head (pointer to newest version)
Implement write_key(store, key, value, commit_ts): add a new version at the head of the chain
Implement read_key(store, key, read_ts): traverse the version chain and return the value with the largest commit_ts <= read_ts
Simulate transactions:
- T1 starts at TS=1, writes key=10 value=100 at TS=2
- T2 starts at TS=3, reads key=10 (should see 100)
- T2 writes key=10 value=200 at TS=4
- T3 starts at TS=1, reads key=10 (should still see 100 — snapshot isolation)
- T4 starts at TS=5, reads key=10 (should see 200)
Print the version chain for key=10 showing all versions and their commit timestamps
Print what each transaction sees
Implement garbage_collection(store, oldest_active_ts): remove versions with commit_ts < oldest_active_ts
Run GC with oldest_active_ts=3 and show the remaining version chain
Explain how MVCC prevents dirty reads and non-repeatable reads

Progressive Hints

Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.

Resources

Related Read

Designing Data-Intensive Applications

Open Source

All starter code and reference implementations are available for your local setup.

View on Github

Storage Engines & DatabasesBuild a Simple Key-Value StoreHard

Multi-Version Concurrency Control (MVCC)

Master the fundamental concepts of build a simple key-value store through this focused micro-challenge.

Open Editor

~90 minutes Build a Simple Key-Value Store Ready to learn

Topic Overview

Multiple Versions Per Key

Version Chain Sketch

Map key to sorted list of (seq, value) pairs. Read picks latest version with seq <= read_snapshot.

c
Loading…

Garbage-collect versions older than oldest active snapshot
MVCC pairs naturally with LSM append-only writes
Conflicts detected at commit if snapshot rules violated
Track min_active_snapshot for retention policy

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

Trace first: walk one failing input step by step
Read the manual: skim the official doc for the mechanism named in this task
Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will implement simplified MVCC get/put with snapshot reads. This exercise requires a reader at snapshot S not to see writes committed after S.

Implementation Task

Write a C program that implements a simplified MVCC key-value store.

Requirements:

Define a Version struct: value (int), commit_ts (int), next (pointer to older version)
Define a KeyEntry struct: key (int), head (pointer to newest version)
Implement write_key(store, key, value, commit_ts): add a new version at the head of the chain
Implement read_key(store, key, read_ts): traverse the version chain and return the value with the largest commit_ts <= read_ts
Simulate transactions:
- T1 starts at TS=1, writes key=10 value=100 at TS=2
- T2 starts at TS=3, reads key=10 (should see 100)
- T2 writes key=10 value=200 at TS=4
- T3 starts at TS=1, reads key=10 (should still see 100 — snapshot isolation)
- T4 starts at TS=5, reads key=10 (should see 200)
Print the version chain for key=10 showing all versions and their commit timestamps
Print what each transaction sees
Implement garbage_collection(store, oldest_active_ts): remove versions with commit_ts < oldest_active_ts
Run GC with oldest_active_ts=3 and show the remaining version chain
Explain how MVCC prevents dirty reads and non-repeatable reads

Progressive Hints

Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.

Resources

Related Read

Designing Data-Intensive Applications

Open Source

All starter code and reference implementations are available for your local setup.

View on Github