Log-structured storage

Deep dive

How it works

Parts:

• segment — append-only file NNNNNN.log; only the newest (active) is written, sealed ones are immutable
• record — [crc][klen][vlen][key][value]; a delete is a record with a tombstone length
• index — in-memory key → (segment, offset, length); the only way to find a key
• cleaner — copies the live records of sealed segments into a new segment, deletes the old ones
• hint file (optional) — per sealed segment, only the index entries, so startup skips the values

 put/delete ──► active segment [rec][rec][rec]►          index: key ─► (seg, off, len)
 sealed: 000001.log 000002.log │ cleaner: copy live ─► new 000002.log, unlink 000001
 get ─► index ─► read(seg, off, len) ─► verify crc

1. Put: encode the record with its CRC, append it to the active segment (roll to a new file past the size limit), then set index[key]. The index changes only after the append.
2. Delete: append a tombstone, remove the key from the index.
3. Get: look up the location, read exactly those bytes, check the CRC.
4. Clean: copy every record the index still points to out of the sealed segments into a new file, fsync it, rename it into place atomically, update the index, unlink the inputs.
5. Recover: replay segments oldest to newest into the index. In the newest segment the first short or bad record is the torn tail: truncate there. Hint files replace the replay for sealed segments.
6. Secondary indexes (harvested items): key = hash(guid); the value header holds feed, time and entities. The recovery scan decodes the header and fills a sparse time index (one entry per few KiB, as in Kafka), a feed posting list and an entity posting list of locations.

The family differs in where the index lives and how it cleans:

• Bitcask: hash index of all keys in RAM, whole-file merges, hint files.
• LFS (log-structured file system): inode map as index, 512 KB or 1 MB segments, cleaner ranks segments by free space gained × age ÷ cost.
• LSM-tree: sorted runs instead of a hash index; keys may exceed RAM, scans work.
• Kafka: addressed by position, sparse offset and time index per segment (segmented log, log compaction).
• Flash translation layer: logical-to-physical page map inside an SSD (SSD internals).

Code

