Опыты · JavaScript: от замыканий до автономных систем · Глава 17
Две копии без связи
Бесконфликтные реплицируемые типы данных (CRDT)
Всё считается в вашем браузере, никуда ничего не отправляется.
Про этот опыт
Что такое CRDT?
CRDT, бесконфликтный реплицируемый тип данных, - структура данных, устроенная так, что копии, изменённые независимо, всегда можно слить без согласования между ними, и результат слияния не зависит ни от порядка, ни от того, сколько раз копии обменялись состоянием. Копии, получившие одни и те же изменения, приходят к одному состоянию. G-Counter хранит отдельную ячейку для каждой копии и складывает их, OR-Set метит каждое добавление, и удаление убирает только те метки, которые видело. Строго идею описали Марк Шапиро и соавторы в 2011 году. CRDT гарантирует схождение копий, но не то, что результат соблюдает правила приложения.
Если при разделении сети система выбирает доступность, её копии продолжают работать порознь, и когда связь возвращается, их приходится сливать. В статье Amazon о хранилище Dynamo 2007 года главным примером была корзина покупателя: разошедшиеся корзины сливались объединением, поэтому добавленный товар никогда не терялся, а удалённый мог вернуться. Многие хранилища просто оставляют последнюю запись. CRDT переносят правило слияния в саму структуру данных.
Выберите вкладку и меняйте две копии, телефон и ноутбук, которые друг друга не видят. Потом нажимайте «Слить A и B», «Слить ещё раз» и «Слить в другом порядке» или включите сценарий книги. На счётчике «последний записавший» стоит рядом с G-Counter. В корзине объединение множеств стоит рядом с OR-Set, и можно убрать товар на одной копии, одновременно положив его на другой. На вкладке с местами одно свободное место, кнопка брони на каждой копии, связь, которую можно оборвать, и выбор между ответом сразу и согласованием до ответа.
В книге, в Node 24.16.0, счётчик 5, к которому на каждой копии прибавили по единице, слился в 6 по правилу «последний записавший побеждает» и в 7 как G-Counter, в любом порядке и при повторном слиянии. Корзина {книга, мяч}, где на одной копии мяч убрали, а на другой добавили ручку, после объединения содержала книгу, мяч и ручку, а после OR-Set книгу и ручку. Когда мяч на одной копии убрали, а на другой положили заново, победило добавление. Одно свободное место, забронированное на обеих копиях, слилось в 2 брони, и правило «не больше броней, чем мест» нарушилось.
Главное в главе показывает последняя вкладка. CRDT обещает, что копии сойдутся, но не обещает, что результат имеет смысл. Правила вроде «не продать больше мест, чем есть» или «не уйти в минус на счёте» требуют, чтобы копии договорились до ответа пользователю, и никакая структура данных этого не отменит. Где копиям придётся договариваться и сколько задержки на это не жалко, решает программист.
Из книги
JavaScript: от замыканий до автономных систем · Глава 17
Границы согласованности
Последний режим опыта это показывает. В зале одно свободное место, и два человека бронируют его на двух копиях, которые в этот момент не видят друг друга. Счётчик броней сливается в два без единого конфликта, потому что конфликтов в CRDT не бывает по построению. Только мест было одно. В 2014 году Питер Бейлис с соавторами разобрали, какие правила целостности данных можно соблюсти без согласования между копиями, а какие нельзя. Правило «не продать больше мест, чем есть» или «не уйти в минус на счёте» требует, чтобы копии договорились до того, как ответить пользователю. Никакая структура данных этого не отменит.