lsm_tree/
lib.rs

1// Copyright (c) 2024-present, fjall-rs
2// This source code is licensed under both the Apache 2.0 and MIT License
3// (found in the LICENSE-* files in the repository)
4
5//! A K.I.S.S. implementation of log-structured merge trees (LSM-trees/LSMTs).
6//!
7//! ##### NOTE
8//!
9//! > This crate only provides a primitive LSM-tree, not a full storage engine.
10//! > You probably want to use <https://crates.io/crates/fjall> instead.
11//! > For example, it does not ship with a write-ahead log, so writes are not
12//! > persisted until manually flushing the memtable.
13//!
14//! ##### About
15//!
16//! This crate exports a `Tree` that supports a subset of the `BTreeMap` API.
17//!
18//! LSM-trees are an alternative to B-trees to persist a sorted list of items (e.g. a database table)
19//! on disk and perform fast lookup queries.
20//! Instead of updating a disk-based data structure in-place,
21//! deltas (inserts and deletes) are added into an in-memory write buffer (`Memtable`).
22//! Data is then flushed to disk-resident table files when the write buffer reaches some threshold.
23//!
24//! Amassing many tables on disk will degrade read performance and waste disk space, so tables
25//! can be periodically merged into larger tables in a process called `Compaction`.
26//! Different compaction strategies have different advantages and drawbacks, and should be chosen based
27//! on the workload characteristics.
28//!
29//! Because maintaining an efficient structure is deferred to the compaction process, writing to an LSMT
30//! is very fast (_O(1)_ complexity).
31//!
32//! Keys are limited to 65536 bytes, values are limited to 2^32 bytes. As is normal with any kind of storage
33//! engine, larger keys and values have a bigger performance impact.
34
35#![doc(html_logo_url = "https://raw.githubusercontent.com/fjall-rs/lsm-tree/main/logo.png")]
36#![doc(html_favicon_url = "https://raw.githubusercontent.com/fjall-rs/lsm-tree/main/logo.png")]
37#![deny(clippy::all, missing_docs, clippy::cargo)]
38#![deny(clippy::unwrap_used)]
39#![deny(clippy::indexing_slicing)]
40#![warn(clippy::pedantic, clippy::nursery)]
41#![warn(clippy::expect_used)]
42#![allow(clippy::missing_const_for_fn)]
43#![warn(clippy::multiple_crate_versions)]
44#![allow(clippy::option_if_let_else)]
45#![warn(clippy::redundant_feature_names)]
46// the bytes feature uses unsafe to improve from_reader performance; so we need to relax this lint
47// #![cfg_attr(feature = "bytes", deny(unsafe_code))]
48// #![cfg_attr(not(feature = "bytes"), forbid(unsafe_code))]
49
50#[doc(hidden)]
51pub type HashMap<K, V> = std::collections::HashMap<K, V, rustc_hash::FxBuildHasher>;
52
53pub(crate) type HashSet<K> = std::collections::HashSet<K, rustc_hash::FxBuildHasher>;
54
55macro_rules! fail_iter {
56    ($e:expr) => {
57        match $e {
58            Ok(v) => v,
59            Err(e) => return Some(Err(e.into())),
60        }
61    };
62}
63
64macro_rules! unwrap {
65    ($x:expr) => {{
66        $x.expect("should read")
67    }};
68}
69
70pub(crate) use unwrap;
71
72mod any_tree;
73
74mod r#abstract;
75
76#[doc(hidden)]
77pub mod blob_tree;
78
79#[doc(hidden)]
80mod cache;
81
82mod checksum;
83
84#[doc(hidden)]
85pub mod coding;
86
87pub mod compaction;
88mod compression;
89
90/// Configuration
91pub mod config;
92
93#[doc(hidden)]
94pub mod descriptor_table;
95
96mod double_ended_peekable;
97mod error;
98
99#[doc(hidden)]
100pub mod file;
101
102mod hash;
103mod iter_guard;
104mod key;
105mod key_range;
106mod manifest;
107mod memtable;
108mod run_reader;
109mod run_scanner;
110
111#[doc(hidden)]
112pub mod merge;
113
114#[cfg(feature = "metrics")]
115pub(crate) mod metrics;
116
117// mod multi_reader;
118
119#[doc(hidden)]
120pub mod mvcc_stream;
121
122mod path;
123
124#[doc(hidden)]
125pub mod range;
126
127#[doc(hidden)]
128pub mod table;
129
130mod seqno;
131mod slice;
132mod slice_windows;
133
134#[doc(hidden)]
135pub mod stop_signal;
136
137mod format_version;
138mod time;
139mod tree;
140
141/// Utility functions
142pub mod util;
143
144mod value;
145mod value_type;
146mod version;
147mod vlog;
148
149/// User defined key (byte array)
150pub type UserKey = Slice;
151
152/// User defined data (byte array)
153pub type UserValue = Slice;
154
155/// KV-tuple (key + value)
156pub type KvPair = (UserKey, UserValue);
157
158#[doc(hidden)]
159pub use {
160    blob_tree::{handle::BlobIndirection, Guard as BlobGuard},
161    checksum::Checksum,
162    iter_guard::IterGuardImpl,
163    key_range::KeyRange,
164    merge::BoxedIterator,
165    slice::Builder,
166    table::{GlobalTableId, Table, TableId},
167    tree::ingest::Ingestion,
168    tree::inner::TreeId,
169    tree::Guard as StandardGuard,
170    value::InternalValue,
171};
172
173pub use {
174    any_tree::AnyTree,
175    blob_tree::BlobTree,
176    cache::Cache,
177    compression::CompressionType,
178    config::{Config, KvSeparationOptions, TreeType},
179    descriptor_table::DescriptorTable,
180    error::{Error, Result},
181    format_version::FormatVersion,
182    iter_guard::IterGuard as Guard,
183    memtable::Memtable,
184    r#abstract::AbstractTree,
185    seqno::SequenceNumberCounter,
186    slice::Slice,
187    tree::Tree,
188    value::SeqNo,
189    value_type::ValueType,
190    vlog::BlobFile,
191};
192
193#[cfg(feature = "metrics")]
194pub use metrics::Metrics;
lsm_tree/lib.rs

lsm_tree/
lib.rs
