Trait AbstractTree

pub trait AbstractTree {
    // Required methods
    fn major_compact(
        &self,
        target_size: u64,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn bloom_filter_size(&self) -> usize;
    fn flush_memtable(
        &self,
        segment_id: SegmentId,
        memtable: &Arc<Memtable>,
        seqno_threshold: SeqNo,
    ) -> Result<Option<Segment>>;
    fn register_segments(&self, segments: &[Segment]) -> Result<()>;
    fn lock_active_memtable(&self) -> RwLockWriteGuard<'_, Arc<Memtable>>;
    fn clear_active_memtable(&self);
    fn set_active_memtable(&self, memtable: Memtable);
    fn sealed_memtable_count(&self) -> usize;
    fn add_sealed_memtable(&self, id: u64, memtable: Arc<Memtable>);
    fn compact(
        &self,
        strategy: Arc<dyn CompactionStrategy>,
        seqno_threshold: SeqNo,
    ) -> Result<()>;
    fn get_next_segment_id(&self) -> SegmentId;
    fn tree_config(&self) -> &Config;
    fn active_memtable_size(&self) -> u32;
    fn tree_type(&self) -> TreeType;
    fn rotate_memtable(&self) -> Option<(u64, Arc<Memtable>)>;
    fn segment_count(&self) -> usize;
    fn level_segment_count(&self, idx: usize) -> Option<usize>;
    fn l0_run_count(&self) -> usize;
    fn approximate_len(&self) -> usize;
    fn disk_space(&self) -> u64;
    fn get_highest_memtable_seqno(&self) -> Option<SeqNo>;
    fn get_highest_persisted_seqno(&self) -> Option<SeqNo>;
    fn keys(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = Result<UserKey>> + 'static>;
    fn values(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = Result<UserValue>> + 'static>;
    fn range<K: AsRef<[u8]>, R: RangeBounds<K>>(
        &self,
        range: R,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static>;
    fn prefix<K: AsRef<[u8]>>(
        &self,
        prefix: K,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static>;
    fn size_of<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: Option<SeqNo>,
    ) -> Result<Option<u32>>;
    fn get<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: Option<SeqNo>,
    ) -> Result<Option<UserValue>>;
    fn snapshot(&self, seqno: SeqNo) -> Snapshot;
    fn insert<K: Into<UserKey>, V: Into<UserValue>>(
        &self,
        key: K,
        value: V,
        seqno: SeqNo,
    ) -> (u32, u32);
    fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u32, u32);
    fn remove_weak<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u32, u32);

    // Provided methods
    fn get_highest_seqno(&self) -> Option<SeqNo> { ... }
    fn blob_file_count(&self) -> usize { ... }
    fn len(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Result<usize> { ... }
    fn is_empty(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Result<bool> { ... }
    fn first_key_value(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Result<Option<KvPair>> { ... }
    fn last_key_value(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Result<Option<KvPair>> { ... }
    fn iter(
        &self,
        seqno: Option<SeqNo>,
        index: Option<Arc<Memtable>>,
    ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static> { ... }
    fn snapshot_at(&self, seqno: SeqNo) -> Snapshot { ... }
    fn contains_key<K: AsRef<[u8]>>(
        &self,
        key: K,
        seqno: Option<SeqNo>,
    ) -> Result<bool> { ... }
}

Generic Tree API

Required Methods

fn major_compact(&self, target_size: u64, seqno_threshold: SeqNo) -> Result<()>

Performs major compaction, blocking the caller until it’s done.

Errors

Will return Err if an IO error occurs.

fn bloom_filter_size(&self) -> usize

Gets the memory usage of all bloom filters in the tree.

fn flush_memtable( &self, segment_id: SegmentId, memtable: &Arc<Memtable>, seqno_threshold: SeqNo, ) -> Result<Option<Segment>>

Synchronously flushes a memtable to a disk segment.

This method will not make the segment immediately available, use AbstractTree::register_segments for that.

Errors

Will return Err if an IO error occurs.

fn register_segments(&self, segments: &[Segment]) -> Result<()>

Atomically registers flushed disk segments into the tree, removing their associated sealed memtables.

Errors

Will return Err if an IO error occurs.

fn lock_active_memtable(&self) -> RwLockWriteGuard<'_, Arc<Memtable>>

Write-locks the active memtable for exclusive access

fn clear_active_memtable(&self)

Clears the active memtable atomically.

fn set_active_memtable(&self, memtable: Memtable)

Sets the active memtable.

May be used to restore the LSM-tree’s in-memory state from a write-ahead log after tree recovery.

fn sealed_memtable_count(&self) -> usize

Returns the amount of sealed memtables.

fn add_sealed_memtable(&self, id: u64, memtable: Arc<Memtable>)

Adds a sealed memtables.

May be used to restore the LSM-tree’s in-memory state from some journals.

fn compact( &self, strategy: Arc<dyn CompactionStrategy>, seqno_threshold: SeqNo, ) -> Result<()>

Performs compaction on the tree’s levels, blocking the caller until it’s done.

Errors

Will return Err if an IO error occurs.

fn get_next_segment_id(&self) -> SegmentId

Returns the next segment’s ID.

fn tree_config(&self) -> &Config

Returns the tree config.

fn active_memtable_size(&self) -> u32

Returns the approximate size of the active memtable in bytes.

May be used to flush the memtable if it grows too large.

fn tree_type(&self) -> TreeType

Returns the tree type.

fn rotate_memtable(&self) -> Option<(u64, Arc<Memtable>)>

Seals the active memtable, and returns a reference to it.

fn segment_count(&self) -> usize

Returns the amount of disk segments currently in the tree.

fn level_segment_count(&self, idx: usize) -> Option<usize>

Returns the amount of segments in levels[idx].

Returns None if the level does not exist (if idx >= 7).

fn l0_run_count(&self) -> usize

Returns the amount of disjoint runs in L0.

Can be used to determine whether to write stall.

fn approximate_len(&self) -> usize

Approximates the amount of items in the tree.

fn disk_space(&self) -> u64

Returns the disk space usage.

fn get_highest_memtable_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number of the active memtable.

fn get_highest_persisted_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number that is flushed to disk.

fn keys( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Box<dyn DoubleEndedIterator<Item = Result<UserKey>> + 'static>

Returns an iterator that scans through the entire tree, returning keys only.

Avoid using this function, or limit it as otherwise it may scan a lot of items.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(3, tree.keys(None, None).count());

fn values( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Box<dyn DoubleEndedIterator<Item = Result<UserValue>> + 'static>

Returns an iterator that scans through the entire tree, returning values only.

Avoid using this function, or limit it as otherwise it may scan a lot of items.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(3, tree.values(None, None).count());

fn range<K: AsRef<[u8]>, R: RangeBounds<K>>( &self, range: R, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static>

Returns an iterator over a range of items.

Avoid using full or unbounded ranges as they may scan a lot of items (unless limited).

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(2, tree.range("a"..="f", None, None).into_iter().count());

fn prefix<K: AsRef<[u8]>>( &self, prefix: K, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static>

Returns an iterator over a prefixed set of items.

Avoid using an empty prefix as it may scan a lot of items (unless limited).

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);
tree.insert("ab", "abc", 1);
tree.insert("abc", "abc", 2);
assert_eq!(2, tree.prefix("ab", None, None).count());

fn size_of<K: AsRef<[u8]>>( &self, key: K, seqno: Option<SeqNo>, ) -> Result<Option<u32>>

Returns the size of a value if it exists.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;
tree.insert("a", "my_value", 0);

let size = tree.size_of("a", None)?.unwrap_or_default();
assert_eq!("my_value".len() as u32, size);

let size = tree.size_of("b", None)?.unwrap_or_default();
assert_eq!(0, size);

Errors

Will return Err if an IO error occurs.

fn get<K: AsRef<[u8]>>( &self, key: K, seqno: Option<SeqNo>, ) -> Result<Option<UserValue>>

Retrieves an item from the tree.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;
tree.insert("a", "my_value", 0);

let item = tree.get("a", None)?;
assert_eq!(Some("my_value".as_bytes().into()), item);

Errors

Will return Err if an IO error occurs.

fn snapshot(&self, seqno: SeqNo) -> Snapshot

Opens a read-only point-in-time snapshot of the tree

Dropping the snapshot will close the snapshot

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);

let snapshot = tree.snapshot(1);
assert_eq!(snapshot.len()?, tree.len(None, None)?);

tree.insert("b", "abc", 1);

assert_eq!(2, tree.len(None, None)?);
assert_eq!(1, snapshot.len()?);

assert!(snapshot.contains_key("a")?);
assert!(!snapshot.contains_key("b")?);

fn insert<K: Into<UserKey>, V: Into<UserValue>>( &self, key: K, value: V, seqno: SeqNo, ) -> (u32, u32)

Inserts a key-value pair into the tree.

If the key already exists, the item will be overwritten.

Returns the added item’s size and new size of the memtable.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;
tree.insert("a", "abc", 0);

Errors

Will return Err if an IO error occurs.

fn remove<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u32, u32)

Removes an item from the tree.

Returns the added item’s size and new size of the memtable.

Examples

tree.insert("a", "abc", 0);

let item = tree.get("a", None)?.expect("should have item");
assert_eq!("abc".as_bytes(), &*item);

tree.remove("a", 1);

let item = tree.get("a", None)?;
assert_eq!(None, item);

Errors

Will return Err if an IO error occurs.

fn remove_weak<K: Into<UserKey>>(&self, key: K, seqno: SeqNo) -> (u32, u32)

Removes an item from the tree.

The tombstone marker of this delete operation will vanish when it collides with its corresponding insertion. This may cause older versions of the value to be resurrected, so it should only be used and preferred in scenarios where a key is only ever written once.

Returns the added item’s size and new size of the memtable.

Examples

tree.insert("a", "abc", 0);

let item = tree.get("a", None)?.expect("should have item");
assert_eq!("abc".as_bytes(), &*item);

tree.remove_weak("a", 1);

let item = tree.get("a", None)?;
assert_eq!(None, item);

Errors

Will return Err if an IO error occurs.

Provided Methods

fn get_highest_seqno(&self) -> Option<SeqNo>

Returns the highest sequence number.

fn blob_file_count(&self) -> usize

Returns the amount of blob files currently in the tree.

fn len( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Result<usize>

Scans the entire tree, returning the amount of items.

Caution

This operation scans the entire tree: O(n) complexity!

Never, under any circumstances, use .len() == 0 to check if the tree is empty, use Tree::is_empty instead.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let folder = tempfile::tempdir()?;
let tree = Config::new(folder).open()?;

assert_eq!(tree.len(None, None)?, 0);
tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);
assert_eq!(tree.len(None, None)?, 3);

Errors

Will return Err if an IO error occurs.

fn is_empty( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Result<bool>

Returns true if the tree is empty.

This operation has O(1) complexity.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;
assert!(tree.is_empty(None, None)?);

tree.insert("a", "abc", 0);
assert!(!tree.is_empty(None, None)?);

Errors

Will return Err if an IO error occurs.

fn first_key_value( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Result<Option<KvPair>>

Returns the first key-value pair in the tree. The key in this pair is the minimum key in the tree.

Examples

let tree = Config::new(folder).open()?;

tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);

let (key, _) = tree.first_key_value(None, None)?.expect("item should exist");
assert_eq!(&*key, "1".as_bytes());

Errors

Will return Err if an IO error occurs.

fn last_key_value( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Result<Option<KvPair>>

Returns the last key-value pair in the tree. The key in this pair is the maximum key in the tree.

Examples

tree.insert("1", "abc", 0);
tree.insert("3", "abc", 1);
tree.insert("5", "abc", 2);

let (key, _) = tree.last_key_value(None, None)?.expect("item should exist");
assert_eq!(&*key, "5".as_bytes());

Errors

Will return Err if an IO error occurs.

fn iter( &self, seqno: Option<SeqNo>, index: Option<Arc<Memtable>>, ) -> Box<dyn DoubleEndedIterator<Item = Result<KvPair>> + 'static>

Returns an iterator that scans through the entire tree.

Avoid using this function, or limit it as otherwise it may scan a lot of items.

Examples

use lsm_tree::{AbstractTree, Config, Tree};

let tree = Config::new(folder).open()?;

tree.insert("a", "abc", 0);
tree.insert("f", "abc", 1);
tree.insert("g", "abc", 2);
assert_eq!(3, tree.iter(None, None).count());

fn snapshot_at(&self, seqno: SeqNo) -> Snapshot

Opens a snapshot of this partition with a given sequence number

fn contains_key<K: AsRef<[u8]>>( &self, key: K, seqno: Option<SeqNo>, ) -> Result<bool>

Returns true if the tree contains the specified key.

Examples

let tree = Config::new(folder).open()?;
assert!(!tree.contains_key("a", None)?);

tree.insert("a", "abc", 0);
assert!(tree.contains_key("a", None)?);

Errors

Will return Err if an IO error occurs.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl AbstractTree for AnyTree

impl AbstractTree for BlobTree

impl AbstractTree for Tree