Являются ли добавить / удалить установленный CRDT монотонным?

Внутренние элементы CRDT для добавления / удаления наборов являются монотонными, поскольку мы добавляем их только во внутренние наборы, поэтому внутреннее состояние CRDT никогда не может вернуться назад в логическое время.

Однако наблюдаемое состояние CRDT состоит в том, что мы добавляем и удаляем элементы, поэтому наблюдаемое состояние не должно быть монотонным.

Если мы объединяем эти системы в цепочку и предпринимаем действия, основанные на наличии или отсутствии элемента, это больше не выглядит монотонным. Конечное состояние все равно будет сходиться в конечном итоге, но мы можем или не можем увидеть некоторые элементы некоторое время, прежде чем оно стабилизируется. Маловероятно, что какой-то побочный эффект возникает из-за этого промежуточного состояния, например, когда пользователь читает состояние системы и реагирует до ее схождения.

Что значит для CRDT быть монотонным?

Источник

2 ответа

Просто добавьте TL;DR поверх удивительного ответа alekibango:

Монотонность относится к тому факту, что, как только реплика наблюдает за операциями и применяет их, состояние объекта всегда будет учитывать эту операцию.

Как только операция применяется, она никогда не будет применена.

Наблюдаемая немонотонность (большинства) наборов CRDT не отменяет монотонное свойство CRDT.

CRDT Наборы, которые поддерживают remove В основе работы лежат два G-комплекта:

  • Один из G-наборов - это набор элементов, которые были добавлены.
  • Другой G-набор - это набор элементов, которые были удалены.

Наблюдаемое состояние - это набор добавленных элементов минус набор удаленных элементов. Хотя каждый из внутренних наборов явно монотонен, их различие может показаться немонотонным.

Источник

CRDT означает бесконфликтный реплицируемый тип данных

Это означает, что (расходящиеся) экземпляры CRDT могут объединяться (в любом порядке и повторениях), чтобы в конечном итоге войти в правильное, согласованное состояние.

Монотонность может помочь в реализации этого (см. CALM - Согласованность как логическая монотонность). Но это не требование для вашего установленного экземпляра.

Прочитайте эти заметки на crdt: https://github.com/pfrazee/crdt_notes

Некоторые примеры наборов CRDT:

  • G-набор (только растущий набор, только добавление предметов)
  • 2P-набор (держит надгробия, элемент может быть вставлен только один раз)
  • LWW-set использует временные метки для отметки "времени" добавления / удаления элемента, позволяет добавлять / удалять элемент несколько раз. Одновременное добавление и удаление решается с использованием смещения.
  • OR-set - аналогично lww set, но использует уникальные теги, чтобы быть уверенным, какой элемент мы удаляем.
  • Оптимизированные наборы OR - могут быть пригодны для использования без большого количества надгробий, посмотрите их, если ваши наборы большие (и имеют много изменений).

некоторые ссылки, чтобы прочитать больше:

Источник
Другие вопросы по тегам