wsync

Documentation

Overview

Package wsync computes a list of operations needed to mutate one file into another file, re-using as much of the former as possible.

Base on code from: https://bitbucket.org/kardianos/rsync/ Original rsync algorithm: http://www.samba.org/~tridge/phd_thesis.pdf

The main change in our fork is supporting blocks of sizes less than the context's block size (instead of just passing them as OpData), and being able to pick from a hash library that can span multiple files, and not just the 'old version' of a file (at the same path). This allows us to handle renames gracefully (incl. partial rewrites)

Definitions

Source: The final content.
Target: The content to be made into final content.
Signature: The sequence of hashes used to identify the content.

Index

• Constants
• type BlockHash
• type BlockLibrary
  • func NewBlockLibrary(hashes []BlockHash) *BlockLibrary
• type Context
  • func NewContext(BlockSize int) *Context
  • func (ctx *Context) ApplyPatch(output io.Writer, pool lake.Pool, ops chan Operation) error
  • func (ctx *Context) ApplyPatchFull(output io.Writer, pool lake.Pool, ops chan Operation, failFast bool) error
  • func (ctx *Context) ApplySingle(output io.Writer, pool lake.Pool, op Operation) error
  • func (ctx *Context) ApplySingleFull(output io.Writer, pool lake.Pool, op Operation, failFast bool) error
  • func (ctx *Context) ComputeDiff(source io.Reader, library *BlockLibrary, ops OperationWriter, ...) (err error)
  • func (ctx *Context) CreateSignature(cctx context.Context, fileIndex int64, fileReader io.Reader, ...) error
  • func (ctx *Context) HashBlock(block []byte) (weakHash uint32, strongHash []byte)
• type OpType
• type Operation
• type OperationWriter
• type SignatureWriter

Constants

const MaxDataOp = (4 * 1024 * 1024)

MaxDataOp is the maximum number of 'fresh bytes' that can be contained in a single Data operation

Types

type BlockHash

type BlockHash struct {
	FileIndex  int64
	BlockIndex int64
	WeakHash   uint32

	// ShortSize specifies the block size when non-zero
	ShortSize int32

	StrongHash []byte
}

BlockHash is a signature hash item generated from target.

type BlockLibrary

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

A BlockLibrary contains a collection of weak+strong block hashes, indexed by their weak-hashes for fast lookup.

func NewBlockLibrary

func NewBlockLibrary(hashes []BlockHash) *BlockLibrary

NewBlockLibrary returns a new block library containing all the given hashes, for fast lookup later.

type Context

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

Context holds the state during a sync operation

func NewContext

func NewContext(BlockSize int) *Context

NewContext creates a new Context, given a blocksize. It uses MD5 as a 'strong hash' (in the sense of an RSync paper, and compared to the very weak rolling hash)

func (*Context) ApplyPatch

func (ctx *Context) ApplyPatch(output io.Writer, pool lake.Pool, ops chan Operation) error

ApplyPatch applies the difference to the target.

func (*Context) ApplyPatchFull

func (ctx *Context) ApplyPatchFull(output io.Writer, pool lake.Pool, ops chan Operation, failFast bool) error

ApplyPatchFull is like ApplyPatch but accepts an ApplyWound channel

func (*Context) ApplySingle

func (ctx *Context) ApplySingle(output io.Writer, pool lake.Pool, op Operation) error

func (*Context) ApplySingleFull

func (ctx *Context) ApplySingleFull(output io.Writer, pool lake.Pool, op Operation, failFast bool) error

func (*Context) ComputeDiff

func (ctx *Context) ComputeDiff(source io.Reader, library *BlockLibrary, ops OperationWriter, preferredFileIndex int64) (err error)

ComputeDiff creates the operation list to mutate the target signature into the source. Any data operation from the OperationWriter must have the data copied out within the span of the function; the data buffer underlying the operation data is reused.

func (*Context) CreateSignature

func (ctx *Context) CreateSignature(cctx context.Context, fileIndex int64, fileReader io.Reader, writeHash SignatureWriter) error

CreateSignature calculate the signature of target.

func (*Context) HashBlock

func (ctx *Context) HashBlock(block []byte) (weakHash uint32, strongHash []byte)

type OpType

type OpType byte

An OpType describes the type of a sync operation

const (
	// OpBlockRange is a type of operation where a block of bytes is copied
	// from an old file into the file we're reconstructing
	OpBlockRange OpType = iota

	// OpData is a type of operation where fresh bytes are pasted into
	// the file we're reconstructing, because we weren't able to re-use
	// data from the old files set
	OpData
)

type Operation

type Operation struct {
	Type       OpType
	FileIndex  int64
	BlockIndex int64
	BlockSpan  int64
	Data       []byte
}

Operation describes a step required to mutate target to align to source.

type OperationWriter

type OperationWriter func(op Operation) error

An OperationWriter consumes sync operations and does whatever it wants with them

type SignatureWriter

type SignatureWriter func(hash BlockHash) error

A SignatureWriter consumes block hashes and does whatever it wants with them