rdx

package
v0.0.0-...-8a4113d Latest Latest
Warning

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

 Go to latest Published: Nov 22, 2024 License: MIT Imports: 12 Imported by: 0

README

Replicated Data Interchange (RDX CRDT) library

Our goal here is to create a format and a library for data replication using state-of-the-art Replicated Data Types. Replicated Data interchange format (RDX) is like protobuf, but CRDT. Apart from RPC applications, one can use it for data storage, distributed and asynchronous data exchange and in other similar applications. RDX fully supports local-first, offline-first and peer-to-peer replication, with no central server required, as any two replicas can merge their data. By installing RDX data types as merge operators in an LSM database (leveldb, RocksDB, pebble, Cassandra, etc) one can effectively have a CRDT database (which Chotki basically is).

We will implement unified CRDTs able to synchronize using operations, full states or deltas. Types may imply causal consistency of updates in matters of performance, but their correctness does not depend on that. RDX data types are fully commutative, associative and idempotent. Hence, immune to reordering or duplication of updates.

The default syncing protocol (not described here) generally relies on version vectors. Do not confuse that with vector clocks used by Amazon Dynamo and similar systems. While there are strong parallels, inner workings of VV and VC are not identical.

Data types

Our objects can have fields of the following CRDT types. Each type is named by a letter.

  1. last-write-wins variables (I for int64, S for string, F is float64, and R is id64)
  2. counters, N increment-only uint64 and Z two-way int64
  3. maps (M), like key-value maps, where keys and values are FIRST
  4. sets (E), contain arbitrary FIRST elements
  5. arrays (L) of arbitrary FIRST elements
  6. version vectors (V)
  7. codegen

The format and the merge rules are as follows.

FIRST Float, Integer, Reference, String, Term

The last-write-wins register is the simplest data type to implement. For each LWW field, we only need the latest "winner" op containing the logical timestamp and the value per se. A logical timestamp is a pair {rev, src} where rev is the revision number and src is the id of the author. For example, let's see how a bare (no TLV envelope) I int64 -11 would look like, assuming it is the 4th revision of the register autored by replica #5. The TLV would look like: 32 08 05 15 (hex) where 0x15 is a zig-zag encoded and zipped -11, while 32 08 05 is a tiny ToyTLV record for a zipped pair of ints, 4 (signed, zig-zagged, so 08) and 5 (unsigned, so 05). If we add a ToyTLV envelope, that becomes 69 04 32 08 05 15 (type of record I, length 4, then the bare part).

String S values are simply UTF-8 strings. Int64 I, float64 F and id64 R values get compressed using zip_int routines. Overlong encodings are forbidden both for strings and for zip-ints!

T ops have a timestamp, but no value. That is the equivalent of a nil or void value. Those are used as placeholders in various cases.

The string value for FIRST types is as follows:

  1. F the e-notation, JSON-like
  2. I signed integer notation,
  3. R 5-8-3 hex notation (e.g. c187-3a62-12)
  4. S double-quoted JSON-like, e.g. "Sarah O'Connor"
  5. T null

Merge rules for LWW are straighforward:

  1. higher revision wins
  2. in case of a tie, higher value wins (like bytes.Compare())
  3. in case of a tie, who cares, but higher replica id wins
NZ Counters

N are increment-only counters. Their TLV state is a sequence of T records containing zipped uint64 pairs {val,src}, the counter value and source replica id. As the counter is inc-only, we may use the value itself as a revision number. The merge operator is per-replica max, as later versions are greater. The native value is the sum of all replica values (sum of contributions).

Z are two-way counters (inc/dec). Their TLV format is a sequence of I records each having {rev,src} metadata as described in the FIRST section. One record corresponds to one source, per-source merge rules are same as LWW. The native value is the sum of all I values.

E Eulerian

Generic sets containing any FIRST elements. The TLV format is a sequence of enveloped FIRST records. It can contain records with negative revision numbers. Those are tombstones (deleted entries). For example, I{4,5}-11 from the FIRST example would go as 69 04 32 08 05 15. Then, if replica #3 would want to remove that entry, it will issue a tombstone op I{-5,3}-11 or 69 04 32 09 03 15. Here, the version number changes from 08 to 09 or 4 to -5, the author changes to 3.

