CRDTs The Hard Parts 笔记

陈易生, notesdist-sys
Back

Designing Data-Intensive Applications (DDIA) 的作者 Martin Kleppmann 目前在剑桥大学担任研究员,研究重心为 CRDTs。今年 7 月,他进行了名为 "CRDTs: The Hard Parts" 的分享,介绍了 CRDTs 领域最新的研究进展,讲义、视频、参考文献列表见信息页。以下是我的笔记,仅供参考。

协同软件与收敛算法

包括 Google Docs、Figma、Trello 在内的协同编辑软件,需要依赖收敛算法(convergence algorithms)使得不同节点上发生的修改可以确定地(deterministically)合并到一致的状态。最常见的收敛算法有两类:OT(Operational Transformation)和 CRDT(Conflict-free replicated data type)。

收敛算法之 OT

首先以 Google Docs 为例介绍 OT。server 会接收不同节点的写,按照规则调整插入的 offset,例如,将"insert ! at position 4"按照一定的规则调整为"insert ! at position 5"。

OT

OT 的关键在于使用 server 统筹不同节点的写。OT 保证了只要两个节点接收到同一列操作,即便两列操作的顺序不同,节点上的状态也肯定收敛至相同状态。收敛是很好的性质,但收敛到的状态是否合意(desirable),还需要人为的判断,这一点对于 CRDTs 同样适用。相比 OT,CRDT 的合并是去中心化的,无需通过 server,但同样需要保证合并是合意的。

下面介绍 CRDTs 有关的四项研究进展。

CRDTs: Interleaving anomalies

方案一:给新插入的字母分配一个位于[0,1]的数字。

assign random numbers

这种方法确实能保证收敛,但下面这种情况明显不是合意的收敛,其中节点 1 将"Hello!"修改为"Hello Alice!",节点 2 将它修改为"Hello Charlie!",可能被合并为"Hello Al Ciharcliee!"这样奇怪的结果。

char-by-char interleaving anomaly

这种 interleaving 发生在很多 CRDTs(包括 Logoot、LSEQ、Astrong)实现中,而且没办法修复,因为问题根植在算法本身。

方案二:RGA。一种叫做 RGA 的 CRDT 算法存在不那么严重的 interleaving 问题。用户 2 输入的 Alice 可能被插入到用户 1 输入的 dear 和 reader 之间,原因在于 RGA 使用了一种基于时间戳的列表数据结构。

RGA lesser interleaving anomaly

用户 1 依次输入"Hello!"、" reader"和" dear",用户 2 依次输入"Hello!"和" Alice"。根据 RGA 算法,用户的节点上会形成一个如下的树状链表,每个节点都指向输入时该位置所位于的节点,因此"!"指向"o"," reader"也指向"o"。算法规定,来到节点"o"后,对"o"的几个兄弟节点按照时间戳降序访问。

对于用户 1," Alice"可能在任何时刻抵达,而发生在本地节点上的输入" dear"、" reader"和"!"的顺序是确定的且时间戳 τ4>τ2>τ1,因此合并的结果可能是:

  1. 如果 τ2>τ3>τ1:Hello dear reader Alice!
  2. 如果 τ4>τ3>τ2:Hello dear Alice reader!
  3. 如果 τ3>τ4:Hello Alice dear reader!

其中,第二种情况是不合意的。但总体来说,比方案一可能造成的 character-by-character interleaving 要好。

RGA data structure

方案三:在 RGA 的基础上进行修改,杜绝了任何 interleaving 的出现,见论文 Interleaving anomalies in collaborative text editors

CRDTs: Moving list items

许多 CRDTs 都实现了 List 数据结构,但不支持 move 操作。用户可以把 move 拆解为 delete-then-insert。但是会发生下面的 anomaly。

move list item anomaly

因此,我们需要一个原子性的 move 操作。

move list item last-write-wins

在上面这个场景中,要想合并顺利发生,需要找到一个合适的数据结构来表达 pos,让 pos 具有 last writes win 的性质,即

merge(pos("phone joe") := "head of the list", pos("phone joe") := "after buy milk"))
=>
pos("phone joe") := "head of the list"

因此每个 list item 都要有一个 LWWRegister,并把它们放在一个 Add-Wins Set (AWSet) 中,形如 AWSet({v1: LWWRegister(p1), v2: LWWRegister(p2), ...})。此外,还要找到一个可以稳定表达 list item 位置的方法,不同的 CRDTs 使用了不同的方法。最终,普通 List CRDT + AWSet + LWWRegister = List CRDT with move operation,它可以 move 单个 list item。