use std::{collections::HashMap, fs::{self, File, OpenOptions}, io::{self, Write}};
use std::{os::unix::fs::FileExt, path::{Path, PathBuf}};
fn crc32(d: &[u8]) -> u32 { // bitwise CRC-32 (IEEE); real code uses a table or the CPU instruction
    !d.iter().fold(!0u32, |c, &b| (0..8).fold(c ^ b as u32, |c, _| (c >> 1) ^ (0xEDB8_8320 & (c & 1).wrapping_neg())))
}
// record = [crc u32][klen u32][vlen u32][key][value]; the CRC covers klen..end; vlen = TOMB marks a delete
const H: usize = 12; const TOMB: u32 = u32::MAX;
fn encode(k: &[u8], v: Option<&[u8]>) -> Vec<u8> {
    let vl = v.map_or(TOMB, |v| v.len() as u32);
    let mut r = [&[0u8; 4][..], &(k.len() as u32).to_le_bytes(), &vl.to_le_bytes(), k, v.unwrap_or(&[])].concat();
    let c = crc32(&r[4..]);
    r[..4].copy_from_slice(&c.to_le_bytes());
    r
}
/// The record at the start of `b`: (key, value or None = tombstone, length). None if short or corrupt.
fn decode(b: &[u8]) -> Option<(&[u8], Option<&[u8]>, usize)> {
    if b.len() < H { return None; }
    let u = |i: usize| u32::from_le_bytes(b[i..i + 4].try_into().unwrap());
    let (kl, vl) = (u(4) as usize, u(8));
    let end = H + kl + if vl == TOMB { 0 } else { vl as usize };
    if end > b.len() || crc32(&b[4..end]) != u(0) { return None; }
    Some((&b[H..H + kl], (vl != TOMB).then(|| &b[H + kl..end]), end))
}
type Loc = (u32, u64, u32); // segment id, record offset, record length
fn seg(d: &Path, id: u32) -> PathBuf { d.join(format!("{id:06}.log")) }
fn seg_ids(d: &Path) -> io::Result<Vec<u32>> {
    let mut v: Vec<u32> = fs::read_dir(d)?.filter_map(|e| e.ok()?.file_name().to_str()?.strip_suffix(".log")?.parse().ok()).collect();
    v.sort();
    Ok(v)
}
fn read_at(d: &Path, (id, off, len): Loc) -> io::Result<Vec<u8>> {
    let mut b = vec![0u8; len as usize];
    File::open(seg(d, id))?.read_exact_at(&mut b, off)?;
    Ok(b)
}
fn open_append(d: &Path, id: u32) -> io::Result<File> { OpenOptions::new().create(true).append(true).open(seg(d, id)) }
pub struct Store { dir: PathBuf, active: File, id: u32, len: u64, max: u64, sync: bool, idx: HashMap<Vec<u8>, Loc> }
impl Store {
    /// Rebuilds the index by replaying all segments in order; truncates a torn tail of the newest one.
    pub fn open(dir: &Path, max: u64, sync: bool) -> io::Result<Store> {
        fs::create_dir_all(dir)?;
        let ids = seg_ids(dir)?;
        let (mut idx, mut end) = (HashMap::new(), 0usize);
        for &id in &ids {
            let data = fs::read(seg(dir, id))?;
            end = 0;
            while let Some((k, v, l)) = decode(&data[end..]) {
                if v.is_some() { idx.insert(k.to_vec(), (id, end as u64, l as u32)); } else { idx.remove(k); }
                end += l;
            }
        }
        let id = ids.last().copied().unwrap_or(0);
        let active = open_append(dir, id)?;
        active.set_len(end as u64)?; // drops the torn tail of the newest segment
        Ok(Store { dir: dir.into(), active, id, len: end as u64, max, sync, idx })
    }
    fn append(&mut self, k: &[u8], v: Option<&[u8]>) -> io::Result<Loc> {
        let r = encode(k, v);
        if self.len > 0 && self.len + r.len() as u64 > self.max { // roll to a new segment
            self.active.sync_all()?;
            (self.id, self.len) = (self.id + 1, 0);
            self.active = open_append(&self.dir, self.id)?;
        }
        self.active.write_all(&r)?;
        if self.sync { self.active.sync_data()?; }
        self.len += r.len() as u64;
        Ok((self.id, self.len - r.len() as u64, r.len() as u32))
    }
    pub fn put(&mut self, k: &[u8], v: &[u8]) -> io::Result<()> {
        self.append(k, Some(v)).map(|at| { self.idx.insert(k.to_vec(), at); })
    }
    pub fn delete(&mut self, k: &[u8]) -> io::Result<()> { // the tombstone makes replay forget the key too
        if self.idx.remove(k).is_some() { self.append(k, None)?; } Ok(())
    }
    pub fn get(&self, k: &[u8]) -> io::Result<Option<Vec<u8>>> {
        let Some(&at) = self.idx.get(k) else { return Ok(None) };
        Ok(decode(&read_at(&self.dir, at)?).and_then(|(_, v, _)| v.map(<[u8]>::to_vec))) // CRC checked on every read
    }
    /// Copies the live records of all sealed segments into one file that atomically replaces the newest sealed id.
    pub fn compact(&mut self) -> io::Result<()> {
        let sealed: Vec<u32> = seg_ids(&self.dir)?.into_iter().filter(|&i| i < self.id).collect();
        let Some(&top) = sealed.last() else { return Ok(()) };
        let mut live: Vec<_> = self.idx.iter().filter(|(_, l)| l.0 < self.id).map(|(k, l)| (k.clone(), *l)).collect();
        live.sort_by_key(|(_, l)| (l.0, l.1)); // read sequentially
        let (mut out, mut moved) = (Vec::new(), Vec::new());
        for (k, at) in live {
            moved.push((k, (top, out.len() as u64, at.2)));
            out.extend(read_at(&self.dir, at)?);
        }
        let tmp = self.dir.join("compact.tmp");
        fs::write(&tmp, &out)?;
        File::open(&tmp)?.sync_all()?;
        fs::rename(&tmp, seg(&self.dir, top))?; // old or new `top`, never half
        for id in &sealed[..sealed.len() - 1] { fs::remove_file(seg(&self.dir, *id))?; }
        self.idx.extend(moved);
        Ok(())
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn all() -> io::Result<()> {
        let d = std::env::temp_dir().join(format!("logstore-{}", std::process::id()));
        let mut s = Store::open(&d, 128, false)?;
        for i in 0..40 { s.put(format!("k{}", i % 10).as_bytes(), format!("v{i}").as_bytes())?; }
        s.delete(b"k3")?;
        assert_eq!((s.get(b"k2")?.unwrap(), s.get(b"k3")?), (b"v32".to_vec(), None));
        let n = seg_ids(&d)?.len(); s.compact()?;
        assert!(seg_ids(&d)?.len() < n && s.get(b"k9")?.unwrap() == b"v39");
        s.put(b"last", b"x")?;
        let f = OpenOptions::new().write(true).open(seg(&d, s.id))?;
        f.set_len(f.metadata()?.len() - 3)?; // crash mid-write: torn last record
        let mut s = Store::open(&d, 128, false)?; // recovery scan
        assert_eq!((s.get(b"last")?, s.get(b"k3")?, s.get(b"k9")?.unwrap()), (None, None, b"v39".to_vec()));
        s.put(b"last", b"y")?;
        assert_eq!(Store::open(&d, 128, false)?.get(b"last")?.unwrap(), b"y");
        fs::remove_dir_all(&d)
    }
}

The test (passes) covers overwrite, delete, compaction, reopen and a torn last record (3 bytes cut off). Not shown: directory fsync, hint files, locking.

Complexity and constants

• Put: one write of 12 + key + value bytes (116 B for a 100 B value and 4 B key). The index costs key bytes + a location (16 B here) + hash-table overhead per key, in RAM; this limits capacity.
• Cleaning: if the cleaned segments have live fraction u, bytes written per byte of new data = 1/(1 - u): u = 0.5 gives 2×, 0.8 gives 5×, 0.9 gives 10×. LFS also counts the read: 2/(1 - u). This is arithmetic, not a measurement. Sprite LFS in production: write cost 1.2-1.6 (Table 2 of the paper).
• Recovery, measured on this Mac (Apple M4 Pro, machine busy): 200,000 records (about 23 MB) replayed in 0.29-0.38 s with this code's bitwise CRC.

Efficiency

• Cost: one 116 B append, measured on this Mac (Apple M4 Pro, other load running, 10 runs): 46,000-224,000 appends/s without fsync (one write syscall plus bitwise CRC); 130-212 appends/s with sync_data after every record, about 5-8 ms each. Bound: fsync latency when durable, syscalls and CRC otherwise.
• Levers:
  • batch records per fsync (group commit) — commit rate ≈ batch size ÷ fsync latency (arithmetic) — concurrent writers or bufferable producers
  • cost-benefit cleaning with age-sorted rewrites — most cleaned segments had about 15 % utilization in the LFS simulation (75 % disk full) — hot and cold data mixed
  • hint files — startup reads keys and locations, not values (Bitcask paper, no figure) — big values, restarts that matter
  • expire by dropping whole segments — no copying (Kafka retention) — data with a time limit, like harvested news
• Naive → standard → state of the art:
  • update records in place · one random write each, torn pages after a crash
  • one log, RAM hash index, whole-file merge (Bitcask) · one sequential write, one read per get, keys must fit RAM
  • segmented log, cost-benefit cleaning, hint files, batched fsync · write cost near 1 when dead data is cold; sorted-run LSM when keys exceed RAM

Implementation notes

• Write each record in one write in append mode, so a crash tears at most the last record.
• After creating, renaming or unlinking a segment, fsync the directory, or the change can vanish.
• One writer process per directory (Bitcask enforces this).
• Start cleaning on garbage ratio (dead ÷ total bytes) and throttle it.

Pitfalls

• Resurrected deletes: cleaning drops tombstones, so a crash after the rename but before the old files are unlinked brings a deleted key back (this code has that window). Fix: a manifest of live segments.
• A bad record in the middle of a sealed segment is not a torn tail; this code silently skips the rest of that segment. Fail loudly instead.
• Without an fsync per record or batch, acknowledged writes can be lost; with it, throughput falls to 1 ÷ fsync latency (fsync, ordering).

Variants and alternatives

In production

• Databases: Bitcask (Riak); Raft Engine (TiKV) keeps Raft logs in a Bitcask-like layout with an in-memory index.
• Message brokers: Kafka: per-partition segment files with sparse offset and time indexes.
• File systems and SSDs: Sprite LFS; SSD firmware also copies valid pages forward before erasing a block.
• Feed archives, telemetry, audit trails: append-only item or event files indexed by time, source and entity.

Implementations

Sources

• M. Rosenblum, J. K. Ousterhout, The Design and Implementation of a Log-Structured File System, ACM TOCS 10(1), 1992 (SOSP 1991). paper · PDF
• J. Sheehy, D. Smith, Bitcask: A Log-Structured Hash Table for Fast Key/Value Data, Basho, 2010. paper · code
• J. Kreps, The Log: What every software engineer should know about real-time data's unifying abstraction, LinkedIn Engineering, 2013. archived copy
• Apache Kafka documentation, Log and broker configs. log · configs · KIP-33, time based log index