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

论文地址

1. 目前存在的问题

当直接使用 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

2. 可行解

  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

3. Resettable Counter

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

embedded_crdt_counters_resettable_counter

将 Resettable Counter 和 OR-Set 有效结合便可实现我们想要的数据结构(如，ZSET)。但需要注意的是：

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