Introducing SSTables
Step 6 of 12, and the store grows a second file. Step 5 ended with a compaction that rewrites the log sorted — a side effect nobody was exploiting. This step promotes that sorted rewrite into a structure of its own: an SSTable, written sorted in the first place, with a sparse index that lets a lookup read one block instead of the whole file. The append-only log stops being the database and goes back to what it does best: absorbing writes fast.
You are continuing from lsm-ch05 — the tinylsm crate whose compact() rewrites the log in
place. 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]Two files, one memory table
Section titled “Two files, one memory table”A store now owns up to two files. The log keeps the path you gave open() — tinylsm.log,
say — and stays append-only. Beside it sits the table: same name, .sst extension
(tinylsm.sst), written only by compaction. A compaction in flight also owns a temporary
tinylsm.sst.tmp, which its rename removes. If your project is called something other than
tinylsm, your files carry that name instead — the extension is the part the code chooses.
Between them sits the in-memory table, and it changes in one visible way: values become
Option<Vec<u8>>, so the map of a live store is a BTreeMap<Vec<u8>, Option<Vec<u8>>>.
Some(value) is a live key; None is a tombstone. Tombstones are what keep deletes working
once the table exists. Put a key, compact it into the table, delete it — the table still holds
the old value, and something has to shadow it. That something is a None in memory, and it
survives until the next compaction erases the entry for real.
put reads the same as step 5: append the record to the log, then insert into memory. delete
still returns io::Result<bool>, but it has a new job — a key that lives only in the table has
to be looked up on disk before the delete can say whether it existed, and an existing one gets a
tombstone in the log. Deletes got more expensive; that is the table’s price, and the bloom-filter
step later in this track exists to shave it.
get changes signature, and the change is forced:
pub fn get(&self, key: &[u8]) -> io::Result<Option<Vec<u8>>>The newest value may live on disk now, so the call can fail — hence the Result — and it cannot
always borrow the answer from memory, hence the owned Vec. The lookup order: memory first, and
a hit answers the call; a tombstone in memory answers None without ever consulting the table;
only a key the memory table has never heard of goes to disk.
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;
/// A persistent key-value store in two files: an append-only log that/// absorbs writes, and a sorted table on disk that answers reads — plus/// the in-memory table of what the log holds that the disk table does not/// yet know about.pub struct TinyLsm { /// Newest writes. `Some(value)` is a live key; `None` is a tombstone /// that shadows an older copy of the key in the on-disk table. mem: BTreeMap<Vec<u8>, Option<Vec<u8>>>, /// Path of the append-only log, the store's write path. path: PathBuf, /// The sorted table on disk, present once the first compaction has run. table: Option<Sstable>,}
impl TinyLsm { /// Open the store at `path`: load the sorted table's sparse index, if a /// table exists, then replay the log on top of it. The log is newer /// than the table by construction — compaction empties the log the /// moment it folds its records into the table — so replaying it after /// loading the table 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. pub fn open(path: impl AsRef<Path>) -> io::Result<Self> { let path = path.as_ref().to_path_buf(); let table = Sstable::load(&table_path(&path))?; 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)?; Ok(TinyLsm { mem, path, table }) }
/// Insert or overwrite `key`. The write hits the log before the map. 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)); append(&self.path, &payload)?; self.mem.insert(key, Some(value)); Ok(()) }
/// Return the newest value for `key`. The in-memory table wins over the /// on-disk one, and a tombstone in memory shadows the table's older /// copy. Reading the table 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 => {} } match &self.table { Some(table) => table.lookup(key), None => Ok(None), } }
/// Remove `key`, appending a tombstone when the key exists — in memory /// or in the on-disk table. Returns whether it did. The tombstone is /// what keeps the table's older copy shadowed until the next compaction /// drops it, so a delete of a table-only key still writes to the log. pub fn delete(&mut self, key: &[u8]) -> io::Result<bool> { let live = match self.mem.get(key) { Some(live) => live.is_some(), None => match &self.table { Some(table) => table.lookup(key)?.is_some(), None => false, }, }; if !live { return Ok(false); } let payload = encode(b'D', key, None); append(&self.path, &payload)?; self.mem.insert(key.to_vec(), None); Ok(true) }
/// Fold the log and the old table into a new table — one put record per /// live key, in key order, tombstones gone — then empty the log. The new /// table lands through a temporary file and a rename, so a crash part /// way through leaves the old table and the log exactly as they were. pub fn compact(&mut self) -> io::Result<()> { let mut merged: BTreeMap<Vec<u8>, Vec<u8>> = BTreeMap::new(); if let Some(table) = &self.table { // Compaction is the one reader allowed to walk the whole table: // it is about to rewrite all of it anyway. let bytes = std::fs::read(&table.path)?; for (_, payload) in walk(&bytes)? { if let Some((b'P', key, value)) = parse(payload) { merged.insert(key.to_vec(), value.to_vec()); } } } for (key, value) in &self.mem { match value { Some(value) => { merged.insert(key.clone(), value.clone()); } None => { // a tombstone erases the table's older copy merged.remove(key); } } } self.table = Some(Sstable::build(&table_path(&self.path), &merged)?); File::create(&self.path)?; // the table has absorbed the log: empty it self.mem.clear(); Ok(()) }}
/// The sorted table that belongs to a log at `log`: `store.log` keeps its/// records in `store.sst`.fn table_path(log: &Path) -> PathBuf { log.with_extension("sst")}
/// A sorted table on disk: the framed records from steps 3 and 4, 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 { path: PathBuf, index: Vec<(Vec<u8>, u64)>,}
impl Sstable { /// Load the sparse index for the table at `path`, or `None` when no /// table exists yet. 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) -> io::Result<Option<Sstable>> { let bytes = match std::fs::read(path) { Ok(bytes) => bytes, Err(e) if e.kind() == io::ErrorKind::NotFound => return Ok(None), Err(e) => return Err(e), }; 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(Some(Sstable { path: path.to_path_buf(), index, })) }
/// Value for `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<Option<Vec<u8>>> { let block = self.index.partition_point(|(k, _)| k.as_slice() <= key); if block == 0 { return Ok(None); // 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((_, found, value)) = parse(payload) else { return Err(io::Error::new( io::ErrorKind::InvalidData, "table is corrupt: unreadable record", )); }; match found.cmp(key) { Ordering::Equal => return Ok(Some(value.to_vec())), Ordering::Greater => return Ok(None), Ordering::Less => {} } } Ok(None) }
/// Write `entries` as a new table at `path`, atomically: the records go /// to a temporary file that is fsynced and renamed over `path` once the /// last one lands. 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, entries: &BTreeMap<Vec<u8>, Vec<u8>>) -> io::Result<Sstable> { let tmp = path.with_extension("sst.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 record = frame(&encode(b'P', key, Some(value))); out.write_all(&record)?; offset += record.len() as u64; } out.sync_all()?; } std::fs::rename(&tmp, path)?; Ok(Sstable { path: path.to_path_buf(), index, }) }}
/// Frame one payload as a record and append it to the log at `path`. The/// handle is opened per call: one extra `open` per write is noise next to/// the flush, and it keeps no handle alive that a rename could orphan.fn append(path: &Path, payload: &[u8]) -> io::Result<()> { let mut log = OpenOptions::new().append(true).open(path)?; log.write_all(&frame(payload))?; log.flush()}
/// 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 table 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 path per test: the tests in this module run in /// parallel, and a shared path would have them overwriting each other. fn temp_log(name: &str) -> PathBuf { let mut path = std::env::temp_dir(); path.push(format!("tinylsm-{}-{}.log", name, std::process::id())); path }
/// A store now lives in up to three files: the log, the sorted table /// beside it, and the table's temporary file mid-compaction. fn cleanup(path: &Path) { let _ = std::fs::remove_file(path); let _ = std::fs::remove_file(path.with_extension("sst")); let _ = std::fs::remove_file(path.with_extension("sst.tmp")); }
#[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_empties_the_log_and_fills_the_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 table beside it holds both records, // 25 + 24 bytes in the step 3 format assert_eq!(std::fs::read(&path).unwrap().len(), 0); let table = std::fs::read(path.with_extension("sst")).unwrap(); assert_eq!(table.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 compact_drops_tombstones_and_superseded_values() { let path = temp_log("compact-shrinks"); 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();
// one record survives: beta's put, 8-byte header + 16-byte payload let table = std::fs::read(path.with_extension("sst")).unwrap(); assert_eq!(table.len(), 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 table = std::fs::read(path.with_extension("sst")).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_table() { 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 the 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 compaction_erases_what_a_tombstone_points_at() { let path = temp_log("compact-erase"); let mut store = TinyLsm::open(&path).unwrap(); store.put(b"alpha", b"one").unwrap(); store.put(b"beta", b"two").unwrap(); store.compact().unwrap(); store.delete(b"alpha").unwrap(); store.compact().unwrap();
// the tombstone removes alpha from the merged table: beta's put, // 24 bytes, and nothing else let table = std::fs::read(path.with_extension("sst")).unwrap(); assert_eq!(table.len(), 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 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 rewrite 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_an_empty_table() { let path = temp_log("compact-empty"); let mut store = TinyLsm::open(&path).unwrap(); store.compact().unwrap(); assert_eq!(std::fs::read(&path).unwrap().len(), 0); assert_eq!(std::fs::read(path.with_extension("sst")).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 tmp = path.with_extension("sst.tmp"); assert!(!tmp.exists()); 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-compaction leaves a half-written temp file behind; // the next compaction truncates it and carries on let tmp = path.with_extension("sst.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("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); }}Four things in there deserve more than the doc comments give them.
One walker, two readers. Steps 3 through 5 had one loop that walked the log frame by frame.
Now both files need walking — the log on open, the table on load — so the loop became walk(),
which returns each record’s offset and payload, stops at a torn tail, and turns a failed
checksum into an error. replay() feeds everything it returns to apply(); Sstable::load()
keeps every fourth record for the index and requires the walk to reach the end of the file.
The torn-tail rule is different per file, on purpose. A torn tail in the log is normal: the
last write can be interrupted mid-flight, so open cuts the file back to the last whole record
and carries on. A torn tail in the table is not: the table is installed by a rename, so it is
never caught mid-write. Records that stop short of the end of the file mean damage, and load
refuses the open with InvalidData rather than quietly dropping the tail.
A delete no longer removes its key. In the map-only store, apply answered a delete with
map.remove(key). Here that would be wrong the moment a table exists: remove the key from
memory and the next get falls through to the table and resurfaces the old value. So a delete
stores a tombstone, and the tombstone — not the absence — is what the lookup order respects.
Compaction’s order of operations is load-bearing. It reads the old table, overlays the
memory table (Some inserts, None removes), writes the merged map to tinylsm.sst.tmp,
fsyncs it, renames it over the old table — and only then truncates the log and clears memory.
The order matters. Rename first, truncate second: a crash between the two leaves a new table
and a log whose records are already in it, and replaying those records over the table produces
the same state twice. Truncate first and a crash before the rename loses every record since the
last compaction. The rename also means the whole rewrite stays all-or-nothing, same as step 5.
The sparse index
Section titled “The sparse index”The table is the same framed records steps 3 and 4 defined, written in BTreeMap iteration
order — which is key order. Sortedness is what makes the index cheap: you don’t need one entry
per record, only one per block. BLOCK_RECORDS, a constant at the top of the file, says every
fourth record’s key and offset goes into the index.
Six records make the geometry visible:
const BLOCK_RECORDS: usize = 4;
fn main() { let entries = [ ("alpha", "one"), ("beta", "two"), ("gamma", "three"), ("delta", "four"), ("echo", "five"), ("fox", "six"), ]; let mut index = Vec::new(); let mut offset = 0u64; for (i, (key, value)) in entries.iter().enumerate() { if i % BLOCK_RECORDS == 0 { index.push((*key, offset)); } offset += record(key.as_bytes(), value.as_bytes()).len() as u64; } for (key, at) in &index { println!("indexed {key} at offset {at}"); } let total = offset; println!("the table is {total} bytes in {} records", entries.len()); // a lookup for fox lands in the block starting at echo; the read runs // from that offset to the end of the file let start = index.last().unwrap().1; println!("a lookup for fox reads {} bytes, not {total}", total - start);}
/// The record format from steps 3 and 4: a length, a checksum, and a/// payload of op byte, key length, key, value length, value.fn record(key: &[u8], value: &[u8]) -> Vec<u8> { let mut payload = vec![b'P']; 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); let mut hash: u32 = 0x811c_9dc5; for &byte in &payload { hash ^= u32::from(byte); hash = hash.wrapping_mul(0x0100_0193); } let mut r = (payload.len() as u32).to_le_bytes().to_vec(); r.extend_from_slice(&hash.to_le_bytes()); r.extend_from_slice(&payload); r}indexed alpha at offset 0indexed echo at offset 102the table is 150 bytes in 6 recordsa lookup for fox reads 48 bytes, not 150The index holds two of the six keys. A lookup for fox binary-searches those two keys, lands in
the block starting at echo, and reads 48 bytes instead of 150. The block boundaries come from
the index too: the block ends where the next indexed key starts, or at the end of the file for
the last block, so the read is seek to the block’s start, then take(end - start).read_to_end.
In code the binary search is one call: index.partition_point(|(k, _)| k.as_slice() <= key)
counts the indexed keys less than or equal to the lookup key, and the block to search starts at
the last of them. A count of zero means the key sorts before the table’s smallest key — the
first indexed key is the first record — and the answer is None without reading anything. The
scan inside the block stops at the first key greater than the one you asked for, which is the
sortedness paying off a second time: past it, the key is not in the table.
One honest cost: Sstable::load rebuilds the index by scanning the whole table, checksums and
all, on every open. A real store writes the index into a footer at the end of the file so open
reads a few hundred bytes instead of the whole file. This toy rescans and says so — the win it
is buying is at lookup time, not open time.
What this does not fix
Section titled “What this does not fix”Open still touches every byte: the table scan for the index, then the log replay on top. Get clones the value on a memory hit — the owned return type forces it. And compaction still reads everything it rewrites. None of that is a bug; all of it is the next few steps’ material.
See it run
Section titled “See it run”From the tinylsm directory:
cargo testrunning 28 teststest tests::a_reopened_store_keeps_appending_cleanly ... oktest tests::compact_leaves_no_temporary_file_behind ... oktest tests::compact_empties_the_log_and_fills_the_table ... oktest tests::a_temporary_file_left_by_a_crash_is_replaced ... oktest tests::a_tombstone_survives_a_reopen ... oktest tests::a_store_keeps_working_after_compaction ... oktest tests::compacting_an_empty_store_writes_an_empty_table ... oktest tests::compact_writes_keys_in_sorted_order ... oktest tests::a_tombstone_in_memory_shadows_the_table ... oktest tests::delete_removes_and_reports ... oktest tests::a_lookup_after_a_reopen_uses_the_rebuilt_index ... oktest tests::get_missing_is_none ... oktest tests::deleting_a_missing_key_writes_nothing ... oktest tests::keys_are_independent ... oktest tests::delete_appends_a_tombstone ... oktest tests::compact_drops_tombstones_and_superseded_values ... oktest tests::compaction_round_trips_through_a_reopen ... oktest tests::open_refuses_a_corrupt_record ... oktest tests::put_overwrites ... oktest tests::open_replays_tombstones ... oktest tests::put_then_get ... oktest tests::open_replays_writes ... oktest tests::compaction_erases_what_a_tombstone_points_at ... oktest tests::open_replays_the_last_write ... oktest tests::open_cuts_a_torn_tail ... oktest tests::put_appends_one_record ... oktest tests::reopen_refuses_a_truncated_table ... ok
test result: ok. 28 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.05sYour run may list the tests in a different order — they run in parallel — and the timing line
will differ. Twenty-two of these are steps 2 through 5’s tests, adapted to the new get
signature and asserting the same behaviour through the public API. The six new ones pin this
step: the log drains into the table, a tombstone in memory shadows a table entry and survives a
reopen, compaction erases what a tombstone points at, a lookup works through an index rebuilt
from disk, and a truncated table is refused instead of trusted.
Where this lands in the repository
Section titled “Where this lands in the repository”This step’s state is tagged lsm-ch06 in
the examples repository:
git clone https://github.com/hackingwithrust/examplescd examples/toy-databasegit checkout lsm-ch06The 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 7, Merging SSTables, drops the part of compaction you should now find suspicious: it reads the whole table and rewrites everything, every time. Writes will start piling up as several tables — each sorted, each with its own index — and a lookup will walk them newest first. Then tombstones get interesting, because a delete can no longer erase its key from a file that stays; it has to outlive it and travel through the merge.