cdc#

Content-defined chunking (FastCDC) in pure OCaml.

Overview#

Content-defined chunking splits a byte stream into variable-size chunks whose boundaries are decided by the bytes around them, not by absolute positions. Insert or delete a few bytes early in a stream and only the chunks around the edit change; every later chunk keeps its boundary and therefore its hash. That property is the building block of deduplicating storage and delta synchronization.

The algorithm is FastCDC (Xia et al., USENIX ATC 2016): a gear rolling hash with normalized chunking -- a harder boundary test before the expected chunk size and an easier one after it, narrowing the chunk-size distribution around the expected size.

• cut -- chunk boundaries of a string
• fold -- streaming chunker over a Bytesrw.Bytes.Reader.t, memory bounded by the maximum chunk size

The gear table is a fixed constant of this implementation: boundaries are stable across runs and versions, but there is no cross-implementation standard for them.

Installation#

$ opam install cdc

If opam cannot find the package, it may not yet be released in the public opam-repository. Add the overlay repository, then install it:

$ opam repo add samoht https://tangled.org/gazagnaire.org/opam-overlay.git
$ opam update
$ opam install cdc

Usage#

# let p = Cdc.params ~min_size:64 ~avg_size:256 ~max_size:1024 ();;
val p : Cdc.params = <abstr>
# let gen () = String.init 20000 (fun i -> Char.chr ((i * 31 + (i / 7)) land 0xff));;
val gen : unit -> string = <fun>
# let data = gen () in
  let chunks = Cdc.cut p data in
  List.for_all
    (fun (c : Cdc.chunk) -> c.len >= 1 && c.len <= 1024)
    chunks
- : bool = true
# let data = gen () in
  let chunks = Cdc.cut p data in
  String.concat ""
    (List.map (fun (c : Cdc.chunk) -> String.sub data c.off c.len) chunks)
  = data
- : bool = true

Chunk a stream without materializing it:

# let data = gen () in
  let r = Bytesrw.Bytes.Reader.of_string ~slice_length:4096 data in
  Cdc.fold p (fun n ~off:_ chunk -> n + String.length chunk) 0 r
  = String.length data
- : bool = true

License#

ISC -- see LICENSE.md.