如何使用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

(或者查看由https://youtu.be/yCcWpzY8dIA?t=29m36s的精彩Martin Kleppmann编写的关于特定案例实现的更详细解释)

我还没有看到任何人在GUN之上具体实现RGA，但是考虑到你发送的代码是如此之短，它应该是相当简单的。(虽然"delete“需要是null tombstone，但这没问题)

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

https://gun.eco/docs/Counter

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

Gun.chain.rga = function(...

然后在内部，就像使用计数器一样，您可以调用gun.put(或gun.set(或任何其他命令来将数据保存到图形中(put和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或“注入”一个CRDT，只需@pgte将CRDT的数据结构建模到GUN上(可能通过GUN扩展提供了一个很好的简单应用程序接口)，那么你也可以让该扩展支持一个回调，如果传递这个回调，你就会gun.get(...通过RGA图/树并运行各种RGA逻辑，然后将结果返回给开发人员。这棵树可以由许多同行在GUN中并发地动态变异，比如Alice和Bob！

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