Date: 2026-05-29
Time: 12:35
stcscompact — Size-Tiered Compaction Strategy (STCS)This is the core compaction routine for the size-tiered compaction strategy. It finds groups of similarly-sized SSTables that have accumulated past a threshold, merges each group into a single larger SSTable, and updates the manager's SSTable list. The goal: reduce the number of SSTables the system must search during reads, while grouping files by size so that small, recently-flushed tables merge with peers rather than being immediately folded into a massive file.
Preconditions:
self._sstables contains valid SSTableReader instances with readable files on disk.self.datadir exists and is writable (needed by nextpath() for output files).stcsneeds_compaction() first, though calling this when no compaction is needed is safe — it returns an empty list and is a no-op.Postconditions:
self._sstables and one merged SSTable takes their place.Invariant:
merge_sstables, which resolves duplicate keys by newest timestamp.None beyond self. All configuration comes from instance state:
| Field | Role |
|-------|------|
| self._sstables | The live set of SSTables managed by this instance |
| self.minthreshold | Minimum bucket size to trigger a merge (default 4) |
| self.sizethresholds | Tier boundaries used by stcsbuckets() → gettier() |
List[SSTableReader] — the newly created merged SSTables, one per compacted bucket. Empty list if no bucket met the threshold. The caller doesn't need to register these; the method already appends them to self._sstables.
1. Bucket SSTables by size tier. Calls stcsbuckets(), which groups every SSTable by its tier index (determined by comparing filesize against self.size_thresholds). Tier 0 is the smallest files, tier N is the largest.
2. Iterate each bucket. For each (tier, bucket) pair:
minthreshold SSTables, skip it — not enough peers to justify a merge.mergesstables(bucket, self.next_path()) — a k-way merge that produces a single sorted SSTable on disk. Duplicate keys resolve to the entry with the highest timestamp.SSTableReader to new_sstables.self._sstables via list.remove().3. Register new SSTables. Extend self._sstables with the merged results.
4. Return the list of newly created SSTables.
.sst file per compacted bucket under self.datadir.self._sstables: Removes compacted inputs, appends merged outputs.self.counter: Incremented by next_path() for unique filenames..sst files remain on disk even after their readers are removed from the managed list. This is a potential resource leak — the caller (or a higher-level component) is responsible for cleanup.Essentially none. Several failure modes propagate as unhandled exceptions:
list.remove(sst) raises ValueError if an SSTable appears in multiple buckets or was already removed — shouldn't happen given gettier assigns each SSTable to exactly one tier, but the code doesn't defend against it.merge_sstables can raise I/O errors if the output path is unwritable or input files are corrupted.nextpath() generates a path that collides with an existing file, SSTableWriter silently overwrites it (uses open(..., "wb")).Called exclusively through runcompaction() when the strategy is "sizetiered":
mgr = CompactionManager(data_dir, strategy="size_tiered", min_threshold=4)
# ... add SSTables over time ...
if mgr.needs_compaction():
new = mgr.run_compaction()
Typically invoked after memtable flushes — each flush produces a small L0 SSTable, and once enough accumulate in the same size tier, they get merged. The merged result is larger, so it lands in a higher tier, where it eventually merges with other similarly-sized files. This creates a natural hierarchy of increasingly large SSTables over time.
| Dependency | Role |
|------------|------|
| stcsbuckets() / gettier() | Classify SSTables into size tiers |
| merge_sstables() | K-way sorted merge with timestamp-based deduplication |
| nextpath() | Generate unique output file paths |
| SSTableReader | Returned by merge_sstables, appended to the managed list |
1. self._sstables contains no duplicates. list.remove() removes the first match — if an SSTable appears twice, only one copy is removed, leaving the list inconsistent.
2. SSTables are internally sorted. mergesstables assumes each input yields entries in key order. Nothing prevents adding an unsorted SSTable via addsstable().
3. Old files are cleaned up externally. The method orphans input files on disk.
4. Concurrent access is unsafe. The method mutates self.sstables while iterating buckets derived from it. Safe only because stcsbuckets() creates a snapshot (new dict of lists), but concurrent calls to addsstable() during compaction could corrupt state.
stcs-merges-within-size-tiers — Size-tiered compaction only merges SSTables in the same size tier; it never merges a small SSTable directly with a much larger one.stcs-min-threshold-default-four — A size tier must accumulate at least 4 SSTables (the default min_threshold) before compaction merges them.stcs-compact-preserves-tombstones — stcscompact calls mergesstables with removetombstones=False (the default), so deleted keys survive compaction as tombstone markers.stcs-compact-does-not-delete-old-files — After merging, the original SSTable files remain on disk; only the in-memory references in self._sstables are removed.stcs-compact-mutates-sstable-list — stcscompact both removes old and appends new entries to self._sstables as a side effect, so callers must not rely on the list being stable across a compaction call.