README
¶
Conflict-Free Replicated Versions (CFRV)
This package implements conflict-free replicated versions of multiple types. A conflict-free version number implemented on a distributed system means that two versions can be concurrently generated but still be ordered. Unlike auto-incrementing primary keys or sequences, this means that versions are structs that contain additional information.
The simplest type of CFRV (and the primary implementation of this package) I typically refer to as a Lamport Scalar. Each replica assigns scalar version numbers with a monotonically increasing counter and additionally include a unique process id. When a version is replicated locally, the counter is updated to the latest scalar. If two versions have the same scalar, then the process id is used to break the tie (e.g. the version with the lower process id is ordered before the later one).
Other types of CFRVs include vector and matrix clocks and more complex data structures (even things like TrueTime!). This package may implement these in the future, but primarily relies on vector component representations.
Rules for vectors:
- All versions must be monotonically increasing
- All versions must be unique and able to be ordered
- Versions must point to their parent to show version sequences
Documentation
¶
Overview ¶
Package cfrv implements conflict-free replicated versions of multiple types. A conflict-free version number implemented on a distributed system means that two versions can be concurrently generated but still be ordered. Unlike auto-incrementing primary keys or sequences, this means that versions are structs that contain additional information.
The simplest type of CFRV (and the primary implementation of this package) is typically referred to as a Lamport Scalar. Each replica assigns scalar version numbers with a monotonically increasing counter and additionally include a unique process id. When a version is replicated locally, the counter is updated to the latest scalar. If two versions have the same scalar, then the process id is used to break the tie (e.g. the version with the lower process id is ordered before the later one).
Other types of CFRVs include vector and matrix clocks and more complex data structures (even things like TrueTime!). This package may implement these in the future, but primarily relies on vector component representations.
Index ¶
Constants ¶
This section is empty.
Variables ¶
var NullVersion = Version{0, 0}
NullVersion is the zero value version that does not exist.
Functions ¶
This section is empty.
Types ¶
type CFRV ¶
type CFRV interface {
IsZero() bool // Returns true if the version is the zero value
Equals(other CFRV) bool // Returns true if version == other
Greater(other CFRV) bool // Returns true if version > other
GreaterEqual(other CFRV) bool // Returns true if version >= other
Lesser(other CFRV) bool // Returns true if version < other
LesserEqual(other CFRV) bool // Returns true if version <= other
String() string // Returns a parseable string representation of the version
Parse(s string) error // Parses the string into the version struct
}
CFRV describes the behavior of a conflict-free replicated version data structure, particularly the methods for comparing two versions to each other to order the versions. All CFRVs must implement this interface to be used interchangeably in systems with varying requirements.
type Factory ¶
type Factory interface {
Next() CFRV // return the next version for the given key
Update(vers CFRV) // update the state of the factory with the given version
Parse(s string) (CFRV, error) // parse the version from a string and return
}
Factory describes the behavior of a datastructure that generates conflict- free replicated versions. The factory maintains the global state to issue new versions, allowing version objects themselves to be stateless. Factories maintain versions for all objects in the system (even if there is just one) therefore they must identify the object by a unique name, the key. Factories that don't support keys can simply accept an empty string.
type Version ¶
type Version struct {
Scalar uint64 // monotonically increasing scalar version number (starts at one)
PID uint16 // process identifier for tie-breaks (should not be zero)
}
Version implements conflict-free or concurrent versioning for objects.
func ParseVersion ¶
ParseVersion converts a version string into a version object.
func (Version) GreaterEqual ¶
GreaterEqual returns true if the local version is greater than or equal to the other version.
func (Version) LesserEqual ¶
LesserEqual returns true if the local version is less than or equal to the other version.
type VersionFactory ¶
type VersionFactory struct {
// contains filtered or unexported fields
}
VersionFactory tracks version information and returns new versions on a per-key basis. Implements Lamport scalar versioning. Note that the factory is not thread-safe and should be used in a thread-safe object.
func (*VersionFactory) Next ¶
func (f *VersionFactory) Next(key string) *Version
Next creates and returns the next version for the given key.
func (*VersionFactory) Update ¶
func (f *VersionFactory) Update(key string, vers *Version)
Update the latest version with the version for the given key.
Source Files