Skip to main content

kevy_seg/
lib.rs

1//! Immutable ordered-record segment files — build once, binary-search
2//! forever. The storage stone every cold tier shares: row segments,
3//! scalar-index cold segments and text bucket segments differ only in
4//! what their records MEAN; how records are laid out, located,
5//! checksummed and retired is identical, so it lives here once.
6//!
7//! ```
8//! use kevy_seg::{Manifest, ManifestEntry, Seg, SegBuilder};
9//!
10//! # let dir = std::env::temp_dir().join(format!("kevy-seg-crate-doc-{}", std::process::id()));
11//! # std::fs::create_dir_all(&dir)?;
12//! // keys go in strictly ascending; the footer seals the file
13//! let mut b = SegBuilder::create(&dir.join("s1.seg"))?;
14//! b.push(b"a", b"1")?;
15//! b.push(b"b", b"2")?;
16//! let meta = b.finish()?;
17//!
18//! // the manifest makes the sealed segment part of the live set
19//! Manifest::open(&dir)?.add(ManifestEntry::new("s1.seg", meta))?;
20//!
21//! let seg = Seg::open(&dir.join("s1.seg"))?;
22//! assert_eq!(seg.get(b"b")?, Some(b"2".to_vec()));
23//! assert_eq!(seg.count_range(b"a", b"z")?, 2);
24//! # std::fs::remove_dir_all(&dir).ok();
25//! # Ok::<(), kevy_seg::SegError>(())
26//! ```
27//!
28//! # Model
29//!
30//! [`SegBuilder`] appends records in strictly ascending key order,
31//! pages them, checksums every page, and seals the file with a footer
32//! (record count, min/max key, and a fence table — the first key of
33//! every page). [`Seg`] opens the sealed file, keeps the fence table
34//! in memory, and answers `get` / `range` / `count_range` with one
35//! fence binary search plus one page read. Nothing ever mutates a
36//! sealed segment; deletion is the caller's directory concern
37//! (tombstones live above this crate), and removal is `unlink`.
38//!
39//! # Layout (v1)
40//!
41//! Data pages are 4 KiB: a small header, cells packed forward, a slot
42//! directory (u16 cell offsets) packed backward from the tail, and a
43//! CRC32C over the page in the last 4 bytes. A record too large for
44//! one page spills its payload into a run of dedicated overflow pages
45//! (the cell keeps the key and points at the run — SQLite's overflow
46//! idea, shorn of its freelist because nothing here is ever freed).
47//! The footer is written last: fence entries, min/max keys, counts,
48//! magic, and its own CRC; the final 16 bytes locate and size it.
49//!
50//! # References
51//!
52//! The read-only half of SQLite's page format (slot directory growing
53//! backward, overflow chains) is the reference for the data pages.
54//! Its WAL, freelist, cursors and varint cell headers are deliberately
55//! absent: an immutable segment needs none of them.
56
57#![warn(missing_docs)]
58
59mod builder;
60mod layout;
61mod manifest;
62mod manifest_entry;
63mod reader;
64
65pub use builder::SegBuilder;
66pub use manifest::Manifest;
67pub use manifest_entry::ManifestEntry;
68pub use reader::{RangeIter, Seg};
69
70// Send and Sync are part of the public contract: a change that loses
71// either fails to compile here rather than in a caller.
72const _: () = {
73    const fn send_sync<T: Send + Sync>() {}
74    send_sync::<Seg>();
75    send_sync::<SegBuilder>();
76    send_sync::<SegMeta>();
77    send_sync::<Manifest>();
78    send_sync::<ManifestEntry>();
79    send_sync::<SegError>();
80};
81
82/// Sealed-segment summary, from the footer.
83///
84/// ```
85/// # let dir = std::env::temp_dir().join(format!("kevy-segmeta-doc-{}", std::process::id()));
86/// # std::fs::create_dir_all(&dir)?;
87/// let mut b = kevy_seg::SegBuilder::create(&dir.join("a.seg"))?;
88/// b.push(b"k1", b"v")?;
89/// b.push(b"k2", b"v")?;
90/// let meta = b.finish()?;
91/// assert_eq!((meta.records, meta.min_key.as_slice(), meta.max_key.as_slice()), (2, &b"k1"[..], &b"k2"[..]));
92/// # std::fs::remove_dir_all(&dir).ok();
93/// # Ok::<(), kevy_seg::SegError>(())
94/// ```
95#[derive(Debug, Clone, PartialEq, Eq, Hash, Default)]
96#[non_exhaustive]
97pub struct SegMeta {
98    /// Records in the segment.
99    ///
100    /// ```
101    /// # let dir = kevy_tmpdir::TmpDir::new("segmeta-records");
102    /// let mut b = kevy_seg::SegBuilder::create(&dir.path().join("a.seg"))?;
103    /// for k in [b"a", b"b", b"c"] {
104    ///     b.push(k, b"v")?;
105    /// }
106    /// assert_eq!(b.finish()?.records, 3);
107    /// # Ok::<(), kevy_seg::SegError>(())
108    /// ```
109    pub records: u64,
110    /// Data pages (excluding overflow and footer pages).
111    ///
112    /// A record too large for one page spills into overflow pages, which
113    /// this count leaves out:
114    ///
115    /// ```
116    /// # let dir = kevy_tmpdir::TmpDir::new("segmeta-pages");
117    /// let mut b = kevy_seg::SegBuilder::create(&dir.path().join("a.seg"))?;
118    /// b.push(b"big", &vec![7u8; 64 * 1024])?;
119    /// assert_eq!(b.finish()?.data_pages, 1);
120    /// # Ok::<(), kevy_seg::SegError>(())
121    /// ```
122    pub data_pages: u32,
123    /// Smallest key.
124    ///
125    /// ```
126    /// # let dir = kevy_tmpdir::TmpDir::new("segmeta-min");
127    /// let mut b = kevy_seg::SegBuilder::create(&dir.path().join("a.seg"))?;
128    /// b.push(b"apple", b"1")?;
129    /// b.push(b"pear", b"2")?;
130    /// assert_eq!(b.finish()?.min_key, b"apple");
131    /// # Ok::<(), kevy_seg::SegError>(())
132    /// ```
133    pub min_key: Vec<u8>,
134    /// Largest key.
135    ///
136    /// ```
137    /// # let dir = kevy_tmpdir::TmpDir::new("segmeta-max");
138    /// let mut b = kevy_seg::SegBuilder::create(&dir.path().join("a.seg"))?;
139    /// b.push(b"apple", b"1")?;
140    /// b.push(b"pear", b"2")?;
141    /// assert_eq!(b.finish()?.max_key, b"pear");
142    /// # Ok::<(), kevy_seg::SegError>(())
143    /// ```
144    pub max_key: Vec<u8>,
145}
146
147/// Why a segment file was refused at open. Corruption is a refusal,
148/// never a silent partial read.
149///
150/// ```
151/// use kevy_seg::{Seg, SegError};
152/// # let dir = kevy_tmpdir::TmpDir::new("segerror");
153/// let path = dir.path().join("junk.seg");
154/// std::fs::write(&path, b"not a segment")?;
155/// let err = Seg::open(&path).unwrap_err();
156/// assert!(matches!(err, SegError::Corrupt(_)));
157/// assert!(err.to_string().starts_with("corrupt segment"));
158/// # Ok::<(), Box<dyn std::error::Error>>(())
159/// ```
160#[derive(Debug)]
161#[non_exhaustive]
162pub enum SegError {
163    /// OS-level failure.
164    ///
165    /// ```
166    /// use kevy_seg::{Seg, SegError};
167    /// # let dir = kevy_tmpdir::TmpDir::new("segerror-io");
168    /// let err = Seg::open(&dir.path().join("missing.seg")).unwrap_err();
169    /// assert!(matches!(err, SegError::Io(ref e) if e.kind() == std::io::ErrorKind::NotFound));
170    /// ```
171    Io(std::io::Error),
172    /// Not a segment / truncated / bit-rotted — the named reason.
173    ///
174    /// ```
175    /// use kevy_seg::{Seg, SegBuilder, SegError};
176    /// # let dir = kevy_tmpdir::TmpDir::new("segerror-corrupt");
177    /// let path = dir.path().join("a.seg");
178    /// let mut b = SegBuilder::create(&path)?;
179    /// b.push(b"k", b"v")?;
180    /// b.finish()?;
181    /// // cut the file short: the trailer no longer locates the footer
182    /// let bytes = std::fs::read(&path)?;
183    /// std::fs::write(&path, &bytes[..bytes.len() - 1])?;
184    /// assert!(matches!(Seg::open(&path), Err(SegError::Corrupt(_))));
185    /// # Ok::<(), Box<dyn std::error::Error>>(())
186    /// ```
187    Corrupt(&'static str),
188    /// Builder misuse: keys not strictly ascending.
189    ///
190    /// ```
191    /// use kevy_seg::{SegBuilder, SegError};
192    /// # let dir = kevy_tmpdir::TmpDir::new("segerror-unsorted");
193    /// let mut b = SegBuilder::create(&dir.path().join("a.seg"))?;
194    /// b.push(b"b", b"1")?;
195    /// assert!(matches!(b.push(b"a", b"2"), Err(SegError::Unsorted)));
196    /// assert!(matches!(b.push(b"b", b"2"), Err(SegError::Unsorted)));
197    /// # Ok::<(), SegError>(())
198    /// ```
199    Unsorted,
200}
201
202impl std::fmt::Display for SegError {
203    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
204        match self {
205            Self::Io(e) => write!(f, "io: {e}"),
206            Self::Corrupt(why) => write!(f, "corrupt segment: {why}"),
207            Self::Unsorted => write!(f, "keys must be strictly ascending"),
208        }
209    }
210}
211
212impl std::error::Error for SegError {
213    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
214        match self {
215            Self::Io(e) => Some(e),
216            _ => None,
217        }
218    }
219}
220
221impl From<std::io::Error> for SegError {
222    fn from(e: std::io::Error) -> Self {
223        Self::Io(e)
224    }
225}
226
227#[cfg(test)]
228#[path = "tests.rs"]
229mod tests;