lsm-tree-leveled-compaction
The implementation is at ~/lsm-tree/lsm-tree.js and contains a full LSM-tree storage engine with 5 core components:
1. Scalable Bloom Filter — Dynamically grows by chaining fixed-capacity bloom filters with doubling sizes, guaranteeing a bounded false positive rate. Each SSTable gets one, enabling zero-disk-read negative lookups.
class ScalableBloomFilter {
add(key) {
if (this.count >= this.totalCapacity) {
const newCap = this.initialCapacity * Math.pow(this.scaleFactor, this.filters.length);
const fpp = this.falsePositiveRate / Math.pow(this.scaleFactor, this.filters.length);
this.filters.push(new BloomFilter(Math.ceil(newCap), fpp));
this.totalCapacity += newCap;
}
this.filters[this.filters.length - 1].add(key);
this.count++;
}
contains(key) {
for (let i = 0; i < this.filters.length; i++) {
if (this.filters[i].contains(key)) return true;
}
return false;
}
}
2. SSTable — Binary format with data blocks, scalable bloom filter, and in-memory index. Point lookups check the bloom filter (memory), binary search the index (memory), then read exactly one data entry from disk.
static get(filePath, key, handle) {
if (!handle.bloomFilter.contains(key)) // 0 disk reads
return { found: false, bloomPass: false };
const idx = SSTable._binarySearchIndex(handle.index, key); // memory
// ... single fs.readSync to fetch data entry // 1 disk read
return { found: true, key, value };
}
3. Memtable — In-memory Map sorted on flush. Backed by a synchronous WAL (fs.appendFileSync) for crash durability. Flushes to an L0 SSTable when full.
4. Leveled Compaction — Size ratio T=10. L0 flushes accumulate up to a file count limit (4), then get merged into L1. Each subsequent level has 10× the max size of the previous level. The multi-way merge iterator properly deduplicates (most recent wins) and skips tombstones.
_compactLevel(level) {
const nextLevel = level + 1;
const maxSize = this.baseLevelSize * Math.pow(this.sizeRatio, nextLevel - 1);
// read source files + overlapping files in next level
// multi-way merge sort
// split merged output into target-size SSTables
// delete old files, add new files to next level
if (nextLevelSize > maxSize) this._compactLevel(nextLevel); // cascade
}
5. Amplification Measurement — Tracks bytesWritten, bytesRead, sstableReads, userDataBytes, uniqueKeys to compute all three metrics.
All 10 tests pass, including edge cases: | Test | Result | |------|--------| | Empty database | ✅ | | Basic put/get | ✅ | | Key overwrite (returns latest) | ✅ | | SSTable round-trip serialization | ✅ | | Scalable bloom filter (6-filter chain, 1.76% FPR) | ✅ | | WAL crash recovery | ✅ (84 bytes WAL, all 3 keys recovered) | | Memtable flush to L0 | ✅ (2 files, all 100 keys readable) | | Bloom filter point lookups | ✅ (1000/1000 positive, 0/1000 false negatives, 1.08% FPR) | | Leveled compaction T=10 | ✅ (4 levels, 9 files in L3, WA=7.02, 500/500 data integrity) | | Zipfian workload (100K ops) | ✅ (WA=1.12, RA=1.64, SA=2.68) | **200K operation Zipfian run (θ=0.99, range=50K):** ``` Write Amplification: 1.61 — each byte of user data → 1.61 bytes written Read Amplification: 4.03 — avg 4 SSTable checks per point lookup Space Amplification: 2.97 — disk usage 2.97× unique data size Bloom filter FPR: 0.9979% — below 1% target Missing key false positives: 0 ``` The read amplification of ~4 means the bloom filter successfully filters out most negative checks, keeping actual disk reads minimal. With more levels, this increases linearly as each level may need checking. Level structure: L0 (0 files, compacted away), L1 (0 files, compacted away), L2 (14 files, 2.4 MB). ---
{"model": "node20", "problem_class": "lsm-tree-leveled-compaction", "result": "passed", "tests": 10}The implementation is at ~/lsm-tree/lsm-tree.js and contains a full LSM-tree storage engine with 5 core components:
1. Scalable Bloom Filter — Dynamically grows by chaining fixed-capacity bloom filters with doubling sizes, guaranteeing a bounded false positive rate. Each SSTable gets one, enabling zero-disk-read negative lookups.
class ScalableBloomFilter {
add(key) {
if (this.count >= this.totalCapacity) {
const newCap = this.initialCapacity * Math.pow(this.scaleFactor, this.filters.length);
const fpp = this.falsePositiveRate / Math.pow(this.scaleFactor, this.filters.length);
this.filters.push(new BloomFilter(Math.ceil(newCap), fpp));
this.totalCapacity += newCap;
}
this.filters[this.filters.length - 1].add(key);
this.count++;
}
contains(key) {
for (let i = 0; i < this.filters.length; i++) {
if (this.filters[i].contains(key)) return true;
}
return false;
}
}
2. SSTable — Binary format with data blocks, scalable bloom filter, and in-memory index. Point lookups check the bloom filter (memory), binary search the index (memory), then read exactly one data entry from disk.
static get(filePath, key, handle) {
if (!handle.bloomFilter.contains(key)) // 0 disk reads
return { found: false, bloomPass: false };
const idx = SSTable._binarySearchIndex(handle.index, key); // memory
// ... single fs.readSync to fetch data entry // 1 disk read
return { found: true, key, value };
}
3. Memtable — In-memory Map sorted on flush. Backed by a synchronous WAL (fs.appendFileSync) for crash durability. Flushes to an L0 SSTable when full.
4. Leveled Compaction — Size ratio T=10. L0 flushes accumulate up to a file count limit (4), then get merged into L1. Each subsequent level has 10× the max size of the previous level. The multi-way merge iterator properly deduplicates (most recent wins) and skips tombstones.
_compactLevel(level) {
const nextLevel = level + 1;
const maxSize = this.baseLevelSize * Math.pow(this.sizeRatio, nextLevel - 1);
// read source files + overlapping files in next level
// multi-way merge sort
// split merged output into target-size SSTables
// delete old files, add new files to next level
if (nextLevelSize > maxSize) this._compactLevel(nextLevel); // cascade
}
5. Amplification Measurement — Tracks bytesWritten, bytesRead, sstableReads, userDataBytes, uniqueKeys to compute all three metrics.
All 10 tests pass, including edge cases: | Test | Result | |------|--------| | Empty database | ✅ | | Basic put/get | ✅ | | Key overwrite (returns latest) | ✅ | | SSTable round-trip serialization | ✅ | | Scalable bloom filter (6-filter chain, 1.76% FPR) | ✅ | | WAL crash recovery | ✅ (84 bytes WAL, all 3 keys recovered) | | Memtable flush to L0 | ✅ (2 files, all 100 keys readable) | | Bloom filter point lookups | ✅ (1000/1000 positive, 0/1000 false negatives, 1.08% FPR) | | Leveled compaction T=10 | ✅ (4 levels, 9 files in L3, WA=7.02, 500/500 data integrity) | | Zipfian workload (100K ops) | ✅ (WA=1.12, RA=1.64, SA=2.68) | **200K operation Zipfian run (θ=0.99, range=50K):** ``` Write Amplification: 1.61 — each byte of user data → 1.61 bytes written Read Amplification: 4.03 — avg 4 SSTable checks per point lookup Space Amplification: 2.97 — disk usage 2.97× unique data size Bloom filter FPR: 0.9979% — below 1% target Missing key false positives: 0 ``` The read amplification of ~4 means the bloom filter successfully filters out most negative checks, keeping actual disk reads minimal. With more levels, this increases linearly as each level may need checking. Level structure: L0 (0 files, compacted away), L1 (0 files, compacted away), L2 (14 files, 2.4 MB). ---
{"model": "node20", "problem_class": "lsm-tree-leveled-compaction", "result": "passed", "tests": 10}