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 ingestion;
104mod iter_guard;
105mod key;
106mod key_range;
107mod manifest;
108mod memtable;
109mod run_reader;
110mod run_scanner;
111
112#[doc(hidden)]
113pub mod merge;
114
115#[cfg(feature = "metrics")]
116pub(crate) mod metrics;
117
118// mod multi_reader;
119
120#[doc(hidden)]
121pub mod mvcc_stream;
122
123mod path;
124
125#[doc(hidden)]
126pub mod range;
127
128#[doc(hidden)]
129pub mod table;
130
131mod seqno;
132mod slice;
133mod slice_windows;
134
135#[doc(hidden)]
136pub mod stop_signal;
137
138mod format_version;
139mod time;
140mod tree;
141
142/// Utility functions
143pub mod util;
144
145mod value;
146mod value_type;
147mod version;
148mod vlog;
149
150/// User defined key (byte array)
151pub type UserKey = Slice;
152
153/// User defined data (byte array)
154pub type UserValue = Slice;
155
156/// KV-tuple (key + value)
157pub type KvPair = (UserKey, UserValue);
158
159#[doc(hidden)]
160pub use {
161    blob_tree::{handle::BlobIndirection, Guard as BlobGuard},
162    checksum::Checksum,
163    iter_guard::IterGuardImpl,
164    key_range::KeyRange,
165    merge::BoxedIterator,
166    slice::Builder,
167    table::{GlobalTableId, Table, TableId},
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    ingestion::AnyIngestion,
183    iter_guard::IterGuard as Guard,
184    memtable::Memtable,
185    r#abstract::AbstractTree,
186    seqno::SequenceNumberCounter,
187    slice::Slice,
188    tree::Tree,
189    value::SeqNo,
190    value_type::ValueType,
191    vlog::BlobFile,
192};
193
194#[cfg(feature = "metrics")]
195pub use metrics::Metrics;
196
197#[doc(hidden)]
198#[must_use]
199#[allow(missing_docs, clippy::missing_errors_doc, clippy::unwrap_used)]
200pub fn get_tmp_folder() -> tempfile::TempDir {
201    if let Ok(p) = std::env::var("LSMT_TMP_FOLDER") {
202        tempfile::tempdir_in(p)
203    } else {
204        tempfile::tempdir()
205    }
206    .unwrap()
207}
lsm_tree/lib.rs

lsm_tree/
lib.rs
