Chunking and Content-Defined Boundaries

The previous section established the basic CAS rule: an object’s identity comes from its bytes. This section asks how to represent a large file as smaller, reusable objects without losing the original byte sequence.

CAS can reuse only the object it receives. If an entire file is one object, a one-byte edit gives the edited file a new identity, even though almost all of its bytes may still be unchanged.

The unchanged regions are still present, but whole-file CAS cannot see them. We need a smaller unit of reuse. That smaller unit is a chunk.

1. What Is a Chunk?

Chunking means splitting a byte stream into contiguous pieces. The pieces preserve the original bytes and their order; the representation simply gives us smaller units to store, compare, transfer, and reuse.

Here || means concatenate: read C₀, then C₁, then C₂:

B = C₀ || C₁ || C₂

A chunk is only a range of bytes. It is not a file-format record, a paragraph, or a cryptographic identity. The order of the chunks is part of the representation: the same pieces in a different order describe different bytes.

The file therefore needs a small ordered recipe that says which chunks to read. The chunk data can live in one shared pool:

The second file is not stored as a second full copy. Its index changes from [C1, C2, C3] to [C1, C4, C3]: the unchanged outer chunks are reused, and only the changed middle chunk is new.

A chunk is easy to define. The difficult question is where its end should fall.

2. Why Positional Boundaries Fail

Suppose abcdefghij is split into ranges of three bytes. If X is inserted after c, every later range starts one byte later:

Before:  abcdefghij       → [abc] [def] [ghi] [j]
After:   abcXdefghij      → [abc] [Xde] [fgh] [ij]

The first range can still be reused, but the later ranges no longer contain the same bytes. Their content addresses change too. This is the boundary-shift problem: a local edit has caused every later fixed-position boundary to move.

Fixed-size boundaries are simple and fast, but they follow offsets rather than content. We need a rule that can recognize a suitable boundary from the bytes near the current position.

3. Content-Defined Chunking (CDC)

Content-defined chunking makes the boundary a function of the content. The scanner does not cut only because it has reached a predetermined offset. Instead, the bytes near the current position influence whether the current position is a good boundary.

The same bytes, scanned with the same profile, produce the same boundary decision. A local edit may disturb one decision, but the scan can later recognize unchanged content again instead of permanently losing alignment.

At a high level, CDC repeats one small loop:

read bytes → produce a content signal → decide cut or continue

The next section explains the signal. The section after that explains how FastCDC uses it to control chunk sizes.

4. Rolling Fingerprint and GearHash

Generic rolling hash: the moving-window intuition

The scanner advances one byte at a time while reusing its previous state. The following animation gives the generic rolling-hash intuition:

The window moves from ABCD to BCDE: the outgoing A is removed, the incoming E is added, and the next state reuses work from the previous state. The point is not the particular arithmetic; it is that the scanner does not start from scratch at every position.

GearHash: the fast fingerprint

GearHash is a particularly simple rolling fingerprint for CDC. For each input byte bᵢ, it updates the previous fingerprint with a shift and a lookup in a fixed table:

fpᵢ = ((fpᵢ₋₁ << 1) + G[bᵢ]) mod 2ʷ

w is the fingerprint width, normally 64 bits. G is a fixed table of 256 precomputed w-bit constants, typically chosen to look random. The table and the width are part of the chunking profile and must be identical across implementations. In code, unsigned wrapping arithmetic is equivalent to reducing the result modulo 2ʷ.

The recurrence and its three basic operations—one shift, one addition, and one table lookup—are described in the FastCDC paper and Josh Lee’s GearHash explanation.

GearHash does not retain an explicit byte window or subtract an outgoing byte. It retains only the current w-bit fingerprint. Each shift moves older table contributions toward the discarded end of the state; after roughly w updates, contributions from older bytes no longer affect the fingerprint. This is why GearHash behaves like a rolling window while remaining only a shift, an addition, and an array lookup.

The animation shows the conceptual one-byte recurrence with toy 16-bit values. The current LayerFS scanner unrolls two consecutive updates in its hot loop; algebraically, that is:

fpᵢ₊₂ = ((fpᵢ << 2) + (G[bᵢ] << 1) + G[bᵢ₊₁]) mod 2ʷ

It is the same recurrence applied twice, while allowing the implementation to test a boundary after either byte.

That distinction matters: the generic sliding-window animation is intuition, while GearHash’s precise state transition is the recurrence above. GearHash is fast and useful for finding boundaries, but it is not a cryptographic hash and must not be used as the chunk’s immutable identity.

Hash judgment: cut or continue

Once the scanner has a fingerprint, it needs a separate test for whether to end the current chunk. The zero-mask form used by FastCDC and the current LayerFS profile is:

(fp & mask) == 0

If the selected fingerprint bits are all zero, the scanner cuts; otherwise it continues. Earlier Gear-based descriptions commonly express the judgment as fp mod D == r; FastCDC uses a padded, spread-out mask and the convenient zero test above. The exact predicate is part of the chunking profile.

If the selected bits behave approximately uniformly and independently, an N-bit zero test matches with probability roughly 1 / 2ᴺ at each tested position. That probability controls a tendency toward a target chunk scale, not the exact size of every chunk; minimum and maximum limits and FastCDC normalization also shape the observed distribution.

This completes the basic CDC loop: update the fingerprint, judge it, then emit the chunk or continue scanning. Minimum and maximum range limits keep that loop practical. A later CAS layer can hash the completed bytes to name and verify the chunk; the boundary fingerprint is only a fast signal.

