vclock

package module
v1.3.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 6, 2023 License: MIT Imports: 9 Imported by: 0

README

Go Doc Go Report Card

vclock

vclock implements a vector clock, which can be used concurrently across goroutines.

The VClock instance can either maintain only the current state of the underlying Clock, or it can retain all the Events that create the history of change to the original Clock, in the order they are received. This history is available as a slice of *HistoryItem.

The VClock obeys the state of the parent context that is passed into either New function, ensuring that all resources are released correctly. Should the parent context end, then all subsequent calls to the VClock instance will return an error.

Vector clocks can be compared, and have four outcomes:

  • They are equal; i.e. each identifier in the Clocks being compared have identical values
  • One is the ancestor of the other. Both clocks will include the identifiers within the ancestoral clock, with the ancestor having at least one identifier value that is smaller than in the other clock
  • One is the descendant of the other. This is essentially the reverse of ancestor.
  • They are causally concurrent; i.e. there is no clear history linking them together.

Vector clocks can have identifiers that are arbitrarily long. To keep the size of the Clock small, the New functions include the argument shortener which is an interface of type IdentifierShortener. If provided, then the Vector clock will apply the functions from this interface to shorten the identifiers during updates, and recover the identifiers when the Clock is returned externally.

There are examples of specific use cases within example_test.go, but general use looks as follows:

Usage:

func main() {
    c, _ := New(context.Background(), Clock{"x":0, "y":0}, nil)
    defer c.Close()

    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(i int) {
            defer wg.Done()
            if i % 2 == 0 {
                c.Tick("x")
            } else {
                c.Tick("y")
            }
        }(i)        
    }

    wg.Wait()

    b, _ := c.Bytes()
}

Documentation

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrShortenerMustNotBeNil = errors.New("shortener cannot be nil")

Functions

This section is empty.

Types

type AllowedReq added in v1.1.0 

type AllowedReq interface {
	Clock | *respComp | *reqFullHistory | *reqGet | *reqHistory | *reqLastUpdate | *reqPrune | *reqSnap | *reqSnapShortenedIdentifiers | *SetInfo | *reqTick
}

type AllowedResp added in v1.1.0 

type AllowedResp interface {
	*respClock | *respErr | bool | *respGetter | *respGetterWithStatus | *respHistory | *respHistoryAll
}

type Clock added in v1.1.0 

type Clock map[string]uint64

Clock is the underlying type of the vector clock

type Event 

type Event struct {
	Type  EventType
	Set   *SetInfo
	Tick  string
	Merge Clock
}

Event captures the details of a specific update to the vector clock. Only one of the attributes will contain information.

func (*Event) String 

func (e *Event) String() string

type EventType 

type EventType uint

EventType describes the type of update within an Event 

const (
	Set EventType = 1 << iota
	Tick
	Merge
)

func (EventType) String 

func (e EventType) String() string

type HistoryItem 

type HistoryItem struct {
	HistoryId uint64
	Change    *Event
	Clock     Clock
}

HistoryItem stores details of a state change due to the specified Event, and holds the updated clock after the Event has been applied.

func (*HistoryItem) String 

func (h *HistoryItem) String() string

type IdentifierShortener added in v1.2.0 

type IdentifierShortener interface {
	Name() string                     // Name of the shortener - msut be unique
	Shorten(s string) string          // Returns the shortened version of the supplied string
	Recover(s string) (string, error) // Recovers the original string from the shortened version
	Bytes() ([]byte, error)           // The full map of shortened strings to original strings as a serialised ShortenedMap
	Merge(b []byte) error             // Merge the contents of the ShortenedMap into the instance
}

IdentifierShortener provides functions to shorten vector clock identifiers to minimise the overall memory footprint of the clock.

type InMemoryShortener added in v1.2.0 

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

InMemoryShortener uses a map to store the results of Shorten for a given string, so that it can be easily recovered.

func NewInMemoryShortener added in v1.3.0 

func NewInMemoryShortener(name string, shortener Shortener) (*InMemoryShortener, error)

NewInMemoryShortener creates an instance of InMemoryShortener that will use the specified Shortener

func (*InMemoryShortener) Bytes added in v1.3.0 

func (h *InMemoryShortener) Bytes() ([]byte, error)

func (*InMemoryShortener) Merge added in v1.3.0 

func (h *InMemoryShortener) Merge(b []byte) error

func (*InMemoryShortener) Name added in v1.3.0 

func (h *InMemoryShortener) Name() string

func (*InMemoryShortener) Recover added in v1.2.0 

func (h *InMemoryShortener) Recover(s string) (string, error)

func (*InMemoryShortener) Shorten added in v1.2.0 

func (h *InMemoryShortener) Shorten(s string) string

type SetInfo 

type SetInfo struct {
	Id    string
	Value uint64
}

SetInfo stores the value to be applied to the vector clock for the specified identifier.

func (*SetInfo) String 

func (s *SetInfo) String() string

type ShortenedMap added in v1.3.0 

type ShortenedMap map[string]string

ShortenedMap is the underlying type expected to be serialised by IdentifierShortener implementations

type Shortener added in v1.2.0 

type Shortener func(string) string

Shortener is the function that applies the transformation

type ShortenerFactory added in v1.3.0 

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

ShortenerFactory manages IdentifierShortener instances

func GetShortenerFactory added in v1.3.0 

func GetShortenerFactory() *ShortenerFactory

