CRDT: Conflict-free Replicated Data Types

[CheY]

Про patch theory и применение в darcs/pijul планируется статья? Тема интересная, спасибо.

[amberovsky]

Честно говоря нет, в планах пока что закончить с репликами, пройтись по шардированию и кворумам. Я помню была какая-то статья от авторов, не очень большая, но скорее теоретическая (в том смысле что тяжело будет адаптировать в формат Хабра). Посмотрю что из других материалов есть по вашей теме для статьи, и попробую написать, если будет время.
Спасибо за предложение!

[Xitsa]

Вот две статьи из блога, с помощью которых я наконец-то понял, в чём уникальность идеи Pijul:

• Merging and patches (архив) — Идеи за теорией патчей
• Merging, patches, and pijul (архив) — Особенности конкретной реализации теории патчей в pijul’е

Информация в них как раз в формате Хабра: полезная и не излишне подробная.

[LighteR]

Заметим, что SEC (как бы) решает проблему CAP теоремы: все три свойства выполняются.

Не выполняются. Consistency в контексте CAP-теоремы подразумавает, что при чтении мы всегда получаем последние (актуальные) данные. В случае с EC (как и SEC) это условие не выполняется.

[amberovsky]

Вы правы, я имел ввиду что если ослабить требование Strong consistency в CAP, то все три свойства будут выполняться.

[youngmysteriouslight]

Неотрицательный счётчик (Non-negative counter)
Простой реализации пока не существует. Предлагайте в комментариях ваши идеи, обсудим.

Можете пояснить постановку задачи?
Правильно ли понимаю, что речь идёт о предложении такой решетки, в которой ни один элемент не сооветствует отрицательному значению, т.е. нужно средствами CRDT гарантировать, чтобы на каждой реплике было неотрицательное значение?
Какое значение должно быть после слияния, если исходно на двух репликах была одно и то же состояние со значением 1 и на обеих репликах был сделан dec?

[amberovsky]

Пример — количество здоровья у игрока во время битвы или банковский счёт когда идёт несколько списаний с разных точек. Кстати интересный факт — банкоматы могут (и кое-где так и есть) выдавать деньги в условиях network partitioning.

Какое значение должно быть после слияния, если исходно на двух репликах была одно и то же состояние со значением 1 и на обеих репликах был сделан dec?

В случае независимых декрементов наш счётчик должен сойтись в -1.

т.е. нужно средствами CRDT гарантировать, чтобы на каждой реплике было неотрицательное значение?

Это как вы пожелаете. Предлагаю вам рассмотреть несколько вариантов
1) разрешать репликам временно уходить в минус (а что тогда делать клиентам, которые получили отрицательное? Значит ли это, что герой мёртв?), если при этом гарантировать, что целевое значение сходится в неотрицательное число (а как?)
2) запрещать репликам уходить в минус
3) разрешать итоговому значению временно уходить в минус (пример с банкоматами)

[Daemon_Hell]

Кстати интересный факт — банкоматы могут (и кое-где так и есть) выдавать деньги в условиях network partitioning.

Более того — можно провести транзакцию вообще без интернета. Но это решается не техническими методами — просто спишут деньги в минус и уже банк будет трясти их с клиента.

[youngmysteriouslight]

<off>Очень стыдно, что не в той ветке ответил. Ответ к этому комментарию.</off>

В случае независимых декрементов наш счётчик должен сойтись в -1.

Если мы разрешаем счётчику сходится в -1, то как же он тогда может называться неотрицательным?

Это как вы пожелаете.

Как так? Вы же задачу ставите. При том конкретную, потому что утверждаете, что «Простой реализации пока не существует».

[amberovsky]

Если мы разрешаем счётчику сходится в -1, то как же он тогда может называться неотрицательным?

Это ответ ваш вопрос «Какое значение должно быть после слияния, если исходно на двух репликах была одно и то же состояние со значением 1 и на обеих репликах был сделан dec?»

Понимаете, в случае с (S)EC вы уже не мыслите так категорично. Я вам предложил три варианта задачи — выбирайте любую. В любой разумной постановке (я же вам привёл примеры использования) этой задачи нет простого решения. Посмотрите — сколько вариантов реализаций множества придумано, каждый со своими особенностями.

[msvn]

например, пока ещё не придумали CRDT для JSON

Уже придумали, хотя это и не реализация JSON, но специальный протокол для CRDT: www.youtube.com/watch?v=QFWZlfSChoY

Демки здесь: github.com/gritzko/swarm#demos

[amberovsky]

Спасибо за ссылку, очень интересный проект.

Но как вы сами отметили, это не реализация JSON, если я правильно понял — там от него осталась только возможность конвертации из RON в JSON, так что ваш пример не совсем корректен.

Интересно, как я понял они вводят отношение порядка через uuid на каждое сообщение протокола и при этом на все CRDT применяют last write wins. Честно говоря, для меня не очень понятны цели этого проекта (всё-таки они предлагают и БД свою использовать — а это довольно серьёзное ограничение), было бы интересно пообщаться с автором.

Если вам интересно узнать про попытку реализации JSON — вот тут интересная статья, но она пока ещё в теоретическом статусе.

[msvn]

Не за что! Я за развитием идей CRDT c 2014-2015 года слежу.

вот тут интересная статья, но она пока ещё в теоретическом статусе

Вот репозиторий где есть прототип решения от авторов статьи: github.com/automerge/automerge

не очень понятны цели этого проекта

в конченом счёте — выпустить коммерческий продукт или сервис, например, по модели www.ditto.live

было бы интересно пообщаться с автором:

twitter.com/gritzko и gritzko

[amberovsky]

Спасибо за ссылку, я добавил её в статью!

Немного настораживает

It is based on academic research on JSON CRDTs, but the details of the algorithm in Automerge are different from the JSON CRDT paper, and we are planning to publish more detail about it in the future.

всё-таки статья была далеко от практической реализации, будем следить за развитием событий :)