阅读中文版本

Build a KV Store with WAL

A persistent key-value store that writes a write-ahead log for durability, an in-memory index for fast lookups, and checkpoints to bound recovery time.

kv-store-wal/
├── src/store.ts
├── src/wal.ts
├── src/checkpoint.ts
├── tests/store.test.ts
└── package.json

await wal.append({op:"put", key, val}); index.set(key, val); await wal.sync();

return index.get(key);

await snapshot.write(index); await wal.truncate(upTo);

const snap = await snapshot.load(); for (const r of wal.tail()) apply(r, snap);

Project overview

A key-value store that writes to memory and forgets to disk is fast and wrong, because a crash loses everything. A store that writes to disk on every read is slow and right. A write-ahead log is the middle ground: writes append to a log and fsync, so they survive a crash, and an in-memory index makes lookups fast without reading the log.

The write-ahead log is an append-only file of records, each a put or a delete with a key and a value. A write appends the record, updates the in-memory index, and fsyncs the log before acknowledging. The fsync is the durability guarantee: the record is on disk before the ack, so a crash after the ack does not lose the write.

The in-memory index is a map from key to value, updated on every write. A lookup reads the index and returns the value, with no disk read, so it is O(1) and fast. The index is rebuilt on recovery by replaying the log, so it is not persisted directly, only through the log.

The checkpoint is what bounds the recovery time. A log that grows forever makes recovery slow, because replay is O(log size). A checkpoint writes the full index to a snapshot file and truncates the log, so recovery loads the snapshot and replays only the tail, which is fast.

The value of this project is the fsync before ack, not the log. Appending to a file is trivial; making the write durable before telling the client it succeeded is the part worth learning, because that is the guarantee that makes the store safe to use for data that must not be lost.

What you will build

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

• Write-ahead log durability
• In-memory index for lookups
• Checkpoint to bound recovery
• Atomic multi-key transactions
• Crash recovery and replay

A write appends a record to the write-ahead log, updates the in-memory index, and fsyncs the log. A lookup reads the index and returns the value. A checkpoint writes the full index to a snapshot file and truncates the log. Recovery loads the snapshot and replays the log tail.

Architecture and data model

The write-ahead log is an append-only file of records. A record is a type byte (put or delete), a key length, a key, a value length, and a value. The format is binary for compactness and self-describing for recovery. The log is fsynced after every write, which is the durability guarantee and the performance bottleneck.

The in-memory index is a Map from key to value. A put sets the key, a delete deletes it. The index is the only structure a lookup reads, so lookups are O(1) with no disk I/O. The index is rebuilt on recovery, so it is not persisted directly.

The checkpoint writes the full index to a snapshot file. The snapshot is a binary file of key-value pairs, written atomically to a temporary file and renamed. After the snapshot is written, the log is truncated up to the checkpoint position, so the log holds only the tail. The checkpoint is a stop-the-world operation for the index, but it is infrequent.

The recovery loads the snapshot, which rebuilds the index, then replays the log tail, which applies the writes since the checkpoint. The replay is a sequential scan of the log, applying each record to the index. The recovery is fast because the tail is short, bounded by the checkpoint frequency.

The atomic multi-key transaction appends a begin record, the put and delete records, and a commit record to the log. The index is updated only on commit, so a crash before commit leaves the index unchanged. A recovery that sees a begin without a commit skips the records, so the transaction is all or nothing.

The fsync is the performance bottleneck. A write that fsyncs on every record is durable but slow, because fsync is a system call that waits for the disk. A batch write that appends several records and fsyncs once is faster, because the fsync cost is amortized. The batch is a tunable that trades latency for throughput.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• Disk space for the log and snapshots

The dependencies cover the core needs:

• node:fs (built-in) — Write-ahead log and snapshot persistence

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

kv-store-wal/ is organized so each concern is testable in isolation:

kv-store-wal/
├── src/store.ts
├── src/wal.ts
├── src/checkpoint.ts
├── tests/store.test.ts
└── package.json

Phase 1: Write and fsync

Append a put or delete record to the WAL, update the index, and fsync before acknowledging.

await wal.append({op:"put", key, val}); index.set(key, val); await wal.sync();

The fsync before ack guarantees the write survives a crash.

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: Point lookup

Read the in-memory index and return the value, or undefined for a missing key.

return index.get(key);

