Expand description
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-resident table files when the write buffer reaches some threshold.
Amassing many tables on disk will degrade read performance and waste disk space, so tables
can be periodically merged into larger tables 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.
Re-exports§
pub use encryption::EncryptionProvider;pub use config::Config;pub use config::KvSeparationOptions;pub use config::TreeType;
Modules§
- compaction
- Contains compaction strategies
- config
- Configuration
- encryption
- Block-level encryption at rest. Block-level encryption at rest.
- fs
- Pluggable filesystem abstraction for I/O backends. Pluggable filesystem abstraction for I/O backends.
- util
- Utility functions
- verify
- Integrity verification for SST and blob files.
Structs§
- Blob
File - A blob file stores large values and is part of the value log
- Blob
Tree - A key-value-separated log-structured merge tree
- Cache
- Cache, in which blocks or blobs are cached in-memory after being retrieved from disk
- Default
User Comparator - Default comparator using lexicographic byte ordering.
- Descriptor
Table - Caches file descriptors to tables and blob files
- Memtable
- The memtable serves as an intermediary, ephemeral, sorted storage for new items
- Sequence
Number Counter - 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§
- AnyIngestion
- Unified ingestion builder over
AnyTree - AnyTree
- May be a standard
Treeor aBlobTree - Compression
Type - Compression algorithm to use
- Error
- Represents errors that can occur in the LSM-tree
- Format
Version - Disk format version
- Value
Type - Value type (regular value or tombstone)
Constants§
- MAX_
SEQNO - The maximum allowed sequence number value.
Traits§
- Abstract
Tree - Generic Tree API
- Guard
- Guard to access key-value pairs
- Merge
Operator - A user-defined merge operator for commutative LSM operations.
- Prefix
Extractor - Extracts prefixes from keys for prefix bloom filter indexing.
- Sequence
Number Generator - Trait for custom sequence number generation.
- User
Comparator - Trait for custom user key comparison.
Type Aliases§
- KvPair
- KV-tuple (key + value)
- Memtable
Id - Unique memtable ID
- Result
- Tree result
- SeqNo
- Sequence number - a monotonically increasing counter
- Shared
Comparator - Shared reference to a
UserComparator. - Shared
Sequence Number Generator - A shared, cloneable sequence number generator.
- UserKey
- User defined key (byte array)
- User
Value - User defined data (byte array)