vclock

README

vclock — A Go Vector Clock Implementation

This repository is a stripped-down version of the brilliant DistributedClocks/GoVector library. Unfortunately, the original library is outdated and has a few bugs that make its use impossible. This library is created as a drop-in replacement for github.com/DistributedClocks/GoVector/govec/vclock. Other functionality of the package is not implemented.

As of now, these are the major changes:

• include a working go.mod file with a specific tag
• fix a bug where ReturnVCString is non-deterministic (see this PR)
• fix a subtle bug in the vector clock comparison function (see this issue)
• introduce a Order() function that returns the relationship of two vector clocks, based on the Voldemort implementation of vector clocks
• improve documentation

To use this package in your code, download the latest version:

go get git.tu-berlin.de/mcc-fred/vclock

Then replace your import directives from

import (
    "github.com/DistributedClocks/GoVector/govec/vclock"
)

to

import (
    "git.tu-berlin.de/mcc-fred/vclock"
)

All code continues to be licensed under the MIT license.

Note that most development is on the TU Berlin GitLab instance. A GitHub mirror is provided for convenience.

Documentation

Overview

Package vclock implements vector clocks. Vector clocks are a way of capturing partial ordering of events in a distributed system. For more information see http://en.wikipedia.org/wiki/Vector_clock

Create a new vector clock with the New function:

vc := vclock.New()

Set the clock value for a given id:

vc.Set("A", 1)

Tick the clock for a given id (increment the value by 1):

vc.Tick("A")

Merge two vector clocks together:

vc.Merge(other)

Compare two vector clocks:

vc.Compare(other, vclock.Equal)

Get the relative ordering of two vector clocks:

vc.Order(other)

Index

• type Condition
• type VClock
  • func FromBytes(data []byte) (vc VClock, err error)
  • func New() VClock
  • func (vc VClock) Bytes() []byte
  • func (vc VClock) Compare(other VClock, cond Condition) bool
  • func (vc VClock) CompareOld(other VClock, cond Condition) bool
  • func (vc VClock) Copy() VClock
  • func (vc VClock) CopyFromMap(otherMap map[string]uint64) VClock
  • func (vc VClock) FindTicks(id string) (uint64, bool)
  • func (vc VClock) GetMap() map[string]uint64
  • func (vc VClock) LastUpdate() (last uint64)
  • func (vc VClock) Merge(other VClock)
  • func (vc VClock) Order(other VClock) Condition
  • func (vc VClock) PrintVC()
  • func (vc VClock) ReturnVCString() string
  • func (vc VClock) Set(id string, ticks uint64)
  • func (vc VClock) Tick(id string)

Types

type Condition

type Condition int

Condition constants define how to compare a vector clock against another, and may be ORed together when being provided to the Compare method. Use the Equal, Ancestor, Descendant, and Concurrent constants to compare vector clocks.

const (
	Equal Condition = 1 << iota
	Ancestor
	Descendant
	Concurrent
)

type VClock

type VClock map[string]uint64

VClock is the type of a vector clock. A VClock is a map of process ids (string) to clock values (uint64). Note that this implies that the zero clock value is 0.

func FromBytes

func FromBytes(data []byte) (vc VClock, err error)

FromBytes decodes a vector clock from a byte slice using the gob package.

func New

func New() VClock

New returns a new, empty vector clock.

func (VClock) Bytes

func (vc VClock) Bytes() []byte

Bytes returns an encoded vector clock using the gob package.

func (VClock) Compare

func (vc VClock) Compare(other VClock, cond Condition) bool

Compare takes another clock ("other") and determines if it is Equal, an Ancestor, Descendant, or Concurrent with the callees ("vc") clock. The condition is specified by the cond parameter, which may be ORed. For example, to check if two clocks are concurrent or descendants, you would call Compare(other, Concurrent|Descendant). If the condition is met, true is returned, otherwise false is returned.

func (VClock) CompareOld

func (vc VClock) CompareOld(other VClock, cond Condition) bool

CompareOld takes another clock and determines if it is Equal, an Ancestor, Descendant, or Concurrent with the callees clock. Deprecated: This is the original implementation of Compare, which is now deprecated. It is left here for reference.

func (VClock) Copy

func (vc VClock) Copy() VClock

Copy returns a deep copy of a vector clock.

func (VClock) CopyFromMap

func (vc VClock) CopyFromMap(otherMap map[string]uint64) VClock

CopyFromMap creates a shallow copy of a map that is compatible with the VClock type.

func (VClock) FindTicks

func (vc VClock) FindTicks(id string) (uint64, bool)

FindTicks returns the clock value for a given id or false if the id is not found. This is a convenience function for accessing the clock value of a given id, you can also access the clock value directly using the map syntax, e.g.: vc["A"].

func (VClock) GetMap

func (vc VClock) GetMap() map[string]uint64

GetMap returns the underlying map of the vector clock.

func (VClock) LastUpdate

func (vc VClock) LastUpdate() (last uint64)

LastUpdate returns the smallest clock value in the vector clock.

func (VClock) Merge

func (vc VClock) Merge(other VClock)

Merge takes the maximum of all clock values in other and updates the values of the callee. If the callee does not contain a given id, it is added to the callee with the value from other. Merge updates the callee vector clock in place.

func (VClock) Order

func (vc VClock) Order(other VClock) Condition

Order determines the relationship between two clocks. It returns Ancestor if the given clock other is an ancestor of the callee vc, Descendant if other is a descendant of vc, Equal if other and vc are equal, and Concurrent if other and vc are concurrent.

Two important notes about this implementation:

1. The return value is a constant, it is not ORed together. This means that if you want to compare the output, you can use the == operator. Note that we recommend using the Compare method instead.
2. If the clocks are equal, the return value is Equal. This is different from the original vector clock implementation, which returned Concurrent AND Equal.

func (VClock) PrintVC

func (vc VClock) PrintVC()

PrintVC prints the callees vector clock to stdout.

func (VClock) ReturnVCString

func (vc VClock) ReturnVCString() string

ReturnVCString returns a deterministic string encoding of a vector clock.

func (VClock) Set

func (vc VClock) Set(id string, ticks uint64)

Set sets the clock value of the given process id to the given value.

func (VClock) Tick

func (vc VClock) Tick(id string)

Tick increments the clock value of the given process id by 1. If the process id is not found in the clock, it is added with a value of 1.