A key-value store in memory

Step 2 of 12, and the store starts working. By the end of this page you have a library crate called tinylsm with a three-method interface — put, get, delete — backed by a BTreeMap that holds everything in memory. Nothing touches a disk yet, and that is deliberate: the next ten steps change what sits underneath this interface, and the interface itself stays put. Fixing it now is what lets each later step land without breaking the one before it.

The starting state is an empty directory — step 1 committed no code. If you would rather start from the finished version of this step, clone the examples repository and git checkout lsm-ch02; that is shown at the end.

Create the crate

cargo new --lib tinylsm
cd tinylsm

--lib makes a library crate: something other code links against, not a program to run. That is what a storage engine is, and it shapes how this track checks itself — a library has no main to print things, so the way you drive it is cargo test. Nearly every step from here on verifies with plain cargo test, no crates installed, nothing networked.

Cargo generates one manifest:

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

[dependencies]

The track is written and tested against Rust 1.99.0, where edition 2024 is the default a current toolchain writes — so this file is probably already what you have.

The interface

Three methods, chosen so the rest of the track can live behind them:

put(key, value) — insert, or overwrite if the key is already there.
get(key) -> Option<&[u8]> — the newest value for a key, or None.
delete(key) -> bool — remove a key, reporting whether it existed.

Both keys and values are bytes: Vec<u8> owned by the store, &[u8] on the way in. A database does not know or care that your keys were strings, and String would rule out keys that are not UTF-8 — a hash, a binary id. The cost is one piece of ceremony you will meet below: b"alpha" is a &[u8; 5], not a &[u8], and the two are not interchangeable where the map is concerned.

put takes impl Into<Vec<u8>> on both sides so the caller never writes .to_vec() by hand — b"alpha" and "alpha" both work. get returns a slice borrowed from the store, not a copy; what that costs you is the next section.

The whole file

This is src/lib.rs in full, and it is the entire implementation:

use std::collections::BTreeMap;

/// An in-memory key-value store. The interface every later step of the
/// track keeps; what sits underneath it changes from here on.
pub struct TinyLsm {
    map: BTreeMap<Vec<u8>, Vec<u8>>,
}

impl TinyLsm {
    pub fn new() -> Self {
        TinyLsm {
            map: BTreeMap::new(),
        }
    }

    /// Insert or overwrite `key`. Both sides are stored as owned bytes.
    pub fn put(&mut self, key: impl Into<Vec<u8>>, value: impl Into<Vec<u8>>) {
        self.map.insert(key.into(), value.into());
    }

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

    /// Remove `key`. Returns true when the key existed.
    pub fn delete(&mut self, key: &[u8]) -> bool {
        self.map.remove(key).is_some()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn put_then_get() {
        let mut store = TinyLsm::new();
        store.put(b"alpha", b"one");
        assert_eq!(store.get(b"alpha"), Some(&b"one"[..]));
    }

    #[test]
    fn get_missing_is_none() {
        let store = TinyLsm::new();
        assert_eq!(store.get(b"nope"), None);
    }

    #[test]
    fn put_overwrites() {
        let mut store = TinyLsm::new();
        store.put(b"alpha", b"one");
        store.put(b"alpha", b"two");
        assert_eq!(store.get(b"alpha"), Some(&b"two"[..]));
    }

    #[test]
    fn delete_removes_and_reports() {
        let mut store = TinyLsm::new();
        store.put(b"alpha", b"one");
        assert!(store.delete(b"alpha"));
        assert_eq!(store.get(b"alpha"), None);
        assert!(!store.delete(b"alpha"));
    }

    #[test]
    fn keys_are_independent() {
        let mut store = TinyLsm::new();
        store.put(b"alpha", b"one");
        store.put(b"beta", b"two");
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
        store.delete(b"alpha");
        assert_eq!(store.get(b"beta"), Some(&b"two"[..]));
    }
}

Note what get has to do itself: take key: &[u8]. The map underneath cannot accept a bare b"alpha" — its get looks up &Q where K: Borrow<Q>, and Borrow<[u8; 5]> is not implemented for Vec<u8>. Taking a plain &[u8] at the boundary means the coercion happens once, here, instead of at every call site.

The borrow rule

get hands back a slice that points into the store’s memory. While you hold it, the store is frozen: putting or deleting would move the map’s entries out from under your reference. Holding a value across a write is the one mistake this interface lets you make, and the compiler catches it. The same shape, with the bare map the store wraps:

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<Vec<u8>, Vec<u8>> = BTreeMap::new();
    map.insert(b"alpha".to_vec(), b"one".to_vec());

    let value = map.get(&b"alpha"[..]);
    map.insert(b"beta".to_vec(), b"two".to_vec());

    println!("{}", String::from_utf8_lossy(value.unwrap()));
}

Run this in the Rust Playground

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> borrow.rs:8:5
   |
 7 |     let value = map.get(&b"alpha"[..]);
   |                 --- immutable borrow occurs here
 8 |     map.insert(b"beta".to_vec(), b"two".to_vec());
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
 9 |
10 |     println!("{}", String::from_utf8_lossy(value.unwrap()));
   |                                            ----- immutable borrow later used here

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0502`.

When you need to keep a value and write at the same time, copy it out: store.get(key).map(|v| v.to_vec()) gives you an owned Option<Vec<u8>> and releases the borrow. In later steps the store copies on the way out anyway, once values start coming back from a file.

Why BTreeMap and not HashMap

HashMap is the default map for a reason, but it offers no order: iterating it visits keys in whatever order the hash function produced. A key-value store needs sorted keys — step 10 builds range scans, “everything from user:000 to user:999”, and with a HashMap that means collecting and sorting on every scan. BTreeMap is O(log n) per operation instead of O(1) on average, and in exchange the keys come out in order, always.

One thing to see early: the order is byte order, not dictionary order.

use std::collections::BTreeMap;

fn main() {
    let mut map: BTreeMap<Vec<u8>, &str> = BTreeMap::new();
    map.insert(b"apple".to_vec(), "red");
    map.insert(b"Zebra".to_vec(), "striped");
    map.insert(b"banana".to_vec(), "yellow");

    for (key, colour) in &map {
        println!("{} -> {}", String::from_utf8_lossy(key), colour);
    }
}

Run this in the Rust Playground

Zebra -> striped
apple -> red
banana -> yellow

Zebra sorts before apple because Z is byte 90 and a is byte 97. That is not a bug to work around — byte order is the right default for a database, because it is stable and locale-free, and it is what the range scans in step 10 will rely on.

See it run

From the tinylsm directory:

cargo test

running 5 tests
test tests::delete_removes_and_reports ... ok
test tests::get_missing_is_none ... ok
test tests::keys_are_independent ... ok
test tests::put_overwrites ... ok
test tests::put_then_get ... ok

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

Five tests, five passes, in well under a second. The Doc-tests section that follows runs zero tests — that is normal for a crate with no documentation examples yet.

Where this lands in the repository

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

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

The tag contains the Cargo.toml above, src/lib.rs in full, and the five tests. If your own 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 3, Appending writes to a log, starts the part the track is named for: put and delete begin appending one record per call to a file on disk, and the BTreeMap turns from the store itself into an index over that log. The three methods above are where it hooks in — their signatures stay exactly as they are here; their bodies change.