1

添加/删除集 CRDT 的内部是单调的，因为我们只添加到内部集，因此 CRDT 的内部状态永远不会在逻辑时间上倒退。

但是，CRDT 的观察状态是我们正在添加和删除元素，因此观察到的状态不必是单调的。

如果我们将这些系统链接在一起并根据元素的存在或不存在采取行动，它看起来就不再单调了。最终状态最终仍会收敛，但在它稳定之前我们可能会或可能不会看到一些元素。由于该中间状态而发生某些副作用的可能性不大，例如用户读取系统状态并在其收敛之前做出反应。

CRDT 是单调的意味着什么？

4

2 回答 2

2

只是添加一个 TL;DR 在 alekibango 的真棒答案之上：

单调性是指一旦操作被副本观察和应用，对象的状态将始终考虑该操作。

一旦应用了操作，就永远不会取消应用。

观察到的（大多数）CRDT 集的非单调性不会使 CRDT 单调特性无效。

支持该remove操作的 CRDT 集的核心是两个 G-Set：

  • 其中一个 G 集是添加的元素集。
  • 另一个 G 集是被移除的元素集。

观察到的状态是添加元素的集合减去移除的元素的集合。尽管每个内部集显然是单调的，但它们的差异可能看起来是非单调的。

于 2018-04-12T00:11:36.597 回答
1

CRDT 表示无冲突复制数据类型

这意味着（发散的）CRDT 实例可能会合并在一起（以任何顺序和重复）最终进入正确、一致的状态。

单调性可能有助于实现这一点（参见 CALM -- 一致性作为逻辑单调性）。但这不是您设置的实例的要求。

阅读 crdt 上的这些注释：https ://github.com/pfrazee/crdt_notes

CRDT 集的一些示例是：

  • G-set （只成长套装，只增加物品）
  • 2P-set（保留墓碑，元素只能插入一次）
  • LWW-set 使用时间戳来标记添加/删除项目的“时间”，允许多次添加/删除项目。并发添加和删除是使用偏差决定的。
  • OR-set - 类似于 lww set，但使用唯一标签来确定我们要删除的元素。
  • 优化的 OR-Sets - 可以在没有很多墓碑的情况下使用，如果你的集合很大（并且有很多变化），请查看那些。

一些阅读更多内容的链接：

于 2018-03-08T14:05:24.653 回答