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
93mod double_ended_peekable;
94
95mod error;
96
97#[doc(hidden)]
98pub mod file;
99
100mod hash;
101
102mod iter_guard;
103
104mod key;
105mod key_range;
106
107mod run_reader;
108mod run_scanner;
109
110mod manifest;
111mod memtable;
112
113#[doc(hidden)]
114pub mod descriptor_table;
115
116#[doc(hidden)]
117pub mod merge;
118
119#[cfg(feature = "metrics")]
120pub(crate) mod metrics;
121
122// mod multi_reader;
123
124#[doc(hidden)]
125pub mod mvcc_stream;
126
127mod path;
128
129#[doc(hidden)]
130pub mod range;
131
132#[doc(hidden)]
133pub mod table;
134
135mod seqno;
136mod slice;
137mod slice_windows;
138
139#[doc(hidden)]
140pub mod stop_signal;
141
142mod format_version;
143mod time;
144mod tree;
145
146/// Utility functions
147pub mod util;
148
149mod value;
150mod value_type;
151mod version;
152mod vlog;
153
154/// User defined key (byte array)
155pub type UserKey = Slice;
156
157/// User defined data (byte array)
158pub type UserValue = Slice;
159
160/// KV-tuple (key + value)
161pub type KvPair = (UserKey, UserValue);
162
163#[doc(hidden)]
164pub use {
165    blob_tree::handle::BlobIndirection,
166    checksum::Checksum,
167    key_range::KeyRange,
168    merge::BoxedIterator,
169    slice::Builder,
170    table::{GlobalTableId, Table, TableId},
171    tree::ingest::Ingestion,
172    tree::inner::TreeId,
173    value::InternalValue,
174};
175
176pub use {
177    any_tree::AnyTree,
178    blob_tree::BlobTree,
179    cache::Cache,
180    compression::CompressionType,
181    config::{Config, KvSeparationOptions, TreeType},
182    descriptor_table::DescriptorTable,
183    error::{Error, Result},
184    format_version::FormatVersion,
185    iter_guard::IterGuard as Guard,
186    memtable::Memtable,
187    r#abstract::AbstractTree,
188    seqno::SequenceNumberCounter,
189    slice::Slice,
190    tree::Tree,
191    value::SeqNo,
192    value_type::ValueType,
193    vlog::BlobFile,
194};
195
196#[cfg(feature = "metrics")]
197pub use metrics::Metrics;
lsm_tree/lib.rs

lsm_tree/
lib.rs
