CRDT 学习笔记。


CRDT 相关资源

背景知识

A CRDT Primer Part I: Defanging Order Theory

Order

Definition

An Order set is a binary relation $\le$ on a set $\mathcal{S}$, written $(\mathcal{S},\le)$.

Core concepts

  • If we can say that $a \le b$ or $b \le a$, then we know that $a$ is comparable to $b$.
  • In order theory, if $a$ and $b$ are incomparable, we write $a \parallel b$.
  • A join between two elements, written $a \vee b$.

Type of order

  • An order is total if for any $a$ and $b$ in the set, either $a \le b$ or $b \le a$.

    例: 集合是自然数,二元关系为小于等于

  • A partial order is weaker than a total. It does not require that every pair $a$ and $b$ in a set can be compared.

    例: 集合是地理位置,二元关系为"位于"

Join

Upper bound

For a set $\mathcal{S}$, an order $(\mathcal{S},\le)$, and $\mathcal{A} \subseteq \mathcal{S}$ is an aibitrary subset, then an element $u \in \mathcal{S}$ is said to be an upper bound of $\mathcal{A}$ if $a \le u, \forall a \in \mathcal{A}$.

Definition

For a set $\mathcal{S}$, an order $(\mathcal{S},\le)$, and two elements $a,b \in \mathcal{S}$, then join of $a$ and $b$ (written $a \vee b$) is a least upper bound of ${a, b}$ according to our order $(\mathcal{S},\le)$.

In total order, a join of two elelments is always equals to one of those two elements. However, if we’re talking about partial orders, this is not guaranteed.

Properties

  1. Commutativity: $a \vee b = b \vee a$
  2. Associativity: $(a \vee b) \vee c = a \vee (b \vee c)$
  3. Idempotence: $a \vee a = a$

Join-semilattice

A join-semilattice is a order set $(\mathcal{S},\le)$ that has a join(a least upper bound) for any nonempty finite subset.

Dually, a meet-semilattice (or lower semilattice) is a ordered set which has a meet (or greatest lower bound) for any nonempty finite subset.

扩展阅读

CRDT 相关论文

Conflict-free Replicated Data Types

在这篇文章中,作者主要提出了两种本质上等价的 CRDT:CvRDT 和 CmRDT。为了保证强最终一致性,作者表示在 CvRDT 中需定义合适的操作,使得状态集合在给定的偏序关系下构成 Join-semilattice;而在 CmRDT 中,操作需满足要么可比较,不可比的便可交换的条件,除此之外,还需要消息传输提供 exactly once 的保证。详细内容请点击

A comprehensive study of Convergent and Commutative Replicated Data Types

理论内容和上一篇相比几乎相同,新增了一些 CRDT 数据结构示例、垃圾回收和简单应用的内容。

An Optimized Conflict-free Replicated Set

利用 Causal order 进行空间上的优化,和 $\delta$-CRDT 中的 Optimized Add-Wins OR-Set 类似。

Efficient State-based CRDTs by Delta-Mutation

本文正式定义了 $\delta$-CRDT, 其通过传递状态增量而不是传递整个状态,有效地改善了 CvRDT 通信消耗过大的不足,最后给出了 PN-CounterOR-SetMulti-value Register 基于 $\delta$-CRDT 的实现。详细内容请点击

Delta state replicated data types

本文在 Efficient State-based CRDTs by Delta-Mutation 基础之上补充了一些数学证明,添加了更丰富的示例,包括 PN-CounterGSet2PSetAdd-Wins Last-Writer-Wins SetLexicographic CounterMulti-Value RegisterAdd-Wins SetRemove-Wins SetA Map Embedding Causal -CRDTs

Efficient Synchronization of State-Based CRDTs

本文在 $\delta$-CRDT 的基础上,通过以下两步优化,以减小消息通信冗余带来的多余开销:

  • Avoiding back-propagation of $\delta$-groups
  • Removing reundant state in received $\delta$-groups

私认为,完全可以通过使用适宜的网络拓扑结构,以防止消息回源带来的通信冗余开销。

Conflict-Free Replicated Data Types CRDTs

一篇关于 CRDT 的 survey,作者首先给出了 CRDT 的定义;然后从 Concurrency Semanitics 和 Synchronization Model 两个方面介绍了 CRDT 的具体内容;之后,又介绍了一些研究发现与 CRDT 的具体应用示例;最后,从 Scalability、Reversible Computation、Security、Nonuniform Replicas 和 Verification 五个方面总结并展望了未来的研究方向。

PS:Nonuniform Replicas 和 Verification 看起来比较有趣一些。

Conclusions

在分布式数据库中,想让各个副本保持一致,大致有两种方案:

  • 阻止分歧产生:写入时,各个副本通过 py 交易保持一致 (耗时)
  • 允许分歧产生:存储分区恢复所需的必要信息,使得分区恢复后各个副本保持一致 (消耗空间)

假设现有两个副本:A 和 B,我们很容易想到,在 A 上回放 B 的操作记录,使得 B 上发生的更改能同步至 A(对 B 同样操作,下述以 A 为主角)。但是,若想 A 和 B 收敛至同一确定状态,需要满足以下条件:

  1. 接收到的 B 的操作记录要么可交换顺序,要么可明确顺序
  2. 接收到的 B 的操作记录要么满足 exactly once,要么操作幂等
  3. 来自客户端的请求和来自 B 的操作记录要么可交换顺序,要么可明确顺序
  • 条件 1 使用消息队列可达成,但单线程通信效率较低,此时可将消息按 key 哈希多线程发送,保证因果一致性即可。
  • 条件 2exactly once 的要求有点难以实现,还是从操作幂等入手较为现实,这也是 CRDT 存在的意义之一(通过设计合适的数据结构和操作转换使得操作幂等)
  • 条件 3 其含义即为并发操作无分歧,这是 CRDT 存在的意义之二

综上所述,我们知道了 CRDT 主要作用在两方面:

  • 使得同步更新操作幂等
  • 使得同步更新操作和本地更新操作要么可交换顺序,要么可明确顺序。一般而言明确操作顺序会产生额外的依赖,比如人为设定的规则(add-wins)或全局时钟,所以在设计策略时应尽量使得并发操作可交换顺序,以较少依赖。

我们回过头来看 CvRDTCmRDT。在 CmRDT 中,需要满足以下约束:

  • 更新操作要么可明确因果顺序,要么可交换 (条件 1 和 条件 3)
  • 消息传输提供 exactly once 的保证 (条件 2)

而在 CvRDT 中,需满足以下约束:

  • 状态满足单调性,消息最终可达
  • 状态更新操作需满足交换律,结合律,幂等 (条件 1 2 3)

其中,状态的单调性即保证了最终所有副本会收敛至同一状态,也便于设计满足要求的更新操作。

CRDT 动态规划说

DP CRDT
最终获得的结果与依次遍历获取更新的结果相同 最终所有的节点会收敛至相同的状态
通过缓存历史信息降低时间复杂度,以空间换时间 通过存储额外 meta 信息保证最终收敛至相同状态,操作都是 local 的,延时低,以空间换时间
状态与操作顺序无关,即操作需满足交换律,结合律 并发更新操作需满足交换律、结合律,通过定义状态的结构获取,也即状态与并发操纵顺序无关

又由 ASCII 表 可知,$D \mapsto 68, P \mapsto 80, C \mapsto 67, R \mapsto 82, T \mapsto 84$

In DP:

$68 + 80 = 148 = 1 \times (145 - 1 + 4)$

In CRDT:

$67 + 82 + 68 + 84 = 301 = -11 \times (4! - 51) + 4$

Q.E.D