Content-Addressed Storage

Most storage systems name data by where it is stored: a pathname, an object key, a URL, or a database row. Content-addressed storage (CAS) uses a different rule. It derives an object’s name from the object’s bytes, then uses that name to store, retrieve, reuse, and verify the object.

That rule is small, but it changes what a storage reference means. A path such as /docs/report.txt can point to different bytes tomorrow. A content address continues to identify the same bytes; changing the bytes produces a new address.

This section develops a vanilla CAS from first principles. It covers the architecture, core algorithm, exact-content deduplication, real-world applications, and why file-scale objects need a chunked representation. It does not yet cover the content-defined boundary algorithm, LayerFS object formats, typed identities, object graphs, admission, packs, or production publication. Those mechanisms make sense only after the basic CAS contract is clear.

1. The Address Is the Content

Consider a conventional filesystem path:

/docs/report.txt

The path tells the filesystem where to look. It does not permanently identify the bytes found there. A process can overwrite the file while keeping the same path, or move the same file to a different path. The relationship between name and content is mutable.

A content-addressed store starts from the opposite direction:

object address = hash(object bytes)

The address is derived from the content rather than chosen independently. If the content remains unchanged, so does the address. If the content changes, its address changes too.

The distinction is not that one system has locations and the other does not. Every physical store eventually places bytes somewhere. The distinction is what the public identity means:

This gives CAS a useful vocabulary for immutable data. Two callers referring to the same content address mean the same expected bytes, even if the storage system later changes the object’s physical placement.

It also changes lookup. CAS does not search the store for bytes that resemble a request. The caller already has an object identifier. The store uses that identifier to locate the object directly, just as a key-value store uses a key. The difference is that the CAS key is derived from the value.

2. Identity from Bytes

Let x be an object’s byte sequence and H a cryptographic hash function. A minimal content identity is:

id(x) = H(x)

The hash function processes an input of arbitrary length and produces a fixed-length digest. A CAS depends on several properties:

• Determinism: hashing the same bytes with the same algorithm produces the same digest.
• Sensitivity to change: changing the input should produce an unrelated digest.
• Collision resistance: finding two different inputs with the same digest should be computationally infeasible for the chosen algorithm.
• Streaming evaluation: the digest can be computed incrementally without loading the whole object into memory.

A digest is not a mathematical proof that collisions are impossible. It is a security assumption: the digest is large enough and the algorithm strong enough that accidental or deliberate collisions are infeasible for the system’s threat model. Long-lived systems also need a way to evolve when a hash algorithm ages; Git’s hash-function transition design is one example of why algorithm choice cannot be assumed permanent.

Identity enables verification

Suppose a caller requests an object by expected_id, and the store returns content. The caller or store recomputes the digest and compares it with the requested ID:

actual_id = H(content)

if actual_id != expected_id:
    return integrity_error

If the values differ, the returned bytes are not the requested object. This can detect corruption, truncation, a faulty locator, or storage returning the wrong object.

This is an integrity check, not a complete security system. It does not prove who created the bytes, whether the bytes are trustworthy, whether they are encrypted, or whether another copy is available for repair.

Identity enables exact deduplication

If an object with address d is already stored, another insertion of the same object can reuse it instead of writing another payload copy. This is exact-content deduplication at the CAS object’s boundary.

Object boundary matters. A CAS storing whole files recognizes two identical files, but a one-byte change makes the edited file a different whole object. Reusing unchanged regions inside the file requires the system to divide the file into smaller objects. Chunking is an additional design choice, not part of the basic CAS definition.

The distinction among CAS, deduplication, and incremental backup is worth making explicit:

These techniques often appear together, especially in backup products, but they are not synonyms. The BlinkDisk CAS overview describes a chunked backup system; the chunking is what allows unchanged regions inside an edited file to be reused. Its separate introductions to deduplication and incremental backup show the related storage and backup concepts. A vanilla CAS can deduplicate exact objects without implementing either chunking or an incremental-backup chain.

3. Architecture: A Minimal Content-Addressed Store

A minimal CAS needs a narrow set of responsibilities:

1. accept a sequence of bytes;
2. derive its object identifier;
3. retain one immutable object for that identifier;
4. locate an object from its identifier; and
5. optionally rehash returned bytes to verify them.

The locator does not have to be a database. A simple store can derive a pathname directly from the digest. A larger store may use an index because objects are packed, remote, replicated, or moved between storage tiers. Both designs preserve the same separation:

logical identity:  which exact bytes?
physical locator:  where are those bytes currently stored?

Above the CAS, an application usually maintains names and relationships that people care about. A backup system maps snapshots and pathnames to stored objects. Git maps trees and commits to objects, then uses mutable branch names to select commits. A container registry maps tags to manifests whose descriptors identify blobs by digest. These upper layers supply meaning; the vanilla CAS stores opaque bytes.

