Compacting the log

Step 5 of 12, and the log learns to shrink. Step 4 ended with a store that recovers from a crash — and a file that only ever grows. A delete appends a tombstone and removes nothing; an overwrite appends a second record for a key the log already describes; reopening replays all of it, every time, forever. This step adds compact(), which rewrites the log down to what the map actually holds.

You are continuing from lsm-ch04 — the tinylsm crate whose open replays the log and cuts a torn tail. This step rewrites src/lib.rs in full and changes nothing else. Cargo.toml is untouched, still with no dependencies:

[package]
name = "tinylsm"
version = "0.1.0"
edition = "2024"

[dependencies]

What compaction keeps

A record earns its place in the log only until it has been applied to the map. After that, most of the file is history: the value an overwrite replaced, the key a tombstone deleted. Walk a short history through the format from steps 3 and 4 and count:

fn main() {
    let history = [
        (b'P', "alpha", Some("one")),
        (b'P', "alpha", Some("two")),
        (b'P', "beta", Some("two")),
        (b'D', "alpha", None),
    ];
    let mut total = 0;
    for (op, key, value) in history {
        let bytes = record(op, key.as_bytes(), value.map(str::as_bytes)).len();
        total += bytes;
        match value {
            Some(v) => println!("put    {key} = {v}: {bytes} bytes"),
            None => println!("delete {key}:      {bytes} bytes"),
        }
    }
    println!("the log: {total} bytes, for a map holding one key");
    let kept = record(b'P', b"beta", Some(b"two")).len();
    println!("after compaction: {kept} bytes, the one record that is still true");
}

/// The whole 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(op: u8, key: &[u8], value: Option<&[u8]>) -> Vec<u8> {
    let value = value.unwrap_or(&[]);
    let mut payload = vec![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);
    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
}

Run this in the Rust Playground

put    alpha = one: 25 bytes
put    alpha = two: 25 bytes
put    beta = two: 24 bytes
delete alpha:      22 bytes
the log: 96 bytes, for a map holding one key
after compaction: 24 bytes, the one record that is still true

Ninety-six bytes describe a map with one entry. Seventy-two of them — the first put, the last put, and the tombstone — say things that are no longer true. Compaction keeps exactly one record per live key: a put, in the map’s iteration order. Tombstones disappear entirely; the map is the authority on what exists, and a delete is an instruction the map already obeyed.

The whole file

This replaces src/lib.rs:

use std::collections::BTreeMap;
use std::fs::OpenOptions;
use std::io::{self, Read, Write};
use std::path::{Path, PathBuf};

/// A persistent key-value store: an append-only log on disk, indexed in
/// memory by a `BTreeMap`.
pub struct TinyLsm {
    map: BTreeMap<Vec<u8>, Vec<u8>>,
    path: PathBuf,
}

impl TinyLsm {
    /// Open the log at `path` and replay it: every whole record with a
    /// valid checksum rebuilds the index, and the file is cut back to the
    /// last whole record. A record that is complete but 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 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 map = BTreeMap::new();
        let valid = replay(&bytes, &mut map)?;
        log.set_len(valid as u64)?;
        Ok(TinyLsm { map, path })
    }

    /// 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.map.insert(key, value);
        Ok(())
    }

    /// Return the newest value for `key`, borrowed from the in-memory index.
    pub fn get(&self, key: &[u8]) -> Option<&[u8]> {
        self.map.get(key).map(Vec::as_slice)
    }

    /// Remove `key`, appending a tombstone when it existed. Returns whether
    /// it did — a delete of a missing key writes nothing to the log.
    pub fn delete(&mut self, key: &[u8]) -> io::Result<bool> {
        if self.map.get(key).is_none() {
            return Ok(false);
        }
        let payload = encode(b'D', key, None);
        append(&self.path, &payload)?;
        self.map.remove(key);
        Ok(true)
    }

    /// Rewrite the log down to what the map holds: one put record per live
    /// key, in key order, with no tombstones and no superseded values. The
    /// rewrite lands in a temporary file next to the log and is renamed
    /// over it, so a crash part way through leaves the old log intact.
    pub fn compact(&mut self) -> io::Result<()> {
        let tmp = self.path.with_extension("log.tmp");
        {
            let mut out = OpenOptions::new()
                .create(true)
                .write(true)
                .truncate(true)
                .open(&tmp)?;
            for (key, value) in &self.map {
                let payload = encode(b'P', key, Some(value));
                out.write_all(&frame(&payload))?;
            }
            out.sync_all()?;
        }
        std::fs::rename(&tmp, &self.path)
    }
}

/// 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 the rename in `compact`
/// 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 log byte by byte, applying each whole record to `map`, and
/// return the offset where the valid prefix ends. Everything after that
/// offset is a torn tail — a record a crash cut short — and the caller
/// truncates the file back to it.
fn replay(bytes: &[u8], map: &mut BTreeMap<Vec<u8>, Vec<u8>>) -> io::Result<usize> {
    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,
                "log is corrupt: record checksum mismatch",
            ));
        }
        apply(payload, map)?;
        rest = tail;
        pos += 8 + len;
    }
    Ok(pos)
}

/// Apply one record payload to the map: op byte, key, value. `Err` when the
/// payload is not shaped like an operation — with the checksum already
/// verified, that is a bug in the writer, not a damaged file.
fn apply(payload: &[u8], map: &mut BTreeMap<Vec<u8>, Vec<u8>>) -> io::Result<()> {
    let bad = |what: &str| {
        io::Error::new(
            io::ErrorKind::InvalidData,
            format!("log is corrupt: {what}"),
        )
    };
    let Some((&op, rest)) = payload.split_first() else {
        return Err(bad("empty payload"));
    };
    let Some((klen, rest)) = read_u32(rest) else {
        return Err(bad("no key length"));
    };
    let Some((key, rest)) = take(klen as usize, rest) else {
        return Err(bad("key runs past the payload"));
    };
    let Some((vlen, rest)) = read_u32(rest) else {
        return Err(bad("no value length"));
    };
    let Some((value, rest)) = take(vlen as usize, rest) else {
        return Err(bad("value runs past the payload"));
    };
    if !rest.is_empty() {
        return Err(bad("trailing bytes after the value"));
    }
    match op {
        b'P' => {
            map.insert(key.to_vec(), value.to_vec());
            Ok(())
        }
        b'D' => {
            map.remove(key);
            Ok(())
        }
        _ => Err(bad("unknown operation")),
    }
}

