阅读中文版本

Build a Log-Structured Store

A log-structured store that appends every write to a segment, indexes keys to segment offsets, and compacts segments in the background to reclaim space from superseded records.

log-structured-store/
├── src/segment.ts
├── src/index.ts
├── src/compact.ts
├── tests/store.test.ts
└── package.json

const off = await active.append({key, val}); index.set(key, {seg: active.id, off});

const {seg, off} = index.get(key); return segments[seg].read(off);

if (active.size > THRESHOLD) { readonly.push(active); active = newSegment(); }

const latest = latestPerKey(segments); writeSegment(latest); deleteOld(segments);

Project overview

A store that overwrites a record in place must seek to the offset, write, and fsync, which is slow on spinning disk and wasteful on SSD. A log-structured store appends every write to the end of a segment, so the write is sequential and fast. The old record stays, superseded but not removed, and a compaction reclaims the space later.

The index is the key to fast lookups. A sparse index maps each key to the segment and offset of its latest record, so a lookup is one index read and one seek. The index is sparse because it does not index every byte, only every key, so it fits in memory for a large store.

The segment rotation is what keeps the active segment bounded. A segment that grows forever is a single large file, which is hard to compact and slow to read. A segment that rotates at a size threshold is a sequence of bounded files, which are easy to compact individually and fast to read.

The compaction is what reclaims the space. A segment that has been overwritten has superseded records that waste space, and a compaction that merges segments, keeping only the latest record per key, reclaims that space. The compaction runs in the background, so writes and reads proceed while it runs.

The value of this project is the append-only write, not the index. Indexing is trivial; making every write a sequential append so the disk is used efficiently is the part worth learning, because that is the trick that makes a log-structured store fast on both spinning disk and SSD.

What you will build

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

• Append-only segment writes
• Sparse key-to-offset index
• Background segment compaction
• Tombstone deletes
• Segment rotation by size

A write appends a record to the active segment and updates a sparse index from key to segment and offset. A lookup reads the index, seeks to the offset, and reads the record. When the active segment reaches a size threshold, it is rotated to a read-only segment and a new active segment starts. Compaction merges read-only segments, discarding superseded records and tombstones.

Architecture and data model

The active segment is an append-only file. A write appends a record, which is a key length, a key, a value length, a value, and a timestamp. The append returns the offset, which the index stores. The segment is fsynced on every write, or batched for throughput, depending on the durability setting.

The sparse index is a map from key to a pointer (segment id, offset). The index is in memory, so a lookup is a map read and a seek. The index is sparse because it has one entry per key, not per record, so a key that is overwritten has one entry pointing to the latest record. The index is rebuilt on recovery by scanning the segments, which is slow but correct.

The segment rotation happens when the active segment reaches a size threshold. The active segment is marked read-only, a new active segment is created, and subsequent writes go to the new segment. The threshold is a tunable that trades segment count for segment size: large segments are fewer but harder to compact; small segments are more but easier to compact.

The compaction picks a set of read-only segments, merges them by key, keeping only the latest record per key, and drops tombstones. The merge is a k-way merge of sorted streams, which requires the segments to be sorted by key, which they are not, because the append is in write order, not key order. A sort during compaction, or an index that orders by key, is needed for a sorted merge. A hash-based merge that reads all records into a map is simpler but uses more memory.

The tombstone is a delete record. A delete appends a tombstone with the key and no value, and the index points to the tombstone. A lookup that reads a tombstone returns absent. The compaction drops tombstones for keys that have no live record, and keeps tombstones for keys that might be re-added, which is a subtlety that a real compaction must handle.

The recovery scans the segments from oldest to newest, rebuilding the index. The scan is O(total records), which is slow for a large store, so a snapshot of the index can be taken at compaction time to bound the recovery. The snapshot is the index, not the segments, so the recovery loads the snapshot and replays the segments since the snapshot.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• Disk space for segments and indexes

The dependencies cover the core needs:

• node:fs (built-in) — Segment and index 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

log-structured-store/ is organized so each concern is testable in isolation:

log-structured-store/
├── src/segment.ts
├── src/index.ts
├── src/compact.ts
├── tests/store.test.ts
└── package.json

Phase 1: Append write

Append a record to the active segment and update the sparse index.

const off = await active.append({key, val}); index.set(key, {seg: active.id, off});

The append is sequential, so it is fast on spinning disk and SSD.

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