5. FastCDC

GearHash makes the fingerprint cheap, but a cheap fingerprint does not automatically produce a useful chunk-size distribution. Josh Lee’s illustrative 8 KiB GearHash run on the Shakespeare corpus reported 38.49% of chunks below 4 KiB, 13.76% above 16 KiB, and two chunks above 80 KiB. Those numbers are from that example, not a universal GearHash guarantee, but they make the problem concrete: the average can be near the target while individual chunks are still poorly distributed. (GearHash article)

The FastCDC paper identifies two related problems with plain Gear-based CDC: the boundary judgment sees only a short span of recent history, and once GearHash makes fingerprinting cheap, judging every position becomes a noticeable part of the work. In its evaluation, FastCDC was reported as roughly 10× faster than the paper’s best open-source Rabin baseline and roughly 3× faster than Gear- and AE-based CDC, while achieving nearly the same deduplication ratio as Rabin. Those are measurements from the paper’s workloads and hardware, not guarantees for every implementation. (FastCDC paper)

FastCDC keeps GearHash’s fast fingerprint update and changes the boundary policy around it. Think of it as three guardrails and one safety rail:

• Before the minimum: copy bytes only. Do not hash or judge; a cut is not allowed yet.
• From minimum to target: update GearHash and use a strict MaskS, so a match is rare and the chunk is encouraged to grow.
• From target to maximum: update GearHash and use a relaxed MaskL, so a match is more likely and the chunk is encouraged to finish.
• At the maximum: emit if no earlier match appeared. This is a normal size bound, not a fourth FastCDC technique.

The animation uses a toy profile—minimum 4, target 10, maximum 18—so the policy fits on one screen. The exact LayerFS construction profile is an implementation contract, not a universal CDC setting.

The key idea: copy first, then make early matches rare, later matches likely, and progress unconditional at the maximum.

The three named improvements explain why those guardrails work together. Read them as one sequence rather than as separate algorithms. (FastCDC article)

1. Broaden the boundary test — enhanced hash judgment. FastCDC pads the mask with zero bits and distributes its effective bits across a wider range of the fingerprint. The GearHash update itself does not change: the same number of effective bits can keep roughly the same match probability, while the decision reflects a longer span of recent history. FastCDC also simplifies the conventional remainder/threshold test to the zero-mask form fp & mask == 0. The mask must be generated deterministically; a different mask can produce different boundaries and destroy reuse.

2. Skip impossible early cuts — sub-minimum cut-point skipping. Before the minimum length, LayerFS copies bytes into the candidate chunk but does not update or judge the Gear state. Once the candidate reaches the minimum, GearHash scanning begins. This avoids tiny chunks and avoids work where a cut is forbidden. The skipped positions might have been useful content-defined boundaries, so this improves speed at a possible deduplication cost.

3. Pull the result toward the target — normalized chunking. Before the target, MaskS has more effective bits, so matches are rarer and the chunk is encouraged to grow. After the target, MaskL has fewer effective bits, so matches are more likely and the chunk is encouraged to finish. Conceptually, mask = if len < target { MaskS } else { MaskL }. At the maximum, the scanner cuts to guarantee progress. The goal is not an exact target-sized chunk; it is a useful size range with good deduplication behavior.

At end of input, any remaining range is emitted as the tail, even when it is shorter than the minimum. This is normal tail behavior, not a boundary-detection error. If input ends with one byte of an incomplete pair, that byte is appended to the tail; end of input does not create another boundary test.

FastCDC therefore gives LayerFS a repeatable sequence of byte ranges. The next two sections place those ranges in the larger LayerFS design and preview the file representation built from them.

6. Why LayerFS Chooses CAS + CDC + COW

CAS, CDC, and COW solve three different forms of storage amplification. Keeping their contracts separate makes the complete LayerFS design easier to reason about:

This separation is the reason LayerFS does not put version information into a chunk. A chunk is just immutable bytes with a content-derived identity. FastCDC chooses its range; the CAS stores and verifies it; an ordered file representation records how the ranges reconstruct the file.

Structural COW operates one level higher than the file representation. When one file changes, it creates a new file manifest and new directory records only along that file’s path. Every unrelated file and subtree remains shared with the previous immutable root.

The resulting division of responsibility is:

1. FastCDC finds useful, reproducible boundaries without scanning the whole file for every candidate.
2. CAS gives each completed chunk an immutable identity and reuses equal bytes.
3. The file representation preserves chunk order, lengths, and exact reconstruction.
4. Structural COW rebuilds only the affected path and produces a new complete immutable root.

FastCDC is therefore a boundary policy, not the storage format. Changing the physical CAS layout or the way layers are persisted should not change the logical chunk ranges, chunk identities, or reconstructed bytes.

7. What Comes Next

At this point we can explain the complete chunking decision: start with a byte stream, update a content-derived fingerprint, apply the FastCDC policy, and emit bounded ranges. We also know why those ranges are useful: unchanged ranges can keep their CAS identities after a local edit.

One piece still sits above the chunker: a complete file needs an ordered, durable recipe for its chunks. A storage layer can build that representation by:

• hashing each completed chunk to its ChunkId;
• recording chunk IDs and lengths in order;
• reconstructing and verifying the original file bytes; and
• measuring how a small edit reuses existing chunks.

The planned Section 1.3 will take that file representation into the filesystem tree: one edited file, one rebuilt path, and one new immutable root. LayerStacks and agent-workspace history come later, after the root model is established.