Storage Engines & DatabasesBuild a Simple Key-Value StoreHard

Crash Recovery Using WAL and Checkpoints

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

Replay Log After Crash

The WAL records memtable inserts before they are durable in SSTables. After crash, reopen the log, redo entries since the last checkpoint, and rebuild in-memory state. ARIES formalizes this as analysis, redo, undo phases in larger systems.

Recovery Pass

Scan WAL sequentially, validate checksums, apply idempotent redo to memtable, then mark checkpoint.

c
Loading…

Checksum failure stops replay to avoid corruption spread
Checkpoint truncates WAL for faster restart
Idempotent redo safe if partially applied before crash
Test by killing process mid-write then restarting

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 WAL replay that restores memtable contents after simulated crash. This exercise asks you to skip records before the checkpoint LSN and verify recovered key set.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Implementation Task

Write a C program that implements crash recovery for a key-value store using WAL.

Requirements:

Define a LogRecord: lsn, key, old_value, new_value, committed (int)
Define a database state: array of 8 key-value pairs, initially zeros
Define a WAL as an array of 6 log records:
1. LSN=1, key=0, old=0, new=10, committed=1
2. LSN=2, key=1, old=0, new=20, committed=1
3. LSN=3, key=2, old=0, new=30, committed=0 (uncommitted — transaction active at crash)
4. LSN=4, key=0, old=10, new=15, committed=1
5. LSN=5, key=3, old=0, new=40, committed=0 (uncommitted)
6. LSN=6, key=1, old=20, new=25, committed=1
Simulate a checkpoint at LSN=2: mark that pages for keys 0 and 1 were flushed
Simulate crash recovery:
- Redo phase: replay all log records from LSN=1 onwards. For each record, if committed=1, apply new_value to the key
- Track which keys were modified by uncommitted transactions
- Undo phase: for uncommitted transactions, restore old_value
Print database state after checkpoint, after crash (some pages not flushed), and after recovery
Print which log records were redone and which were undone
Verify that the final state is consistent: committed changes persist, uncommitted changes are rolled back

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

Database Internals

Related Read

ARIES Recovery Algorithm

Related Read

Database Recovery Explained

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

Crash Recovery Using WAL and Checkpoints

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

Replay Log After Crash

Recovery Pass

Scan WAL sequentially, validate checksums, apply idempotent redo to memtable, then mark checkpoint.

c
Loading…

Checksum failure stops replay to avoid corruption spread
Checkpoint truncates WAL for faster restart
Idempotent redo safe if partially applied before crash
Test by killing process mid-write then restarting

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 WAL replay that restores memtable contents after simulated crash. This exercise asks you to skip records before the checkpoint LSN and verify recovered key set.

Document one invariant you will assert in tests and how you would detect its violation from observable symptoms.

Implementation Task

Write a C program that implements crash recovery for a key-value store using WAL.

Requirements:

Define a LogRecord: lsn, key, old_value, new_value, committed (int)
Define a database state: array of 8 key-value pairs, initially zeros
Define a WAL as an array of 6 log records:
1. LSN=1, key=0, old=0, new=10, committed=1
2. LSN=2, key=1, old=0, new=20, committed=1
3. LSN=3, key=2, old=0, new=30, committed=0 (uncommitted — transaction active at crash)
4. LSN=4, key=0, old=10, new=15, committed=1
5. LSN=5, key=3, old=0, new=40, committed=0 (uncommitted)
6. LSN=6, key=1, old=20, new=25, committed=1
Simulate a checkpoint at LSN=2: mark that pages for keys 0 and 1 were flushed
Simulate crash recovery:
- Redo phase: replay all log records from LSN=1 onwards. For each record, if committed=1, apply new_value to the key
- Track which keys were modified by uncommitted transactions
- Undo phase: for uncommitted transactions, restore old_value
Print database state after checkpoint, after crash (some pages not flushed), and after recovery
Print which log records were redone and which were undone
Verify that the final state is consistent: committed changes persist, uncommitted changes are rolled back

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

Database Internals

Related Read

ARIES Recovery Algorithm

Related Read

Database Recovery Explained

Open Source

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

View on Github