gun - 如何使用 Gun 实现无损 CRDT？

Question

如何使用 Gun 创建 CRDT？

例如，如果我想实现一个只增长数组，其中每个元素都指向下一个元素，我该如何解决冲突？

为简化起见，让我们创建一个 Alice 和 Bob 合作的场景。

数组包含 3 个元素，[a, b, d]。

这个数组的内部表示是这样一个链表:

a => b => c

(当然，内部表示类似于 {value: 'a', next: { value: 'b' next: { value: 'c' }}})，但是我想你用简洁的符号明白了我的意思。

Alice 现在想在 b 和 d 之间插入元素 c。

同时，Bob 想在 b 和 d 之间插入元素 C。

同时，它们具有数组的内部表示:

爱丽丝:a => b => c => d

鲍勃:a => b => C => d

当他们加入 CRDT 时，他们将收敛到以下任一值:

a => b => c => C => d

或

a => b => C => c => d

无论如何，a) 它们都会收敛于相同的值并且 b) 它们不会丢失彼此的数据。

我们可以使用 Gun 实现吗？

(这个问题是 https://github.com/amark/gun/issues/602 的简化和后续问题)

Answer 1

是的。

这是几年前的代码演示:

https://youtu.be/rci89p0o2wQ

您可以在 GUN 的基础 CRDT 之上创建任何其他 CRDT 作为数据结构。

我们甚至为这类东西做了一个关于通用算法的完整卡通解释:

https://gun.eco/explainers/school/class.html

(或查看来自精彩的 Martin Kleppmann 的关于特定案例实现的更详细解释，起始于 https://youtu.be/yCcWpzY8dIA?t=29m36s)

我还没有看到有人专门在 GUN 上实现 RGA，但考虑到您发送的代码有多短，这应该很容易。 (虽然“删除”需要是空墓碑，但没关系)

最简单的方法可能是查看计数器 CRDT 以了解“如何使用自定义扩展将数据保存到 GUN”，这是一个仅需 12 行代码即可增长的 CRDT:

https://gun.eco/docs/Counter

你注意到它是非常基础的，RGA 会类似，你可能有一些 GUN 扩展(只是一个 JS 方法/函数，这使得开发人员更容易使用)，比如

Gun.chain.rga = function(...

然后在内部，就像计数器一样，您将调用 gun.put( 或 gun.set( 或任何其他命令来将数据保存到图形中(将和 set 本身只是像 RGA 一样的扩展，这里没什么特别的)你可以在其中构建/构建图形/树/表，或者你可以偷懒，只做类似的事情:

// fictional code
var myData = {
  rgaTree: {left: {}, right: {}}
}
myData.rgaTree.left.next = myData.rgaTree.right;
myData.rgaTree.right.prev = myData.rgaTree.left;
// yes! circular references are supported!
gun.put(myData);

显然，您可能想要更详细并使用 cuid 和其他东西控制 UUID，但您明白了。

没有理由直接替换 HAM CRDT 或在其旁边“注入(inject)”CRDT，只是@pgte 会在 GUN 上模拟 CRDT 的数据结构(可能通过 GUN 扩展使用一个简单的 API)，然后你' d 还让该扩展支持回调，如果通过回调，您将 gun.get(... 通过 RGA 图/树并运行各种 RGA 逻辑，然后再将结果返回给开发人员. 这棵树可以在 GUN 内部被许多对等点同时动态地改变，比如 Alice 和 Bob!

然后，GUN 将通过(许多)存储引擎之一(例如 IPFS!)将动态更改和更新的数据保存到磁盘，因此 IPFS 可以随着时间的推移托管数据的持久性，并且 GUN 可以管理 O(1)可变/变化/动态树/图形/索引结构的树查找。