CRDT

Правку стиля главы 44 базового курса — 146 изменений по словам — раздадим трём редакторам по очереди: первое изменение первому, второе второму, третье третьему, четвёртое снова первому. Каждый правит свою копию старой версии, ничего не зная о других. Потом правки надо свести. git сравнивает строки, а в HTML-главе абзац — одна длинная строка, и если в абзаце правили двое, это конфликт. Листайте абзацы.

Попарно git merge-file находит 17, 18 и 16 конфликтов: столько мест, где человеку придётся вручную выбирать, что оставить. А слияние по словам сводит три копии без единого вопроса, и результат совпадает с настоящей правкой байт в байт — как если бы главу правил один человек. Секрет не в хитром сравнении: каждое слово помнит своё место в общем документе, и правка выражена как «удалить такие-то слова, вставить новые после такого-то», а такие правки складываются в любом порядке.

Идея

Копии меняются независимо и рассылают изменения как придётся: с задержкой, в разном порядке, иногда повторно. Если тип данных устроен так, что слияние не зависит от порядка и повторов, все копии, получившие одни и те же изменения, оказываются в одном состоянии — без сервера, без выборов лидера, без блокировок. Такие типы называют CRDT: бесконфликтными реплицируемыми типами данных.

Есть два способа добиться этого. В первом копии пересылают состояние целиком, и слияние двух состояний должно быть коммутативным, ассоциативным и идемпотентным: a ⊔ b = b ⊔ a, (a ⊔ b) ⊔ c = a ⊔ (b ⊔ c), a ⊔ a = a. Во втором копии пересылают операции, и тогда коммутативными должны быть сами операции, а доставка — в причинном порядке, без потерь и без повторов. Это противоположность консенсусу: Raft добивается одного порядка всех записей и платит за это доступностью, когда большинство недоступно; CRDT не нужен общий порядок, и каждая копия принимает изменения всегда, даже без сети.

Счётчик

Начнём с самого простого — лайков. Три телефона принимают лайки сами и иногда обмениваются состоянием. Если у каждого одно число, а при обмене побеждает большее («больше — значит новее»), лайки теряются: телефон A принял пять, B — три, C — четыре, а после обменов все показывают пять вместо двенадцати.

G-счётчик (от grow-only, «только растёт») хранит вектор: сколько лайков принял каждый телефон. Свой элемент телефон увеличивает сам, а при обмене берёт покомпонентный максимум. Значение — сумма вектора. Чужой счётчик никто не увеличивает, поэтому максимум не теряет ничего: каждый элемент — это знание о чьём-то счётчике, и знание новее, если число больше. Это те же векторные часы, только считающие не события, а лайки.

Уменьшать G-счётчик нельзя: максимум не умеет «забывать». Для лайков, которые можно отменить, держат два G-счётчика — плюсы и минусы — и показывают разность; это PN-счётчик.

Множество

Со множеством сложнее: что делать, если одна копия удалила элемент, а другая в это же время его добавила? Простое множество, где удаление — запись в «удалённые навсегда», вычеркнутое не вернёт никогда, даже если его добавили снова. OR-множество (observed-remove, «удаление увиденного») решает это метками: каждое добавление получает уникальную метку, а удаление вычёркивает только те метки, которые удаляющий видел. Добавление, о котором он не знал, остаётся в силе: одновременное добавление побеждает удаление. Это первая задача статьи — список покупок на двоих.

Текст

Текст — последовательность, и вставка «на пятую позицию» у разных копий означает разное: у кого-то перед пятой позицией уже вставили два слова. Поэтому позиции заменяют номерами. Каждый элемент — слово или символ — получает уникальный номер: пару «счётчик, копия», где счётчик больше всех номеров, которые копия уже видела, как у часов Лэмпорта. Вставка говорит не «на позицию 5», а «после элемента с номером такой-то». Удаление не убирает элемент, а превращает его в надгробие: на него могут ссылаться чужие вставки, пришедшие позже.

Остаётся решить, что делать, когда после одного элемента параллельно вставили двое. В RGA (replicated growable array, растущий реплицированный массив) правило такое: встаём после элемента-соседа, но пропускаем всех, у кого номер больше нашего, — это параллельные вставки, которым правило отдаёт первенство, и всё, что вставлено после них позже. Тогда все копии ставят параллельные вставки в одном порядке — по убыванию номеров, — какой бы порядок доставки ни был. Вторая задача статьи — ровно это правило.

Сходимость не означает, что результат осмыслен. Если двое по-разному исправили одно слово — один написал «slow», другой «fast», — RGA удалит старое слово и оставит обе вставки рядом: «fastslow». Конфликта в смысле системы нет, все копии видят одно и то же, но решать, что имелось в виду, придётся человеку. Есть и тоньше: при параллельном наборе в одно место некоторые алгоритмы перемешивают буквы двух авторов. Мартин Клеппман с соавторами в 2019 году показали такое перемешивание у Logoot и LSEQ; RGA при обычном наборе слева направо его не допускает, но при наборе в обратную сторону может. Позже появились алгоритмы вроде Fugue, которые сводят перемешивание к минимуму.

Код

Листинг показывает счётчик лайков с одним числом и с вектором, затем RGA на настоящих правках трёх редакторов: каждая копия получает операции в своём порядке, и все три приходят к одному тексту, совпадающему с правкой стиля. В конце — два редактора меняют одно и то же слово.

Сколько это стоит

Время операций почти бесплатно: увеличить счётчик, добавить метку, вставить элемент после соседа — O(1). Платят памятью. G-счётчик держит число на каждую копию, когда-либо принимавшую лайки. OR-множество помнит удалённые метки, иначе пришедшее позже старое состояние оживит вычеркнутое. Текст хранит номер у каждого элемента и надгробие у каждого удалённого: в правке трёх редакторов на 16 684 видимых элемента приходится ещё 327 надгробий, а у документа, который правят годами, надгробий может накопиться больше, чем живого текста.

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

Где работает

Хранилища. Riak предлагает CRDT как типы данных: счётчики, множества, карты, флаги. Redis Enterprise в базах Active-Active, которые работают сразу на нескольких площадках, сливает одновременные записи как CRDT — у счётчиков, множеств и строк свои правила слияния.

Совместное редактирование. Automerge и Yjs — библиотеки, которые позволяют редактировать документ на нескольких устройствах без постоянной связи и сливать правки потом; внутри — последовательности с номерами элементов и надгробиями, как у RGA. Google Docs устроены иначе: на преобразованиях операций, где сервер упорядочивает правки. Figma в 2019 году описала свою синхронизацию как вдохновлённую CRDT, но упрощённую: раз в системе есть центральный сервер, часть забот о порядке можно отдать ему.

История

Совместное редактирование без центра искали с конца 1980-х: Клэренс Эллис и Саймон Гиббс в 1989 году предложили преобразование операций, на котором выросли первые совместные редакторы. Алгоритмы, где сходимость следует из устройства данных, появились в середине 2000-х: WOOT в 2006 году, Treedoc в 2009-м, RGA в 2011-м. Общую теорию — условия, при которых копии гарантированно сходятся, — и само название CRDT дали в 2011 году Марк Шапиро, Нуно Прегиса, Карлос Бакеро и Марек Завирский.

Задачи

Первая — OR-множество: список покупок на двоих, где одновременное добавление побеждает удаление. Вторая — RGA: собрать документ из операций, пришедших в любом порядке, в том числе из настоящих правок трёх редакторов.