A basic portfolio study of Convergent and Commutative Replicated Data Types

這是篇 survey 文章,介紹 Convergent And Commutative Replicated Types 有哪幾種資料結構,不定期更新

op-based CRDT 基本上就這些問題

  • 要分散還是集中
  • 要不要存 operation dependency
  • 先新增再刪除沒問題,那先刪除再新增我得到的結果可不可以一樣?tombstone garbage collection 怎麼做
  • 大家同時對一個欄位新增不同的值,我要怎麼辦?

CmRDTs

Operations on CmRDTs need to adhere to the following rules:

  • Associativity (a+(b+c)=(a+b)+c), so that grouping doesn’t matter.
  • Commutativity (a+b=b+a), so that order of application doesn’t matter.
  • idempotence (a+a=a), so that duplication doesn’t matter.

Counters

G-Counter

  • 沒有減的運算

PN-Counter

  • 有正負

Registers

Last-Writer-Win Register (LWW-Register)

A Last-Writer-Wins Register (LWW-Register) creates a total order of assignments by asso- ciating a timestamp with each update. Timestamps are assumed unique, totally ordered, and consistent with causal order; i.e., if assignment 1 happened-before assignment 2, the former’s timestamp is less than the latter’s [24]. This may be implemented as a per-replica counter concatenated with a unique replica identifier, such as its MAC address [24].

Multi-Value Register (MV-Register)

An alternative semantics is to define a LUB operation that merges concurrent assignments, for instance taking their union, as in file systems such as Coda [19] or in Amazon’s shopping cart [10]. Clients can later reduce multiple values to a single one, by a new assignment. Alternatively, in Ficus [34] merge is an application-specific resolver procedure.
 MV-Register does not behave like a set. It does not store all concurrent assignments but only stores concurrent ones.

Sets

Grow-Only Set (G-Set)

The simplest solution is to avoid remove altogether.
 In both the state- and op-based approaches, the payload is a set. Since add is based on union, and union is commutative, the op-based implementation converges;

2P-Set

A Set where an element may be added and removed, but never added again thereafter.
 It combines a G-Set for adding with another for removing; the latter is col- loquially known as the tombstone set. To avoid anomalies, removing an element is allowed only if the source observes that the element is in the set.

U-Set

A simplified 2P-Set,Remove always before add (casual delivery)

LWW-element-Set

— Add timestamp to each elements
 — Each of the items added to the set and removed from the set have a timestamp. The final current set is yielded by adding all the most recently added items and removing the most recently removed items.

PN-Set

  • To associate a counter to each element, initially 0.
  • Adding an element increments the associated counter, and removing an element decrements it.
  • The element is considered in the set if its counter is strictly positive.
  • An actual use-case is Logoot-Undo [43], a (totally-ordered) set of elements for text editing.

Observed-Remove Set (OR-Set)

  • Each element added to the set is assigned a unique identity.
  • kept up to date by applying causal consistency.

Graphs

2P2P-Graph

  • A graph is a pair of sets (V,E) (called vertices and edges respectively) such that E ⊆ V ×V .
  • A 2P2P-Graph is the combination of two 2P-Sets; as we showed, the dependencies between them are resolved by causal delivery.
  • Dependencies between addEdge and removeEdge, and between addVertex and removeVertex are resolved as in 2P-Set.

Add-Only Monotonic Directed Acyclic Graph

No remove operation because a client adds a vertex around w, removes the edges to and from w, and finally removes w.

Concurrently, another client (at another source replica) does the same with x.

When the former operations propagate, the downstream precondition of addEdge is false at Replica 2, and, consequently the downstream precondition of removeVertex can never be satisfied; and vice-versa.

Add-Remove Partial Order

  • Use simple DAG.
  • Keep deletion as tombstones
  • impilar to tombstones transform in Operation Transform.

Sequence

Replicated Growable Array (RGA)

  • 用 linked list 做成 Graph

Continuous Sequence

  • RGA 的變形
  • 有 identifier depth grow problem
Like what you read? Give hychen a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.