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.

## 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-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 看起来比较有趣一些。

• The problem with embedded CRDT counters and a solution

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

## 4. Conclusions

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

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

• 使得同步更新操作幂等

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

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

CRDT 动态规划说

DP CRDT

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