Struct Leveled 

pub struct Leveled { /* private fields */ }

Leveled compaction strategy (LCS)

When a level reaches some threshold size, parts of it are merged into overlapping tables in the next level.

Each level Ln for n >= 2 can have up to level_base_size * ratio^(n - 1) tables.

LCS suffers from comparatively high write amplification, but has decent read amplification and great space amplification (~1.1x).

LCS is the recommended compaction strategy to use.

More info here: https://fjall-rs.github.io/post/lsm-leveling/

Implementations

impl Strategy

pub fn with_level_ratio_policy(self, policy: Vec<f32>) -> Self

Sets the growth ratio between levels.

Same as set_max_bytes_for_level_multiplier in RocksDB.

Default = [10.0]

pub fn with_l0_threshold(self, threshold: u8) -> Self

Sets the L0 threshold.

When the number of runs in L0 reaches this threshold, L0 is merged into L1. A run’s tables have disjoint key ranges, so a read pays at most one table per run: the run count bounds L0’s read amplification, where the table count does not. A flush larger than Config::table_target_size writes one run of several tables and counts once.

Plays the role of level0_file_num_compaction_trigger in RocksDB, whose flushes write one table each, so files and runs coincide there.

Default = 4; 0 is taken as 1, since no run count is below zero.

pub fn with_l0_file_threshold(self, threshold: u16) -> Self

Sets the L0 table count that triggers a merge into L1 whatever the run count.

A guard against fan-out: every L0 table costs a file handle, a manifest entry and per-table metadata in memory, however few runs hold them.

Keep it above the run threshold times the tables one flush writes (memtable size over Config::table_target_size): below that it fires before the run trigger, on every few flushes, and L0 merges into L1 as often as a file-count trigger would make it. The default, with the default run threshold of 4, leaves room for a memtable of 125 tables of the target (about 8 GiB at 64 MiB).

Default = 500; 0 is taken as 1, since no table count is below zero.

Examples

use lsm_tree::compaction::Leveled;

let strategy = Leveled::default().with_l0_file_threshold(200);

impl Strategy

pub fn with_table_target_size(self, bytes: u64) -> Self

Sets the table target size on disk (possibly compressed).

Same as target_file_size_base in RocksDB.

Default = 64 MiB

pub fn with_dynamic_level_bytes(self, enabled: bool) -> Self

Enables dynamic level sizing based on actual data in the last level.

When enabled, level target sizes are computed top-down from the actual size of the last non-empty level, divided by the ratio at each step. This reduces space amplification to ~1.1x while keeping write amplification comparable to static leveling.

Same as level_compaction_dynamic_level_bytes in RocksDB.

Default = false

pub fn with_multi_level(self, enabled: bool) -> Self

Enables multi-level compaction optimization.

When L0→L1 compaction is selected but L1 already exceeds its target size, this option allows compacting L0+L1 directly into L2 in one pass, avoiding the write-then-rewrite cycle that would otherwise occur.

Default = false

pub fn with_promotion_slack(self, bytes: u64) -> Self

Sets how many bytes past a level’s overshoot a merge may promote and still be preferred.

A leveled merge is chosen by the bytes it rewrites per byte it moves down a level, among the candidates that promote no more than the level’s overshoot plus this slack; when none is that small, the cheapest candidate overall is taken, so the level still makes progress.

Default = the table target size.

Examples

use lsm_tree::compaction::Leveled;

let strategy = Leveled::default().with_promotion_slack(128 * 1_024 * 1_024);

pub fn with_level_policy(self, level: u8, policy: LevelPolicy) -> Self

Sets the four choices for level level in place of the leveled ones: when it compacts, how it holds its data, how much one compaction out of it takes and which data that is. A level index past the tree’s last level is ignored.

The leveled defaults are: L0 triggered by its shape (see Self::with_l0_threshold and Self::with_l0_file_threshold), tiered and compacted whole (through L1 when Self::with_multi_level is on); every other level leveled, triggered by its size, and compacted a window at a time chosen by the least rewrite per promoted byte (see Self::with_promotion_slack); the last level never triggered.

Examples

use lsm_tree::compaction::{Granularity, Layout, LevelPolicy, Leveled, Movement, Trigger};

// L1 accumulates runs and goes down whole once it holds four.
let strategy = Leveled::default().with_level_policy(
    1,
    LevelPolicy {
        trigger: Trigger::Shape { runs: 4, tables: u16::MAX },
        layout: Layout::Tiered,
        granularity: Granularity::Level { through_full_next: false },
        movement: Movement::LeastRewrite { slack: None },
    },
);

Trait Implementations

impl Clone for Strategy

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl CompactionStrategy for Strategy

fn get_name(&self) -> &'static str

Gets the compaction strategy name.

fn pending_compaction_bytes(&self, version: &Version) -> u64

Estimated bytes pending compaction: on-disk data currently sitting above its level’s target size that must eventually be rewritten downward (a RocksDB estimate-pending-compaction-bytes analog). A scheduler / tiering consumer reads it as a compaction-debt signal; 0 means the tree is at or below its target shape.

fn choose( &self, version: &Version, config: &Config, state: &CompactionState, ) -> Choice

Decides on what to do based on the current state of the LSM-tree’s levels

fn next_merge_level(&self, version: &Version, dest_level: u8) -> Option<usize>

The level a merge into dest_level writes outputs that are next merged into, whose table boundaries they are cut on (see Config::compaction_output_alignment); None cuts them at the target size alone.

impl Default for Strategy

fn default() -> Self

Returns the “default value” for a type.