Within a set, the ops are sorted in the value order. Namely, if the type differs, they go in the alphabetical order (F, I, R, S, T). If the type is the same, they go in the ascending order, as per strcmp or bytes.Compare. That way, merging multiple versions of a set only requires one parallel pass of those, no additional allocation or sorting, very much like mergesort works.

The string value for a set is like {1,2,3} where 1,2,3 are FIRST elements of the set.

M Mapping

Generic maps, mapping any FIRST value to any other FIRST value. The TLV format is a sequence of enveloped key-value op pairs. Any update should also contain the affected key-value pairs. Deleted entries might have T values (the key is present, the value is null) or the key might have a negative revision (no such key present).

Pairs are sorted in the value-order of their keys. When merging two pairs having an identical value of their keys, both the key and the value ops are merged according to the LWW rules. As with E sets, this only requires one parallel pass of the versions.

The string value for a map is like {4:null, "key":"value"}

L Linear

Generic arrays store any FIRST elements. Internally, L are Causal Trees (also known as Replicated Growable Arrays, RGAs). The TLV format is a sequence of enveloped FIRST ops. The order of the sequence is a weave, i.e. ops go in the same order as they appear(ed) in the resulting array. Deleted ops change to tombstones, same as E.

The merging procedure follows the tree-traversal logic. Any change to an array must have a form of subtrees, each one arranged in the same weave order, each one prepended with a T op specifying its attachment point in the edited tree.

Deletions look like T ops with negative revision numbers. As an example, suppose we have an array authored by #3 I{1,3}1 I{2,3}2 I{3,3}3 or [1,2,3] and replica #4 wants to delete the first entry. Then, it issues a patch T{1,3}T{-4,4} that merges to produce I{1,3}1 T{-4,4} I{2,3}2 I{3,3}3 or [2,3].

The string value for an array is like [1,2,3]

V Version vector

Version vector is a way to track dataset versions in a causally ordered system. It is a vector of seq numbers, where each seq is the version of the state as seen by each respective replica. Alternatively, that is a map {src: seq}, where src is the replica id. It is assumed, that we received updates from replica src all the way up to seq.

Bare TLV for a version vector is a sequence of V records (yes, V nested in V) each containing one id64 as a zipped seq-src pair (see ZipUint64Pair). The sequence is sorted in the ascenting order of record bytes, like bytes.Compare().

The merge algorithm for version vectors is simple: take the maximum seq for each src. Note that seq=0 is distinct from having no record.

Data type implementation

To fully implement an RDT one has to implement these 10 functions. The function name starts with the type name letter, here we imply I last-write-wins int64.

    // Xvalid verifies validity of a bare TLV record.
    // Any other function may assume the input is valid.
    func Ivalid(tlv []byte) bool 


    // Xstring converts a TLV representation into a string.
    func Istring(tlv []byte) (txt string) 

    // Xparse converts a string back into bare TLV.
    // Must round-trip with Xstring.
    func Iparse(txt string) (tlv []byte) 


    // Xtlv converts the native type into a TLV, zero metadata.
    func Itlv(i int64) (tlv []byte)

    // Xnative converts TLV into the native value.
    // Must round-trip with Xtlv.
    func Inative(tlv []byte) int64


    // Xdelta produces a TLV value that, once merged with
    // the old TLV value using Xmerge, will produce the new
    // native value using Xnative. Returns nil if none needed.
    // This function we need to *save changes* from a native
    // object/struct into RDX.
    func Idelta(tlv []byte, new_val int64) (tlv_delta []byte) 

    // Xmerge CRDT-merges several bare TLV values into the
    // resulting one. For example, given two I records
    // {3,8}15 and {4,1}44 will return {4,1}44 as version 4 is
    // newer than version 3.
    func Imerge(tlvs [][]byte) (tlv []byte) 

    // Xdiff produces a TLV delta given a TLV value and a
    // version vector of suspected changes (may skip this).
    func Idiff(tlv []byte, vvdiff VV) (tlv []byte)

Serialization format

We use the ToyTLV format for enveloping/nesting all data. That is a bare-bones type-length-value format with zero semantics. What we put into ToyTLV envelopes is integers, strings, and floats. Strings are UTF-8, no surprises. Floats are taken as raw bits and treated same as integers. id64 is stored as a compressed pair of integers.