如果是 move ranges of elements 呢?继续使用刚刚这个新的 List CRDT,在下面这个场景中,得不到期待的结果。理想:

move range of elements desired

现实:

move range of elements actual

目前还没有很好解决办法。详细讨论见论文 Moving Elements in List CRDTs

CRDTs: Moving subtrees of a tree

在一棵树内移动子树也是个很 tricky 的问题,但是这样的场景比较常见,例如文件系统就是一棵树。下面的场景有 4 种 move 结果:a 有重复,不好。b 不再是棵树,不好。c 和 d 都可以,都忽略掉其中一个 move。

move subtree 1

另一个场景。a 有环,不要。b 重复,不要。c 和 d 都可以。

move subtree 2

关键在于要设计出算法,使得合并的结果确定地选择 c,或者 d。一个可行的解决办法是引入操作的时间戳。在下面的例子中,要在副本 1 上合并来自副本 2 的操作序列,需要将副本 2 的操作序列逐个 move in。副本 2 中每个操作的 move in 都可能伴随副本 1 中多个操作的 undo 和 redo。在合并副本 2 的 mv B A 操作时,这个操作与 t=4 时发生的 mv A B 矛盾,被认为是 unsafe 的,选择无视。这个过程看上去非常耗时,但对于单个用户打字这样的场景,每秒 600 次 move 操作的效率是可以接受的。

how to merge move

下面是具体的数据结构。LogEntry 要存更多的上下文,用于 undo 和 redo。例如,要 undo 一个 op,只需把 child 的 parent 从 newParent 设为 oldParent,meta 从 newMeta 设为 oldMeta。

struct MoveOp {
Timestamp time; // globally unique (e.g. Lamport timestamp)
NodeID parent; // destination of move
Metadata meta; // e.g. filename within parent directory
NodeID child; // subtree being moved
}
struct LogEntry {
Timestamp time; // from the move operation
Option<NodeID> oldParent; // empty if child was previously not in the tree
Option<Metadata> oldMeta; // empty if child was previously not in the tree
NodeID newParent; // from the move operation
NodeID newMeta; // from the move operation
NodeID child; // from the move operation
}

下面是 move 算法的形式化表达。

定义 tree:Tree is a set of (parent, meta, child) triples.

定义 ancestor(a,b):称 a 是 b 的祖先,当且仅当 a 是 b 的 parent,或存在一个节点 c,使得 a 是 c 的祖先,且 c 是 b 的 parent。

func doMove(move, tree) =
if ancestor(move.child, move.parent) || move.child == move.parent {
// unsafe, do nothing
} else {
// part 1, the tree without the moved child
// part 2, the new edge created by the move
// new tree = part 1 union part 2
tree' = { (p, m, c) ∈ tree | c != move.child }{ (move.parent, move.meta, move.child) }
}

算法的关键在于要事先检查是否存在“把 parent 移到 child 下”的情况,如果是,则 do nothing,否则完成 move 操作。

Martin 还证明了 move 操作是 commutative 的,即 applyOps(ops1) == applyOps(ops2), if ops1 is a permutation of ops2

详细讨论见论文 A highly-available move operation for replicated trees and distributed filesystems

CRDTs: Reducing metadata overhead

上面提到,为了完成 undo 和 redo,CRDT 需要存储很大的 metadata。在下面这个例子中,真正的文本才占 1 字节,各种 metadata 就好几十字节。

crdt overhead

Martin 开始介绍 automerge 项目,他的 proposalPR#253 使用 columnar encoding 的思路,使得 CRDT 的 overhead 变得很小。

为了得到具体的压缩比例,Martin 团队在自己实现的一个小文本编辑器上,用 LaTeX 打了一篇学术 paper。这个文本编辑器能记录每一次键盘输入和光标移动,最终记下 300K 次键盘输入和光标移动,称为编辑历史。文本自身的体积为 100KB。下图演示了压缩优化的过程。

crdt compression

最后,Martin 介绍了 columnar encoding 的实现。

crdt columnar encoding

总结

CRDTs 的研究一直在快速推进,但目前还主要停留在原型(prototype)阶段,欢迎大家多多使用 CRDTs 搭建应用。

参考文献

讲义、视频、参考文献请参见信息页


© Yik San Chan. Built with Vercel and Nextra.