ふわふわ時間

0%

CRDT-notes

CRDT 学习笔记。


学习路线:CRDT Research

背景知识

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 中,操作需满足要么可比较,不可比的便可交换的条件。CvRDT 还算有点技巧,CmRDT 完全就是扯淡,全靠复杂的具体实现来保证。详细内容请点击

A comprehensive study of Convergent and Commutative Replicated Data Types

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

Delta state replicated data types