A note on integer compression. From the fact that protobuf has about ten integer types, one can guess that things can be complicated here. We use ZipInt routines to produce efficient varints in a TLV format (differently from protobuf which has a separate bit-level LEB128 coding for ints).

  • ZipUint64 packs an integer skipping all leading zeroes
  • ZipUint64Pair packs a pair of ints, each one taking 1,2,4 or 8 bytes
  • ZipZagInt64 packs a signed integer using the zig-zag coding
  • ZipFloat64 packs a float (integers and binary fractions pack well)

id64 and logical timestamps get packed as pairs of uint64s. All zip codings are little-endian.

Enveloping

RDX values can be bare, enveloped or double-enveloped. We use bare values when we already know what field of what object we are dealing with and what RDT it belongs to. That might be the case when we read a value from a key-value storage where the key contains object id, field and RDT. In such a case, a bare Integer is like {3,2}1 or 32 03 02 02.

Within a network packet, that integer may need to be single-enveloped: I({3,2}1) or 69 04 32 03 02 02 assuming the other metadata is known from the context.

A bare ELM or NZ value would only contain a sequence of single-enveloped FIRST values. To make that single-enveloped we only prepend a TLV header.

In case we also have to convey the rest of the metadata, namely the object id and the field, we have to use the double-enveloped form. For a simple map[string]string{"Key":"Value"} that looks like: M({b0b-af0-3} S({0,0}"Key") S({0,0}"Value")) or 6D 15 36 03 00 af 00 0b 0b 73 04 30 4b 65 79 73 06 30 56 61 6c 75 65. For FIRST values, there is no need to use two nested TLV records, so a double-enveloped Integer looks like: I({b0b-af0-7}{3,2}1)

Object/fields ids are serialized as tiny ZipUint64Pairs. Revisions are serialized as tiny ZipIntUint64Pairs.

Documentation

Index

Constants

View Source 
const (
	MergeA = iota
	MergeAB
	MergeB
	MergeBA
)
View Source 
const (
	None      = byte(0)
	Float     = byte('F')
	Integer   = byte('I')
	Reference = byte('R')
	String    = byte('S')
	Term      = byte('T')
	Natural   = byte('N')
	NInc      = byte('n')
	ZCounter  = byte('Z')
	ZInc      = byte('z')
	Eulerian  = byte('E')
	Linear    = byte('L')
	Mapping   = byte('M')
	VVector   = byte('V')
)
View Source 
const (
	RdxOOpen = iota
	RdxOClose
	RdxAOpen
	RdxAClose
	RdxComma
	RdxColon
	RdxDot
)
View Source 
const (
	VvSeen = -1
	VvNext = 0
	VvGap  = 1
)
View Source 
const BadId = ID(0xffffffffffffffff)
View Source 
const Bytes1 = 0xff
View Source 
const Bytes2 = 0xffff
View Source 
const Bytes4 = 0xffffffff
View Source 
const Hex = "0123456789abcdef"
View Source 
const Hex583Len = 18
View Source 
const MaxSrc = (1 << SrcBits) - 1
View Source 
const OffBits = 12
View Source 
const OffMask = ID(1<<OffBits) - 1
View Source 
const ProBits = SeqBits + OffBits
View Source 
const ProInc = ID(1 << OffBits)
View Source 
const ProMask = uint64(uint64(1)<<ProBits) - 1
View Source 
const RdxMaxNesting = 64
View Source 
const SeqBits = 32
View Source 
const SeqOne = 1 << OffBits
View Source 
const SrcBits = 20
View Source 
const ValidZipPairLen = 0xe880 ^ 0xffff
View Source 
const ZeroId = ID(0)

Variables

View Source 
var ErrBadFIRST = errors.New("bad FIRST record")
View Source 
var ErrBadId = errors.New("not an expected id")
View Source 
var ErrBadPacket = errors.New("bad packet")
View Source 
var ErrBadRdx = errors.New("bad RDX syntax")
View Source 
var ErrBadV0Record = errors.New("bad V0 record")
View Source 
var ErrBadVRecord = errors.New("bad V record")
View Source 
var ErrBadValueForAType = errors.New("rdx: bad value for the type")
View Source 
var ErrGap = errors.New("id sequence gap")
View Source 
var ErrSeen = errors.New("previously seen id")
View Source 
var MalformedStringEscapeError = errors.New("malformed string escape")
View Source 
var RdxSep = []byte("{}[],:.")

Functions