The index is in memory, so a lookup is O(1) with no disk read.

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: Checkpoint

Write the full index to a snapshot, then truncate the log up to the checkpoint.

await snapshot.write(index); await wal.truncate(upTo);

A checkpoint bounds the log size and the recovery time.

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: Recovery

Load the snapshot, then replay the log tail to rebuild the index.

const snap = await snapshot.load(); for (const r of wal.tail()) apply(r, snap);

Recovery replays only the tail, not the full log, so it is fast.

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

Put a key, crash, recover, and assert the key is present; delete a key, crash, recover, and assert it is absent; checkpoint, write more, crash, and assert recovery replays only the tail; do an atomic multi-key transaction and assert all or none survive.

The durability test puts a key, simulates a crash by discarding the index, recovers, and asserts the key is present. The delete test deletes a key, crashes, recovers, and asserts the key is absent, proving the delete is durable.

The checkpoint test writes enough to trigger a checkpoint, writes more, crashes, and asserts recovery replays only the tail, not the full log. The recovery-time test measures the recovery time and asserts it is bounded by the tail size, not the log size.

The transaction test begins a transaction, puts two keys, commits, crashes, and asserts both keys are present. The abort test begins a transaction, puts a key, does not commit, crashes, and asserts the key is absent, proving the transaction is atomic.

The fsync test puts a key, crashes before the fsync, and asserts the key is absent, proving the fsync is the durability boundary. The idempotent-recovery test recovers twice and asserts the index is the same, proving recovery is idempotent.

The concurrent-write test puts two keys concurrently and asserts both are present after recovery, proving the log is append-only and concurrent writes do not corrupt it.

pnpm vitest run

Observability

Track the write-ahead log durability rate, the kv-store resource usage, and the error count as the three primary signals for the kv-store-wal 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 in-memory index for lookups alongside the write-ahead log durability so a correlation is visible at a glance, because a rising in-memory index for lookups with a stable write-ahead log durability means the system is doing more work per unit, not that it is failing.

Log every write and fsync 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 kv-store 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 write-ahead log durability error rate crossing a threshold, the kv-store utilization exceeding a percentage, and the in-memory index for lookups 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 kv-store-wal 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 file, because two processes on the same log would corrupt it, as both would append and fsync independently. A single-process store is the simplest safe deployment, and a multi-process store needs a lock or a shared log, which is a distributed system.

Checkpoint on a schedule or when the log exceeds a size threshold. A schedule is simpler; a threshold is more adaptive. The right choice depends on the write pattern: a steady write rate suits a schedule, a bursty rate suits a threshold. The checkpoint bounds the recovery time, so the frequency is a trade-off between checkpoint cost and recovery time.

Batch writes to amortize the fsync. A write that fsyncs on every record is durable but slow; a batch that fsyncs once per group is faster and still durable, because the batch is committed atomically. The batch size is a tunable that trades latency for throughput.

Monitor the log size, the checkpoint rate, and the recovery time. A growing log means checkpoints are not happening; a long recovery time means the tail is too long. Both are operator signals to checkpoint more often.

Do not use the store for data larger than memory. The index is in memory, so a store larger than memory is out of scope. A disk-backed index, such as a B-tree, is a different structure that trades lookup speed for capacity.

Security considerations

Treat every input to the kv-store-wal system as untrusted, because the write-ahead log durability path is the one place an external caller controls what the system processes. Validate the input shape before any kv-store operation, and reject early with a clear error rather than letting a malformed input propagate into the write and fsync 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:fs credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured kv-store-wal 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 write-ahead log durability endpoint per caller, because an unbounded kv-store operation is a resource leak as much as a security problem. A caller that can trigger the point lookup 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 write and fsync 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 kv-store-wal 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 kv-store 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

• The index is in memory; a store larger than memory is out of scope.
• No range scans; this is a point store.
• Single-process; two processes on the same log corrupt it.

The index is in memory. A store larger than memory is out of scope, because the index would not fit. A disk-backed index, such as a B-tree or an LSM, is a different structure that handles larger data at the cost of lookup speed.

There are no range scans. The store is a point store, keyed by a hash, so a range of keys is not meaningful. A store that needs range scans should use an ordered structure, which is a different design.

It is single-process. Two processes on the same log would corrupt it, because both would append and fsync independently. A multi-process store needs a lock or a shared log, which is a distributed system and out of scope.