Способно ли OR-Set сохранить конкурентное добавление элемента после удаления на другой реплике без координации?
Да. OR-Set сохраняет конкурентное добавление: удаление убирает только те уникальные версии элемента, которые реплика уже видела. Если добавление произошло одновременно с удалением и не было замечено удаляющей репликой, оно сохраняется после слияния.
Такое поведение называется add-wins. Оно достигается не сравнением времени, а использованием уникальных идентификаторов добавлений и слиянием их состояний.
Обычные реплицируемые множества плохо работают при временной недоступности связи: две реплики могут независимо добавить и удалить один элемент, после чего системе нужно детерминированно объединить состояния без центрального координатора.
CRDT появились как класс структур данных, в которых локальные изменения можно выполнять независимо, а состояния — объединять так, чтобы результат не зависел от порядка доставки обновлений. Для этого структура задаёт математически корректную операцию слияния и явную политику разрешения конфликтов.
Пусть реплика A добавила элемент x, а реплика B ранее увидела x и удалила его. Если связь между репликами временно отсутствует, A может одновременно добавить x снова, пока B выполняет удаление.
Простое правило «удаление всегда побеждает» может потерять новое, конкурентное добавление. Правило Last Write Wins зависит от часов, может скрыть корректную операцию из-за расхождения времени и не выражает причинную связь между изменениями.
В OR-Set каждое добавление получает уникальный идентификатор, например пару из идентификатора реплики и локального счётчика. Поэтому два добавления одного логического элемента считаются разными версиями.
Удаление записывает не просто имя элемента, а множество идентификаторов добавлений, которые удаляющая реплика наблюдала в момент удаления. При слиянии удаляются именно эти идентификаторы. Любой идентификатор конкурентного добавления, которого в удаляющем состоянии не было, остаётся в множестве.
Обычно состояние можно концептуально представить как две части: набор известных добавлений и набор удалённых идентификаторов. Слияние выполняется объединением этих наборов, после чего элемент присутствует, если у него остался хотя бы один идентификатор добавления, не отмеченный удалённым.
Ключевое свойство — идемпотентность слияния: повторная доставка одного состояния не меняет результат. Порядок доставки также не должен влиять на итог, что позволяет передавать состояния или операции через ненадёжную сеть.
У OR-Set есть ограничения. Уникальные идентификаторы и записи об удалениях требуют памяти, а безопасное удаление таких метаданных возможно только при наличии гарантии, что все заинтересованные реплики уже увидели соответствующие изменения. Поэтому на практике применяют причинные контексты, версии, компактные «dot»-метаданные или контролируемую сборку мусора.
OR-Set не является универсальным ответом на любой конфликт. Если бизнес-правило требует, чтобы удаление всегда побеждало конкурентное добавление, нужна другая CRDT-семантика, например remove-wins set, либо отдельный слой разрешения конфликтов.
В офлайн-приложении список участников проекта реплицируется между телефоном и сервером. Пользователь на телефоне повторно добавил участника, пока сервер обрабатывал удаление старой версии этого участника.
Рассматривались три варианта. Last Write Wins прост и компактен, но зависит от часов и может потерять изменение. Remove-wins set предсказуемо запрещает появление участника после конкурентного удаления, но требует повторного добавления после восстановления связи. OR-Set сохраняет новое добавление, если удаление его не наблюдало, что лучше соответствует семантике «удалить текущую версию, но не будущую».
Выбрали OR-Set, потому что офлайн-изменения должны сохраняться, а конкурентное повторное добавление считалось осознанным действием пользователя. Для ограничения роста метаданных сервер периодически выполнял уплотнение после подтверждения, что все реплики получили старые версии.
Потому что удаление в OR-Set адресует конкретные идентификаторы уже наблюдавшихся добавлений. У конкурентного добавления другой идентификатор, отсутствующий в удаляющем контексте, поэтому операция удаления не затрагивает его. Это и есть источник семантики add-wins.
Каждое добавление получает отдельный уникальный идентификатор. Удаление должно отметить все наблюдавшиеся идентификаторы элемента; после этого элемент исчезнет, если конкурентных или более новых добавлений не осталось. Поэтому логическое значение элемента нельзя надёжно представить одной булевой переменной.
Нет, если другие реплики ещё могут прислать состояние, в котором эти добавления присутствуют. Раннее удаление метаданных способно снова сделать старую версию видимой или нарушить сходимость. Сборка мусора безопасна только после доказательства, что все реплики учли соответствующие удаления, либо после применения протокола снапшотов и согласованного уплотнения.