Conflict-free Replicated Data Types: An Overview

CRDT

Abstarct

强一致性需要的延迟高，无法应当网络分区（network partition）故障，很有可能导致无法执行操作，那么可选的方案就是弱一致性模型，比如最终一致性（eventual consistency），因果一致性（causal consistency），此时任何一个副本都能接受更新，并异步复制到其他副本。

采用弱一致性模型的系统，就允许副本短暂的和集群分离(比如因为网络问题等），并且需要一个机制来合并 (merge mechanism) 对同一个状态的并发更新。Conflict-free Replicated Data Types(CRDT) 就是这么一种算法。

CRDTs for the Application Developer

Happend-before relation

happen-before relation 定义：event1 happend-before event2 （表述为 e1 ≺ e2）， 当且仅当满足条件以下三个条件之一：

  1. 相同进程中，e1 在发生在 e2
  2. e1 是 message m 的发送端，e2 是 message m 的接收端
  3. 已经存在一个 event e，满足 e1 ≺ e ≺ e2 条件

在 CRDT 中，如果 update u1 happend-before update u2，u1 ≺ u2，当且仅当当u2开始执行时 u1 已经生效。

Total order among updates

定义全局序

Question

  1. fig7 的结果???

CRDTs for the System Developer

3.1 Synchronization model

3.1 State-based synchronization

crdt 需要设计一个 merge 函数来合并remote rpelica 发送的状态，收敛条件有三个：

  1. 基于的状态是可以形成一个偏序的:
  2. 产生的新状态要大于等于原始状态：对于更新 u, $s leq u(s)$，
  3. merge 函数需要生成两个状态的最小上界：对于状态 states s1, s2 ， 能得到 $s1 \bigcup s2$.

为了确保所有的更新最终都能到达所有的副本，我们只需要保证同步图是连通的。

这里的”同步图”代表分布式系统中不同数据副本间的通信路径。如果图是连通的，那就意味着图中任意两个节点（副本）之间都存在路径。 这是保证所有更新最终到达所有副本的必要条件。如果图不连通，那么可能存在一些副本与其他副本隔离，无法接收到所有的更新。然而，需要注意的是，虽然连通的同步图是必要的，但在所有情况下，它可能并不足以确保最终的一致性。其他因素，如操作的顺序和网络延迟，也可能影响所有副本是否最终达到一致。例如，在一些分布式系统中，可能需要使用额外的机制，如向量时钟，来跟踪操作的因果顺序，或使用确保按照某种顺序将更新传播到所有副本的协议。

3.1.2 Operation-based synchronization

传递的是更新。除了要可靠地传递给 operations，一些 crdt 设计还需要按照某些顺序来传递 operation。

TODO….