The Problem With Embedded CRDT Counters and a Solution 阅读笔记。


论文地址

目前存在的问题

当直接使用 OR-Set 记录 Map 的 field ,PN-Counter 存储对应的 value 时,可能存在以下问题:利用 OR-Set 虽可确定某 field 是否存在,但其对应的 value 并未包含所有历史操作信息,仅记录了当前状态值。因此,对于该 field 的删除操作在同步至对端时,并不能撤消所观察到的历史操作的影响。

例如,在经历以下操作序列之后

time replica 1 replica 2
$t_1$ m[‘a’].inc(2)
$t_2$ – sync – – sync –
$t_3$ m[‘a’].inc(3) m.remove(‘a’)
$t_4$ – sync – – sync –

我们期望的结果是最终收敛至 $3$:

embedded_crdt_counters_anomaly_desired

但事实上,会收敛至 $5$,因为在 $t_4$ 同步时,$t_3$ 的 m.remove('a') 并未撤销在 $t_2$ 已同步的 m['a'].inc(2) 操作:

embedded_crdt_counters_anomaly_fact

当使用 remove-wins set 作为 field 时,虽然可以撤销所观察的操作,但同时也会丢弃未观察到的并发操作,收敛至 $0$:

embedded_crdt_counters_anomaly_remove_win

add-wins 在每次 inc 操作时更新 tag,remove-wins 则会复用已存在的 tag

可行解

  1. 每个 field 在删除时,存储 tombstone。虽然可行,但是 GC 较为麻烦,希望可以将 GC 控制在 key 维度,如此 GC 的实现便可借鉴 key 的主动过期机制。

  2. remove-wins set 加 fresh 机制

    • remove-wins set 记录 Map 的 field
    • 在将状态传输至其他 replicas 之后调用 fresh 生成新的 tag,以防止本地后续更新被其他 replicas 并行的 reset 操作覆盖
    • 该方法的缺点是 tag 的数量较多,与调用 fresh 的次数成正比

    embedded_crdt_counters_remove_win_fresh

Resettable Counter

基于之前的讨论,作者提出了 Resettable Counter,其描述如下:

embedded_crdt_counters_resettable_counter

Resettable CounterOR-Set 有效结合便可实现我们想要的数据结构(如,ZSET)。但需要注意的是:

  • 上述数学描述给出的 Resettable Counter 是 reset-wins 的,因此需要手动调用 fresh 接口防止更新操作被并行的 reset 所覆盖
  • 只有在计数器状态被发送到其他 replicas 后调用 fresh 可适当减少 tag 数量
  • 上述数学描述是 state-CRDT,在与 Optimized Add-Wins OR-Set 结合时,需要进行适当修改
  • 事实上,当 Resettable CounterOptimized Add-Wins OR-Set 结合后,在集合 $s$ 中存储的即为操作历史(五元组 <id, seq, ele, pcnt, ncnt>),利用 tag(<id, seq>) 的唯一性、集合的互异性以及加减操作满足结合律和交换律的性质使得集合 $s$ 的 join 满足交换律、结合律和幂等的性质,故最后所有副本收敛至同一状态