Content-addressed storage

Deep dive

How it works

In: blob bytes (put) or a hash (get) · Out: the hash, or the verified bytes · State: immutable objects at ab/cdef… paths, plus roots for GC · Cost: put O(n) hash plus 1 file write (2 fsyncs); get O(n) read plus O(n) re-hash.

1. key = H(bytes) with a collision-resistant H (SHA-256, BLAKE3). Git hashes a header and the content (blob <size>\0<content>), so a blob and a tree with equal bytes still get different names.
2. Layout: hex key ab/cdef…: the first byte picks one of 256 directories (git: 2 hex characters, then the remaining 38 of SHA-1).
3. put: hash; if the path exists, stop (dedup); else write to a temp file on the same filesystem, fsync it, rename into place, fsync the directory. Readers see the whole object or none; concurrent writers of one key race harmlessly (identical bytes).
4. get: read, re-hash, compare. A mismatch means bit rot, a torn write or tampering: never return the bytes.
5. Trees: a large file becomes chunks plus a manifest of their hashes; a directory is an object listing (name, hash). The root hash names the whole snapshot; unchanged subtrees keep their hashes (Merkle DAG, Merkle tree).
6. GC: objects are never edited, so space is reclaimed by reachability: mark everything reachable from the roots (refs, snapshots, pins), sweep the rest (mark-sweep). Refcounts work too but need crash-safe counter updates.

file ──chunk──► c1 c2 c3 c4
                 │  │  │  │            put each chunk → H(c_i)
                 ▼  ▼  ▼  ▼
manifest = [H(c1) H(c2) H(c3) H(c4)]   put manifest → root
root = H(manifest)                      edit c4 → new c4', new manifest, new root
                                        c1..c3 are shared, stored once

Code

Rust, blake3 crate (1.8 tested) via its streaming Hasher, rest is std. Compiled and run: asserts cover dedup, corruption, shared chunks, GC.

use std::{collections::HashSet, path::PathBuf};
use std::fs::{self, File, OpenOptions};
use std::io::{self, Read, Write};
use std::sync::atomic::{AtomicU64, Ordering};
pub type Hash = [u8; 32];
pub fn hash_bytes(data: &[u8]) -> Hash {
    let mut h = blake3::Hasher::new(); // streaming API: update() any number of times
    h.update(data);
    *h.finalize().as_bytes()
}
pub fn hex(h: &Hash) -> String { h.iter().map(|b| format!("{b:02x}")).collect() }
pub struct Cas { root: PathBuf }
static SEQ: AtomicU64 = AtomicU64::new(0);

