README
¶
chunk
Cuts a stream into pieces at boundaries the content decides. Pure Go, no
dependencies, CGO_ENABLED=0.
Why
Cut every sixty-four kilobytes, and inserting one byte at the front moves every later boundary: nothing matches what was stored before, so the whole thing is written and sent again. Cut where a rolling hash over the last few bytes has some shape, and inserting one byte disturbs the two chunks around it and nothing else.
That is what makes deduplication and delta transfer work — a backup that keeps only what changed, an archive that fetches only the chunks it lacks, a content-addressed store where the same bytes are stored once.
The difference is measured rather than asserted. TestAnEditDisturbsOnlyWhatIsNearIt
inserts one byte a tenth of the way into 200 kB and counts what survives:
958 of 1067 chunks unchanged after inserting one byte at 10%
cutting every 256 bytes kept 0 of 782
Use
// A stream.
c := chunk.New(reader, chunk.Config{})
for {
offset, piece, err := c.Next()
if errors.Is(err, io.EOF) {
break
}
// …
}
// Bytes already in hand, for a caller that wants the pieces and nothing else.
pieces := chunk.Cut(chunk.Config{})(data)
Cut returns the shape a content-addressed store usually asks for — for
instance go-crdt/crdt's blob store, which cuts a file into operations of its
own and takes any chunker:
blobs.PutWith("figure.png", data, chunk.Cut(chunk.Config{}))
Where it comes from
The rolling hashes, the seed, the table and the boundary test are bita's, so a stream cut here is cut in the same places bita cuts it and an archive written by either is readable by the other.
They were written for bita and lived inside it, where nothing else could reach them. This is the same code with a name, so that the next thing needing content-defined chunks does not write its own.
What is not here, and must not be
Two other rolling sums live in this organisation and are not these: rdiff's
is librsync's, zsync2's is zsync's. All three are the same Fletcher family and
no two are the same function — different widths, different initial state,
differently packed digests, and zsync adds no offset to a byte where the other
two add thirty-one. On the same eight bytes:
chunk.RollSum 0x011c0740
rdiff.Rollsum 0x04d4011c
zsync.Rsum 0x00240078
That is not an oversight to tidy up. Each is a constant of a wire format
something else already wrote — a signature file, a .zsync header, an archive.
Sharing one would make this package's users agree with each other and one of
those formats unreadable.
Configuration
The zero Config is BuzHash over a sixteen-byte window, aiming at 64 KiB chunks
between 16 KiB and 16 MiB — bita's defaults. RollSumConfig is bita's other
hash, over the window it was tuned for.
Average sets how many bits of the hash a boundary needs, so it is rounded down
to a power of two; Min and Max bound what that can produce. A run of one
repeated byte never trips the test, so Max is what ends the chunk — without it
a file of zeroes would be a single chunk.
Licence
BSD-3-Clause.
Documentation
¶
Overview ¶
Package chunk cuts a stream into pieces at boundaries the content decides.
What it is for ¶
Anything that stores or sends a large thing in pieces wants the pieces to depend on the bytes rather than on how far into the stream they are. Cut every sixty-four kilobytes and inserting one byte at the front moves every later boundary, so nothing matches what was stored before and the whole thing is written and sent again. Cut where a rolling hash over the last few bytes has some shape, and inserting one byte disturbs the two chunks around it and nothing else.
That is the whole idea, and it is what makes deduplication and delta transfer work: a backup that keeps only what changed, an archive that fetches only the chunks it lacks, a content-addressed store where the same bytes are stored once.
Where it comes from ¶
The rolling hashes, the seed, the table and the boundary test are bita's, so a stream cut here is cut in the same places bita cuts it. They were written for github.com/go-deltasync/bita and lived inside it, where nothing else could reach them; this is the same code with a name, so that the next thing needing content-defined chunks does not write its own.
What is not here, and must not be ¶
Two other rolling sums live in this organisation, and they are not these: rdiff's is librsync's and zsync2's is zsync's. All three are the same Fletcher family, and none of them is the same function — the widths differ, the initial state differs, the digest is packed differently, and zsync adds no offset to a byte where the other two add thirty-one. On eight bytes they give three different answers.
That is not an oversight to be tidied up. Each is a constant of a wire format that something else already wrote: a signature file, a .zsync header, an archive. Sharing one of them would make this package's users agree with each other and one of those formats unreadable.
Using it ¶
For a stream, New and Chunker.Next. For bytes already in memory — a figure being put into a document, say — Cut returns the function a caller of that shape usually wants:
blobs.PutWith("figure.png", data, chunk.Cut(chunk.Config{}))
Index ¶
Examples ¶
Constants ¶
const ( // DefaultAverage is the chunk size boundaries are chosen to average. DefaultAverage = 64 * 1024 // DefaultMin and DefaultMax bound what an average is allowed to produce: a // run of bytes that never trips the boundary test would otherwise be one // chunk as long as the stream, and a stream that trips it constantly would // be one chunk per byte. DefaultMin = 16 * 1024 DefaultMax = 16 * 1024 * 1024 // DefaultWindow is the window a [BuzHash] rolls over. RollSum's is // RollSumWindow, because the two hashes were tuned separately. DefaultWindow = 16 // RollSumWindow is the window bita rolls a [RollSum] over. RollSumWindow = 64 )
The defaults, which are bita's.
Variables ¶
This section is empty.
Functions ¶
func BitsFromAverage ¶ added in v0.2.0
filled returns the config with every zero replaced by its default. BitsFromAverage returns how many boundary bits an average implies, by bita's arithmetic. It is what Config.Average is turned into, exposed because a caller writing an archive header has to record the count rather than the size.
func Cut ¶
Cut returns a function that cuts a byte slice, which is the shape a caller that only wants the pieces asks for — go-crdt's blob store, for one:
blobs.PutWith("figure.png", data, chunk.Cut(chunk.Config{}))
The config is read once, here, rather than on every call.
Example ¶
data := bytes.Repeat([]byte("the quick brown fox "), 5000)
pieces := Cut(Config{Average: 1024, Min: 256, Max: 8192})(data)
fmt.Println(len(pieces) > 1, len(rejoin(pieces)) == len(data))
Output: true true
Types ¶
type BuzHash ¶
type BuzHash struct {
// contains filtered or unexported fields
}
A BuzHash is the cyclic-polynomial rolling hash bita uses, over a window of a fixed number of bytes. It has a priming phase: until the window is full the hash is not a hash of a window and no boundary should be taken from it.
func NewBuzHash ¶
NewBuzHash returns one over a window of the given size.
type Chunker ¶
type Chunker struct {
// contains filtered or unexported fields
}
A Chunker cuts what it reads. It is not safe for concurrent use.
type Config ¶
type Config struct {
// Rolling makes the hash to roll. Nil is [NewBuzHash].
Rolling func(window int) Rolling
// Window is how many bytes the hash rolls over. Zero is [DefaultWindow].
Window int
// Average is the chunk size to aim for. Zero is [DefaultAverage].
//
// What it sets is how many bits of the hash a boundary needs, so it is
// rounded down to a power of two and two averages within a factor of two of
// each other cut the same way. The count is log2(Average) minus one, which
// is bita's — a boundary then falls every Average/2 bytes on average, and
// Min pushes the chunks that result back up towards Average. Aiming through
// the pair rather than through the mask alone is what makes the defaults
// come out near the size they name; see TestTheChunksComeOutNearTheAverage.
Average int
// Bits says how many bits of the hash a boundary needs, and overrides
// Average when it is set.
//
// It is here for a caller that has the count rather than a size to aim at:
// bita stores it in an archive header, and a chunker rebuilt to read that
// archive has to cut where the count says and not where a rounded average
// would. Zero means Average decides.
Bits int
// Min and Max bound a chunk. Zero is [DefaultMin] and [DefaultMax].
Min, Max int
}
A Config says where the cuts fall. The zero Config is BuzHash at the defaults above, which is what bita writes by default.
func BuzHashConfig ¶
func BuzHashConfig() Config
BuzHashConfig and RollSumConfig are bita's two rolling-hash configurations, each with the window that hash was tuned for.
func RollSumConfig ¶
func RollSumConfig() Config
type RollSum ¶
type RollSum struct {
// contains filtered or unexported fields
}
A RollSum is the rsync/bup rolling hash bita uses. Unlike BuzHash it needs no priming: its window starts as zeroes and rolls straight away. See bitar/src/rolling_hash/rollsum.rs. All arithmetic is u32 wrapping, which Go provides natively for uint32.
func NewRollSum ¶
NewRollSum returns one over a window of the given size.
func (*RollSum) Prime ¶
Prime is what BuzHash uses to fill its window. A RollSum has nothing to fill, so this does nothing and RollSum.Primed is true from the start.
type Rolling ¶
type Rolling interface {
// Prime feeds a byte while the window is still filling.
Prime(b byte)
// Primed reports whether the window is full.
Primed() bool
// Roll feeds a byte, dropping the one that leaves the window.
Roll(b byte)
// Sum is the hash of the window as it stands.
Sum() uint32
}
A Rolling is a rolling hash over a window of bytes: it is fed the stream one byte at a time and says what the last window's worth of it hashes to.
Prime and Primed exist because a hash may need its window filled before its value means anything. RollSum does not and says so; BuzHash does.
func NewBuzHashRolling ¶
NewBuzHashRolling and NewRollSumRolling are the two hashes as a Config wants them. They exist because a method set on a pointer type is not a func value until something writes one.
Source Files