Content-addressable storage, explained

Most storage is addressed by location: a path, a row id, an offset. You say where the data lives and get back whatever is there now. Content-addressable storage turns that around. The address is computed from the data itself, so the name of an object is a fingerprint of its bytes.

Git works this way, and so does Ark. This entry walks one small file all the way from its bytes to its address, with real values.

The recipe

Ark builds an address in three moves: put a header in front of the bytes, hash the result with SHA-256, and use the hex digest as the name.

A worked example

Take a file holding Hello World and a newline. That is 12 bytes:

48 65 6c 6c 6f 20 57 6f 72 6c 64 0a
H  e  l  l  o     W  o  r  l  d  \n

Add the header. The type, a space, the length in decimal, and a NUL byte: blob 12 then 00. That is eight more bytes, twenty in all.

Hash all twenty bytes. You can reproduce Ark’s result from a shell, without Ark:

❯ $ printf 'blob 12\0Hello World\n' | shasum -a 2567c5c8610459154bdde4984be72c48fb5d9c1c4ac793a6b5976fe38fd1b0b1284  -

That is exactly what ark hash-object file.txt prints for this file.

Split the digest. The first two hex characters become a directory and the remaining 62 become the file name: .ark/objects/7c/5c86…1284. Two hex characters allow 256 directories, which keeps any one directory from collecting every object in the repository.

Change one byte

Swap the newline for an exclamation mark. The length is still 12, so the header is identical and only the last byte of the input differs:

❯ $ printf 'blob 12\0Hello World!' | shasum -a 256745b1517d3a647e2a45689c4c0cf968ffed35e6bdc6a90e3e5c6e648dc30508b  -

The first two digests happen to share their leading 7, and nothing else lines up. A good hash gives no hint of how similar two inputs were, which is the property that makes it usable as a name.For the third row the header changes too, to blob 13, because the length is part of it.

What falls out of it

Deduplication is free. Two files with the same bytes produce the same address, so the store holds one copy however many paths point at it. Nothing has to look for duplicates; they collide by construction.

Integrity is built in. Reading an object back, you can hash it again and compare with its name. A flipped bit on disk shows up as a mismatch rather than as silently wrong data.

Structure is hashed too. A tree lists the hashes of its children, and a commit names its root tree. In Ark’s first demo commit, tree becca28 contains the line for blob 7c5c861, and commit b36cd6c names tree becca28. Edit one byte of file.txt and the blob hash changes, so the tree’s text changes, so the tree hash changes, so any new commit has a different hash too. A single commit hash pins down every byte beneath it.

Git does the same with SHA-1

Git builds the identical blob 12 header and, in a default repository, hashes it with SHA-1, which gives a shorter 40-character name for the same file:¹1 Git can also create repositories that use SHA-256 object names (git init --object-format=sha256); SHA-1 remains the default.

❯ $ printf 'Hello World\n' | git hash-object --stdin557db03de997c86a4a028e1ebd3a1ceb225be238

Same recipe, different hash function. Ark’s choice of SHA-256 means its object names are 64 characters and its fan-out directories hold 62-character file names.