Skip to content

crdt

class DotKernel

DotKernel[A: Any val]¶

This class is a reusable abstraction meant for use inside other CRDTs.

It contains a "dot context", which is used to track a logical remembrance of all changes we've generated and observed. Each is represented by a "dot", where the dot is a unique replica identifier and a sequence number. See docs for the DotContext type for more information on how this works.

We also maintain a map of "active" values - those we wish to retain for inclusion in the calculation of the result value, using whatever semantics are appropriate for that calculation, based on the needs of the outer data structure that holds this kernel. For example, the CCounter calculates its result by summing all active values, while the AWORSet calculates its result by returning the active values as a set. Other data structures may use more exotic calculations.

Each active value is associated with a "dot" - a point in causal history on a particular replica. Because we retain a remembrance of all dots we've ever seen in the "dot context", we can determine whether data we observe is new to us or outdated by checking if the dot is already in the dot context.

Note that because active values are indexed by their dot (and not simply their replica id) it is possible to retain multiple active values per replica if the outer data structure doesn't take steps to prevent this. For some data structures, this is desirable; for others, it isn't. If you wish to always keep only the latest causal active value per replica, prefer using the DotKernelSingle class instead of this one.

class ref DotKernel[A: Any val] is
  Replicated ref

Implements¶

Replicated ref

Constructors¶

create¶

Instantiate under the given unique replica id.

It will only be possible to add dotted values under this replica id, aside from converging it as external data with the converge function.

new ref create(
  id': ID)
: DotKernel[A] ref^

Parameters¶

id': ID

Returns¶

DotKernel[A] ref^

create_in¶

Instantiate under the given DotContext.

new ref create_in(
  ctx': DotContext ref)
: DotKernel[A] ref^

Parameters¶

ctx': DotContext ref

Returns¶

DotKernel[A] ref^

Public Functions¶

context¶

Get the underlying DotContext.

fun box context()
: this->DotContext ref

Returns¶

this->DotContext ref

is_empty¶

Return true if there are no values ever recorded from any replica. This is true at creation, after calling the clear method, or after a converge that results in all values being cleared.

fun box is_empty()
: Bool val

Returns¶

Bool val

values¶

Return an iterator over the active values in this kernel.

fun box values()
: Iterator[A] ref^

Returns¶

Iterator[A] ref^

pairs¶

Return an iterator over the active values and their associated dots.

fun box pairs()
: Iterator[(_Dot , A)] ref^

Returns¶

Iterator[(_Dot , A)] ref^

set[optional D: DotKernel[A] ref]¶

Add the given value to the map of active values, under this replica id. The next-sequence-numbered dot for this replica will be used, so that the new value has a happens-after causal relationship with previous value(s).

fun ref set[optional D: DotKernel[A] ref](
  value': A,
  delta': D = recover DotKernel[A](0) end)
: D^

Parameters¶

value': A
delta': D = recover DotKernelA end

Returns¶

D^

remove_value[E: EqFn[A] val, optional D: DotKernel[A] ref]¶

Remove all dots with this value from the map of active values, using the given eq_fn for testing equality between pairs of values of type A. They will be retained in the causal context (if they were already present).

This removes the dots and associated value while keeping reminders that we have seen them before, so that we can ignore them if we see them again.

If the value was not present, this function silently does nothing.

Accepts and returns a convergent delta-state.

fun ref remove_value[E: EqFn[A] val, optional D: DotKernel[A] ref](
  value': A,
  delta': D = recover DotKernel[A](0) end)
: D^

Parameters¶

value': A
delta': D = recover DotKernelA end

Returns¶

D^

remove_all[optional D: DotKernel[A] ref]¶

Remove all dots currently present in the map of active values. They will be retained in the causal context.

This removes the dots and associated values while keeping reminders that we have seen them before, so that we can ignore them if we see them again.

Accepts and returns a convergent delta-state.

fun ref remove_all[optional D: DotKernel[A] ref](
  delta': D = recover DotKernel[A](0) end)
: D^

Parameters¶

delta': D = recover DotKernelA end

Returns¶

D^

converge¶

Catch up on active values and dot history from that kernel into this one, using the dot history as a context for understanding for which disagreements we are out of date, and for which disagreements the other is out of date.

fun ref converge(
  that: DotKernel[A] box)
: Bool val

Parameters¶

that: DotKernel[A] box

Returns¶

Bool val

converge_empty_in¶

Optimize for the special case of converging from a peer with an empty map, taking only their DotContext as an argument for resolving disagreements.

fun ref converge_empty_in(
  ctx': DotContext box)
: Bool val

Parameters¶

ctx': DotContext box

Returns¶

Bool val

string¶

Return a best effort at printing the data structure. This is intended for debugging purposes only.

fun box string()
: String iso^

Returns¶

String iso^

from_tokens¶

Deserialize an instance of this data structure from a stream of tokens.

fun ref from_tokens(
  that: TokensIterator ref)
: None val ?

Parameters¶

that: TokensIterator ref

Returns¶

None val ?

from_tokens_map¶

Deserialize an instance of this data structure from a stream of tokens, using a custom function for deserializing the B tokens as instance(s) of A.

fun ref from_tokens_map(
  that: TokensIterator ref,
  a_fn: {(TokensIterator): A ?}[A] val)
: None val ?

Parameters¶

that: TokensIterator ref
a_fn: {(TokensIterator): A ?}[A] val

Returns¶

None val ?

each_token¶

Serialize the data structure, capturing each token into the given Tokens.

fun ref each_token(
  tokens: Tokens ref)
: None val

Parameters¶

tokens: Tokens ref

Returns¶

None val

each_token_map¶

Serialize the data structure, capturing each token into the given Tokens. using a custom function for serializing the A type as one or more B tokens.

fun ref each_token_map(
  tokens: Tokens ref,
  a_fn: {(Tokens, A)}[A] val)
: None val

Parameters¶

tokens: Tokens ref
a_fn: {(Tokens, A)}[A] val

Returns¶

None val