阅读中文版本

Build a Dedup Store on LSM

A log-structured merge store with content-addressed chunks that deduplicates writes by hash, compacts SSTables in the background, and serves point lookups via an index.

dedup-store-lsm/
├── src/memtable.ts
├── src/sstable.ts
├── src/compact.ts
├── tests/store.test.ts
└── package.json

const h = sha256(chunk); memtable.set(h, chunk);

const ss = writeSSTable(sortedEntries); ss.bloom = buildBloom(keys);

if (memtable.has(k)) return memtable.get(k); for (const ss of tables) if (ss.bloom.has(k)) if (ss.get(k)) return it;

const merged = mergeKWay(tables); writeSSTable(merged); deleteOld(tables);

Project overview

A store that writes the same content twice is wasting disk. A content-addressed store keys every chunk by its hash, so a second write of the same bytes hits the same key and is a no-op. The dedup is automatic, because the key is the content.

The log-structured merge tree is what keeps the writes fast. A write goes to an in-memory memtable, which is a sorted map. When the memtable is full, it is flushed to an immutable SSTable on disk, and a new memtable starts. Writes never overwrite, they only append, so the disk is a log of sorted runs.

The compaction is what keeps the reads fast. A point lookup checks the memtable, then each SSTable from newest to oldest. The more SSTables, the more checks, and the slower the read. Compaction merges several SSTables into one, discarding duplicate keys, so the number of tables a lookup must check stays bounded.

The Bloom filter per SSTable is what keeps the lookups cheap. A lookup for a missing key would otherwise check every SSTable, because the key could be in any. The Bloom filter says definitely-absent for most, so the lookup skips them and checks only the few that might contain the key.

The value of this project is the dedup, not the LSM. An LSM is a well-known structure; keying it by content hash so identical writes are free is the part worth learning, because that is the trick that turns a key-value store into a deduplicating store without a separate dedup layer.

What you will build

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

• Content-addressed dedup
• Memtable plus SSTable
• Background compaction
• Point lookup via sparse index
• Bloom filter per SSTable

A write hashes the chunk and inserts (hash, chunk) into an in-memory memtable. On flush, the memtable becomes an immutable SSTable on disk with a sparse index and a Bloom filter. A point lookup checks the memtable, then each SSTable from newest to oldest, using the Bloom filter to skip SSTables that definitely lack the key. Compaction merges SSTables into fewer, larger ones, discarding duplicate keys.

Architecture and data model

The memtable is a sorted map in memory, keyed by the content hash. A write inserts into the memtable, which is fast because it is in memory. When the memtable reaches a size threshold, it is frozen, flushed to an SSTable, and a new memtable starts. The flush sorts the entries by key, writes them to a file, and builds a sparse index that maps every n-th key to a file offset.

The SSTable is an immutable sorted file on disk. The sparse index lets a lookup seek to the right block without scanning the file. The Bloom filter, built from the keys during flush, lets a lookup skip the SSTable entirely for a key that is definitely absent. Both are loaded into memory when the SSTable is opened, so a lookup is a Bloom check, an index seek, and a block read.

A point lookup checks the memtable first, because it has the newest writes. If the key is not there, it checks each SSTable from newest to oldest, because a newer SSTable may have a newer value for the key. The Bloom filter skips SSTables that definitely lack the key, so the lookup checks only the few that might contain it.

Compaction picks a set of SSTables, merges them by key with a k-way merge, and writes the result as a new SSTable. Duplicate keys are resolved by keeping the newest value, which is the one from the newest SSTable. The old SSTables are deleted after the new one is written, so the merge is atomic from the lookup perspective.

The compaction strategy is size-tiered: compact SSTables of similar size into a larger one. This bounds the number of SSTables at each size level, so a lookup checks at most a few tables per level. The compaction runs in the background, so writes and reads proceed while it runs, though the merged SSTables are briefly unavailable.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• Disk space for SSTables and compaction temporary files

The dependencies cover the core needs:

• node:crypto (built-in) — SHA-256 content addressing
• node:fs (built-in) — SSTable 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

dedup-store-lsm/ is organized so each concern is testable in isolation:

dedup-store-lsm/
├── src/memtable.ts
├── src/sstable.ts
├── src/compact.ts
├── tests/store.test.ts
└── package.json

Phase 1: Write and dedup

Hash the chunk, insert into the memtable keyed by hash; identical content hits the same key and is stored once.

const h = sha256(chunk); memtable.set(h, chunk);

The hash is the key, so a second write of the same content is a no-op.

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: Flush to SSTable

When the memtable is full, sort by key, write an SSTable with a sparse index and a Bloom filter, and start a new memtable.

const ss = writeSSTable(sortedEntries); ss.bloom = buildBloom(keys);

