📖Delta State Replicated Data Types

authors

Almeida, Paulo S'ergio and Shoker, Ali and Baquero, Carlos

year

2016

url

http://arxiv.org/abs/1603.01529v1

• I think most of these data structures are available in Riak via riak_dt

• Excerpts:

  • Instead of shipping the whole state, ship only deltas (δ-state) generated by δ-mutators.

  • Definition 1 (Delta-mutator). A delta-mutator $m^δ$ is a function, corresponding to an update operation, which takes a state $X$ in a join-semilattice $S$ as parameter and returns a delta-mutation $m^δ(X)$, also in $S$.

  • Definition 2 (Delta-group). A delta-group is inductively defined as either a delta-mutation or a join of several delta-groups.

  • Definition 3 (δ-CRDT). A δ-CRDT consists of a triple $(S, M^δ, Q)$, where $S$ is a join-semilattice, $M^δ$ is a set of delta-mutators, and $Q$ a set of query functions, where the state transition at each replica is given by either joining the current state $X ∈ S$ with a delta-mutation: $X' = X ⊔ m^δ(X)$, or joining the current state with some received delta-group $D$: $X' = X ⊔ D$.

  • it will be useful to find a non-trivial decomposition such that delta-states returned by delta-mutators in $M^δ$ are smaller than the resulting state: $size(m^δ(X))≪size(m(X))$

  • Definition 4 (Delta-interval). Given a replica $i$ progressing along the states $X^0_i, X^1_i, . . .$, by joining delta $d^k_i$ (either local delta-mutation or received delta-group) into $X^k_i$ to obtain $X^{k+1}_i$, a delta-interval $\Delta^{a,b}_i$ is a delta-group resulting from joining deltas $d^a_i, . . . , d^{b-1}_i$: $\Delta^{a,b}_i=⊔\{d^k_i | a ≤ k < b\}$

  • Definition 5 (Delta-interval-based anti-entropy algorithm). A given anti-entropy algorithm for δ-CRDTs is delta-interval-based, if all deltas sent to other replicas are delta-intervals.

  • Definition 6 (Causal delta-merging condition). A delta-interval based anti-entropy algorithm is said to satisfy the causal delta-merging condition if the algorithm only joins $\Delta^{a,b}_j$ from replica $j$ into state $X_i$ of replica $i$ that satisfy: $X_i ⊒ X^a_j$

  • 

  • Portfolios contains the following data types:

    • G-Set

    • 2P-Set

    • LWW-Set (Add-Wins or Remove-Wins)

    • PN-Counter

    • Lexicographic Counter

      • state = a lexicographic pair for each replica

    • Causal delta-CRDTs

      • DotSet, DotFun, DotMap

      • Enable-Wins Flag

      • Multi-Value Register

      • Add-Wins Set (this can be seen as a map from elements to enable-wins flags, but with a single causal context)

      • Remove-Wins Set

      • Nesting CRDTs in a map

Backlinks

• 📝 CRDT