clock

Documentation

Overview

Package clock implements a logical clock, tracking changes at multiple peers.

Is is inspired by the paper "File Synchronization with Vector Time Pairs" and the Tra software. This structure avoids the need for tombstones.

http://publications.csail.mit.edu/tmp/MIT-CSAIL-TR-2005-014.pdf
http://swtch.com/tra/

Index

• Constants
• Variables
• type Action
  • func Sync(a, b *Clock) Action
  • func SyncToMissing(a, b *Clock) Action
  • func (i Action) String() string
• type Clock
  • func Create(id Peer, now Epoch) *Clock
  • func TombstoneFromParent(parent *Clock) *Clock
  • func (v *Clock) MarshalBinary() ([]byte, error)
  • func (c *Clock) ResolveNew(other *Clock)
  • func (c *Clock) ResolveOurs(other *Clock)
  • func (c *Clock) ResolveTheirs(other *Clock)
  • func (c *Clock) RewritePeers(m map[Peer]Peer) error
  • func (c Clock) String() string
  • func (c *Clock) Tombstone()
  • func (v *Clock) UnmarshalBinary(p []byte) error
  • func (c *Clock) Update(id Peer, now Epoch)
  • func (c *Clock) UpdateFromChild(child *Clock) bool
  • func (c *Clock) UpdateFromParent(parent *Clock)
  • func (c *Clock) UpdateParent(id Peer, now Epoch)
  • func (c *Clock) UpdateSync(id Peer, now Epoch)
• type Epoch
  • func (e *Epoch) MarshalBinary() ([]byte, error)
  • func (e *Epoch) UnmarshalBinary(data []byte) error
• type Peer

Constants

const MaxPeer = ^Peer(0)

MaxPeer is the largest possible value a Peer can have.

Variables

var (
	ErrRewritePeerNotMapped = errors.New("cannot rewrite peer id for an unknown peer")
)

Types

type Action

type Action int

Action is a suggested action to take to combine two data items.

The zero value of Action is not valid.

const (

	// Copy means that the incoming version is newer, and its data
	// should be used.
	Copy Action
	// Nothing means the local version is newer (or same), and data
	// should not change.
	Nothing
	// Conflict means the two versions have diverged.
	Conflict
)

func Sync

func Sync(a, b *Clock) Action

Sync returns what action receiving state from A to B should cause us to take.

func SyncToMissing

func SyncToMissing(a, b *Clock) Action

SyncToMissing returns what action receiving state from A to B should cause us to take. B does not exist currently.

func (Action) String

func (i Action) String() string

type Clock

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

Clock is a logical clock.

The zero value is a valid empty clock, but most callers should call Create to get the creation time set up.

func Create

func Create(id Peer, now Epoch) *Clock

Create returns a new Vector Pair that knows it was created by id at time now.

func TombstoneFromParent

func TombstoneFromParent(parent *Clock) *Clock

TombstoneFromParent returns a new tombstone clock based on the parent.

func (*Clock) MarshalBinary

func (v *Clock) MarshalBinary() ([]byte, error)

MarshalBinary encodes Version into binary form.

func (*Clock) ResolveNew

func (c *Clock) ResolveNew(other *Clock)

ResolveNew records a conflict resolution in favor of newly created content.

func (*Clock) ResolveOurs

func (c *Clock) ResolveOurs(other *Clock)

ResolveOurs records a conflict resolution in favor of us.

func (*Clock) ResolveTheirs

func (c *Clock) ResolveTheirs(other *Clock)

ResolveTheirs records a conflict resolution in favor of other.

func (*Clock) RewritePeers

func (c *Clock) RewritePeers(m map[Peer]Peer) error

RewritePeers updates the peer identifiers in the clock based on the given mapping. This is useful because the short identifiers are not globally allocated.

Returns ErrRewritePeerNotMapped if the clock contains a peer not present in the map. If an error occurs, the clock is in an undefined state and must not be used.

func (Clock) String

func (c Clock) String() string

func (*Clock) Tombstone

func (c *Clock) Tombstone()

Tombstone changes clock into a tombstone.

func (*Clock) UnmarshalBinary

func (v *Clock) UnmarshalBinary(p []byte) error

UnmarshalBinary decodes Version from binary form.

func (*Clock) Update

func (c *Clock) Update(id Peer, now Epoch)

Update adds or updates the version vector entry for id to point to time now.

As an optimization, it removes all the other modification time entries. This is only safe for files, not directories; see section 3.5.2 "Encoding Modification Times" of the Tra paper.

Caller guarantees that one of the following is true:

• now is greater than any old value seen for peer id
• now is equal to an earlier value for this peer id, and no other peer ids have been updated since that Update

func (*Clock) UpdateFromChild

func (c *Clock) UpdateFromChild(child *Clock) bool

UpdateFromChild tracks child modification times in the parent.

Return value reports whether s changed.

func (*Clock) UpdateFromParent

func (c *Clock) UpdateFromParent(parent *Clock)

UpdateFromParent simplifies child sync times based on the parent.

func (*Clock) UpdateParent

func (c *Clock) UpdateParent(id Peer, now Epoch)

UpdateParent is like Update, but does not simplify the modification time version vector. It is safe to use for directories and other entities where updates are not necessarily sequenced.

Caller guarantees if an entry exists for id already, now is greater than or equal to the old value.

func (*Clock) UpdateSync

func (c *Clock) UpdateSync(id Peer, now Epoch)

UpdateSync updates the sync time only for id to point to time now.

Caller guarantees if an entry exists for id already, now is greater than or equal to the old value.

type Epoch

type Epoch uint64

Epoch is a logical clock timestamp. Time 0 is never valid.

func (*Epoch) MarshalBinary

func (e *Epoch) MarshalBinary() ([]byte, error)

func (*Epoch) UnmarshalBinary

func (e *Epoch) UnmarshalBinary(data []byte) error

type Peer

type Peer uint32

A Peer is a replica that may create new versions of the tracked data. Peers are identified by small unsigned integers, for efficiency.