Read the index, seek to the offset in the segment, and read the record.

const {seg, off} = index.get(key); return segments[seg].read(off);

The index is sparse, so it fits in memory; the read is one seek.

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: Rotate segment

When the active segment reaches a size threshold, rotate it to read-only and start a new active segment.

if (active.size > THRESHOLD) { readonly.push(active); active = newSegment(); }

Rotation bounds the active segment size and enables compaction.

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

Merge read-only segments, keeping only the latest record per key and dropping tombstones.

const latest = latestPerKey(segments); writeSegment(latest); deleteOld(segments);

Compaction reclaims space from superseded records and tombstones.

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, overwrite it, and assert the lookup returns the new value; delete a key and assert the lookup returns absent; compact and assert the segment size drops and lookups still succeed; put enough to rotate and assert lookups span segments.

The overwrite test puts a key, puts the same key with a new value, and asserts the lookup returns the new value, proving the index points to the latest record. The delete test puts a key, deletes it, and asserts the lookup returns absent, proving the tombstone is respected.

The rotation test puts enough to rotate a segment and asserts the lookup spans segments, so a key in an old segment is still found. The compaction test puts and overwrites enough to create superseded records, compacts, and asserts the segment size drops and every lookup still succeeds.

The tombstone-compaction test puts a key, deletes it, compacts, and asserts the key is absent and the tombstone is dropped, because there is no live record. The recovery test writes some records, simulates a crash by discarding the index, and asserts recovery rebuilds the index and lookups succeed.

The concurrent-compaction test writes while compaction runs and asserts no write is lost and no lookup returns stale data. The fsync test writes a record, crashes before the fsync, and asserts the record is absent, proving the fsync is the durability boundary.

The large-value test puts a value larger than a segment and asserts it is stored correctly, which may require spanning segments or a side file, a design choice the test exposes.

pnpm vitest run

Observability

Track the append-only segment writes rate, the log-structured resource usage, and the error count as the three primary signals for the log-structured-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 sparse key-to-offset index alongside the append-only segment writes so a correlation is visible at a glance, because a rising sparse key-to-offset index with a stable append-only segment writes means the system is doing more work per unit, not that it is failing.

Log every append write 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 log-structured 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 append-only segment writes error rate crossing a threshold, the log-structured utilization exceeding a percentage, and the sparse key-to-offset index 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 log-structured-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 directory, because two stores on the same segments would corrupt each other. The store is single-process, like the WAL store, and a multi-process store needs a lock or a shared log, which is a distributed system.

Choose the segment size from the compaction cost and the read pattern. A large segment is cheaper to compact, because the per-segment overhead is amortized, but a large segment that is partially superseded wastes more space before compaction. A small segment compacts more often but reclaims space sooner. The right size depends on the overwrite rate.

Run compaction in the background, so writes and reads are not blocked. A compaction that blocks writes is a latency spike, and a compaction that blocks reads is a stall. A background compaction that writes to a new segment and atomically swaps is the right design, because it does not block the active segment.

Monitor the segment count, the compaction rate, and the space amplification. A growing segment count means compaction is not keeping up; a high space amplification means the overwrite rate is high and compaction should run more often. Both are operator signals.

Do not use the store for range scans. The index is by key, not by order, so a range scan is a full scan. A store that needs range scans should use an ordered structure, such as a B-tree, which is a different design.

Security considerations

Treat every input to the log-structured-store system as untrusted, because the append-only segment writes path is the one place an external caller controls what the system processes. Validate the input shape before any log-structured operation, and reject early with a clear error rather than letting a malformed input propagate into the append write 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 log-structured-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 append-only segment writes endpoint per caller, because an unbounded log-structured operation is a resource leak as much as a security problem. A caller that can trigger the 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 append write 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 log-structured-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 log-structured 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 with more keys than memory is out of scope.
• No range scans; the index is by key hash, not order.
• Compaction is stop-the-world for the compacted segments.

The index is in memory. A store with more keys than memory is out of scope, because the index would not fit. A disk-backed index, such as a B-tree, is a different structure that handles larger key counts at the cost of lookup speed.

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

Compaction is stop-the-world for the compacted segments. A compaction that reads and merges segments blocks lookups on those segments, because the old segments are being replaced. A compaction that writes to a new segment and atomically swaps is non-blocking, but the swap is still a brief pause. A fully non-blocking compaction is a real improvement but out of scope.