impl Cas {
    pub fn open(root: impl Into<PathBuf>) -> io::Result<Cas> {
        let root = root.into();
        fs::create_dir_all(root.join("tmp"))?; // same filesystem as the objects: rename stays atomic
        Ok(Cas { root })
    }
    fn path(&self, h: &Hash) -> PathBuf { // ab/cdef...: 256 fan-out directories
        let s = hex(h);
        self.root.join(&s[..2]).join(&s[2..])
    }
    /// Idempotent: same bytes -> same key -> one copy.
    pub fn put(&self, data: &[u8]) -> io::Result<Hash> {
        let h = hash_bytes(data);
        let dst = self.path(&h);
        if dst.exists() { return Ok(h); } // dedup: no write, no fsync
        let tmp = self.root.join("tmp").join(format!("{}-{}", std::process::id(), SEQ.fetch_add(1, Ordering::Relaxed)));
        let mut f = OpenOptions::new().write(true).create_new(true).open(&tmp)?;
        f.write_all(data)?;
        f.sync_all()?; // bytes durable BEFORE the name appears
        drop(f);
        let dir = dst.parent().unwrap();
        fs::create_dir_all(dir)?;
        fs::rename(&tmp, &dst)?; // atomic: readers see the whole object or nothing
        File::open(dir)?.sync_all()?; // directory entry durable
        Ok(h)
    }
    /// The key is the checksum: every read verifies it.
    pub fn get(&self, h: &Hash) -> io::Result<Vec<u8>> {
        let mut buf = Vec::new();
        File::open(self.path(h))?.read_to_end(&mut buf)?;
        if hash_bytes(&buf) != *h {
            return Err(io::Error::new(io::ErrorKind::InvalidData, format!("corrupt {}", hex(h))));
        }
        Ok(buf)
    }
    fn objects(&self) -> io::Result<Vec<(String, PathBuf)>> { // (hex name, path)
        let mut v = Vec::new();
        for d in fs::read_dir(&self.root)? {
            let d = d?;
            let dn = d.file_name().to_string_lossy().into_owned();
            if dn.len() != 2 { continue; } // skips tmp/
            for e in fs::read_dir(d.path())? {
                let e = e?;
                v.push((format!("{dn}{}", e.file_name().to_string_lossy()), e.path()));
            }
        }
        Ok(v)
    }
    /// Scrub: names whose bytes no longer hash to the name.
    pub fn verify_all(&self) -> io::Result<Vec<String>> {
        let mut bad = Vec::new();
        for (name, p) in self.objects()? { if hex(&hash_bytes(&fs::read(p)?)) != name { bad.push(name); } }
        Ok(bad)
    }
    /// Sweep: delete every object outside `live` (the caller marked it by walking roots).
    pub fn sweep(&self, live: &HashSet<String>) -> io::Result<usize> {
        let mut n = 0;
        for (name, p) in self.objects()? { if !live.contains(&name) { fs::remove_file(p)?; n += 1; } }
        Ok(n)
    }
    /// File = manifest object listing chunk hashes (a one-level Merkle tree).
    pub fn put_chunked(&self, data: &[u8], chunk: usize) -> io::Result<Hash> {
        let mut manifest = Vec::new();
        for c in data.chunks(chunk) { manifest.extend_from_slice(&self.put(c)?); }
        self.put(&manifest)
    }
    pub fn get_chunked(&self, root: &Hash) -> io::Result<Vec<u8>> {
        let mut out = Vec::new();
        for h in self.get(root)?.chunks_exact(32) { out.extend(self.get(h.try_into().unwrap())?); }
        Ok(out)
    }
}

fn main() -> io::Result<()> {
    let dir = std::env::temp_dir().join(format!("cas-demo-{}", std::process::id()));
    let cas = Cas::open(&dir)?;
    let (a, b, c) = (cas.put(b"hello")?, cas.put(b"hello")?, cas.put(b"other")?);
    assert_eq!(a, b); assert_ne!(a, c); // dedup: same bytes, same key
    assert_eq!(cas.objects()?.len(), 2); // ...and one copy on disk
    assert_eq!(cas.get(&a)?, b"hello");

    // two files share 3 of 4 chunks: 10 puts, but only 5 + 2 = 7 new objects
    let mk = |last: u8| [vec![1u8; 4096], vec![2; 4096], vec![3; 4096], vec![last; 4096]].concat();
    let (f1, f2) = (mk(4), mk(9));
    let (r1, r2) = (cas.put_chunked(&f1, 4096)?, cas.put_chunked(&f2, 4096)?);
    assert_eq!(cas.objects()?.len(), 2 + 7);
    assert_eq!(cas.get_chunked(&r1)?, f1);
    assert_eq!(cas.get_chunked(&r2)?, f2);

    // flip one bit on disk: get() and the scrubber both notice
    let mut raw = fs::read(cas.path(&a))?;
    raw[0] ^= 1;
    fs::write(cas.path(&a), raw)?;
    assert_eq!(cas.get(&a).unwrap_err().kind(), io::ErrorKind::InvalidData);
    assert_eq!(cas.verify_all()?, vec![hex(&a)]);
    assert_eq!(cas.get(&c)?, b"other");

    // GC: only f1 (manifest + its chunks) is live
    let mut live: HashSet<String> = HashSet::from([hex(&r1)]);
    for h in cas.get(&r1)?.chunks_exact(32) { live.insert(hex(h.try_into().unwrap())); }
    assert_eq!(cas.sweep(&live)?, 4); // a, c, f2's manifest and chunk 9
    assert_eq!(cas.objects()?.len(), 5);
    assert!(cas.get_chunked(&r1).is_ok() && cas.get_chunked(&r2).is_err());
    fs::remove_dir_all(&dir)
}

tmp/ lives inside the store: rename is atomic only within one filesystem.

Complexity and constants

