Crate lsm_tree 

A K.I.S.S. implementation of log-structured merge trees (LSM-trees/LSMTs).

NOTE

This crate only provides a primitive LSM-tree, not a full storage engine. You probably want to use https://crates.io/crates/fjall instead. For example, it does not ship with a write-ahead log, so writes are not persisted until manually flushing the memtable.

About

This crate exports a Tree that supports a subset of the BTreeMap API.

LSM-trees are an alternative to B-trees to persist a sorted list of items (e.g. a database table) on disk and perform fast lookup queries. Instead of updating a disk-based data structure in-place, deltas (inserts and deletes) are added into an in-memory write buffer (Memtable). Data is then flushed to disk segments when the write buffer reaches some threshold.

Amassing many segments on disk will degrade read performance and waste disk space, so segments can be periodically merged into larger segments in a process called Compaction. Different compaction strategies have different advantages and drawbacks, and should be chosen based on the workload characteristics.

Because maintaining an efficient structure is deferred to the compaction process, writing to an LSMT is very fast (O(1) complexity).

Keys are limited to 65536 bytes, values are limited to 2^32 bytes. As is normal with any kind of storage engine, larger keys and values have a bigger performance impact.

Example usage

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

// A tree is a single physical keyspace/index/...
// and supports a BTreeMap-like API
let tree = Config::new(folder).open()?;

// Note compared to the BTreeMap API, operations return a Result<T>
// So you can handle I/O errors if they occur
tree.insert("my_key", "my_value", /* sequence number */ 0);

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

// Search by prefix
for item in tree.prefix("prefix", 1, None) {
  // ...
}

// Search by range
for item in tree.range("a"..="z", 1, None) {
  // ...
}

// Iterators implement DoubleEndedIterator, so you can search backwards, too!
for item in tree.prefix("user1", 1, None).rev() {
  // ...
}

// Flush to secondary storage, clearing the memtable
// and persisting all in-memory data.
// Note, this flushes synchronously, which may not be desired
tree.flush_active_memtable(0)?;

// When some disk segments have amassed, use compaction
// to reduce the number of disk segments

// Choose compaction strategy based on workload
use lsm_tree::compaction::Leveled;

let strategy = Leveled::default();

let version_gc_threshold = 0;
tree.compact(Arc::new(strategy), version_gc_threshold)?;

Re-exports

pub use config::Config;

pub use config::TreeType;

Modules

compaction

Contains compaction strategies

config

Configuration

gc

Blob garbage collection utilities

Structs

BlobFile

A blob file stores large values and is part of the value log

BlobTree

A key-value-separated log-structured merge tree

Cache

Cache, in which blocks or blobs are cached in-memory after being retrieved from disk

DescriptorTable

Caches file descriptors to disk segments and blob files

Memtable

The memtable serves as an intermediary, ephemeral, sorted storage for new items

SequenceNumberCounter

Thread-safe sequence number generator

Slice

An immutable byte slice that can be cloned without additional heap allocation

Tree

A log-structured merge tree (LSM-tree/LSMT)

Enums

AnyTree

May be a standard Tree or a BlobTree

CompressionType

Compression algorithm to use

DecodeError

Error during deserialization

EncodeError

Error during serialization

Error

Represents errors that can occur in the LSM-tree

FormatVersion

Disk format version

ValueType

Value type (regular value or tombstone)

Traits

AbstractTree

Generic Tree API

Guard

Guard to access key-value pairs

Type Aliases

KvPair

KV-tuple, typically returned by an iterator

Result

Tree result

SeqNo

Sequence number - a monotonically increasing counter

UserKey

User defined key

UserValue

User defined data (byte array)