GetShortenerFactory returns the ShortenerFactory

func (*ShortenerFactory) Get added in v1.3.0 

func (f *ShortenerFactory) Get(name string) (IdentifierShortener, error)

Get returns the IdentifierShortener with the specified name, or an error if not found.

func (*ShortenerFactory) Names added in v1.3.0 

func (f *ShortenerFactory) Names() []string

Names returns the list of shorteners in the factory

func (*ShortenerFactory) Register added in v1.3.0 

func (f *ShortenerFactory) Register(shortener IdentifierShortener) error

Register adds the specified shortener, returns error if the shortener is already registered (i.e. key with the shortener name already exists)

type VClock 

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

VClock is an instance of a vector clock that can suppport concurrent use across multiple goroutines

func FromBytes 

func FromBytes(context context.Context, data []byte, shortenerName string) (vc *VClock, err error)

FromBytes decodes a vector clock. This requires both the serialised clock and also the name of the IdentifierShortener to be used (which may be empty string)

func FromBytesWithHistory added in v1.3.0 

func FromBytesWithHistory(context context.Context, data []byte, shortenerName string) (vc *VClock, err error)

FromBytesWithHistory decodes a vector clock and preserves history from this point forwards. This requires both the serialised clock and also the name of the IdentifierShortener to be used (which may be empty string)

func New 

func New(context context.Context, init Clock, shortenerName string) (*VClock, error)

New returns a VClock that is initialised with the specified Clock details, and which will not maintain any history. The specified shortener (which may be empty string) reduces the memory footprint of the vector clock if the identifiers are large strings.

Example 
ctx := context.Background()

c, _ := New(ctx, Clock{"x": 0, "y": 0}, "")
defer c.Close()

var wg sync.WaitGroup

for i := 0; i < 10; i++ {
	wg.Add(1)
	go func(i int) {
		defer wg.Done()
		if i%2 == 0 {
			c.Tick("x")
		} else {
			c.Tick("y")
		}
	}(i)
}

wg.Wait()

m, _ := c.GetClock()
fmt.Println(m)

Output:

map[x:5 y:5]

func NewWithHistory added in v1.1.0 

func NewWithHistory(context context.Context, init Clock, shortenerName string) (*VClock, error)

NewWithHistory returns a VClock that is initialised with the specified Clock details, and which will maintain a full history of all updates. The specified shortener (which may be empty string) reduces the memory footprint of the vector clock if the identifiers are large strings.

func (*VClock) AncestorOf 

func (vc *VClock) AncestorOf(other *VClock) (bool, error)

AncestorOf returns true if the contents of this clock instance shows that it can have descended from the other clock instance. This means that the other clock's identifiers must all be present in the this clock, and that the other clock's identifier values must all be the same or less than their value in this clock, with at least one of the other clock's identifier's value being less.

func (*VClock) Bytes 

func (vc *VClock) Bytes() ([]byte, error)

Bytes returns an encoded vector clock

func (*VClock) Close 

func (vc *VClock) Close() error

Close releases all resources associated with the VClock instance

func (*VClock) Concurrent 

func (vc *VClock) Concurrent(other *VClock) (bool, error)

Concurrent returns true if the contents of the other clock are either completely or partially distinct. Where partially distinct, matching identifiers in the clocks must have the same value.

func (*VClock) Copy 

func (vc *VClock) Copy() (*VClock, error)

Copy creates a new VClock instance, initialised to the values of this instance

func (*VClock) DescendsFrom 

func (vc *VClock) DescendsFrom(other *VClock) (bool, error)

DescendsFrom returns true if the contents of the other clock shows that it can have descended from this clock instance. This means that this clock's identifiers must all be present in the other clock, and that this clock's identifier values must all be the same or less than their value in the other clock, with at least one identifier's value being less.

func (*VClock) Equal 

func (vc *VClock) Equal(other *VClock) (bool, error)

Equal returns true if the contents of the other clock exactly match this instance.

func (*VClock) Get 

func (vc *VClock) Get(id string) (uint64, bool)

Get returns the latest clock value for the specified identifier, returning true if the identifier is found, otherwise false

func (*VClock) GetClock added in v1.3.0 

func (vc *VClock) GetClock() (Clock, error)

GetClock returns a copy of the complete vector clock map

func (*VClock) GetFullHistory 

func (vc *VClock) GetFullHistory() ([]*HistoryItem, error)

GetFullHistory returns a copy of each state change of the vectory clock map, including the Event detail of the change as well as new state of the clock

func (*VClock) GetHistory 

func (vc *VClock) GetHistory() ([]Clock, error)

GetHistory returns a copy of each state change of the vector clock map

func (*VClock) LastUpdate 

func (vc *VClock) LastUpdate() (string, uint64, error)

LastUpdate returns the latest clock time and its associated identifier

func (*VClock) Merge 

func (vc *VClock) Merge(other *VClock) error

Merge combines this clock with the other clock. The other clock must not be nil, and neither must be closed

func (*VClock) Prune 

func (vc *VClock) Prune() error

Prune resets the clock history, so that only the latest is available

func (*VClock) Set 

func (vc *VClock) Set(id string, v uint64) error

Set assigns the specified value to the given clock identifier. The identifier must not be an empty string, nor can an identifier be set more than once

func (*VClock) Tick 

func (vc *VClock) Tick(id string) error

Tick increments the clock with the specified identifier. An error is raised if the identifier is not found in the vector clock

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.