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

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

0 голосов
/ 30 августа 2018

Как мне создать 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

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

Можем ли мы добиться этого с помощью пистолета?

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

1 Ответ

0 голосов
/ 01 сентября 2018

Да.

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

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 и прочего, но вы получите точку.

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

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

...