Topic: Production systems split merge output into multiple fixed-size SSTables rather than one giant file; this implementation merges into a single file, which limits LCS correctness (L1+ should have non-overlapping key ranges across files)

Date: 2026-05-29

Time: 13:25

I'll work with the observations provided, which give us enough to explain the key issue. Let me also check what's in the LSM tree module's compaction logic.

Topics to Explore

• [function] sstable-and-compaction/sstable.py:merge_sstables — The merge function itself: examine how the heap-based k-way merge works, how it resolves duplicate keys by timestamp, and where you'd inject a size-based file rotation
• [function] sstable-and-compaction/sstable.py:CompactionManager.run_compaction — See how files are selected for compaction at each level and how the single-file merge output gets assigned to L1 — this is where the split logic would need to live
• [general] leveldb-table-splitting — LevelDB's DoCompactionWork splits output at 2MB boundaries and also when the output file starts overlapping too many grandparent (L+2) files — understanding this policy explains why naive single-file merge causes cascading problems at deeper levels
• [file] log-structured-merge-tree/lsm.py — The LSM tree module has its own SSTable and compaction implementation; compare whether it has the same single-file limitation or handles splitting differently
• [general] size-tiered-vs-leveled-write-amplification — Understanding why LCS accepts higher write amplification (rewriting files to maintain non-overlapping ranges) in exchange for bounded read amplification clarifies why the split-on-output step is non-negotiable for correctness

Beliefs

• merge-produces-single-file — merge_sstables accepts one output path and writes all merged entries into a single SSTable file, with no size-based splitting
• lcs-l1-can-have-overlapping-ranges — The CompactionManager with strategy='leveled' does not enforce non-overlapping key ranges across L1+ files because merge output is never split
• merge-resolves-duplicates-by-timestamp — When multiple SSTables contain the same key, the multi-way merge keeps only the entry with the highest timestamp (verified by the 'shared' key test at line 97 of test_sstable.py)
• sstable-writer-single-file-lifecycle — SSTableWriter binds to one file descriptor at construction and has no mechanism to rotate to a new file mid-write, making it structurally incompatible with size-bounded output splitting
• compaction-result-assigned-level-1 — CompactionManager.runcompaction with leveled strategy assigns merged output to level 1 (asserted at line 115 of testsstable.py), but does not verify that the new file's key range is disjoint from existing L1 files