That boundary is deliberate. CAS is easier to reason about when its core contract does not also try to be a filesystem, version-control system, backup catalog, or distributed availability service.

4. Core Algorithm: Put, Get, and Verify

At the conceptual level, a vanilla CAS has two operations:

put(bytes) -> object_id
get(object_id) -> bytes

The core algorithm can be written as:

put(bytes):
    id = hash(bytes)

    if id is not already stored:
        publish bytes as the immutable object named by id

    return id

get(id):
    bytes = locate and read the object named by id

    if hash(bytes) != id:
        return integrity error

    return bytes

The phrase publish ... as immutable hides real engineering work. A production implementation must handle crashes, concurrent writers, a destination that already exists, partial writes, and storage errors without replacing trusted data. Chapter 2 returns to those mechanics. For now, the logical rule is enough: after successful publication, the bytes associated with an object ID never change.

A put operation

Both paths return the same object ID; only the publication work differs.

The same input produces the same candidate ID, so exact duplicates converge on one name. A trustworthy implementation must not blindly trust an existing occupant merely because it has the expected pathname; Chapter 2 will strengthen this reuse path with authenticated admission.

A get operation

A caller supplies the ID of the bytes it expects. The store resolves the ID, reads the bytes, and recomputes the digest. A matching digest authenticates the byte sequence against the requested content identity. A mismatch must be reported rather than returning bytes as though the read succeeded.

Verification can occur at different boundaries. A local store may verify every read, verify during admission and rely on trusted immutable media, or let a client verify a remote response. The placement changes cost and trust assumptions, but not the equation H(bytes) = requested ID.

A worked example

Assume strings are stored as their UTF-8 bytes:

The application submitted 16 logical bytes, but the CAS retained 11 unique payload bytes. The second hello still had to be identified—normally by reading and hashing its five bytes—but it did not require another payload copy.

This small example captures both the strength and the boundary of vanilla CAS:

• exact repeats are cheap to retain because they share an ID;
• any changed byte creates a new whole-object identity; and
• higher-level references are needed to explain why an application cares about either object.

5. Content Addressing in Real Systems

CAS is rarely the whole product. Mature systems use it as a stable object layer and add structures that give objects meaning, reachability, policy, and efficient physical representation.

Git is the most familiar teaching example. Its object database stores content-addressed blobs, trees, commits, and tags, as described in Git Objects. A branch such as main is not itself an immutable content address; it is a mutable reference that selects a commit.

This separation lets Git retain stable historical objects while allowing a branch name to advance. Git also demonstrates that logical identity and physical encoding can evolve separately: packfiles can store objects compactly using deltas without changing the identities used by commits and trees.

Venti is an early, influential example of a network storage system built around content-addressed immutable blocks. Its clients build archival data structures above the block store, reinforcing the same boundary: CAS provides stable blocks, while higher layers provide roots and interpretation.

Container and build systems use the idea for distribution and reuse. The OCI image specification’s descriptors carry digests used to identify and verify referenced content. Bazel remote caching separates a content-addressable store for files from an action cache that maps actions to results. In both cases, CAS is one component in a larger protocol.

Distributed CAS makes another boundary visible. An IPFS content identifier identifies content independently of a particular host, but knowing a CID does not guarantee that a reachable peer currently provides the data. Content identity and content availability are different properties.

Backup systems commonly combine all three concepts introduced earlier: chunking chooses deduplication units, content addressing names them, and snapshot or incremental metadata records recoverable states. Storage savings and restore behavior therefore belong to the complete backup design, not to hashing alone.

6. Why CAS Needs a Chunked Representation

The unit of deduplication in a CAS is the object. If an entire file is one object, two identical files share one identity, but changing one byte changes the identity of the entire file. Without another encoding such as delta compression, the edited version contributes another whole-file payload.

A chunked representation changes the deduplication unit from the whole file to smaller byte regions. Each chunk receives its own content identity, and a small manifest records their order. After a localized edit, unchanged chunks retain their identities and can be reused; only the affected boundary region and the manifest need new objects.

For example, if a 1 GiB file is stored as one CAS object, a one-byte edit can add another 1 GiB payload. With chunking, the added payload is instead proportional to the affected chunking region plus a small manifest. The exact amount depends on chunk size and boundary behavior; chunking improves the reuse opportunity but does not promise that every edit changes exactly one chunk.

CAS supplies identity and exact reuse; chunking chooses the smaller regions that CAS can reuse.

This creates the next design question: where should the boundaries fall? Fixed-size boundaries are simple, but an insertion can shift every later chunk. The next section introduces content-defined chunking, which chooses boundaries from the content so the stream can resynchronize after a localized edit.