Как я могу реализовать CRDT без потерь, используя Gun?

Question

Как мне создать CRDT с помощью Gun?

Например, если я хочу реализовать массив только для роста, где каждый элемент указывает на следующий, как мне разрешать конфликты?

Для упрощения давайте создадим этот сценарий, в котором Алиса и Боб сотрудничают.

Массив содержит 3 элемента, [a, b, d],

Внутреннее представление этого массива будет связанным списком:

a => b => c

(конечно, внутреннее представление было бы что-то вроде {value: 'a', next: { value: 'b' next: { value: 'c' }}}), но я думаю, что вы поняли мою точку зрения.

Алиса теперь хочет вставить элемент c между b а также d,

Одновременно Боб хочет вставить элемент C между b а также d,

Одновременно у них есть это внутреннее представление массива:

Алиса: a => b => c => d

Боб: a => b => C => d

Когда они присоединяются к CRDT, они сходятся к одному из следующих значений:

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

или же

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

Неважно, что, а) они оба сходятся по одному значению и б) они не потеряют данные друг друга.

Можем ли мы достичь этого с помощью Gun?

(Этот вопрос является упрощенным и дополнительным вопросом к https://github.com/amark/gun/issues/602)

Answer 1

Да.

Вот демонстрация кода, сделавшего это несколько лет назад:

https://youtu.be/rci89p0o2wQ

Вы можете создать любую другую CRDT как структуру данных поверх базовой CRDT GUN.

Мы даже сделали целый мультфильм для общих алгоритмов для такого типа вещей:

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

(Или посмотрите более подробное объяснение для конкретной реализации, замечательный Мартин Клеппманн, начинающий со страницы https://youtu.be/yCcWpzY8dIA?t=29m36s)

Я не видел, чтобы кто-нибудь реализовал RGA специально для GUN, но, учитывая, насколько короткий код, который вы отправили, это должно быть довольно легко. (Хотя "удалить" должно быть пустым надгробием, но это нормально)

Вероятно, проще всего начать с поиска в счетчике CRDT "как начать сохранять данные в GUN с пользовательским расширением", CRDT только для роста, всего в 12 строках кода:

https://gun.eco/docs/Counter

Вы заметите, что это очень просто, RGA будет похожим, у вас, вероятно, будет какое-то расширение GUN (просто метод / функция JS, который облегчает использование разработчиками), например

Gun.chain.rga = function(...

Тогда внутри, как со счетчиком, вы бы позвонили gun.put( или же gun.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);

Очевидно, что вы, возможно, захотите быть более подробным и контролировать UUID с помощью cuids и прочего, но вы получите суть.

Нет никаких оснований фактически заменять HAM CRDT напрямую или "вставлять" CRDT рядом с ним, просто @pgte смоделирует структуру данных CRDT в GUN (возможно, с хорошим простым API через расширение GUN), тогда у вас также будет это расширение поддерживает обратный вызов, который, если вы передадите gun.get(... через граф / дерево RGA и запустите различную логику RGA, прежде чем выкладывать результат обратно разработчику. Это дерево может динамически мутировать одновременно в GUN многими пэрами, такими как Алиса и Боб!

Затем GUN сохранит это динамически изменяющееся и обновляющее данные на диск с помощью одного из (многих) механизмов хранения (таких как IPFS!), Чтобы IPFS могла хранить постоянство данных во времени, а GUN мог управлять поисками дерева O(1), которые являются изменчивыми / изменяющимися / динамическими структурами дерева / графика / индекса.