The Bloom filter lets a lookup skip SSTables that definitely lack the key.

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

Check the memtable, then each SSTable newest to oldest, using the Bloom filter to skip.

if (memtable.has(k)) return memtable.get(k); for (const ss of tables) if (ss.bloom.has(k)) if (ss.get(k)) return it;

Newest-first checks the most likely SSTable first.

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

Merge several SSTables into one, discarding duplicate keys, and rebuild the sparse index and Bloom filter.

const merged = mergeKWay(tables); writeSSTable(merged); deleteOld(tables);

Compaction bounds the number of SSTables a lookup must check.

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

Write the same chunk twice and assert it is stored once; write a thousand chunks, flush, and assert a point lookup finds each; compact and assert the SSTable count drops and lookups still succeed; look up a missing key and assert the Bloom filter skips every SSTable.

The dedup test writes the same chunk twice and asserts the store contains one entry, not two, proving the content addressing deduplicates. The flush test writes enough chunks to fill the memtable, asserts an SSTable is written, and asserts a point lookup finds each chunk.

The lookup test writes a thousand chunks, flushes, and asserts a point lookup for each returns the right content. The missing-key test looks up a key that was never written and asserts the Bloom filter skips every SSTable, so the lookup is fast even with many tables.

The compaction test writes enough to create several SSTables, compacts, and asserts the table count drops and every lookup still succeeds. The newest-wins test writes a key, flushes, writes the same key with new content, flushes, and asserts the lookup returns the newest content.

The Bloom-skip test writes a thousand keys, flushes, and looks up a missing key, asserting the Bloom filter reports definitely-absent for every SSTable so no block is read. The sparse-index test seeks to a key in the middle of an SSTable and asserts the index directs the seek to the right block.

The concurrent-compaction test writes while compaction runs and asserts no write is lost and no lookup returns stale data, proving the compaction is safe under concurrency.

pnpm vitest run

Observability

Track the content-addressed dedup rate, the lsm resource usage, and the error count as the three primary signals for the dedup-store-lsm 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 memtable plus sstable alongside the content-addressed dedup so a correlation is visible at a glance, because a rising memtable plus sstable with a stable content-addressed dedup means the system is doing more work per unit, not that it is failing.

Log every write and dedup 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 lsm 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 content-addressed dedup error rate crossing a threshold, the lsm utilization exceeding a percentage, and the memtable plus sstable 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 dedup-store-lsm 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 writer per store to avoid concurrent memtable flushes that would produce overlapping SSTables. Compaction can run in a background thread or a separate process, because it reads and writes SSTables, not the memtable. A single writer and a background compactor is the simplest safe deployment.

Size the memtable from the write rate and the flush cost. A large memtable flushes less often but uses more memory and a larger SSTable. A small memtable flushes often but produces many small SSTables that need compaction. The right size is the one where flush keeps up with writes.

Trigger compaction when the SSTable count at a level exceeds a threshold, not on a schedule. A schedule compacts too often or too rarely; a threshold compacts when needed. The threshold is a tunable that trades write amplification for read amplification.

Monitor the SSTable count, the memtable flush rate, and the compaction rate. A growing SSTable count means compaction is not keeping up; a growing memtable means flush is not keeping up. Both are operator signals to scale or tune.

Do not use this store for range scans. The SSTables are sorted by hash, not by a meaningful order, so a range scan is a full scan. A separate ordered index, if needed, is a different structure.

Security considerations

Treat every input to the dedup-store-lsm system as untrusted, because the content-addressed dedup path is the one place an external caller controls what the system processes. Validate the input shape before any lsm operation, and reject early with a clear error rather than letting a malformed input propagate into the write and dedup 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 dedup-store-lsm 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 content-addressed dedup endpoint per caller, because an unbounded lsm operation is a resource leak as much as a security problem. A caller that can trigger the flush to sstable 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 dedup 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 dedup-store-lsm 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 lsm 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 range scans; this is a point store, not an ordered store.
• Compaction is stop-the-world for the merged SSTables; a large compaction pauses lookups on those tables.
• The Bloom filter is per SSTable and not updated on compaction; it is rebuilt.

There are no range scans. The store is keyed by content hash, which is random, so a range of hashes is meaningless. A store that needs range scans should use a meaningful key order, not a hash, and that is a different design.

Compaction is stop-the-world for the merged SSTables. A lookup that hits a table being compacted waits for the merge to finish, because the old table is being deleted. A large compaction can pause lookups on those tables for seconds, which is a latency spike. Incremental compaction that does not block is a real improvement but out of scope.

The Bloom filter is per SSTable and rebuilt on compaction. A Bloom filter that is updated incrementally, with a counting array, would support deletion, but this store does not delete, so the rebuild is fine. The rebuild cost is part of compaction, which is already a background operation.