A write-ahead log and a memtable
Step 8 of 12, and the write path gets the two parts its name implies. Step 7 left a write path
that opened the log per call, wrote one framed record, flushed a handle that had nothing to
flush, and dropped it — and a store that only reached for the disk when the caller remembered
compact(). This step gives the log its proper job title. It is a write-ahead log now: a file
handle that stays open for the store’s life, a sync policy you can state in one sentence, and a
memory table with a byte budget that flushes itself when a write crosses the line.
You are continuing from lsm-ch07 — the tinylsm crate with numbered tables that merge four at
a time. 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 after this step:
mem: BTreeMap<Vec<u8>, Option<Vec<u8>>>, // newest writes, tombstones includedmem_bytes: usize, // the memtable's byte costlog: File, // the WAL, kept openpath: PathBuf, // the log's pathtables: Vec<Sstable>, // newest firstThe handle that stays open
Section titled “The handle that stays open”Step 5 gave the store a path instead of a handle because compaction back then rewrote files by
rename, and a handle held across a rename keeps writing into the orphaned old file — no error,
just bytes going nowhere. Step 6 stopped renaming the log: a flush truncates it in place. That
makes the log the one file in the store a handle is safe on, and this step cashes it in — one
open() when the store opens, none per write.
The per-write path it replaces also carried a small lie. A File has no userspace buffer:
write_all hands the bytes to the operating system directly, so the log.flush() the old
append function called did nothing. There was nothing to flush. It reads like durability and
isn’t. This step replaces it with something that is.
A sync policy you can state in one sentence
Section titled “A sync policy you can state in one sentence”After write_all returns, the record sits in the kernel’s page cache — safe against the
process crashing, not against the machine losing power. What this store does about it fits in
one sentence: every write is synced to disk before put or delete returns.
self.log.write_all(&frame(&payload))?; // bytes reach the page cacheself.log.sync_all()?; // bytes reach the disksync_all, not sync_data: a record’s length lives in the file’s metadata, and a record whose
length the crash forgot is a record the replay cannot find. sync_data skips metadata, and on
some platforms an appended record synced with it may not survive a power cut. The full sync
costs a round trip to the drive on every write — the slowest policy a WAL can have, and the
reason real stores group-commit, folding many writers’ records into one fsync. The toy takes
the slow policy because it can be stated without footnotes.
No test here can pull the power cord, so the durability guarantee is argued rather than pinned.
What the tests do pin is the ordering: the record is in the file before the memtable learns of
it, and a put that returns has already synced.
A budget for the memtable
Section titled “A budget for the memtable”Step 7’s flush fired when the caller called compact(). This step’s fires when the memory
table is full. The store tracks its own appetite: mem_bytes, the key and value lengths of
every entry added up — a tombstone costs its key and nothing else. Every write updates the
count and then asks maybe_flush, which runs compact() the moment the budget is crossed:
fn maybe_flush(&mut self) -> io::Result<()> { if self.mem_bytes >= MEMTABLE_BYTES { self.compact()?; } Ok(())}compact() itself keeps step 7’s two moves — flush the memory table into the next numbered
table, then merge when four tables have piled up — so the write path and the manual trigger
share one code path. The flush empties the log through the kept handle now: set_len(0), and
because the handle is in append mode, the next record lands at offset 0. No hole where the
flushed records used to be — a test pins that.
The accounting has one trap worth naming. BTreeMap::insert returns the value it displaced,
wrapped in an Option — and the stored value here is itself an Option<Vec<u8>>, so the
return type is Option<Option<Vec<u8>>>. The outer None means no entry was displaced and
costs nothing; the inner None means the displaced entry was a tombstone and costs its key.
Conflating the two makes every fresh key cheaper than it is and the budget leaks downward —
4096 bytes of budget would hold 64 fresh keys instead of 58. A test pins this too: overwrite a
5000-byte value with a 4-byte one and the store must not flush again.
The arithmetic in miniature — a 12-byte budget, four writes, key and value lengths added up the way the store does it:
fn main() { const MEMTABLE_BYTES: usize = 12;
let writes = [ ("alpha", "one"), ("beta", "two"), ("gamma", "three"), ("delta", "four"), ]; let mut mem_bytes = 0usize; let mut tables = 0usize; for (key, value) in writes { mem_bytes += key.len() + value.len(); if mem_bytes >= MEMTABLE_BYTES { tables += 1; println!("{key}: {mem_bytes} bytes in the memtable — flush as table {tables}"); mem_bytes = 0; } else { println!("{key}: {mem_bytes} bytes in the memtable, staying put"); } } println!("{tables} tables written, {mem_bytes} bytes left in the memtable");}Run this in the Rust Playground
alpha: 8 bytes in the memtable, staying putbeta: 15 bytes in the memtable — flush as table 1gamma: 10 bytes in the memtable, staying putdelta: 19 bytes in the memtable — flush as table 22 tables written, 0 bytes left in the memtableThe write that crosses the line pays for the flush — one table build, one rename, one
truncation, folded into a put. Amortised over the writes that led there, a flush costs what
the memtable held, nothing like step 6’s rewrite-the-world. And a flush can wait for nobody:
there is no background thread, so the unlucky write runs the whole compaction inline.
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;
/// 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.struct Sstable { /// This table's number, the `1` in `tinylsm.1.sst`. Higher is newer. number: u64, path: PathBuf, index: Vec<(Vec<u8>, u64)>,}
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(); for (i, (pos, payload)) in records.iter().enumerate() { if i % BLOCK_RECORDS == 0 { let Some((_, key, _)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); }; index.push((key.to_vec(), *pos as u64)); } } Ok(Sstable { number, path: path.to_path_buf(), index, }) }
/// What this table knows about `key`, through the sparse index: /// binary-search the index for the block that could hold the key, /// read that block, and scan it. The scan stops 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> { 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 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)); } 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, }) }}
/// 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); }}What this does not fix
Section titled “What this does not fix”The sync policy is honest and slow: a put in a loop spends its life waiting for the drive,
and the fix — batching several records into one fsync — changes the durability story to “the
last few writes may be lost”, which deserves a step of its own. The budget counts payload
bytes only: the 8 bytes of framing and the length prefixes are invisible to it, so the real
memtable footprint is a few percent larger than mem_bytes claims. Open still full-scans
every table to rebuild its index, step 7’s leftover. And get still clones a value on a
memory hit.
See it run
Section titled “See it run”From the tinylsm directory:
cargo testrunning 36 teststest tests::a_reopened_store_keeps_appending_cleanly ... oktest tests::a_second_delete_after_a_flush_writes_nothing ... oktest tests::a_flush_truncates_the_log_in_place ... oktest tests::a_temporary_file_left_by_a_crash_is_replaced ... oktest tests::a_flush_writes_its_tombstones ... oktest tests::a_store_keeps_working_after_compaction ... oktest tests::a_lookup_walks_the_tables_newest_first ... oktest tests::a_tombstone_in_memory_shadows_the_tables ... oktest tests::a_lookup_after_a_reopen_uses_the_rebuilt_index ... oktest tests::a_tombstone_survives_a_reopen ... oktest tests::compact_leaves_no_temporary_file_behind ... oktest tests::compacting_an_empty_store_writes_nothing ... oktest tests::a_tombstone_in_a_newer_table_shadows_an_older_one ... oktest tests::an_overwrite_keeps_the_budget_honest ... oktest tests::compact_flushes_the_log_into_a_numbered_table ... oktest tests::deleting_a_missing_key_writes_nothing ... oktest tests::compact_writes_keys_in_sorted_order ... oktest tests::delete_appends_a_tombstone ... oktest tests::get_missing_is_none ... oktest tests::open_a_missing_file_starts_empty ... oktest tests::delete_removes_and_reports ... oktest tests::keys_are_independent ... oktest tests::compaction_round_trips_through_a_reopen ... oktest tests::a_leftover_table_cannot_resurrect_a_deleted_key ... oktest tests::a_merge_keeps_tombstones ... oktest tests::open_replays_the_last_write ... oktest tests::open_replays_writes ... oktest tests::put_appends_one_record ... oktest tests::open_cuts_a_torn_tail ... oktest tests::put_overwrites ... oktest tests::open_refuses_a_corrupt_record ... oktest tests::open_replays_tombstones ... oktest tests::put_then_get ... 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 ... ok
test result: ok. 36 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.41sYour run may list the tests in a different order — they run in parallel — and the timing line will differ. Thirty-three of these are steps 2 through 7’s, carried over unchanged; their writes total a few hundred bytes, so the budget never fires in them. The three new ones pin this step: a memtable that fills itself flushes without being told, a flush truncates the log in place so the next write starts at offset zero, and an overwrite that swaps a big value for a small one keeps the budget honest.
Where this lands in the repository
Section titled “Where this lands in the repository”This step’s state is tagged lsm-ch08 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/toy-databasegit checkout lsm-ch08The 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 9, Bloom filters to skip disk reads, picks at the cost a miss pays. Right now a key that isn’t anywhere costs a block read per table — every table on disk gets touched just to say no. A bloom filter per table turns most of those reads into a bit test in memory, and the step runs the false-positive experiment that says whether the filter earns its keep.