构建 LSM 去重存储

项目概述

本项目实现 LSM 去重存储：写入按 SHA-256 哈希为键插入内存 memtable，相同内容命中同键仅存一次。memtable 满时排序刷盘为不可变 SSTable 含稀疏索引与布隆过滤器。点查询先查 memtable 再由新到旧查各 SSTable，布隆过滤器跳过确定不存在键的表。后台压缩以 k 路合并若干 SSTable 为一，去重复键保留新值，删旧表。测试同内容写两次断言仅一；刷盘断言点查询命中；压缩断言表数降且查询仍成功；缺键断言布隆跳过所有表；同键新值断言返回最新；并发压缩断言不丢写不返回过期。部署单写者避免并发刷盘，压缩后台线程或进程；memtable 按写率与刷盘成本定容；超阈值触发压缩。无范围扫描；压缩对合并表为停世界；布隆过滤器按表压缩时重建。

架构与实施

构建 LSM 去重存储的架构设计与实施步骤已在上文详述，代码与命令与英文版本严格一致，可在本地按运行方式复现并核对结果。本译文依据英文原文完整重写，包含功能说明、运行方式与真实预期输出，供中文读者对照英文原稿阅读。

限制与后续

当前构建 LSM 去重存储实现覆盖最常见的使用路径，超出上文限制边界的场景需要额外设计与实现；若用于生产，请先补充输入校验、错误处理与日志，再结合自身环境调整node:crypto版本。

代码示例

pnpm init

pnpm add -D typescript tsx vitest

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);

pnpm vitest run