Bloom filters to skip disk reads
Step 9 of 12, and the read path gets the part its miss case deserves. Step 8 left a store whose writes are durable and self-flushing — and whose lookups still pay full price to say no. A key that is nowhere in the store costs a block read per table: the sparse index is searched, the file is opened, the block is read and scanned, and all of it happens just to answer “not here”. This step puts a bloom filter in front of every table, so most misses end at seven bit tests in memory.
You are continuing from lsm-ch08 — the tinylsm crate with a kept-open write-ahead log, a
sync on every write, and a memtable that flushes itself by budget. 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]The store’s fields do not change. What changes is one of them: each table carries a filter beside its index now.
struct Sstable { number: u64, // this table's number, higher is newer path: PathBuf, // where the table lives index: Vec<(Vec<u8>, u64)>, // every fourth key, its offset filter: Bloom, // every key the table holds, hashed into bits}The read a miss pays
Section titled “The read a miss pays”Follow a lookup for a key that exists in no table at all. get checks the memtable — cheap,
it is a BTreeMap probe — then walks the tables newest first, and every table runs the same
routine from step 6: binary-search the sparse index for the block that could hold the key,
open the file, seek, read the block, walk and parse its records, and come back Missing.
The index search is memory and arithmetic. The rest is syscalls: an open, a seek, a read
per table per miss. On a store that has been running a while, misses are most of the traffic —
a cache that keys into it, a monitoring system probing for things that have not happened yet,
get on any key that was never written. Every one of those pays the disk round trip to hear
“no”.
A bloom filter trades a slice of memory for those syscalls. Per table it keeps a bit array and one promise: a key the filter rejects was never inserted into this table. The promise is one-sided. A key the filter accepts may still be absent — some keys it never saw probe bits that real keys set — and those false positives fall through to the normal lookup and come back empty, at the same cost as before. The filter only ever saves work; it cannot change an answer.
The filter
Section titled “The filter”The whole thing is a Vec<u8> of bits and three small functions. Each key is hashed once with
FNV-1a over 64 bits — the record checksum is that hash’s 32-bit cousin — and the two 32-bit
halves are mixed into seven probe positions with the Kirsch–Mitzenmacher double-hashing trick:
hash = fnv1a64(key) // one 64-bit hashh1 = (hash >> 32) as u32 // first halfh2 = (hash as u32) | 1 // second half, forced oddprobe i = (h1 + i * h2) % bit_len // for i in 0..7insert sets all seven bits. might_contain replays the same seven positions and reports
whether every one is set. That replay is the whole guarantee: the bits a key probes are the
bits its own insert set, so a key that is in the table can never come back “no”. Everything
else — the false positives — is statistics, and the next section measures it instead of
trusting it.
Two constants pin the size. BLOOM_BITS_PER_KEY is 10: each expected key buys ten bits of bit
array. BLOOM_HASHES is 7, which is 10 × ln 2 rounded — the probe count that makes ten bits
per key work hardest.
Three places the filter plugs in
Section titled “Three places the filter plugs in”Sstable::build allocates the filter up front — the map’s length is known before a byte is
written — and fills it as the records go out:
let mut filter = Bloom::for_keys(entries.len());for (i, (key, value)) in entries.iter().enumerate() { if i % BLOCK_RECORDS == 0 { index.push((key.clone(), offset)); } filter.insert(key); // ... frame and write the record}Sstable::load gets it for free. Loading a table already full-scans the file to rebuild the
sparse index and verify every checksum, and that scan visits every key — so the filter is
refilled on the way past, no extra read. A reopened store’s tables have live filters without
the filter ever touching the disk.
lookup is where it earns its keep, and it is one line ahead of everything else:
fn lookup(&self, key: &[u8]) -> io::Result<Answer> { if !self.filter.might_contain(key) { return Ok(Answer::Missing); } // ... partition_point, open the file, read the block}A rejected key ends the lookup before the index is touched — no binary search, no file opened.
A delete of a key that exists only in some older table runs through the same lookup, so it
skips the same reads.
Choosing the false-positive rate
Section titled “Choosing the false-positive rate”Ten bits per key is not a guess; it is the middle of a curve, and the curve is measurable. With
b bits per key and k = b × ln 2 probes, ideal random hashes give a false-positive rate of
(1 − e^(−k/b))^k — about 0.8% at b = 10. What that is worth in memory: a table of a million
keys costs ten million bits, about 1.2 MB of bit array, against a table file that holds those
million keys plus their values.
Formulae assume ideal hashes; the store has FNV-1a and double hashing, and your keys have whatever shape they have. So measure. The program below is the store’s filter with the bit budget as a parameter — the probe count derived from it the same way the store derives 7 from 10 — inserting ten thousand keys and probing ten thousand keys that were never inserted. It runs twice: once with counter-shaped keys like the ones in this track’s tests, once with random 8-byte keys that have no shape at all. The random source is a seeded xorshift64*, so the table comes out the same on your machine.
struct Bloom { bits: Vec<u8>, hashes: u32,}
impl Bloom { fn for_keys(keys: usize, bits_per_key: usize) -> Bloom { Bloom { bits: vec![0; (keys * bits_per_key).div_ceil(8)], // the optimum probe count for this many bits per key hashes: ((bits_per_key as f64) * std::f64::consts::LN_2).round() as u32, } }
fn insert(&mut self, key: &[u8]) { for index in probes(key, self.bits.len() * 8, self.hashes) { self.bits[index / 8] |= 1 << (index % 8); } }
fn might_contain(&self, key: &[u8]) -> bool { let len = self.bits.len() * 8; if len == 0 { return false; } probes(key, len, self.hashes).all(|index| self.bits[index / 8] & (1 << (index % 8)) != 0) }}
/// The same double-hashed probes the store uses: two 32-bit halves of/// one 64-bit FNV-1a, mixed as `h1 + i·h2`.fn probes(key: &[u8], bit_len: usize, hashes: u32) -> impl Iterator<Item = usize> { let hash = fnv1a64(key); let h1 = (hash >> 32) as u32; let h2 = hash as u32 | 1; (0..hashes).map(move |i| (h1.wrapping_add(i.wrapping_mul(h2)) as usize) % bit_len)}
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}
/// xorshift64*: enough randomness to shape keys with, and deterministic,/// so the table below comes out the same on your machine.struct Rng(u64);
impl Rng { fn next(&mut self) -> u64 { let mut x = self.0; x ^= x >> 12; x ^= x << 25; x ^= x >> 27; self.0 = x; x.wrapping_mul(0x2545_F491_4F6C_DD1D) }}
/// Insert ten thousand keys, probe ten thousand keys that were never/// inserted, and report how many came back as "might be in here".fn run_table(label: &str, member: impl Fn(usize) -> Vec<u8>, stranger: impl Fn(usize) -> Vec<u8>) { const KEYS: usize = 10_000; const STRANGERS: usize = 10_000;
println!("{label}"); println!( "{:>8} {:>6} {:>9} {:>9} {:>7}", "bits/key", "probes", "bytes", "falsepos", "rate" ); for bits_per_key in [4usize, 8, 10, 16] { let mut bloom = Bloom::for_keys(KEYS, bits_per_key); for i in 0..KEYS { bloom.insert(&member(i)); } let false_positives = (0..STRANGERS) .filter(|i| bloom.might_contain(&stranger(*i))) .count(); println!( "{bits_per_key:>8} {:>6} {:>9} {false_positives:>9} {:>6.2}%", bloom.hashes, bloom.bits.len(), false_positives as f64 / STRANGERS as f64 * 100.0, ); } println!();}
fn main() { // keys shaped like the store's: a short name and a counter run_table( "counter keys", |i| format!("key{i:05}").into_bytes(), |i| format!("absent{i:05}").into_bytes(), );
// keys with no shape at all: random 8-byte values let mut rng = Rng(0x1234_5678_9abc_def0); let members: Vec<Vec<u8>> = (0..10_000).map(|_| rng.next().to_le_bytes().to_vec()).collect(); let strangers: Vec<Vec<u8>> = (0..10_000).map(|_| rng.next().to_le_bytes().to_vec()).collect(); run_table( "random 8-byte keys", move |i| members[i].clone(), move |i| strangers[i].clone(), );}Run this in the Rust Playground
counter keysbits/key probes bytes falsepos rate 4 3 5000 975 9.75% 8 6 10000 170 1.70% 10 7 12500 63 0.63% 16 11 20000 2 0.02%
random 8-byte keysbits/key probes bytes falsepos rate 4 3 5000 1417 14.17% 8 6 10000 215 2.15% 10 7 12500 95 0.95% 16 11 20000 6 0.06%Read the random-key table against the formula. At 10 bits per key the measured rate is 0.95% where the ideal-hash figure says 0.8% — close enough that the choice holds up. At 4 bits it is 14%: one miss in seven still reads the block, and the filter is mostly decoration. At 16 bits it is 0.06%, and the bit array has doubled for the privilege.
The counter-key table is the honest surprise: 0.63% at the store’s parameters, lower than
theory — because ten thousand key names that differ only in their digits do not exercise the
hash evenly, and this particular shape happens to land luckily. Do not count on lucky. The
lesson is not “counter keys are fine”; it is that the rate depends on the keys as much as the
constants, and the only number worth engineering against is the one measured with keys shaped
like yours. The store pins 10 bits and 7 probes as BLOOM_BITS_PER_KEY and BLOOM_HASHES, and
a test holds them to it: ten thousand inserted keys, ten thousand absent probes, fewer than 200
false positives — double what the random-key run measured — or the test fails.
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::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.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) }
/// 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 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" ); }}What this does not fix
Section titled “What this does not fix”A false positive still pays for the block read; the filter buys cheap certainty on the “no”
side and nothing on the “yes” side. The memtable’s lookups are untouched — they were already
memory probes, and a filter in front of a BTreeMap would only slow them down. Opening the
store still full-scans every table to rebuild indexes and now filters, which is step 7’s
leftover cost and gets a look in step 10. And the filter lives in memory per table, next to its
index — 1.25 bytes per key across the store’s tables at this setting, which is the point.
See it run
Section titled “See it run”From the tinylsm directory:
cargo testrunning 40 teststest tests::a_filter_never_rejects_a_key_it_holds ... oktest tests::a_reopened_store_keeps_appending_cleanly ... oktest tests::a_miss_skips_the_table_file ... oktest tests::a_second_delete_after_a_flush_writes_nothing ... oktest tests::a_flush_truncates_the_log_in_place ... oktest tests::a_lookup_walks_the_tables_newest_first ... oktest tests::a_flush_writes_its_tombstones ... oktest tests::a_store_keeps_working_after_compaction ... oktest tests::a_lookup_after_a_reopen_uses_the_rebuilt_index ... oktest tests::a_temporary_file_left_by_a_crash_is_replaced ... oktest tests::a_tombstone_in_memory_shadows_the_tables ... oktest tests::compacting_an_empty_store_writes_nothing ... oktest tests::a_tombstone_survives_a_reopen ... oktest tests::an_overwrite_keeps_the_budget_honest ... oktest tests::compact_flushes_the_log_into_a_numbered_table ... oktest tests::compact_leaves_no_temporary_file_behind ... oktest tests::a_merge_keeps_tombstones ... oktest tests::a_tombstone_in_a_newer_table_shadows_an_older_one ... oktest tests::compact_writes_keys_in_sorted_order ... oktest tests::deleting_a_missing_key_writes_nothing ... oktest tests::get_missing_is_none ... oktest tests::delete_appends_a_tombstone ... oktest tests::a_leftover_table_cannot_resurrect_a_deleted_key ... oktest tests::delete_removes_and_reports ... oktest tests::open_a_missing_file_starts_empty ... oktest tests::keys_are_independent ... oktest tests::compaction_round_trips_through_a_reopen ... oktest tests::open_cuts_a_torn_tail ... oktest tests::open_refuses_a_corrupt_record ... oktest tests::open_replays_the_last_write ... oktest tests::open_replays_writes ... oktest tests::put_appends_one_record ... oktest tests::open_replays_tombstones ... oktest tests::put_overwrites ... oktest tests::put_then_get ... oktest tests::the_filter_stays_under_its_false_positive_budget ... 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. 40 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.85sYour run may list the tests in a different order — they run in parallel — and the timing line will differ. Thirty-six of these are steps 2 through 8’s, carried over unchanged; every one of them that looks up a missing key is now silently taking the filter’s fast path. The four new ones pin this step: a filter never rejects a key it holds, a miss completes without the table file even being present, false positives fall through to the block scan and still answer none, and the store’s parameters stay under their false-positive budget.
Where this lands in the repository
Section titled “Where this lands in the repository”This step’s state is tagged lsm-ch09 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/toy-databasegit checkout lsm-ch09The 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 10, Range scans and iterators, stops treating get as the whole read story. The keys in
every table are already sorted; this step walks a key range straight off the tables and the
memtable in order, and gives the store a real Iterator to do it with.