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#![cfg_attr(coverage_nightly, feature(coverage_attribute))]
47
48#[doc(hidden)]
49pub type HashMap<K, V> = std::collections::HashMap<K, V, rustc_hash::FxBuildHasher>;
50
51pub(crate) type HashSet<K> = std::collections::HashSet<K, rustc_hash::FxBuildHasher>;
52
53macro_rules! fail_iter {
54    ($e:expr) => {
55        match $e {
56            Ok(v) => v,
57            Err(e) => return Some(Err(e.into())),
58        }
59    };
60}
61
62macro_rules! unwrap {
63    ($x:expr) => {{
64        $x.expect("should read")
65    }};
66}
67
68pub(crate) use unwrap;
69
70mod any_tree;
71
72mod r#abstract;
73
74#[doc(hidden)]
75pub mod blob_tree;
76
77#[doc(hidden)]
78mod cache;
79
80#[doc(hidden)]
81pub mod checksum;
82
83#[doc(hidden)]
84pub mod coding;
85
86pub mod compaction;
87mod compression;
88
89/// Configuration
90pub mod config;
91
92#[doc(hidden)]
93pub mod descriptor_table;
94
95mod double_ended_peekable;
96mod error;
97
98#[doc(hidden)]
99pub mod file;
100
101mod hash;
102mod ingestion;
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::inner::TreeId,
168    tree::Guard as StandardGuard,
169    value::InternalValue,
170};
171
172pub use {
173    any_tree::AnyTree,
174    blob_tree::BlobTree,
175    cache::Cache,
176    compression::CompressionType,
177    config::{Config, KvSeparationOptions, TreeType},
178    descriptor_table::DescriptorTable,
179    error::{Error, Result},
180    format_version::FormatVersion,
181    ingestion::AnyIngestion,
182    iter_guard::IterGuard as Guard,
183    memtable::{Memtable, MemtableId},
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;
195
196#[doc(hidden)]
197#[must_use]
198#[allow(missing_docs, clippy::missing_errors_doc, clippy::unwrap_used)]
199pub fn get_tmp_folder() -> tempfile::TempDir {
200    if let Ok(p) = std::env::var("LSMT_TMP_FOLDER") {
201        tempfile::tempdir_in(p)
202    } else {
203        tempfile::tempdir()
204    }
205    .unwrap()
206}
lsm_tree/lib.rs

lsm_tree/
lib.rs
