hashsplit

type Node ¶

type Node struct {
	Nodes  []*Node
	Leaves [][]byte

	// Size is the number of bytes represented by this tree node.
	// For a level-0 node this is normally the lengths of the byte slices in Leaves, added together.
	// However, for some applications those byte slices are placeholders for the original data
	// (such as when the original data is saved aside to separate storage).
	// In those cases Size represents the original data, not the placeholder data in Leaves.
	//
	// For higher-level nodes, this is the sum of the Size fields in all child nodes.
	Size uint64

	// Offset is the byte position that this node represents in the original input stream,
	// before splitting.
	// It is equal to the sum of the Size fields of the siblings to this node's "left."
	// Applications can use the Offset field for random access by position to any chunk in the original input stream.
	Offset uint64
}

Node is a node in the tree built by a TreeBuilder. A interior node ("level 1" and higher) contains one or more subnodes as children. A leaf node ("level 0") contains one or more byte slices, which are normally hashsplit chunks of the input. Exactly one of Nodes and Leaves is non-empty.

func Seek(node *Node, pos uint64) *Node

type Splitter ¶

type Splitter struct {
	// MinSize is the minimum chunk size.
	// Only the final chunk may be smaller than this.
	// This should always be >= 64,
	// which is the rolling checksum "window size."
	// If it's less than the size of the checksum window,
	// then the same window can span multiple chunks,
	// meaning a chunk boundary is not independent of the preceding chunk.
	// If you leave this set to zero,
	// 64 is what you'll get.
	// If you really mean "I want no minimum,"
	// set this to 1.
	MinSize int

	// SplitBits is the number of trailing zero bits in the rolling checksum required to produce a chunk.
	// The default (what you get if you leave it set to zero) is 13,
	// which means a chunk boundary occurs on average once every 8,192 bytes.
	//
	// (But thanks to math, that doesn't mean that 8,192 is the median chunk size.
	// The median chunk size is actually the logarithm, base (2^SplitBits-1)/(2^SplitBits), of 0.5.
	// That makes the median chunk size 5,678 when SplitBits==13.)
	SplitBits uint
	// contains filtered or unexported fields
}

Splitter hashsplits a byte sequence into chunks. It implements the io.WriteCloser interface.

Hashsplitting is a way of dividing a byte stream into pieces based on the stream's content rather than on any predetermined chunk size. As the Splitter reads the stream it maintains a rolling checksum of the last several bytes. A chunk boundary occurs when the rolling checksum has enough trailing bits set to zero (where "enough" is a configurable setting that determines the average chunk size).

Hashsplitting has benefits when it comes to representing multiple, slightly different versions of the same data. Consider, for example, the problem of adding EXIF tags to a JPEG image file. The tags appear near the beginning of the file, and the bulk of the image data follows. If the file were divided into chunks at (say) 8-kilobyte boundaries, then adding EXIF data near the beginning would alter every following chunk, except in the lucky case where the size of the added data is an exact multiple of 8kb. With hashsplitting, only the chunks in the vicinity of the change are affected.

Hashsplitting is used to dramatically reduce storage and bandwidth requirements in projects like rsync, bup, and perkeep.

func NewSplitter(f func([]byte, uint) error) *Splitter

func (s *Splitter) Close() error

func (s *Splitter) Write(inp []byte) (int, error)

type TreeBuilder ¶

type TreeBuilder struct {
	// contains filtered or unexported fields
}

TreeBuilder assembles a sequence of chunks into a hashsplit tree.

A hashsplit tree provides another level of space-and-bandwidth savings over and above what Split gives you. Consider, again, the example of adding EXIF tags to a JPEG file. Although most chunks of the hashsplitted file will be the same before and after adding tags, the _list_ needed to reassemble those chunks into the original file will be very different: all the unaffected chunks must shift position to accommodate the new EXIF-containing chunks.

A hashsplit tree organizes that list into a tree instead, whose shape is determined by the content of the chunks, just as the chunk boundaries are. It has the property that only the tree nodes in the vicinity of the change will be affected. Most subtrees will remain the same.

Just as each chunk has a level L determined by the rolling checksum (see NewSplitter), so does each node in the tree have a level, N. Tree nodes at level 0 collect chunks at level 0, up to and including a chunk at level L>0; then a new level-0 node begins. Tree nodes at level N>0 collect nodes at level N-1 up to and including a chunk at level L>N; then a new level-N node begins.

var r io.Reader // Represents the source of some data.

tb := NewTreeBuilder()
err := Split(r, func(bytes []byte, level uint) error {
	tb.Add(bytes, len(bytes), level)
	return nil
})
if err != nil {
	panic(err)
}
// Get the root of the tree with tb.Root().

var r io.Reader // Represents the source of some data.

tb := NewTreeBuilder()
err := Split(r, func(bytes []byte, level uint) error {
	// Map level to a smaller range for wider fan-out.
	tb.Add(bytes, len(bytes), level/4)
	return nil
})
if err != nil {
	panic(err)
}

// Get the root of the tree with tb.Root().

var r io.Reader // Represents the source of some data.

// Represents any function that replaces a chunk with a compact representation of that chunk
// (like a hash or a lookup key).
var saveAside func([]byte) ([]byte, error)

tb := NewTreeBuilder()
err := Split(r, func(chunk []byte, level uint) error {
	size := len(chunk)

	// Replace chunk with a compact representation.
	repr, err := saveAside(chunk)
	if err != nil {
		return err
	}

	// Store the compact representation in the tree,
	// not the chunk itself;
	// but use the original chunk's size.
	tb.Add(repr, size, level)
	return nil
})
if err != nil {
	panic(err)
}

// Get the root of the tree with tb.Root().

func NewTreeBuilder() *TreeBuilder

func (tb *TreeBuilder) Add(bytes []byte, size int, level uint)

func (tb *TreeBuilder) Root() *Node