Range scans and iterators
Step 10 of 12, and the store learns to answer a question get cannot: what lies between two
keys? Everything in tinylsm is sorted — the memtable is a BTreeMap, the tables are written
in key order, compaction merges them in key order — and after ten steps the only way to read
any of it is one key at a time. Anyone who wants “everything from m on” is stuck calling
get in a loop over keys they have to guess. This step gives the store a range scan, and the
scan is where implementing a trait by hand stops being an exercise: Iterator is the
interface the whole standard library already speaks.
You are continuing from lsm-ch09 — the tinylsm crate with a bloom filter in front of every
table. This step rewrites src/lib.rs in full and changes nothing else. Cargo.toml is
untouched, still with no dependencies:
[package]name = "tinylsm"version = "0.1.0"edition = "2024"
[dependencies]What a scan has to merge
Section titled “What a scan has to merge”A point lookup visits the memtable, then the tables newest first, and stops at the first
source with an opinion. A scan cannot do that: it needs every source at once, walked side by
side, because the next key in order might be anywhere. So the scan keeps a cursor into each
source and repeatedly takes the smallest key any cursor is parked on. Three rules come with
it, and they are the same rules get already follows:
- where several sources hold the same key, the newest one answers and the older copies are stepped past — the memtable’s value beats table 3’s, table 3’s beats table 7’s;
- a tombstone is an answer too — it hides the key from the scan entirely, no matter what the older tables hold underneath;
- each live key comes out once, with its newest value.
get stops early because one answer is enough. A scan cannot stop early — it stops when every
cursor runs out.
The signature, and why next cannot fail
Section titled “The signature, and why next cannot fail”The store hands back a real Iterator, and that interface forces one design decision before
any code is written. Iterator::next returns Option, not Result: there is no way to say
“this step failed”. But stepping through this store touches the disk — table files are read,
records are parsed and checksummed — and any of that can fail. If next cannot report an
error, the errors must be spent somewhere that can: the constructor.
pub fn scan(&self, from: Option<&[u8]>, to: Option<&[u8]>) -> io::Result<RangeIter>scan reads and checks every source’s records up front, while it can still return an
io::Result, and the iterator it hands back only merges already-checked data. The merge is
lazy — take(10) walks ten steps, not the whole range — but nothing fallsible happens after
the ?. A real database makes the same trade with more machinery: LevelDB’s iterators carry a
status you poll after seeking, because its Next cannot fail either.
The bounds are a half-open range, like Range: from inclusive, to exclusive, and None
leaves a side unbounded, so scan(None, None) walks the whole store. Why not accept a real
RangeBounds<[u8]> and let callers write scan(b"m"..)? Because b"m".. is a
RangeFrom<&[u8; 1]> — a one-byte array reference — and a generic call site does not coerce
that to a slice. get(b"m") works because get’s parameter is concretely &[u8], which is a
coercion site; behind impl RangeBounds<[u8]> the literal arrives uncoerced and fails the
bound check with E0277. Taking Option<&[u8]> directly keeps every call site as friction-free
as get. It also gives reversed ranges somewhere sane to go: from >= to scans nothing,
where the map’s own range panics on the same input.
The merge
Section titled “The merge”The whole mechanism fits in one iterator, and it is small enough to read whole. This is the store’s merge stripped to its frame — two sources, one memtable-shaped and one table-shaped:
/// One sorted source: key-value pairs, value `None` where the newest/// write was a delete. `IntoIter` carries the cursor.struct Source { records: std::vec::IntoIter<(Vec<u8>, Option<Vec<u8>>)>,}
impl Source { /// The record the cursor is parked on, if any. fn head(&self) -> Option<&(Vec<u8>, Option<Vec<u8>>)> { self.records.as_slice().first() }}
/// A merge over sources ordered newest first. The smallest parked key/// comes out first; where several sources hold it, the newest answers/// and the older copies are stepped past; a tombstone drops the key.struct Merge { sources: Vec<Source>,}
impl Iterator for Merge { type Item = (Vec<u8>, Vec<u8>);
fn next(&mut self) -> Option<Self::Item> { loop { // the smallest key any source is parked on let key = self .sources .iter() .filter_map(Source::head) .map(|(key, _)| key.clone()) .min()?;
// advance every source parked on it; the newest answer wins let mut answer: Option<Option<Vec<u8>>> = None; for source in &mut self.sources { if matches!(source.head(), Some((k, _)) if k == &key) { let (_, value) = source.records.next().unwrap(); if answer.is_none() { answer = Some(value); } } }
if let Some(Some(value)) = answer { return Some((key, value)); } } }}
fn render(pairs: Vec<(Vec<u8>, Vec<u8>)>) -> Vec<String> { pairs .into_iter() .map(|(k, v)| { format!( "{}={}", String::from_utf8(k).unwrap(), String::from_utf8(v).unwrap() ) }) .collect()}
fn main() { // the memtable holds one overwrite and one tombstone; the table // under it holds four records, three of them stale or dead let memtable = Source { records: vec![ (b"beta".to_vec(), Some(b"MEM".to_vec())), (b"gamma".to_vec(), None), ] .into_iter(), }; let table = Source { records: vec![ (b"alpha".to_vec(), Some(b"disk".to_vec())), (b"beta".to_vec(), Some(b"stale".to_vec())), (b"gamma".to_vec(), Some(b"stale".to_vec())), (b"zeta".to_vec(), Some(b"disk".to_vec())), ] .into_iter(), }; let mut merged = Merge { sources: vec![memtable, table], };
// the first two live keys — and nothing past them is walked let first_two: Vec<(Vec<u8>, Vec<u8>)> = merged.by_ref().take(2).collect(); println!("{:?}", render(first_two));
// the rest of the range; the tombstoned key never appears let rest: Vec<(Vec<u8>, Vec<u8>)> = merged.collect(); println!("{:?}", render(rest));}Run this in the Rust Playground
["alpha=disk", "beta=MEM"]["zeta=disk"]alpha comes from the table, because that is the only source holding it. beta comes from the
memtable and the table’s stale copy never shows. gamma was deleted — the memtable’s
tombstone answers newest — so it is gone, and zeta is all that is left.
One line in there deserves its own paragraph, because the obvious version of it is wrong. The merge has to record “the newest source holding this key answered”, where the answer itself is either a value or a tombstone. The tempting line is:
answer = value; // compiles, resurrects deleted keysA tombstone’s value is None, and assigning it wipes out the outer marker that meant “some
source answered” — so the next source down, an older table, sees answer.is_none() and its
stale value wins. A key the reader deleted comes back from the scan. The fix is the
Option<Option<..>> above: the outer layer records whether anyone answered, the inner one
what they answered. The store’s test suite pins this — a_scan_hides_deleted_keys fails on
the tempting line and passes on the right one — which is exactly the kind of bug a test
catches and a code review reads past.
The whole file
Section titled “The whole file”This replaces src/lib.rs:
use std::cmp::Ordering;use std::collections::BTreeMap;use std::fs::{File, OpenOptions};use std::io::{self, Read, Seek, SeekFrom, Write};use std::ops::Bound;use std::path::{Path, PathBuf};
/// How often the sparse index records a key: every fourth record in the/// table starts a block, and a lookup reads only the one block it needs.const BLOCK_RECORDS: usize = 4;
/// How many sorted tables may pile up before compaction merges all of/// them back into one. Below that, a compaction only flushes the log.const MERGE_TABLES: usize = 4;
/// The memtable's budget, in key and value bytes. The write that pushes/// the memtable past it flushes the memtable into a new table as part of/// the write — no call to `compact` required.const MEMTABLE_BYTES: usize = 4096;
/// Filter bits per table key. Ten is the standard middle ground: about/// 1.2 MB of bits for a table of a million keys, and roughly one miss in/// a hundred slips through as a false positive.const BLOOM_BITS_PER_KEY: usize = 10;
/// Probe count per key: `BLOOM_BITS_PER_KEY × ln 2` rounds to 7, the/// optimum for that many bits. Fewer probes waste bits; more spread the/// same bits thinner and raise the false-positive rate.const BLOOM_HASHES: u32 = 7;
/// A persistent key-value store in one write-ahead log plus any number/// of sorted tables: every write lands in the log — synced before the/// call returns — and in the in-memory table, the write that pushes the/// memory table past its budget flushes it into a new numbered table —/// cheap, because it writes only what the memory table holds — and once/// `MERGE_TABLES` tables have piled up, a merge folds all of them back/// into one. Lookups walk the tables newest first, and the in-memory/// table sits in front of all of them; a range scan walks the same/// sources side by side, in key order.pub struct TinyLsm { /// Newest writes. `Some(value)` is a live key; `None` is a tombstone /// that shadows any older copy of the key in the on-disk tables. mem: BTreeMap<Vec<u8>, Option<Vec<u8>>>, /// The memtable's byte cost — key and value lengths added up over /// every entry. Compared against `MEMTABLE_BYTES` after each write. mem_bytes: usize, /// The write-ahead log, kept open for the store's life. The handle /// is safe to keep because the log is never renamed: a flush /// truncates it in place, and only tables — never the log — are /// swapped in and out by rename. log: File, /// Path of the append-only log, the store's write path. path: PathBuf, /// The sorted tables on disk, newest first. Each flush adds one; a /// merge replaces the whole list with a single table. tables: Vec<Sstable>,}
impl TinyLsm { /// Open the store at `path`: scan the directory for the store's /// numbered tables and load their sparse indexes, then replay the log /// on top. The log is newer than every table by construction — a /// flush empties the log the moment it folds its records into a /// table — so replaying it after loading the tables restores the true /// state. A torn tail in the log is cut; a whole record that fails /// its checksum stops the open with an error instead of being /// dropped. The log's handle stays open for the life of the store: /// every write goes through it. pub fn open(path: impl AsRef<Path>) -> io::Result<Self> { let path = path.as_ref().to_path_buf(); let mut tables = load_tables(&path)?; tables.sort_by(|a, b| b.number.cmp(&a.number)); let mut log = OpenOptions::new() .create(true) .read(true) .append(true) .open(&path)?; let mut bytes = Vec::new(); log.read_to_end(&mut bytes)?; let mut mem = BTreeMap::new(); let valid = replay(&bytes, &mut mem)?; log.set_len(valid as u64)?; let mem_bytes = mem_size(&mem); Ok(TinyLsm { mem, mem_bytes, log, path, tables, }) }
/// Insert or overwrite `key`. The record hits the write-ahead log /// first and is synced before the call returns, then the memory /// table. A write that pushes the memory table past its budget /// flushes it, so memory stays bounded without the caller having to /// remember `compact`. pub fn put(&mut self, key: impl Into<Vec<u8>>, value: impl Into<Vec<u8>>) -> io::Result<()> { let key = key.into(); let value = value.into(); let payload = encode(b'P', &key, Some(&value)); self.log.write_all(&frame(&payload))?; self.log.sync_all()?; let old = self.mem.insert(key.clone(), Some(value.clone())); self.mem_bytes += entry_size(&key, Some(&value)); self.mem_bytes -= replaced_size(&key, &old); self.maybe_flush()?; Ok(()) }
/// Return the newest value for `key`. The in-memory table wins over /// every on-disk one, and a tombstone anywhere in front of the answer /// shadows the older copies behind it. Reading the tables touches the /// disk and can fail, so the answer comes back in a `Result` — and /// owned, because it may have been read out of a file rather than /// borrowed from memory. pub fn get(&self, key: &[u8]) -> io::Result<Option<Vec<u8>>> { match self.mem.get(key) { Some(Some(value)) => return Ok(Some(value.clone())), Some(None) => return Ok(None), None => {} } for table in &self.tables { match table.lookup(key)? { Answer::Value(value) => return Ok(Some(value)), Answer::Tombstone => return Ok(None), Answer::Missing => {} } } Ok(None) }
/// Remove `key`, appending a tombstone when the key exists — in /// memory, in a table, or both. Returns whether it did. A tombstone /// found on disk counts as "already deleted", not as a live key, so /// deleting twice writes one tombstone, not two. pub fn delete(&mut self, key: &[u8]) -> io::Result<bool> { let live = match self.mem.get(key) { Some(live) => live.is_some(), None => { let mut live = false; for table in &self.tables { match table.lookup(key)? { Answer::Value(_) => { live = true; break; } Answer::Tombstone => break, Answer::Missing => {} } } live } }; if !live { return Ok(false); } let payload = encode(b'D', key, None); self.log.write_all(&frame(&payload))?; self.log.sync_all()?; let old = self.mem.insert(key.to_vec(), None); self.mem_bytes += entry_size(key, None); self.mem_bytes -= replaced_size(key, &old); self.maybe_flush()?; Ok(true) }
/// Iterate the live keys and values from `from` (inclusive) to `to` /// (exclusive), in key order — `None` leaves a side unbounded, so /// `scan(None, None)` walks the whole store. Each key appears once, /// with the newest value; a key deleted anywhere in front of its /// oldest copy is absent. The merge itself is lazy — `take(10)` /// walks ten steps, not the whole range — but each source's records /// are read and checked when `scan` is called, because /// `Iterator::next` cannot fail and reading a table can: an error /// surfaces as an `Err` here, never in the middle of a scan. pub fn scan(&self, from: Option<&[u8]>, to: Option<&[u8]>) -> io::Result<RangeIter> { // an empty or reversed range holds nothing; without this check // the map's own `range` would panic on the reversed ones if let (Some(from), Some(to)) = (from, to) { if from >= to { return Ok(RangeIter { sources: Vec::new() }); } }
let lo = from.map_or(Bound::Unbounded, Bound::Included); let hi = to.map_or(Bound::Unbounded, Bound::Excluded);
// The memory table is already in memory and in key order, so // its source is a copy of the map's slice of the range. let mem: Vec<_> = self .mem .range::<[u8], _>((lo, hi)) .map(|(key, value)| (key.clone(), value.clone())) .collect(); let mut sources = vec![Source { records: mem.into_iter(), }];
// One source per table, newest first — the order lookups walk. // A table's records are sorted on disk, so the walk keeps that // order; records outside the range are parsed and dropped. for table in &self.tables { let bytes = std::fs::read(&table.path)?; let mut records = Vec::new(); for (_, payload) in walk(&bytes)? { let Some((op, key, value)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); }; let value = match op { b'P' => Some(value.to_vec()), b'D' => None, _ => { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unknown operation", )); } }; if in_range(key, &lo, &hi) { records.push((key.to_vec(), value)); } } sources.push(Source { records: records.into_iter(), }); }
Ok(RangeIter { sources }) }
/// Flush the memory table into a new numbered table and empty the /// log, then merge every table back into one once `MERGE_TABLES` /// have piled up. The write path runs the same two moves on its own /// whenever the memory table passes `MEMTABLE_BYTES` — see /// `maybe_flush` — so this is the manual trigger for work that /// otherwise happens inside a write. A crash part way through leaves /// the store correct either way: the flush's table lands through a /// temporary file and a rename, and the log is emptied only after /// the table is in place. pub fn compact(&mut self) -> io::Result<()> { if !self.mem.is_empty() { let number = self.next_table_number(); let table = Sstable::build(&table_path(&self.path, number), number, &self.mem)?; self.tables.insert(0, table); self.log.set_len(0)?; // the table has absorbed the log: empty it self.mem.clear(); self.mem_bytes = 0; } if self.tables.len() >= MERGE_TABLES { self.merge_tables()?; } Ok(()) }
/// Flush when the memory table has outgrown its budget. Every write /// ends here; the budget decides when a flush happens, not a call /// the caller has to remember to make. fn maybe_flush(&mut self) -> io::Result<()> { if self.mem_bytes >= MEMTABLE_BYTES { self.compact()?; } Ok(()) }
/// The number for the next table this store writes. Tables are kept /// newest first, so the newest table's number, plus one, is a number /// no file on disk is using. fn next_table_number(&self) -> u64 { self.tables.first().map_or(1, |t| t.number + 1) }
/// Fold every table into one new one and remove the old files. The /// walk goes oldest first, so a newer put overwrites an older copy of /// its key, and a tombstone lands in the merged map over whatever the /// older tables held. Tombstones come out the other side alive: the /// scan in `load_tables` cannot tell an obsolete file from a live /// one, so no merge in this store may drop them. fn merge_tables(&mut self) -> io::Result<()> { let mut merged: BTreeMap<Vec<u8>, Option<Vec<u8>>> = BTreeMap::new(); for table in self.tables.iter().rev() { // A merge is the one reader allowed to walk whole tables: // it is about to rewrite all of them anyway. let bytes = std::fs::read(&table.path)?; for (_, payload) in walk(&bytes)? { match parse(payload) { Some((b'P', key, value)) => { merged.insert(key.to_vec(), Some(value.to_vec())); } Some((b'D', key, _)) => { merged.insert(key.to_vec(), None); } _ => { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); } } } } let number = self.next_table_number(); let table = Sstable::build(&table_path(&self.path, number), number, &merged)?; let old: Vec<PathBuf> = self.tables.iter().map(|t| t.path.clone()).collect(); self.tables.clear(); self.tables.push(table); for path in old { std::fs::remove_file(path)?; } Ok(()) }}
/// The iterator `scan` hands back: every live key-value pair in the/// requested range, in key order, each key appearing once. The items/// are owned pairs — the values may have been read out of a table file,/// and an iterator that borrowed from the store would pin it for the/// whole scan.pub struct RangeIter { /// The store's sources, newest first: the memory table, then each /// on-disk table in the order lookups walk them. sources: Vec<Source>,}
/// One source of records for the merge: its in-range records in key/// order, plus the cursor an `IntoIter` carries. Corruption was checked/// when the source was built, so stepping through it cannot fail.struct Source { records: std::vec::IntoIter<(Vec<u8>, Option<Vec<u8>>)>,}
impl Source { /// The record the cursor is parked on, if any. fn head(&self) -> Option<&(Vec<u8>, Option<Vec<u8>>)> { self.records.as_slice().first() }}
impl Iterator for RangeIter { type Item = (Vec<u8>, Vec<u8>);
fn next(&mut self) -> Option<Self::Item> { loop { // The smallest key any source is parked on. No source is // parked: the range is exhausted and the scan is over. let key = self .sources .iter() .filter_map(Source::head) .map(|(key, _)| key.clone()) .min()?;
// Every source parked on that key steps past it, and the // newest one's answer is the store's: a value, or a // tombstone that hides the key from the scan. `answer` is // `Option<Option<..>>` on purpose — the outer layer records // whether any source answered, the inner one whether the // answer was live; assigning the bare value would erase the // difference between "answered: nothing" and "not asked". let mut answer: Option<Option<Vec<u8>>> = None; for source in &mut self.sources { if matches!(source.head(), Some((k, _)) if k == &key) { let (_, value) = source.records.next().unwrap(); if answer.is_none() { answer = Some(value); } } }
// The outer `Some` says a source answered; the inner one // says the answer was live. A tombstone won this key — // drop it and keep looking. if let Some(Some(value)) = answer { return Some((key, value)); } } }}
/// Whether `key` falls inside a scan's bounds. The memory table applies/// the same bounds through `BTreeMap::range`; the table records need/// this spelled out. `scan` builds `lo` as included and `hi` as/// excluded, and the other two arms are here for exhaustiveness.fn in_range(key: &[u8], lo: &Bound<&[u8]>, hi: &Bound<&[u8]>) -> bool { let above = match lo { Bound::Included(start) => key >= *start, Bound::Excluded(start) => key > *start, Bound::Unbounded => true, }; let below = match hi { Bound::Included(end) => key <= *end, Bound::Excluded(end) => key < *end, Bound::Unbounded => true, }; above && below}
/// The memtable's byte cost: key and value lengths added up over every/// entry. Computed once per open, after the replay has rebuilt the map.fn mem_size(mem: &BTreeMap<Vec<u8>, Option<Vec<u8>>>) -> usize { mem.iter() .map(|(key, value)| entry_size(key, value.as_ref())) .sum()}
/// The memtable cost of one entry: the key's bytes, plus the value's/// when the entry is live. A tombstone costs its key and nothing else.fn entry_size(key: &[u8], value: Option<&Vec<u8>>) -> usize { key.len() + value.map_or(0, |v| v.len())}
/// The memtable cost of the entry `BTreeMap::insert` displaced. The map/// hands back the previous value — `Option<Option<Vec<u8>>>` here,/// because the stored value is itself an `Option` — and the outer `None`/// means no entry was displaced, which costs nothing.fn replaced_size(key: &[u8], old: &Option<Option<Vec<u8>>>) -> usize { old.as_ref() .map_or(0, |entry| entry_size(key, entry.as_ref()))}
/// Path of table number `n` for a log at `log`: `store.log` keeps its/// tables in `store.1.sst`, `store.2.sst`, and so on — the `.log`/// extension is replaced, not appended to.fn table_path(log: &Path, n: u64) -> PathBuf { log.with_extension(format!("{n}.sst"))}
/// Find every table belonging to the log at `log` — files beside it named/// `<stem>.<number>.sst` — and load their sparse indexes. The scan is the/// store's whole notion of which files are live; a table a crashed merge/// failed to delete looks exactly like a live one, which is why tombstones/// survive merges. A temporary file mid-write ends in `.tmp` and is/// skipped.fn load_tables(log: &Path) -> io::Result<Vec<Sstable>> { let dir = log.parent().unwrap_or(Path::new(".")); let dir = if dir.as_os_str().is_empty() { Path::new(".") } else { dir }; let prefix = format!("{}.", log.file_stem().unwrap_or_default().to_string_lossy()); let mut tables = Vec::new(); for entry in std::fs::read_dir(dir)? { let entry = entry?; if !entry.file_type()?.is_file() { continue; } let name = entry.file_name(); let name = name.to_string_lossy(); let Some(rest) = name.strip_prefix(&prefix) else { continue; }; let Some(number) = rest.strip_suffix(".sst") else { continue; }; let Ok(number) = number.parse::<u64>() else { continue; }; tables.push(Sstable::load(&entry.path(), number)?); } Ok(tables)}
/// What one table knows about a key. Three answers, not two: a live/// value, a delete that is newer than anything an older table might/// hold, and nothing at all. The distinction is what makes deletes work/// across several tables — a tombstone found in a newer table must stop/// the walk, or an older table's copy of the key would resurface.enum Answer { Value(Vec<u8>), Tombstone, Missing,}
/// A sorted table on disk: the framed records from steps 3 and 4 — puts/// and tombstones alike, written in key order — with a sparse index in/// memory, every fourth record's key and offset, so a lookup reads one/// block instead of the whole file. A bloom filter over the table's keys/// sits in front of all of it: a key the filter rejects never opens the/// file at all.struct Sstable { /// This table's number, the `1` in `tinylsm.1.sst`. Higher is newer. number: u64, path: PathBuf, index: Vec<(Vec<u8>, u64)>, /// Every key the table holds, hashed into bits. Rebuilt by `load`, /// refilled by `build` — it never outlives the table it describes. filter: Bloom,}
impl Sstable { /// Load the sparse index for the table at `path`. The index is /// rebuilt by one sequential scan that verifies every checksum on the /// way; a real store writes the index into a footer at the end of the /// file to skip exactly this scan. fn load(path: &Path, number: u64) -> io::Result<Sstable> { let bytes = std::fs::read(path)?; let records = walk(&bytes)?; if valid_end(&records) != bytes.len() { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: records stop short of the end of the file", )); } let mut index = Vec::new(); // the scan that rebuilds the index visits every key anyway, so // the filter comes out of it for free let mut filter = Bloom::for_keys(records.len()); for (i, (pos, payload)) in records.iter().enumerate() { let Some((_, key, _)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); }; if i % BLOCK_RECORDS == 0 { index.push((key.to_vec(), *pos as u64)); } filter.insert(key); } Ok(Sstable { number, path: path.to_path_buf(), index, filter, }) }
/// What this table knows about `key`. The filter answers first: a /// key it rejects cannot be in the table, so the lookup ends before /// the index is touched — no binary search, no file opened. What /// gets past the filter pays the step 6 price: binary-search the /// index for the block that could hold the key, read that block, /// and scan it, stopping at the first key past `key` — the table is /// sorted, so a larger key means the answer is not in the table. fn lookup(&self, key: &[u8]) -> io::Result<Answer> { if !self.filter.might_contain(key) { return Ok(Answer::Missing); } let block = self.index.partition_point(|(k, _)| k.as_slice() <= key); if block == 0 { return Ok(Answer::Missing); // sorts before the first indexed key } let (_, start) = self.index[block - 1]; let end = self.index.get(block).map_or(u64::MAX, |&(_, off)| off); let mut file = File::open(&self.path)?; file.seek(SeekFrom::Start(start))?; let mut bytes = Vec::new(); file.take(end - start).read_to_end(&mut bytes)?; for (_, payload) in walk(&bytes)? { let Some((op, found, value)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); }; match found.cmp(key) { Ordering::Equal => match op { b'P' => return Ok(Answer::Value(value.to_vec())), b'D' => return Ok(Answer::Tombstone), _ => { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unknown operation", )); } }, Ordering::Greater => return Ok(Answer::Missing), Ordering::Less => {} } } Ok(Answer::Missing) }
/// Write `entries` as a new table at `path`, atomically: the records /// go to a temporary file that is fsynced and renamed into place once /// the last one lands. Live keys are written as puts, tombstones as /// deletes. The map is written in its own iteration order, which is /// key order — sorting is the table's whole point, and it costs /// nothing coming out of a `BTreeMap`. Returns the table with its /// index. fn build( path: &Path, number: u64, entries: &BTreeMap<Vec<u8>, Option<Vec<u8>>>, ) -> io::Result<Sstable> { let tmp = path.with_extension("tmp"); let mut index = Vec::new(); let mut filter = Bloom::for_keys(entries.len()); { let mut out = OpenOptions::new() .create(true) .write(true) .truncate(true) .open(&tmp)?; let mut offset = 0u64; for (i, (key, value)) in entries.iter().enumerate() { if i % BLOCK_RECORDS == 0 { index.push((key.clone(), offset)); } filter.insert(key); let op = if value.is_some() { b'P' } else { b'D' }; let record = frame(&encode(op, key, value.as_deref())); out.write_all(&record)?; offset += record.len() as u64; } out.sync_all()?; } std::fs::rename(&tmp, path)?; Ok(Sstable { number, path: path.to_path_buf(), index, filter, }) }}
/// A bloom filter: one bit per probe, `BLOOM_HASHES` probes per key,/// sized at `BLOOM_BITS_PER_KEY` bits per expected key. It can say "no"/// with certainty — a key it rejects was never inserted — but a "yes" is/// only a probability: some keys it never saw will probe bits that real/// keys set, and the lookup falls through to the table and comes back/// empty. That false-positive rate is the knob `BLOOM_BITS_PER_KEY`/// turns; the experiment below it measures what ten bits buy.struct Bloom { bits: Vec<u8>,}
impl Bloom { /// An empty filter with room for `keys` keys. The table knows its /// key count before writing a byte of it: `build` gets it from the /// map's length, `load` from the record count the scan produced. fn for_keys(keys: usize) -> Bloom { Bloom { bits: vec![0; (keys * BLOOM_BITS_PER_KEY).div_ceil(8)], } }
/// Set this key's probes. Inserting the same key twice sets the same /// bits twice — the filter counts nothing and cannot overflow. fn insert(&mut self, key: &[u8]) { for index in probes(key, self.bits.len() * 8) { self.bits[index / 8] |= 1 << (index % 8); } }
/// Whether `key` might be in the set: true for every key inserted, /// true for a shrinking share of keys that were not, false for /// nothing. The false side is the guarantee the read path leans on. fn might_contain(&self, key: &[u8]) -> bool { let len = self.bits.len() * 8; if len == 0 { return false; } probes(key, len).all(|index| self.bits[index / 8] & (1 << (index % 8)) != 0) }}
/// The bit positions one key probes: `BLOOM_HASHES` positions derived/// from a single 64-bit hash, split into two 32-bit halves and mixed as/// `h1 + i·h2`. Real filters use two honest hashes and pay for them;/// this Kirsch–Mitzenmacher trick costs one hash and, measured below,/// a fraction of a percent of extra false positives.fn probes(key: &[u8], bit_len: usize) -> impl Iterator<Item = usize> { let hash = fnv1a64(key); let h1 = (hash >> 32) as u32; let h2 = hash as u32 | 1; // odd, so the stride never shares a factor with a power of two (0..BLOOM_HASHES).map(move |i| (h1.wrapping_add(i.wrapping_mul(h2)) as usize) % bit_len)}
/// FNV-1a over 64 bits, for the bloom filter. The record checksum is/// this hash's 32-bit cousin; the filter wants the wider version so its/// two halves differ enough to spread probes across the bit array.fn fnv1a64(key: &[u8]) -> u64 { let mut hash: u64 = 0xcbf2_9ce4_8422_2325; for &byte in key { hash ^= u64::from(byte); hash = hash.wrapping_mul(0x0000_0100_0000_01b3); } hash}
/// FNV-1a, 32-bit: three lines, deterministic, and enough to catch a torn/// or corrupted record on the way back in.fn checksum(payload: &[u8]) -> u32 { let mut hash: u32 = 0x811c_9dc5; for &byte in payload { hash ^= u32::from(byte); hash = hash.wrapping_mul(0x0100_0193); } hash}
/// One log payload: op byte, then the key and value, each length-prefixed./// A delete carries no value — its payload ends after an empty length.fn encode(op: u8, key: &[u8], value: Option<&[u8]>) -> Vec<u8> { let value = value.unwrap_or(&[]); let mut payload = Vec::with_capacity(9 + key.len() + value.len()); payload.push(op); payload.extend_from_slice(&(key.len() as u32).to_le_bytes()); payload.extend_from_slice(key); payload.extend_from_slice(&(value.len() as u32).to_le_bytes()); payload.extend_from_slice(value); payload}
/// Frame one payload as a record: payload length, checksum, payload.fn frame(payload: &[u8]) -> Vec<u8> { let mut record = Vec::with_capacity(8 + payload.len()); record.extend_from_slice(&(payload.len() as u32).to_le_bytes()); record.extend_from_slice(&checksum(payload).to_le_bytes()); record.extend_from_slice(payload); record}
/// Walk the framed records in `bytes`, returning each one's offset and/// payload. The walk stops at a torn tail — a record a crash cut short —/// and a whole record whose checksum fails is an error, not a record to/// drop. Both the log and the tables are read through this.fn walk(bytes: &[u8]) -> io::Result<Vec<(usize, &[u8])>> { let mut records = Vec::new(); let mut rest = bytes; let mut pos = 0; while rest.len() >= 8 { let len = u32::from_le_bytes(rest[..4].try_into().unwrap()) as usize; let sum = u32::from_le_bytes(rest[4..8].try_into().unwrap()); if len > rest.len() - 8 { break; // the payload never finished landing: torn tail } let (payload, tail) = rest[8..].split_at(len); if checksum(payload) != sum { return Err(io::Error::new( io::ErrorKind::InvalidData, "corrupt record: checksum mismatch", )); } records.push((pos, payload)); rest = tail; pos += 8 + len; } Ok(records)}
/// Offset just past the last walked record: the end of the valid prefix.fn valid_end(records: &[(usize, &[u8])]) -> usize { records .last() .map_or(0, |(pos, payload)| pos + 8 + payload.len())}
/// Replay the log's records into `mem` and return the offset where the/// valid prefix ends — everything after that, the caller cuts.fn replay(bytes: &[u8], mem: &mut BTreeMap<Vec<u8>, Option<Vec<u8>>>) -> io::Result<usize> { let records = walk(bytes)?; let end = valid_end(&records); for (_, payload) in &records { apply(payload, mem)?; } Ok(end)}
/// Apply one record payload to `mem`: a put stores its value, a delete/// stores a tombstone. `Err` when the payload is not shaped like a record —/// with the checksum already verified, that is a bug in the writer, not a/// damaged file.fn apply(payload: &[u8], mem: &mut BTreeMap<Vec<u8>, Option<Vec<u8>>>) -> io::Result<()> { let Some((op, key, value)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "corrupt record: malformed payload", )); }; match op { b'P' => { mem.insert(key.to_vec(), Some(value.to_vec())); Ok(()) } b'D' => { mem.insert(key.to_vec(), None); Ok(()) } _ => Err(io::Error::new( io::ErrorKind::InvalidData, "corrupt record: unknown operation", )), }}
/// Parse one payload into `(op, key, value)`: an op byte, then the key and/// value, each length-prefixed. `None` when the payload is not shaped like/// a record.fn parse(payload: &[u8]) -> Option<(u8, &[u8], &[u8])> { let (&op, rest) = payload.split_first()?; let (klen, rest) = read_u32(rest)?; let (key, rest) = take(klen as usize, rest)?; let (vlen, rest) = read_u32(rest)?; let (value, rest) = take(vlen as usize, rest)?; if !rest.is_empty() { return None; } Some((op, key, value))}
/// Pop a little-endian `u32` off the front of `bytes`.fn read_u32(bytes: &[u8]) -> Option<(u32, &[u8])> { let head = bytes.get(..4)?; Some((u32::from_le_bytes(head.try_into().ok()?), &bytes[4..]))}
/// Split `n` bytes off the front of `bytes`, or `None` if it is shorter.fn take(n: usize, bytes: &[u8]) -> Option<(&[u8], &[u8])> { if bytes.len() < n { None } else { Some(bytes.split_at(n)) }}
#[cfg(test)]mod tests { use super::*; use std::path::PathBuf;
/// A unique scratch directory per test, with the store's log inside /// it. The tests in this module run in parallel, and a shared /// directory would have them overwriting each other; a directory of /// their own also means cleanup can take the tables with it. fn temp_log(name: &str) -> PathBuf { let mut dir = std::env::temp_dir(); dir.push(format!("tinylsm-{}-{}", name, std::process::id())); std::fs::create_dir_all(&dir).unwrap(); dir.join("tinylsm.log") }
/// The store lives in up to four kinds of file: the log, the numbered /// tables beside it, and a table's temporary file mid-write. Removing /// the directory takes all of them. fn cleanup(log: &Path) { if let Some(dir) = log.parent() { let _ = std::fs::remove_dir_all(dir); } }
/// The table files beside `log`, sorted by name — which, for the /// single-digit numbers this suite produces, is numeric order too. fn sst_files(log: &Path) -> Vec<PathBuf> { let dir = log.parent().unwrap(); let prefix = format!("{}.", log.file_stem().unwrap().to_string_lossy()); let mut found: Vec<PathBuf> = std::fs::read_dir(dir) .unwrap() .flatten() .filter(|e| { let name = e.file_name().to_string_lossy().to_string(); name.starts_with(&prefix) && name.ends_with(".sst") }) .map(|e| e.path()) .collect(); found.sort(); found }
#[test] fn put_then_get() { let path = temp_log("put-get"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"one".to_vec())); cleanup(&path); }
#[test] fn get_missing_is_none() { let path = temp_log("missing"); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"nope").unwrap(), None); cleanup(&path); }
#[test] fn put_overwrites() { let path = temp_log("overwrite"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"alpha", b"two").unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn delete_removes_and_reports() { let path = temp_log("delete"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); assert!(store.delete(b"alpha").unwrap()); assert_eq!(store.get(b"alpha").unwrap(), None); assert!(!store.delete(b"alpha").unwrap()); cleanup(&path); }
#[test] fn keys_are_independent() { let path = temp_log("independent"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); store.delete(b"alpha").unwrap(); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn put_appends_one_record() { let path = temp_log("append"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); drop(store);
let bytes = std::fs::read(&path).unwrap(); // header (4 + 4) + payload (op 1, klen 4, key 5, vlen 4, value 3) assert_eq!(bytes.len(), 8 + 17); assert_eq!(bytes[8], b'P'); assert_eq!(&bytes[13..18], b"alpha"); assert_eq!(&bytes[22..25], b"one"); cleanup(&path); }
#[test] fn delete_appends_a_tombstone() { let path = temp_log("tombstone"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.delete(b"alpha").unwrap(); drop(store);
let bytes = std::fs::read(&path).unwrap(); // the put record (25 bytes), then a delete record with no value: // header 8 + payload (op 1, klen 4, key 5, vlen 4) = 22 assert_eq!(bytes.len(), 25 + 22); assert_eq!(bytes[25 + 8], b'D'); cleanup(&path); }
#[test] fn deleting_a_missing_key_writes_nothing() { let path = temp_log("no-tombstone"); let mut store = TinyLsm::open(&path).unwrap(); assert!(!store.delete(b"ghost").unwrap()); assert_eq!(std::fs::read(&path).unwrap().len(), 0); cleanup(&path); }
#[test] fn open_replays_writes() { let path = temp_log("replay"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); } let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"one".to_vec())); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn open_replays_the_last_write() { let path = temp_log("replay-last"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"alpha", b"two").unwrap(); } let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn open_replays_tombstones() { let path = temp_log("replay-tombstone"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); store.delete(b"alpha").unwrap(); } let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn open_a_missing_file_starts_empty() { let path = temp_log("fresh"); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); assert_eq!(std::fs::read(&path).unwrap().len(), 0); cleanup(&path); }
/// The first 10 bytes of a well-formed put record for `beta`, simulating /// a crash that cut the record short after its header and 2 payload /// bytes landed. fn torn_tail(path: &Path) { let payload = encode(b'P', b"beta", Some(b"two")); let record = frame(&payload); let mut log = OpenOptions::new().append(true).open(path).unwrap(); log.write_all(&record[..10]).unwrap(); }
#[test] fn open_cuts_a_torn_tail() { let path = temp_log("torn"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); } torn_tail(&path);
let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"one".to_vec())); assert_eq!(store.get(b"beta").unwrap(), None); drop(store); // the tail is gone, and the file ends after the last whole record assert_eq!(std::fs::read(&path).unwrap().len(), 25); cleanup(&path); }
#[test] fn a_reopened_store_keeps_appending_cleanly() { let path = temp_log("append-after-torn"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); } torn_tail(&path);
let mut store = TinyLsm::open(&path).unwrap(); store.put(b"beta", b"two").unwrap(); drop(store);
let bytes = std::fs::read(&path).unwrap(); // the cut put (25) plus a whole put record for beta (24): no hole, // no half record between them assert_eq!(bytes.len(), 25 + 24); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn open_refuses_a_corrupt_record() { let path = temp_log("corrupt"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); } // flip one value byte: the record is whole, but not what was written let mut bytes = std::fs::read(&path).unwrap(); bytes[22] ^= 0xff; std::fs::write(&path, &bytes).unwrap();
let err = TinyLsm::open(&path).err().unwrap(); assert_eq!(err.kind(), io::ErrorKind::InvalidData); // the file is left alone — nothing is silently discarded assert_eq!(std::fs::read(&path).unwrap(), bytes); cleanup(&path); }
#[test] fn compact_flushes_the_log_into_a_numbered_table() { let path = temp_log("compact-drains"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); store.compact().unwrap();
// the log is drained; the first table beside it holds both // records, 25 + 24 bytes in the step 3 format assert_eq!(std::fs::read(&path).unwrap().len(), 0); let tables = sst_files(&path); assert_eq!(tables.len(), 1); assert!(tables[0].ends_with("tinylsm.1.sst")); assert_eq!(std::fs::read(&tables[0]).unwrap().len(), 25 + 24);
let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"one".to_vec())); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn a_flush_writes_its_tombstones() { let path = temp_log("flush-tombstone"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"alpha", b"two").unwrap(); store.put(b"beta", b"two").unwrap(); store.delete(b"alpha").unwrap(); store.compact().unwrap();
// the flush collapses superseded values, but the tombstone goes // into the table as a delete record and stays there: alpha's // delete (22 bytes) plus beta's put (24 bytes) let tables = sst_files(&path); assert_eq!(tables.len(), 1); assert_eq!(std::fs::read(&tables[0]).unwrap().len(), 22 + 24); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn compact_writes_keys_in_sorted_order() { let path = temp_log("compact-sorted"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"zeta", b"one").unwrap(); store.put(b"alpha", b"two").unwrap(); store.put(b"mid", b"three").unwrap(); store.compact().unwrap();
// the first record in the table carries the first key in the map's // order, which is sorted let tables = sst_files(&path); let table = std::fs::read(&tables[0]).unwrap(); let len = u32::from_le_bytes(table[..4].try_into().unwrap()) as usize; let payload = &table[8..8 + len]; assert_eq!(payload[0], b'P'); let klen = u32::from_le_bytes(payload[1..5].try_into().unwrap()) as usize; assert_eq!(&payload[5..5 + klen], b"alpha"); cleanup(&path); }
#[test] fn a_tombstone_in_memory_shadows_the_tables() { let path = temp_log("shadow"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); // alpha now lives only in a table
assert!(store.delete(b"alpha").unwrap()); // the tombstone in memory keeps the table's older copy hidden assert_eq!(store.get(b"alpha").unwrap(), None); cleanup(&path); }
#[test] fn a_tombstone_survives_a_reopen() { let path = temp_log("shadow-reopen"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); store.delete(b"alpha").unwrap(); drop(store);
// the log replays the tombstone over the table's older copy let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); cleanup(&path); }
#[test] fn a_tombstone_in_a_newer_table_shadows_an_older_one() { let path = temp_log("shadow-tables"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); // table 1: alpha's put store.put(b"alpha", b"two").unwrap(); store.compact().unwrap(); // table 2: alpha's newer put store.delete(b"alpha").unwrap(); store.compact().unwrap(); // table 3: alpha's tombstone
// three tables, and the tombstone in the newest one wins assert_eq!(sst_files(&path).len(), 3); assert_eq!(store.get(b"alpha").unwrap(), None); drop(store); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); cleanup(&path); }
#[test] fn a_lookup_walks_the_tables_newest_first() { let path = temp_log("newest-first"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); store.put(b"alpha", b"two").unwrap(); store.compact().unwrap();
// both tables hold alpha; the newer one must answer assert_eq!(sst_files(&path).len(), 2); assert_eq!(store.get(b"alpha").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn a_second_delete_after_a_flush_writes_nothing() { let path = temp_log("delete-twice"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.delete(b"alpha").unwrap(); store.compact().unwrap(); // the tombstone now lives in table 1
// the tombstone on disk says "already deleted": no second record assert!(!store.delete(b"alpha").unwrap()); assert_eq!(std::fs::read(&path).unwrap().len(), 0); cleanup(&path); }
#[test] fn compaction_piles_up_tables_then_merges_them() { let path = temp_log("merge"); let mut store = TinyLsm::open(&path).unwrap(); for (key, value) in [("alpha", "one"), ("beta", "two")] { store.put(key, value).unwrap(); } store.compact().unwrap(); for (key, value) in [("gamma", "three"), ("delta", "four")] { store.put(key, value).unwrap(); } store.compact().unwrap(); for (key, value) in [("echo", "five"), ("fox", "six")] { store.put(key, value).unwrap(); } store.compact().unwrap();
// three flushes, three tables: below MERGE_TABLES nothing merges assert_eq!(sst_files(&path).len(), 3);
store.put(b"goose", b"seven").unwrap(); store.compact().unwrap();
// the fourth table trips the threshold, and all four fold into one let tables = sst_files(&path); assert_eq!(tables.len(), 1); let store = TinyLsm::open(&path).unwrap(); for (key, value) in [ ("alpha", "one"), ("beta", "two"), ("gamma", "three"), ("delta", "four"), ("echo", "five"), ("fox", "six"), ("goose", "seven"), ] { assert_eq!( store.get(key.as_bytes()).unwrap(), Some(value.as_bytes().to_vec()), "wrong value for {key}" ); } cleanup(&path); }
#[test] fn a_merge_keeps_tombstones() { let path = temp_log("merge-tombstone"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); // table 1: alpha's put store.delete(b"alpha").unwrap(); store.compact().unwrap(); // table 2: alpha's tombstone store.put(b"beta", b"two").unwrap(); store.compact().unwrap(); // table 3 store.put(b"gamma", b"three").unwrap(); store.compact().unwrap(); // table 4: the threshold trips
// the merged table carries alpha's tombstone with it: the delete // (22 bytes) plus beta's put (24) and gamma's put (27 — "three" // is a byte longer than "two") let tables = sst_files(&path); assert_eq!(tables.len(), 1); assert_eq!(std::fs::read(&tables[0]).unwrap().len(), 22 + 24 + 27); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn a_leftover_table_cannot_resurrect_a_deleted_key() { let path = temp_log("leftover"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); // keep a copy of table 1, as if a crashed merge had failed to // delete it let leftover = std::fs::read(path.with_extension("1.sst")).unwrap();
store.delete(b"alpha").unwrap(); store.compact().unwrap(); // table 2: alpha's tombstone store.put(b"beta", b"two").unwrap(); store.compact().unwrap(); // table 3 store.put(b"gamma", b"three").unwrap(); store.compact().unwrap(); // table 4: merge; table 2's tombstone rides along
// the merge removed tables 1 to 4; put the "leftover" back std::fs::write(path.with_extension("1.sst"), leftover).unwrap();
// the merged table's tombstone shadows the leftover's old put — // this is exactly the read a dropped tombstone would resurrect let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), None); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn a_store_keeps_working_after_compaction() { let path = temp_log("compact-continue"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.delete(b"alpha").unwrap(); store.compact().unwrap(); // writes after the flush land in the log and shadow the table store.put(b"beta", b"two").unwrap(); store.put(b"alpha", b"three").unwrap(); drop(store);
let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"three".to_vec())); assert_eq!(store.get(b"beta").unwrap(), Some(b"two".to_vec())); cleanup(&path); }
#[test] fn compacting_an_empty_store_writes_nothing() { let path = temp_log("compact-empty"); let mut store = TinyLsm::open(&path).unwrap(); store.compact().unwrap(); // nothing in memory, nothing to flush: no table, no log bytes assert_eq!(sst_files(&path).len(), 0); assert_eq!(std::fs::read(&path).unwrap().len(), 0); cleanup(&path); }
#[test] fn compact_leaves_no_temporary_file_behind() { let path = temp_log("compact-tmp"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap();
let dir = path.parent().unwrap(); let tmps: Vec<_> = std::fs::read_dir(dir) .unwrap() .flatten() .filter(|e| e.file_name().to_string_lossy().ends_with(".tmp")) .collect(); assert!(tmps.is_empty()); cleanup(&path); }
#[test] fn a_temporary_file_left_by_a_crash_is_replaced() { let path = temp_log("compact-stale-tmp"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); // a crash mid-flush leaves a half-written temp file behind; the // next flush truncates it and carries on. The temp file for // table 1 is `tinylsm.1.tmp` — the `.sst` is replaced, not // extended let tmp = path.with_extension("1.tmp"); std::fs::write(&tmp, b"garbage bytes").unwrap();
store.compact().unwrap(); assert!(!tmp.exists()); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"one".to_vec())); cleanup(&path); }
#[test] fn compaction_round_trips_through_a_reopen() { let path = temp_log("compact-roundtrip"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); store.put(b"alpha", b"three").unwrap(); store.delete(b"beta").unwrap(); store.compact().unwrap(); } let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"three".to_vec())); assert_eq!(store.get(b"beta").unwrap(), None); cleanup(&path); }
#[test] fn a_lookup_after_a_reopen_uses_the_rebuilt_index() { let path = temp_log("index-rebuilt"); { let mut store = TinyLsm::open(&path).unwrap(); for (key, value) in [ ("alpha", "one"), ("beta", "two"), ("gamma", "three"), ("delta", "four"), ("echo", "five"), ("fox", "six"), ] { store.put(key, value).unwrap(); } store.compact().unwrap(); } // the index is gone with the process; the reopen rebuilds it from // the table, and every lookup through it lands on the right record let store = TinyLsm::open(&path).unwrap(); for (key, value) in [ ("alpha", "one"), ("beta", "two"), ("gamma", "three"), ("delta", "four"), ("echo", "five"), ("fox", "six"), ] { assert_eq!( store.get(key.as_bytes()).unwrap(), Some(value.as_bytes().to_vec()), "wrong value for {key}" ); } assert_eq!(store.get(b"goose").unwrap(), None); cleanup(&path); }
#[test] fn reopen_refuses_a_truncated_table() { let path = temp_log("table-torn"); { let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); } // the table is installed by an atomic rename, so a short table is // not a torn write to recover from — it is damage, and it is refused let table = path.with_extension("1.sst"); let mut bytes = std::fs::read(&table).unwrap(); bytes.truncate(bytes.len() - 4); std::fs::write(&table, &bytes).unwrap();
let err = TinyLsm::open(&path).err().unwrap(); assert_eq!(err.kind(), io::ErrorKind::InvalidData); cleanup(&path); }
#[test] fn a_full_memtable_flushes_on_its_own() { let path = temp_log("auto-flush"); let mut store = TinyLsm::open(&path).unwrap(); for i in 0..100 { let key = format!("key{i:03}"); store.put(key.as_bytes(), vec![b'x'; 64]).unwrap(); } // 70 bytes per write: the 59th crosses MEMTABLE_BYTES and flushes // without any call to compact. The 41 writes after it stay in the // log, still under budget. assert_eq!(sst_files(&path).len(), 1); assert_eq!(std::fs::read(&path).unwrap().len(), 41 * 87); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"key000").unwrap(), Some(vec![b'x'; 64])); assert_eq!(store.get(b"key099").unwrap(), Some(vec![b'x'; 64])); cleanup(&path); }
#[test] fn a_flush_truncates_the_log_in_place() { let path = temp_log("truncate"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); store.put(b"beta", b"two").unwrap(); drop(store);
// the post-flush write starts at offset 0: the log holds exactly // beta's record, not a hole where alpha's record used to be let bytes = std::fs::read(&path).unwrap(); assert_eq!(bytes.len(), 24); assert_eq!(bytes[8], b'P'); assert_eq!(&bytes[13..17], b"beta"); cleanup(&path); }
#[test] fn an_overwrite_keeps_the_budget_honest() { let path = temp_log("overwrite-budget"); let mut store = TinyLsm::open(&path).unwrap(); // 5000 bytes of value: the first put crosses the budget on its own store.put(b"alpha", vec![b'x'; 5000]).unwrap(); assert_eq!(sst_files(&path).len(), 1); // the overwrite is 9 bytes in the memtable: no second flush store.put(b"alpha", b"tiny").unwrap(); assert_eq!(sst_files(&path).len(), 1); assert_eq!(store.get(b"alpha").unwrap(), Some(b"tiny".to_vec())); drop(store); let store = TinyLsm::open(&path).unwrap(); assert_eq!(store.get(b"alpha").unwrap(), Some(b"tiny".to_vec())); cleanup(&path); }
#[test] fn a_filter_never_rejects_a_key_it_holds() { // the one guarantee a bloom filter makes: nothing inserted may // ever come back "no" let mut filter = Bloom::for_keys(1000); let keys: Vec<Vec<u8>> = (0..1000).map(|i| format!("key{i:05}").into_bytes()).collect(); for key in &keys { filter.insert(key); } for key in &keys { assert!(filter.might_contain(key), "filter rejected {key:?}"); } }
#[test] fn a_miss_skips_the_table_file() { let path = temp_log("filter-skip"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); drop(store);
// the reopen rebuilds the filter; then the table file goes away, // so any lookup that touched the disk would fail let store = TinyLsm::open(&path).unwrap(); std::fs::remove_file(path.with_extension("1.sst")).unwrap();
// a miss never opens the file: the filter says no and that is // the whole answer assert_eq!(store.get(b"absent").unwrap(), None); // a hit has to read the file, and it is gone assert!(store.get(b"alpha").is_err()); cleanup(&path); }
#[test] fn a_false_positive_still_answers_none() { let path = temp_log("filter-fp"); let mut store = TinyLsm::open(&path).unwrap(); for i in 0..200 { store.put(format!("key{i:05}").as_bytes(), b"v").unwrap(); } store.compact().unwrap();
// two thousand absent keys: the filter waves some through as // false positives, and the block scan they fall through to must // send every one of them home empty for i in 0..2000 { let key = format!("absent{i:05}"); assert_eq!( store.get(key.as_bytes()).unwrap(), None, "false positive turned into a value for {key}" ); } cleanup(&path); }
#[test] fn the_filter_stays_under_its_false_positive_budget() { // ten thousand real keys, ten thousand absent probes, measured // through the store's own parameters: 10 bits per key, 7 probes, // the double-hashed probes the store uses let mut filter = Bloom::for_keys(10_000); for i in 0..10_000 { filter.insert(format!("key{i:05}").as_bytes()); } let false_positives = (0..10_000) .map(|i| format!("absent{i:05}")) .filter(|key| filter.might_contain(key.as_bytes())) .count(); // theory says about 0.9% with these parameters; the budget here // is double that, and the experiment in the article prints the // exact number assert!( false_positives < 200, "{false_positives} false positives in 10_000 probes" ); }
#[test] fn a_scan_walks_the_whole_store_in_key_order() { let path = temp_log("scan-order"); let mut store = TinyLsm::open(&path).unwrap(); // unsorted inserts, split across a flush and the memtable for (key, value) in [("m", "3"), ("a", "1"), ("z", "4"), ("b", "2")] { store.put(key, value).unwrap(); } store.compact().unwrap(); store.put(b"n", b"5").unwrap(); // stays in the memtable
let scanned: Vec<(Vec<u8>, Vec<u8>)> = store.scan(None, None).unwrap().collect(); let keys: Vec<&[u8]> = scanned.iter().map(|(k, _)| k.as_slice()).collect(); assert_eq!(keys, [b"a", b"b", b"m", b"n", b"z"]); let values: Vec<&[u8]> = scanned.iter().map(|(_, v)| v.as_slice()).collect(); assert_eq!(values, [b"1", b"2", b"3", b"5", b"4"]); cleanup(&path); }
#[test] fn a_scan_answers_within_its_bounds() { let path = temp_log("scan-bounds"); let mut store = TinyLsm::open(&path).unwrap(); for key in [b"c", b"a", b"e", b"b", b"d"] { store.put(key, b"v").unwrap(); } store.compact().unwrap();
// `to` is exclusive, `from` inclusive — a half-open range let keys: Vec<Vec<u8>> = store .scan(Some(b"b"), Some(b"e")) .unwrap() .map(|(k, _)| k) .collect(); assert_eq!(keys, [b"b".to_vec(), b"c".to_vec(), b"d".to_vec()]);
// an unbounded end runs to the store's last key let keys: Vec<Vec<u8>> = store .scan(Some(b"d"), None) .unwrap() .map(|(k, _)| k) .collect(); assert_eq!(keys, [b"d".to_vec(), b"e".to_vec()]); cleanup(&path); }
#[test] fn a_scan_hides_deleted_keys() { let path = temp_log("scan-deleted"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); store.compact().unwrap(); store.delete(b"alpha").unwrap(); // tombstone in the memtable
let keys: Vec<Vec<u8>> = store.scan(None, None).unwrap().map(|(k, _)| k).collect(); assert_eq!(keys, [b"beta".to_vec()]); cleanup(&path); }
#[test] fn a_scan_shows_each_key_once_with_the_newest_value() { let path = temp_log("scan-newest"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.compact().unwrap(); // alpha=one is in a table now store.put(b"alpha", b"two").unwrap(); // alpha=two is in the memtable
// both sources hold alpha; the scan answers once, with the // memtable's copy let scanned: Vec<(Vec<u8>, Vec<u8>)> = store.scan(None, None).unwrap().collect(); assert_eq!(scanned, [(b"alpha".to_vec(), b"two".to_vec())]); cleanup(&path); }
#[test] fn a_scan_plugs_into_the_standard_adapters() { let path = temp_log("scan-adapters"); let mut store = TinyLsm::open(&path).unwrap(); for key in [b"a", b"b", b"c", b"d"] { store.put(key, b"v").unwrap(); } store.compact().unwrap();
// implementing Iterator once buys every adapter in the standard // library; take walks two steps and the rest stays unconsumed let mut iter = store.scan(None, None).unwrap(); let first_two: Vec<Vec<u8>> = iter.by_ref().take(2).map(|(k, _)| k).collect(); assert_eq!(first_two, [b"a".to_vec(), b"b".to_vec()]); assert_eq!(iter.count(), 2); cleanup(&path); }
#[test] fn an_empty_or_reversed_range_scans_nothing() { let path = temp_log("scan-empty"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"m", b"v").unwrap();
// from == to is an empty half-open range; from > to has nothing // between the ends. Neither panics — unlike the map's own range. assert_eq!(store.scan(Some(b"m"), Some(b"m")).unwrap().count(), 0); assert_eq!(store.scan(Some(b"z"), Some(b"a")).unwrap().count(), 0); cleanup(&path); }}What implementing Iterator buys
Section titled “What implementing Iterator buys”RangeIter implements Iterator once, and everything downstream is the standard library’s
problem. for (key, value) in store.scan(None, None)? works. .take(2), .count(),
.filter(), .collect() work, and they compose: scan(None, None)?.take(10) is one concrete
struct wrapped in another, each next a direct call — no trait objects, no Box<dyn Iterator>, no heap allocation per item beyond the pair it hands back. The test
a_scan_plugs_into_the_standard_adapters leans on that: it takes two pairs from an iterator,
then count()s the rest of the same iterator, and both answers are right.
That is the “zero-cost” half of Rust’s iterator story stated plainly: implementing Iterator
for a concrete type gets adapter chains that compile down to the loop you would have
hand-written, because every adapter is its own concrete type rather than a virtual call. The
honest cost side: each next scans every source’s head to find the smallest key — with
sources tables, every step is a walk over sources heads. A real store keeps the cursors in
a binary heap and pays log sources instead. At this store’s table counts, the walk is the
simpler code and it is not the bottleneck; the step after next measures where the actual time
goes.
What this does not fix
Section titled “What this does not fix”scan reads each table file whole — std::fs::read, then walk — and parses every record,
keeping only the ones inside the range. The sparse index from step 6 could take a scan
straight to the first block that might contain from, and the sorted walk could stop at the
first key past to; a real store does exactly that, and reading four blocks instead of a
whole file is the difference between a scan and a table rewrite. The merge is lazy; the reads
under it are not. That, the heap, and the index seek are all on the same shelf: this is a toy
whose job is to make the shape of the thing visible, and the shape is right.
See it run
Section titled “See it run”From the tinylsm directory:
cargo testrunning 46 teststest tests::a_filter_never_rejects_a_key_it_holds ... oktest tests::a_reopened_store_keeps_appending_cleanly ... oktest tests::a_flush_truncates_the_log_in_place ... oktest tests::a_miss_skips_the_table_file ... oktest tests::a_flush_writes_its_tombstones ... oktest tests::a_scan_hides_deleted_keys ... oktest tests::a_lookup_walks_the_tables_newest_first ... oktest tests::a_scan_answers_within_its_bounds ... oktest tests::a_lookup_after_a_reopen_uses_the_rebuilt_index ... oktest tests::a_second_delete_after_a_flush_writes_nothing ... oktest tests::a_scan_shows_each_key_once_with_the_newest_value ... oktest tests::a_scan_plugs_into_the_standard_adapters ... oktest tests::a_temporary_file_left_by_a_crash_is_replaced ... oktest tests::a_scan_walks_the_whole_store_in_key_order ... oktest tests::an_empty_or_reversed_range_scans_nothing ... oktest tests::a_tombstone_in_memory_shadows_the_tables ... oktest tests::a_merge_keeps_tombstones ... oktest tests::a_store_keeps_working_after_compaction ... oktest tests::compacting_an_empty_store_writes_nothing ... oktest tests::a_tombstone_survives_a_reopen ... oktest tests::a_leftover_table_cannot_resurrect_a_deleted_key ... oktest tests::an_overwrite_keeps_the_budget_honest ... oktest tests::a_tombstone_in_a_newer_table_shadows_an_older_one ... oktest tests::compact_leaves_no_temporary_file_behind ... oktest tests::compact_flushes_the_log_into_a_numbered_table ... oktest tests::deleting_a_missing_key_writes_nothing ... oktest tests::delete_appends_a_tombstone ... oktest tests::delete_removes_and_reports ... oktest tests::compact_writes_keys_in_sorted_order ... oktest tests::get_missing_is_none ... oktest tests::open_a_missing_file_starts_empty ... oktest tests::open_cuts_a_torn_tail ... oktest tests::open_refuses_a_corrupt_record ... oktest tests::compaction_round_trips_through_a_reopen ... oktest tests::keys_are_independent ... oktest tests::open_replays_the_last_write ... oktest tests::the_filter_stays_under_its_false_positive_budget ... oktest tests::open_replays_writes ... oktest tests::open_replays_tombstones ... oktest tests::put_appends_one_record ... oktest tests::put_then_get ... oktest tests::put_overwrites ... oktest tests::reopen_refuses_a_truncated_table ... oktest tests::compaction_piles_up_tables_then_merges_them ... oktest tests::a_full_memtable_flushes_on_its_own ... oktest tests::a_false_positive_still_answers_none ... ok
test result: ok. 46 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.86sYour run may list the tests in a different order — they run in parallel — and the timing line
will differ. Forty of these are steps 2 through 9’s, carried over unchanged. The six new ones
pin this step: a scan walks the whole store in key order across a flush boundary, honours its
half-open bounds and an unbounded end, hides deleted keys, shows each key once with its newest
value, composes with take and count, and treats an empty or reversed range as empty rather
than panicking.
Where this lands in the repository
Section titled “Where this lands in the repository”This step’s state is tagged lsm-ch10 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/toy-databasegit checkout lsm-ch10The tag contains the rewritten src/lib.rs and nothing else new. If your build misbehaves,
diff your files against the tag’s — the drifting line is usually findable that way. The
track overview keeps the step list current.
Step 11, Benchmarking against sled and RocksDB, stops taking the store’s speed on faith. It
wires the same operations into criterion, runs the real databases next to it, and prints
honest numbers — including the ones where tinylsm loses, and why.