Leveled compaction. Keeps each compaction's input bounded (one table from L(n) plus the overlapping L(n+1) tables; or, for L0, all L0 tables plus the overlapping L1 tables), so compaction work stays small and even.
Selection: L0 triggers on table COUNT (l0-compaction-trigger); L1+ trigger
on the over-ratio current_size / max_size. The candidate with the highest
score >= 1 is compacted. Within an L1+ level a table is picked round-robin
(an in-memory compact-pointer that resumes after the previous compaction).
Merge is newest-wins (shallower level wins; within L0 larger id wins). Tombstones are preserved until they reach the bottom-most level, where they are dropped (nothing below can hold an older live value).
The heavy merge work holds no lock. Only the commit -- append+fsync the
manifest edit, then atomically swap the version -- is guarded (by the manifest
lock inside sstable/commit-edit!). A compaction failure is fail-stop.
After committing, the superseded input files are physically deleted under the
write lock (sstable/delete-inputs!), which waits out any in-flight readers.
TODO (memory): the merge materializes all input entries in a TreeMap. A streaming k-way merge over the (already sorted) inputs would bound compaction memory; deferred for now.
Leveled compaction. Keeps each compaction's input bounded (one table from L(n) plus the overlapping L(n+1) tables; or, for L0, all L0 tables plus the overlapping L1 tables), so compaction work stays small and even. Selection: L0 triggers on table COUNT (`l0-compaction-trigger`); L1+ trigger on the over-ratio `current_size / max_size`. The candidate with the highest score >= 1 is compacted. Within an L1+ level a table is picked round-robin (an in-memory compact-pointer that resumes after the previous compaction). Merge is newest-wins (shallower level wins; within L0 larger id wins). Tombstones are preserved until they reach the bottom-most level, where they are dropped (nothing below can hold an older live value). The heavy merge work holds no lock. Only the commit -- append+fsync the manifest edit, then atomically swap the version -- is guarded (by the manifest lock inside `sstable/commit-edit!`). A compaction failure is fail-stop. After committing, the superseded input files are physically deleted under the write lock (`sstable/delete-inputs!`), which waits out any in-flight readers. TODO (memory): the merge materializes all input entries in a TreeMap. A streaming k-way merge over the (already sorted) inputs would bound compaction memory; deferred for now.
(compact! tree sstable-id compact-pointers registry config)Run one compaction if the store needs it. Returns true if a compaction was performed, nil if nothing needed compacting. Throws on IO failure (the worker poisons the store).
Run one compaction if the store needs it. Returns true if a compaction was performed, nil if nothing needed compacting. Throws on IO failure (the worker poisons the store).
(merge-inputs paths-low-to-high floor drop-tombstones?)Merge input file paths given LOW->HIGH precedence into a user_key-sorted seq of
[ikey data], applying MVCC GC per user_key against floor
(= min-active-snapshot-seq): keep every version with seq > floor plus the newest
version with seq <= floor, drop older ones (see gc-versions). At the bottom-most
level a surviving tombstone is dropped too (drop-tombstones?).
With no live tx floor is the current seq, so every version is <= floor and each
user_key collapses to its single newest version -- the pre-MVCC behavior.
Merge input file paths given LOW->HIGH precedence into a user_key-sorted seq of [ikey data], applying MVCC GC per user_key against `floor` (= min-active-snapshot-seq): keep every version with seq > floor plus the newest version with seq <= floor, drop older ones (see `gc-versions`). At the bottom-most level a surviving tombstone is dropped too (`drop-tombstones?`). With no live tx `floor` is the current seq, so every version is <= floor and each user_key collapses to its single newest version -- the pre-MVCC behavior.
(pick-compaction version compact-pointers config)Decide the next compaction, or nil if none is needed. L0 scores on table count; L1+ score on current/max bytes; the highest score >= 1 wins.
Decide the next compaction, or nil if none is needed. L0 scores on table count; L1+ score on current/max bytes; the highest score >= 1 wins.
(pick-round-robin tables pointer)Pick one table from an L1+ level, resuming after pointer (the tail-key of
the last compaction of this level); wrap to the first table at the end. Tables
are ordered by head-key (L1+ ranges do not overlap, so this is a total order).
Pick one table from an L1+ level, resuming after `pointer` (the tail-key of the last compaction of this level); wrap to the first table at the end. Tables are ordered by head-key (L1+ ranges do not overlap, so this is a total order).
(spawn-compaction-worker tree
sstable-id
compact-pointers
registry
poison
stall-monitor
req-chan
config)Background compaction worker (a real thread, like the flush writer). On each
:maybe-compact signal it compacts until nothing more is needed (a single
compaction can push the next level over its limit). Fail-stop on error.
After every compaction it notifies stall-monitor: a compaction drains L0, so
any writers stalled by back-pressure should re-check and may proceed.
Background compaction worker (a real thread, like the flush writer). On each `:maybe-compact` signal it compacts until nothing more is needed (a single compaction can push the next level over its limit). Fail-stop on error. After every compaction it notifies `stall-monitor`: a compaction drains L0, so any writers stalled by back-pressure should re-check and may proceed.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |