Appending writes to a log

Step 3 of 12, and the store starts touching a disk. The step 2 store held everything in one BTreeMap and nowhere else — kill the process and the data is gone. Here, every put and every delete appends a record to a file before the map hears about it, and each record carries a checksum. The map stops being the store and becomes an index over the log. What the log cannot do yet is refill the map: reopening starts from empty, and this page ends by showing exactly why that is step 4’s problem.

You are continuing from lsm-ch02 — the tinylsm crate with put, get, delete over a BTreeMap. This step rewrites src/lib.rs in full and changes nothing else; Cargo.toml still has no dependencies:

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

[dependencies]

What one write looks like on disk

The obvious format is one line of text per write — PUT alpha one\n — and it is wrong before you start. Keys in this store are bytes, not strings, and a key is allowed to contain a newline. The log has to be byte-exact, so the format is binary and length-prefixed.

Each write becomes one record:

bytes	field
4	payload length, little-endian
4	checksum of the payload, little-endian
rest	the payload

The payload itself is the operation, then the key and value, each with a 4-byte length:

bytes	field
1	operation: P for put, D for delete
4	key length
n	key
4	value length (0 for a delete)
n	value

Two headers, two different jobs. The payload length says where the record ends — if the process dies halfway through a write, the file ends with a short tail you can spot instead of garbage you read as data. The checksum says whether the bytes you read are the bytes that were written. Neither is optional in a log that is about to be trusted.

Here is the record that put(b"alpha", b"one") produces, byte by byte:

fn main() {
    // the payload for put(b"alpha", b"one"): op, klen, key, vlen, value
    let mut payload = Vec::new();
    payload.push(b'P');
    payload.extend_from_slice(&5u32.to_le_bytes());
    payload.extend_from_slice(b"alpha");
    payload.extend_from_slice(&3u32.to_le_bytes());
    payload.extend_from_slice(b"one");

    let mut record = Vec::new();
    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);

    let hex: Vec<String> = record.iter().map(|b| format!("{:02x}", b)).collect();
    println!("{}", hex.join(" "));
}

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
}

▶Run this in the Rust Playground

11 00 00 00 2b 18 09 69 50 05 00 00 00 61 6c 70 68 61 03 00 00 00 6f 6e 65

Twenty-five bytes. 11 00 00 00 is the payload length: 17. 2b 18 09 69 is the checksum, little-endian for 0x6909182b. Then the payload: 50 is P, 05 00 00 00 a five-byte key, 61 6c 70 68 61 is alpha, 03 00 00 00 a three-byte value, 6f 6e 65 is one.

The checksum is FNV-1a, 32-bit — the whole implementation is the checksum function above. It is not cryptographic and not collision-proof; it is three lines, deterministic, and good enough to catch a torn or corrupted record on the way back in. Engines that mean it use CRC32 — step 4 reaches for the crc32fast crate once the log starts being read back. This step stays dependency-free.

The whole file

This replaces src/lib.rs:

src/lib.rs

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

/// 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>>,
    log: std::fs::File,
}

impl TinyLsm {
    /// Open the log at `path` and start from an empty state.
    ///
    /// The file is truncated: this step has no recovery yet, so reopening a
    /// store discards what the previous one wrote. Step 4 replaces this.
    pub fn new(path: impl AsRef<Path>) -> io::Result<Self> {
        let log = OpenOptions::new()
            .create(true)
            .write(true)
            .truncate(true)
            .open(path)?;
        Ok(TinyLsm {
            map: BTreeMap::new(),
            log,
        })
    }

    /// 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));
        self.append(&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);
        self.append(&payload)?;
        self.map.remove(key);
        Ok(true)
    }

    /// Frame one payload as a record and append it to the log.
    fn append(&mut self, payload: &[u8]) -> io::Result<()> {
        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);
        self.log.write_all(&record)?;
        self.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
}

#[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::new(&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::new(&path).unwrap();
        assert_eq!(store.get(b"nope"), None);
        cleanup(&path);
    }

    #[test]
    fn put_overwrites() {
        let path = temp_log("overwrite");
        let mut store = TinyLsm::new(&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::new(&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::new(&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::new(&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::new(&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::new(&path).unwrap();
        assert!(!store.delete(b"ghost").unwrap());
        assert_eq!(std::fs::read(&path).unwrap().len(), 0);
        cleanup(&path);
    }

    #[test]
    fn reopening_starts_empty() {
        let path = temp_log("reopen");
        {
            let mut store = TinyLsm::new(&path).unwrap();
            store.put(b"alpha", b"one").unwrap();
        }
        let store = TinyLsm::new(&path).unwrap();
        assert_eq!(store.get(b"alpha"), None);
        cleanup(&path);
    }
}

Three things in there deserve a sentence each.

Log first, map second. put and delete both call self.append(...)? before touching the map. If the order were reversed, a failed append would leave an index that claims data the log never received. With append-first, a failed write changes nothing the file disagrees with.

One write_all per record. The header and payload are framed into a single Vec and handed to write_all once, then flushed. That does not make the write atomic — a crash can still land in the middle — but it means the only two states a record can be in are whole and a prefix of itself, which is exactly what the payload-length header is for. Note also what flush is and isn’t: it hands the bytes to the operating system, not to the platter. A real engine calls sync_data on every write and pays for it; that trade-off is a step of its own later.

A delete of a missing key writes nothing. delete checks the map first and returns false without a tombstone when the key isn’t there. A tombstone for a key that does not exist would replay to nothing in step 4 anyway — writing it would only be noise in the file.

Two signatures had to change

Step 2 ended by promising the three method signatures would stay put while their bodies changed. That promise mostly holds — get is untouched, and the parameter lists of put and delete did not move — but two return types did:

• put now returns io::Result<()>, because writing to a file can fail.
• delete now returns io::Result<bool>: did the key exist, and did the tombstone land.
• new takes the log’s path and returns io::Result<Self>, because opening a file can fail too.

This is the overview’s own rule doing its job: step 1 said storage fails in I/O ways — a missing directory, a full disk — and none of those may end in a panic. The moment put touches a file it needs somewhere to put the failure, and Result is that place. In the tests above the failure path is .unwrap(); in a real caller it is ?. If the distinction is fuzzy, the error handling chapters cover both.

Reopening throws everything away

new opens the log with truncate(true). The reopening_starts_empty test pins the behaviour: put a key, drop the store, open the same path again — get returns None, and the file is empty.

For tests that is convenient. For a database it is disqualifying, and it is not an oversight: the store cannot read its own log back yet. Reading it means walking the records, checking each checksum, rebuilding the map, and deciding what to do when the file ends mid-record — the torn tail the payload-length header exists to expose. That is step 4, Replaying the log on startup, and it turns new into a real open: recovery, not a fresh start.

See it run

From the tinylsm directory:

cargo test

running 9 tests
test tests::delete_appends_a_tombstone ... ok
test tests::deleting_a_missing_key_writes_nothing ... ok
test tests::delete_removes_and_reports ... ok
test tests::get_missing_is_none ... ok
test tests::keys_are_independent ... ok
test tests::put_appends_one_record ... ok
test tests::put_overwrites ... ok
test tests::put_then_get ... ok
test tests::reopening_starts_empty ... ok

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

The five step 2 tests still pass, now going through the log on every write, and four new ones pin the file format itself.

To see the bytes, drop a throwaway example into the crate as examples/make-log.rs — it compiles against tinylsm itself, so it is shown as plain text rather than a checked block:

examples/make-log.rs

use tinylsm::TinyLsm;

fn main() {
    let mut store = TinyLsm::new("/tmp/tinylsm-demo.log").unwrap();
    store.put(b"alpha", b"one").unwrap();
    store.put(b"beta", b"two").unwrap();
    store.delete(b"alpha").unwrap();
}

Run it with cargo run --example make-log, then look at the file:

xxd /tmp/tinylsm-demo.log

00000000: 1100 0000 2b18 0969 5005 0000 0061 6c70  ....+..iP....alp
00000010: 6861 0300 0000 6f6e 6510 0000 0010 0257  ha....one......W
00000020: 7050 0400 0000 6265 7461 0300 0000 7477  pP....beta....tw
00000030: 6f0e 0000 002e ee12 a544 0500 0000 616c  o........D....al
00000040: 7068 6100 0000 00                        pha....

Seventy-one bytes: the alpha put (25), the beta put (24), the alpha tombstone (22). The third record starts at offset 0x31 with 0e 00 00 00 — a 14-byte payload — then checksum 2e ee 12 a5, then 44, which is D, then the five-byte key alpha and a value length of zero. That zero length is what makes a delete record distinguishable from a put with an empty value.

Where this lands in the repository

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

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

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.

Next

Step 4, Replaying the log on startup, makes the file mean something across restarts: opening reads every record, verifies each checksum, rebuilds the map, and stops cleanly at a torn tail left by a crash. The format above is the contract it reads — same bytes, finally read back.