/// 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
    }

    fn cleanup(path: &Path) {
        let _ = std::fs::remove_file(path);
    }

    #[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"), Some(&b"one"[..]));
        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"), 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"), Some(&b"two"[..]));
        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"), 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"), Some(&b"two"[..]));
        store.delete(b"alpha").unwrap();
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        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"), Some(&b"one"[..]));
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        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"), Some(&b"two"[..]));
        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"), None);
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        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"), 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"), Some(&b"one"[..]));
        assert_eq!(store.get(b"beta"), 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"), Some(&b"two"[..]));
        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_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();
        let before = std::fs::read(&path).unwrap().len();

        store.compact().unwrap();
        let after = std::fs::read(&path).unwrap().len();

        assert!(after < before);
        // one record survives: beta's put, 8-byte header + 16-byte payload
        assert_eq!(after, 24);
        let store = TinyLsm::open(&path).unwrap();
        assert_eq!(store.get(b"alpha"), None);
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        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 rewritten file carries the first key in
        // the map's order, which is sorted
        let bytes = std::fs::read(&path).unwrap();
        let len = u32::from_le_bytes(bytes[..4].try_into().unwrap()) as usize;
        let payload = &bytes[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_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 on the new file, not the old one
        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"), Some(&b"three"[..]));
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        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();
        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 tmp = path.with_extension("log.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("log.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"), Some(&b"one"[..]));
        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"), Some(&b"three"[..]));
        assert_eq!(store.get(b"beta"), None);
        cleanup(&path);
    }
}

Four things in there deserve more than the doc comments give them.

The stored file handle is gone, on purpose. Step 4 kept the log’s File in the struct; this step stores the path instead, and append opens a fresh handle per write. The reason is the rename: a handle opened before a rename keeps pointing at the old file, so writes after a compaction would land in an orphaned copy and vanish on the next open — with no error anywhere. Opening per write removes the class of bug rather than dodging one instance of it. The cost is one extra open syscall per record, which is noise next to the flush every record already pays. Step 4’s argument for append mode still holds, only now it lives in append: every write opens with .append(true), so a record lands at the current end of the file no matter what any other handle did.

The rewrite is all-or-nothing. The naive way to compact is to truncate the log and write it back out. Crash between those halves and the store is gone — every key, not just the ones being reorganized. Instead, compact writes the surviving records to a temporary file beside the log (tinylsm.log becomes tinylsm.log.tmp), calls sync_all to push it to disk, and only then renames it over the original. The rename is atomic: a crash before it leaves the old log completely intact, and the half-written temp file is just clutter that the next compaction truncates and reuses. This is the same shape a real store uses for its own rewrites, and it costs three lines.

The compacted log comes out sorted. for (key, value) in &self.map walks a BTreeMap, and a BTreeMap walks in key order — so the rewritten file carries its records sorted by key without a single line of sorting code. That is a freebie right now and the whole idea in two steps: step 6, Introducing SSTables, promotes the sorted file from a compaction side effect to the primary structure on disk, with an index to match.

What compaction does not do. It never runs on its own — nothing calls it automatically, and a store that writes a million records between compactions still pays full replay on every open. Deciding when to compact is a policy question, and policy needs numbers first. And while the rename is atomic, its durability across a power cut is a separate per-OS story: a real database also fsyncs the directory after the rename. This toy stops at sync_all on the temp file, and says so rather than pretending otherwise.

See it run

From the tinylsm directory:

cargo test

running 22 tests
test tests::get_missing_is_none ... ok
test tests::a_reopened_store_keeps_appending_cleanly ... ok
test tests::delete_removes_and_reports ... ok
test tests::delete_appends_a_tombstone ... ok
test tests::deleting_a_missing_key_writes_nothing ... ok
test tests::keys_are_independent ... ok
test tests::open_a_missing_file_starts_empty ... ok
test tests::a_temporary_file_left_by_a_crash_is_replaced ... ok
test tests::a_store_keeps_working_after_compaction ... ok
test tests::open_cuts_a_torn_tail ... ok
test tests::compacting_an_empty_store_writes_nothing ... ok
test tests::open_refuses_a_corrupt_record ... ok
test tests::compact_leaves_no_temporary_file_behind ... ok
test tests::compact_drops_tombstones_and_superseded_values ... ok
test tests::open_replays_the_last_write ... ok
test tests::put_appends_one_record ... ok
test tests::open_replays_writes ... ok
test tests::open_replays_tombstones ... ok
test tests::compact_writes_keys_in_sorted_order ... ok
test tests::compaction_round_trips_through_a_reopen ... ok
test tests::put_then_get ... ok
test tests::put_overwrites ... ok

test result: ok. 22 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.02s

Your run may list the tests in a different order — they run in parallel. The fifteen tests steps 2 through 4 left behind pass unchanged: swapping the stored handle for a per-write open is invisible to every test that goes through the public API. The seven new ones pin compaction — the file shrinks to one record, keys come out in sorted order, writes after the rewrite land on the new file, and a temp file left behind by a crash is truncated and carried on from.

Where this lands in the repository

This step’s state is tagged lsm-ch05 in the examples repository:

git clone https://github.com/hackingwithrust/examples
cd examples/toy-database
git checkout lsm-ch05

The 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 6, Introducing SSTables, takes the hint the sorted rewrite just dropped. Right now compaction is something you ask for; the file is a sorted copy of an unsorted log, and lookups still walk the whole thing. Step 6 makes the sorted file the primary structure on disk — written sorted in the first place, with a sparse index so a lookup touches one page instead of the whole file — and the append-only log falls back to what it does best: absorbing writes fast.

Compacting the log

What compaction keeps

The whole file

See it run

Where this lands in the repository

Next