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)

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

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.

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

Constants define comparison conditions between pairs of vector clocks

type VClock

type VClock map[string]uint64

Vector clocks are maps of string to uint64 where the string is the id of the process, and the uint64 is the clock value

func FromBytes

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

FromBytes decodes a vector clock

func New

func New() VClock

New returns a new vector clock

func (VClock) Bytes

func (vc VClock) Bytes() []byte

Bytes returns an encoded vector clock

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 returs a copy of the clock

func (VClock) CopyFromMap

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

CopyFromMap copys a map to a vector clock

func (VClock) FindTicks

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

FindTicks returns the clock value for a given id, if a value is not found false is returned

func (VClock) GetMap

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

GetMap returns the map typed vector clock

func (VClock) LastUpdate

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

LastUpdate returns the clock value of the oldest clock

func (VClock) Merge

func (vc VClock) Merge(other VClock)

Merge takes the max of all clock values in other and updates the values of the callee

func (VClock) Order

func (vc VClock) Order(other VClock) Condition

Order determines the relationship between two clocks. It returns Ancestor if the callee is an ancestor of the other clock, Descendant if the callee is a descendant of the other clock, Equal if the clocks are equal, and Concurrent if the clocks 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.

This code is adapted from the Voldemort implementation of vector clocks: https://github.com/voldemort/voldemort/blob/master/src/java/voldemort/versioning/VectorClockUtils.java The original code is licensed under the Apache License, Version 2.0 http://www.apache.org/licenses/LICENSE-2.0 Copyright 2008-2013 LinkedIn, Inc.

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 string encoding of a vector clock

func (VClock) Set

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

Set assigns a clock value to a clock index

func (VClock) Tick

func (vc VClock) Tick(id string)

Tick has replaced the old update