Когда вы используете 2P CRDT структуры данных (например, 2P-set), как вы освобождаете место?

Question

2P-набор позволяет удалять элементы из набора, но не позволяет освободить пространство, занимаемое этими удаленными элементами. Фактически, удаление элемента занимает место, а не освобождает его. Какой алгоритм для освобождения места для 2P структур?

Я пытаюсь понять, для каких проблем я могу использовать структуры CRDT на практике. Без возможности освободить пространство структуры 2P CRDT, по-видимому, имеют очень ограниченное использование для задач реального мира.

Answer 1

Хотя я не могу говорить за 2P-Set - так как я до сих пор не нашел практического использования для этого. Однако обычно мы можем применять несколько методов:

1. Сжатие метаданных, используемых CRDT: множество CRDT изначально были реализованы с очень простым дизайном, а затем оптимизированы для соответствия отраслевым стандартам. Примером такого может быть OR-Set переопределено поверх пунктирных векторных версий. В этой реализации вам не нужно хранить удаленные элементы в памяти: вместо этого мы можем отслеживать добавленные / удаленные элементы, используя точки, которые в конечном итоге могут быть сжаты в векторные часы. Здесь я описал эту проблему более подробно.
2. Сокращение может быть полезным, если некоторые реплики больше не нужны, например. потому что мы сократили количество узлов или эти узлы больше не доступны. В этом случае мы можем объединить полезную нагрузку с метаданными, как если бы она была создана другой репликой. Пример: дано G-Counter представлены с картой {A:1,B:2,C:1} и мертвый узел B (который больше не может увеличивать свое состояние), мы могли бы обрезать его путем слияния B вход в форму {A:3,C:1}, следовательно, уменьшая его размер при сохранении правильного значения. Проблема в том, что алгоритм сокращения должен гарантировать, что все реплики должны сходиться в этом решении независимо.