CRDT 学习笔记。

1. CRDT 相关资源

2. 背景知识

2.1. A CRDT Primer Part I: Defanging Order Theory

2.1.1. 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.

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

2.1.2. 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 are 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.

2.2. 扩展阅读

3. 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-Counter、OR-Set 和 Multi-value Register 基于 $\delta$-CRDT 的实现。详细内容请点击。

  • Delta state replicated data types

    本文在 Efficient State-based CRDTs by Delta-Mutation 基础之上补充了一些数学证明，添加了更丰富的示例，包括 PN-Counter、GSet、2PSet、Add-Wins Last-Writer-Wins Set、Lexicographic Counter、Multi-Value Register、Add-Wins Set、Remove-Wins Set 和 A 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 看起来比较有趣一些。

  • The problem with embedded CRDT counters and a solution

    本文首先介绍了直接将 OR-Set 和 PN-Counter 简单组合作为 Map 时可能存在的问题，随后提出了相应的解决方案。详细内容请点击.

4. Conclusions

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

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

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

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

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

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

我们回过头来看 CvRDT 和 CmRDT。在 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