func Amerge 

func Amerge(tlvs [][]byte) (merged []byte)

func Atlv 

func Atlv(log LogT) (tlv []byte)

func COYdefault 

func COYdefault() []byte

func Cstring 

func Cstring(tlv []byte) string

func DiffFIRST 

func DiffFIRST(tlv []byte, vvdiff VV) []byte

func ELMdefault 

func ELMdefault() (tlv []byte)

func ELMstring 

func ELMstring(tlv []byte) string

func Edelta 

func Edelta(tlv []byte, new_val int64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Ediff 

func Ediff(tlv []byte, vvdiff VV) []byte

func Emerge 

func Emerge(tlvs [][]byte) (merged []byte)

merge TLV values

func Eparse 

func Eparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Estring 

func Estring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Evalid 

func Evalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func FIRSTcompare 

func FIRSTcompare(a, b []byte) int

func FIRSTdefault 

func FIRSTdefault(rdt byte) []byte

func FIRSTparsee 

func FIRSTparsee(rdt byte, val string) (tlv []byte)

func FIRSTparsez 

func FIRSTparsez(bulk []byte) (zrev uint64, src uint64, value []byte)

same as ParseFIRST, but the Rev number is zigzagged

func FIRSTrdx2tlv 

func FIRSTrdx2tlv(a *RDX) (tlv []byte)

func FIRSTrdxs2tlv 

func FIRSTrdxs2tlv(a []RDX) (tlv []byte)

func FIRSTrdxs2tlvs 

func FIRSTrdxs2tlvs(a []RDX) (tlv protocol.Records)

func FIRSTtlv 

func FIRSTtlv(rev int64, src uint64, value []byte) (bulk []byte)

func Fdelta 

func Fdelta(tlv []byte, new_val float64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Fdiff 

func Fdiff(tlv []byte, vvdiff VV) []byte

func Fmerge 

func Fmerge(tlvs [][]byte) (tlv []byte)

merge TLV values

func Fnative 

func Fnative(tlv []byte) float64

convert a TLV value to a native golang value

func Fparse 

func Fparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Fstring 

func Fstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Ftlv 

func Ftlv(i float64) (tlv []byte)

convert native golang value into a TLV form

func Fvalid 

func Fvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Idefault 

func Idefault() []byte

func Idelta 

func Idelta(tlv []byte, new_val int64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Idiff 

func Idiff(tlv []byte, vvdiff VV) []byte

func Imerge 

func Imerge(tlvs [][]byte) (tlv []byte)

merge TLV values

func Inative 

func Inative(tlv []byte) int64

convert a TLV value to a native golang value

func Iparse 

func Iparse(txt string) (tlv []byte)

parse a text form into a TLV value

func IsFirst 

func IsFirst(c byte) bool

func Istring 

func Istring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Itlv 

func Itlv(i int64) (tlv []byte)

convert native golang value into a TLV form

func Itlve 

func Itlve(rev int64, src uint64, inc int64) []byte

Enveloped I TLV

func Ivalid 

func Ivalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Ldelta 

func Ldelta(tlv []byte, new_val int64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Ldiff 

func Ldiff(tlv []byte, vvdiff VV) []byte

func Lmerge 

func Lmerge(tlvs [][]byte) (merged []byte)

merge TLV values

func Lparse 

func Lparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Lstring 

func Lstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Lvalid 

func Lvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Mdelta 

func Mdelta(tlv []byte, new_tlv []byte) (tlv_delta []byte)

func Mdelta2 

func Mdelta2(tlv []byte, changes []byte) (tlv_delta []byte)

Given a TLV of *changed* key-value pairs, produce a delta

func MdeltaTR 

func MdeltaTR(tlv []byte, changes MapTR, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Mdiff 

func Mdiff(tlv []byte, vvdiff VV) []byte

func MelAppend 

func MelAppend(to []byte, lit byte, t Time, body []byte) []byte

func MelReSource 

func MelReSource(first []byte, src uint64) (ret []byte, err error)

func MergeFIRST 

func MergeFIRST(tlvs [][]byte) (tlv []byte)

func Mmerge 

func Mmerge(tlvs [][]byte) (merged []byte)

merge TLV values

func Mparse 

func Mparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Mrdx2tlv 

func Mrdx2tlv(a *RDX) (tlv []byte)

func Mstring 

func Mstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func MtlvII 

func MtlvII(nat MapTT) (tlv []byte)

func MtlvSS 

func MtlvSS(m MapSS) (tlv []byte)

func MtlvTR 

func MtlvTR(nat MapTR) (tlv []byte)

func MtlvTT 

func MtlvTT(mtt MapTT) (tlv []byte)

func Mvalid 

func Mvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func N2string 

func N2string(tlv []byte, new_val string, src uint64) (tlv_delta []byte)

func NOmerge 

func NOmerge(inputs [][]byte) []byte

func Ndefault 

func Ndefault() []byte

func Ndelta 

func Ndelta(tlv []byte, new_val uint64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one return nil on error, empty slice for "no changes"

func Ndiff 

func Ndiff(tlv []byte, vvdiff VV) []byte

func NextRev 

func NextRev(revz uint64) (next int64)

func Nmerge 

func Nmerge(tlvs [][]byte) (merged []byte)

merge TLV values

func Nmine 

func Nmine(tlv []byte, src uint64) uint64

func Nnative 

func Nnative(tlv []byte) (sum uint64)

convert a TLV value to a native golang value

func NoMerge 

func NoMerge(inputs [][]byte) []byte

func Nparse 

func Nparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Nstring 

func Nstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Ntlv 

func Ntlv(u uint64) (tlv []byte)

convert a native golang value into TLV

func Ntlvt 

func Ntlvt(inc uint64, src uint64) []byte

func Nvalid 

func Nvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func OValid 

func OValid(tlv []byte) bool

func OYstring 

func OYstring(tlv []byte) string

func Parse583Off 

func Parse583Off(hex583 []byte) (off uint16)

func ParseFIRST 

func ParseFIRST(bulk []byte) (rev int64, src uint64, value []byte)

for bad format, value==nil (an empty value is an empty slice)

func Rdefault 

func Rdefault() []byte

func Rdelta 

func Rdelta(tlv []byte, new_val ID, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Rdiff 

func Rdiff(tlv []byte, vvdiff VV) []byte

func Restamp 

func Restamp(first []byte, time Time) (stamped []byte)

func Rmerge 

func Rmerge(tlvs [][]byte) (tlv []byte)

merge TLV values

func Rparse 

func Rparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Rstring 

func Rstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Rtlv 

func Rtlv(i ID) (tlv []byte)

convert native golang value into a TLV form

func Rvalid 

func Rvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Sdefault 

func Sdefault() []byte

func Sdelta 

func Sdelta(tlv []byte, new_val string, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Sdiff 

func Sdiff(tlv []byte, vvdiff VV) []byte

func SetSourceFIRST 

func SetSourceFIRST(bare []byte, src uint64) (res []byte, err error)

func SetTimeFIRST 

func SetTimeFIRST(bare []byte, t Time) (res []byte)

func Smerge 

func Smerge(tlvs [][]byte) (tlv []byte)

merge TLV values

func Snative 

func Snative(tlv []byte) string

convert a TLV value to a native golang value

func Sparse 

func Sparse(txt string) (tlv []byte)

parse a text form into a TLV value; nil on error

func Sparset 

func Sparset(txt string, t Time) (tlv []byte)

func SrcSeqOff 

func SrcSeqOff(id ID) (src uint64, seq uint64, off uint16)

func Sstring 

func Sstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Stlv 

func Stlv(s string) (tlv []byte)

convert native golang value into a TLV form

func Svalid 

func Svalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Tdelta 

func Tdelta(tlv []byte, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Tdiff 

func Tdiff(tlv []byte, vvdiff VV) []byte

func Time64FromRevzSrc 

func Time64FromRevzSrc(revz, src uint64) uint64

func Tmerge 

func Tmerge(tlvs [][]byte) (tlv []byte)

merge TLV values

func Tparse 

func Tparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Tstring 

func Tstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Ttlv 

func Ttlv(term string) (tlv []byte)

convert native golang value into a TLV form

func Tvalid 

func Tvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

func Uint32Pair 

func Uint32Pair(a, b uint32) (x uint64)

func Uint32Unpair 

func Uint32Unpair(x uint64) (a, b uint32)

func UnHex 

func UnHex(hex []byte) (num uint64)

func Unescape 

func Unescape(in, out []byte) ([]byte, error)

unescape unescapes the string contained in 'in' and returns it as a slice. If 'in' contains no escaped characters: 

Returns 'in'.

Else, if 'out' is of sufficient capacity (guaranteed if cap(out) >= len(in)): 

'out' is used to build the unescaped string and is returned with no extra allocation

Else: 

A new slice is allocated and returned.

func UnzipFloat64 

func UnzipFloat64(zip []byte) float64

func UnzipInt64 

func UnzipInt64(zip []byte) int64

func UnzipIntUint64Pair 

func UnzipIntUint64Pair(zip []byte) (i int64, u uint64)

func UnzipUint32Pair 

func UnzipUint32Pair(buf []byte) (big, lil uint32)

func UnzipUint64 

func UnzipUint64(zip []byte) (v uint64)

func UnzipUint64Pair 

func UnzipUint64Pair(buf []byte) (big, lil uint64)

func VValid 

func VValid(tlv []byte) bool

func VVdelta 

func VVdelta(old VV, new_val VV) (tlv_delta []byte)

func Vdelta 

func Vdelta(tlv []byte, new_val VV) (tlv_delta []byte)

func Vdiff 

func Vdiff(tlv []byte, vvdiff VV) (diff_tlv []byte)

func Vmerge 

func Vmerge(tlvs [][]byte) (tlv []byte)

func Vparse 

func Vparse(txt string) (tlv []byte)

func Vstring 

func Vstring(tlv []byte) (txt string)

func Vtlv 

func Vtlv(vv VV) (tlv []byte)

func Vvalid 

func Vvalid(tlv []byte) bool

func X2string 

func X2string(rdt byte, tlv []byte, new_val string, src uint64) (delta []byte)

func Xdefault 

func Xdefault(rdt byte) (tlv []byte)

func Xdiff 

func Xdiff(rdt byte, tlv []byte, sendvv VV) (diff []byte)

func Xmerge 

func Xmerge(rdt byte, tlvs [][]byte) (tlv []byte)

func Xparse 

func Xparse(rdt byte, val string) (tlv []byte)

func Xstring 

func Xstring(rdt byte, tlv []byte) string

func Xvalid 

func Xvalid(rdt byte, bare []byte) bool

func Xvalide 

func Xvalide(tlve []byte) bool

func ZagZigUint64 

func ZagZigUint64(u uint64) int64

func Zdelta 

func Zdelta(tlv []byte, new_val int64, clock Clock) (tlv_delta []byte)

produce an op that turns the old value into the new one

func Zdiff 

func Zdiff(tlv []byte, vvdiff VV) []byte

func ZigZagInt64 

func ZigZagInt64(i int64) uint64

func ZipFloat64 

func ZipFloat64(f float64) []byte

func ZipInt64 

func ZipInt64(v int64) []byte

func ZipIntUint64Pair 

func ZipIntUint64Pair(i int64, u uint64) []byte

func ZipUint64 

func ZipUint64(v uint64) []byte

ZipUint64 packs uint64 into a shortest possible byte string

func ZipUint64Pair 

func ZipUint64Pair(big, lil uint64) []byte

ZipUint64Pair packs a pair of uint64 into a byte string. The smaller the ints, the shorter the string TODO 4+3 etc

func ZipZagInt64 

func ZipZagInt64(i int64) []byte

func Zmerge 

func Zmerge(tlvs [][]byte) (merged []byte)

merge TLV values

func Znative 

func Znative(tlv []byte) (sum int64)

convert a TLV value to a native golang value

func Znative3 

func Znative3(tlv []byte, src uint64) (sum, mine, minerev int64)

func Zparse 

func Zparse(txt string) (tlv []byte)

parse a text form into a TLV value

func Zstring 

func Zstring(tlv []byte) (txt string)

produce a text form (for REPL mostly)

func Ztlv 

func Ztlv(i int64) (tlv []byte)

convert a native golang value into TLV

func Ztlvt 

func Ztlvt(i int64, src uint64, rev int64) (tlv []byte)

func Zvalid 

func Zvalid(tlv []byte) bool

checks a TLV value for validity (format violations)

Types

type AIterator 

type AIterator struct {
	FIRSTIterator
}

func (*AIterator) Merge 

func (a *AIterator) Merge(bb SortedIterator) int

type Clock 

type Clock interface {
	See(time, src uint64)
	Time(maxTime uint64) uint64
	Src() uint64
}

type EIterator 

type EIterator struct {
	FIRSTIterator
}

func (*EIterator) Merge 

func (a *EIterator) Merge(b SortedIterator) int

type FIRSTIterator 

type FIRSTIterator struct {
	TLV []byte
	// contains filtered or unexported fields
}

func (*FIRSTIterator) Next 

func (a *FIRSTIterator) Next() bool

func (*FIRSTIterator) ParsedValue 

func (a *FIRSTIterator) ParsedValue() (rdt byte, time Time, value []byte)

func (*FIRSTIterator) Value 

func (a *FIRSTIterator) Value() []byte

type ID 

type ID uint64
ID is an 64-bit locator/identifier.
This is NOT a Lamport timestamp (need more bits for that).
This is *log time*, not *logical time*.

0...............16..............32..............48.............64 +-------+-------+-------+-------+-------+-------+-------+------- |offset(12)||......sequence.(32.bits)......|..source.(20.bits)..| |...........progress.(44.bits).............|....................| 

const ID0 ID = 0

func IDFromBracketedString 

func IDFromBracketedString(bid []byte) ID

func IDFromBytes 

func IDFromBytes(by []byte) ID

func IDFromSrcSeqOff 

func IDFromSrcSeqOff(src uint64, seq uint64, off uint16) ID

func IDFromString 

func IDFromString(idstr string) (parsed ID)

func IDFromText 

func IDFromText(idstr []byte) (parsed ID)

func IDFromZipBytes 

func IDFromZipBytes(zip []byte) ID

func IDfromSrcPro 

func IDfromSrcPro(src, pro uint64) ID

func Rnative 

func Rnative(tlv []byte) ID

convert a TLV value to a native golang value

func TakeIDWary 

func TakeIDWary(lit byte, pack []byte) (id ID, rest []byte, err error)

func (ID) Bytes 

func (id ID) Bytes() []byte

func (*ID) Drain 

func (id *ID) Drain(from []byte) (rest []byte)

func (ID) Feed 

func (id ID) Feed(into []byte) (res []byte)

func (ID) Hex583 

func (id ID) Hex583() []byte

func (ID) Off 

func (id ID) Off() uint64

func (ID) Pro 

func (id ID) Pro() uint64

func (ID) Seq 

func (id ID) Seq() uint64

Seq is the op sequence number (each replica generates its own sequence numbers)

func (ID) Src 

func (id ID) Src() uint64

Src is the replica id. That is normally a small number.

func (ID) String 

func (id ID) String() string

func (ID) String583 

func (id ID) String583() string

func (ID) ToOff 

func (id ID) ToOff(newoff uint64) ID

func (ID) UInt64 

func (id ID) UInt64() uint64

func (ID) ZeroOff 

func (id ID) ZeroOff() ID

func (ID) ZipBytes 

func (id ID) ZipBytes() []byte

type ItHeap 

type ItHeap[T SortedIterator] []T

func (ItHeap[T]) Fix 

func (ih ItHeap[T]) Fix(i int)

Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a push of the new value. The complexity is O(log n) where n = h.Len().

func (*ItHeap[T]) Len 

func (ih *ItHeap[T]) Len() int

func (*ItHeap[T]) Next 

func (ih *ItHeap[T]) Next() (next []byte)

func (*ItHeap[T]) Pop 

func (ih *ItHeap[T]) Pop() (min T)

Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).

func (*ItHeap[T]) Push 

func (ih *ItHeap[T]) Push(x T)

func (*ItHeap[T]) Remove 

func (ih *ItHeap[T]) Remove(i int) T

Remove removes and returns the element at index i from the heap. The complexity is O(log n) where n = h.Len().

type LIterator 

type LIterator struct {
	FIRSTIterator
}

func (*LIterator) Merge 

func (a *LIterator) Merge(bb SortedIterator) int

type LocalLogicalClock 

type LocalLogicalClock struct {
	Source uint64
}

func (*LocalLogicalClock) See 

func (llc *LocalLogicalClock) See(time, src uint64)

func (*LocalLogicalClock) Src 

func (llc *LocalLogicalClock) Src() uint64

func (*LocalLogicalClock) Time 

func (llc *LocalLogicalClock) Time(maxtime uint64) uint64

type LogT 

type LogT []string

append-only collection of Terms

func AnativeT 

func AnativeT(tlv []byte) (log LogT)

type MIterator 

type MIterator struct {
	Key, Val FIRSTIterator
	// contains filtered or unexported fields
}

func (*MIterator) Merge 

func (a *MIterator) Merge(b SortedIterator) int

func (*MIterator) Next 

func (a *MIterator) Next() (got bool)

func (*MIterator) Value 

func (a *MIterator) Value() []byte

type MapSS 

type MapSS map[string]string

func MnativeSS 

func MnativeSS(tlv []byte) MapSS

type MapTR 

type MapTR map[string]ID

func MnativeTR 

func MnativeTR(tlv []byte) MapTR

func MparseTR 

func MparseTR(arg *RDX) MapTR

func (MapTR) String 

func (m MapTR) String() string

type MapTT 

type MapTT map[string]string

func MnativeTT 

func MnativeTT(tlv []byte) MapTT

type NIterator 

type NIterator struct {
	FIRSTIterator
}

func (*NIterator) Merge 

func (a *NIterator) Merge(b SortedIterator) int

func (*NIterator) Value 

func (a *NIterator) Value() []byte

type RDT 

type RDT interface {
	Merge(tlvs [][]byte)
	State() (tlv []byte)

	String() string
	ToString(txt string, src uint64) error

	Native() interface{}
	ToNative(new_val interface{}, src uint64) (delta []byte)

	Diff(vvdiff VV) (diff []byte)
}

type RDX 

type RDX struct {
	Nested  []RDX
	Text    []byte
	Parent  *RDX
	RdxType byte
}

func ParseRDX 

func ParseRDX(data []byte) (rdx *RDX, err error)

func (*RDX) AddChild 

func (rdx *RDX) AddChild(rdxtype byte, text []byte)

func (*RDX) FIRST 

func (rdx *RDX) FIRST() bool

func (*RDX) Feed 

func (rdx *RDX) Feed() (recs protocol.Records, err error)

func (*RDX) String 

func (rdx *RDX) String() string

type SortedIterator 

type SortedIterator interface {
	Next() bool
	Merge(b SortedIterator) int
	Value() []byte
}

type Time 

type Time struct {
	Rev int64
	Src uint64
}

func ParseEnvelopedFIRST 

func ParseEnvelopedFIRST(data []byte) (lit byte, t Time, value, rest []byte, err error)

Parses an enveloped FIRST record

func TimeFrom64 

func TimeFrom64(t64 uint64) Time

func TimeFromZipBytes 

func TimeFromZipBytes(zip []byte) (t Time)

func (Time) Time64 

func (t Time) Time64() uint64

func (Time) ZipBytes 

func (t Time) ZipBytes() []byte

type VV 

type VV map[uint64]uint64

VV is a version vector, max ids seen from each known replica.

func VVFromString 

func VVFromString(vvs string) (vv VV)

func VVFromTLV 

func VVFromTLV(tlv []byte) (vv VV)

func Vplain 

func Vplain(tlv []byte) VV

func (VV) Get 

func (vv VV) Get(src uint64) (pro uint64)

func (VV) GetID 

func (vv VV) GetID(src uint64) ID

func (VV) IDs 

func (vv VV) IDs() (ids []ID)

func (VV) InterestOver 

func (vv VV) InterestOver(b VV) VV

func (VV) ProgressedOver 

func (vv VV) ProgressedOver(b VV) bool

Whether this VV overlaps with another one (have common non-zero entry)

func (VV) Put 

func (vv VV) Put(src, pro uint64) bool

Put the Src-pro pair to the VV, returns whether it was unseen (i.e. made any difference)

func (VV) PutID 

func (vv VV) PutID(id ID) bool

Adds the id to the VV, returns whether it was unseen

func (VV) PutTLV 

func (vv VV) PutTLV(rec []byte) (err error)

consumes: Vv record

func (VV) Seen 

func (vv VV) Seen(bb VV) bool

func (VV) Set 

func (vv VV) Set(src, pro uint64)

Set the progress for the specified source

func (VV) String 

func (vv VV) String() string

func (VV) TLV 

func (vv VV) TLV() (ret []byte)

TLV Vv record, nil for empty

type ZIterator 

type ZIterator struct {
	FIRSTIterator
}

func (*ZIterator) Merge 

func (a *ZIterator) Merge(b SortedIterator) int

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.