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 相关论文

### Efficient Synchronization of State-Based CRDTs

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

### Conflict-Free Replicated Data Types CRDTs

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

## 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