• put: hash O(n); a dedup hit costs one stat; a new object costs open, write, fsync(file), rename, fsync(dir). The fsyncs dominate small objects (order of ms on SSD). 4 KiB hashed in 1.9 µs with BLAKE3 on an M4 Pro (measured).
• Space: a manifest costs 32 bytes per chunk: order of 0.003 % for 1 MiB chunks, 0.8 % for 4 KiB.
• At backup scale the dedup index, not hashing, is the limit: Zhu et al. keep a Bloom-filter summary in RAM to avoid disk lookups for new chunks.

Efficiency

• Cost: compute-bound hashing: BLAKE3 measured 2.1 GB/s on one M4 Pro core (1 MiB buffers, crate 1.8.7); sha2 0.10 with default features measured 0.53 GB/s there. A new object is latency-bound by two fsyncs (order of ms on SSD); a dedup hit is one hash plus one stat, no write.
• Levers:
  • dedup check before writing — skips the write and both fsyncs — whenever the object exists (Venti, restic, Bazel caches)
  • batch directory fsyncs — fsync each file, then each touched directory once — bulk imports; git's core.fsync selects what is hardened
  • pack small objects — fewer inodes and syscalls, readahead — git packfiles, restic packs
  • SIMD and threads — BLAKE3 is built for both; SHA-256 is serial within one stream — big blobs
  • content-defined chunking — an insert changes only nearby chunks; fixed chunks re-store the tail — versioned or backup data
• Naive → standard → state of the art:
  • one file per object, fsync each, full-scan GC · order of ms per small object
  • fan-out dirs, temp+rename, dedup-before-write, mark-sweep with grace period · git loose objects
  • packs with index, CDC, in-RAM index, batched fsync, zstd · restic, Borg, bazel-remote

Implementation notes

• Pick the hash once and version the layout: git has a SHA-1 to SHA-256 transition plan after the SHAttered collision; REAPI names the digest function. Never key on a non-cryptographic hash.
• Store the length beside the hash (REAPI Digest = hash + size_bytes; OCI descriptors carry size) so wrong-sized content is rejected before hashing.
• For streams, call Hasher::update per buffer while writing the temp file; the final name exists only after finalize.
• Run a scrubber (data scrubbing): the filename is the expected checksum. CAS only detects rot; repair needs replicas or erasure coding.
• Chunk sizes: restic cuts 512 KiB to 8 MiB (1 MiB average); Kubo defaults to fixed 256 KiB. Smaller chunks dedup better, cost more objects.

Pitfalls

• Skipping the directory fsync, or renaming across filesystems (EXDEV): object lost after a crash.
• Trusting "path exists" as "intact": a corrupt file blocks the re-upload.
• GC racing a put: the sweep deletes a just-written, not-yet-referenced object. Use a grace period (git prunes loose unreachable objects older than 2 weeks by default, gc.pruneExpire) or a lock.
• Anyone who can guess a file can test whether you store it; encrypted stores (restic) randomize the chunker per repository.

Variants and alternatives

In production

• Git: zlib-compressed objects named by hash of <type> <size>\0<content> under .git/objects/xx/, later packed; see Git object model.
• IPFS: CIDs name blocks of a Merkle DAG; Kubo garbage-collects blocks that are not pinned.
• Bazel remote caching: REAPI addresses blobs by Digest { hash, size_bytes }; bazel-remote keys CAS by lowercase SHA-256 and stores zstd-compressed by default.
• restic / Borg: chunked, deduplicated backups; borg compact reclaims space after archive deletion.
• OCI registries: layers and manifests addressed by sha256: digests clients should verify.

Implementations

Sources

• Sean Quinlan, Sean Dorward, Venti: a new approach to archival storage, FAST 2002. paper
• Muthitacharoen, Chen, Mazières, A Low-bandwidth Network File System, SOSP 2001. paper
• Zhu, Li, Patterson, Avoiding the Disk Bottleneck in the Data Domain Deduplication File System, FAST 2008. paper
• Juan Benet, IPFS - Content Addressed, Versioned, P2P File System, 2014. arXiv · code
• Pro Git, Git Objects. book · git gc · hash transition
• restic design reference. docs · Bazel remote-apis · OCI image-spec