Идеей CRDT я загорелся, когда прочитал фразу «мерж изменений т | Стой под стрелой
Идеей CRDT я загорелся, когда прочитал фразу «мерж изменений текста становится тривиальным, если каждой букве присвоить уникальный id». Обожаю, когда глубокие идеи с далеко идущими следствиями укладываются в одно предложение!
Но давайте по порядку. Что такое CRDT? Это семейство структур данных, обладающих интересным свойством: их очень удобно мержить. То есть бесконфликтный мерж прям гарантируется: я что-то поменял, ты поменял что-то другое, Вася у себя вообще все переделал, и независимо от того, кто, что, где, как и когда, все эти изменения можно слить в общую кучу полностью автоматически в любом порядке и получить идентичный результат.
Звучит как магия? Почему все этим не пользуются? Подвох вот в чем. Не для всего есть CRDT То есть там, где такой алгоритм получилось придумать, CRDT есть и им можно пользоваться. А где не получилось — ну сорян, ничем не можем помочь.
Простейший пример CRDT — счетчик. Каждой операции присваивается уникальный id, грубо говоря, , и потом множества таких операций только объединяются. Я добавил 1? Кинь . Вася добавил 2? Добавь . Обменялись ченжами? У обоих получился сет {, }, который дает сумму 3 у нас обоих. Вообще объединение множеств это чуть ли не главный CRDT-прием, так что привыкайте.
А, забыл сказать. Удалять из этого множества никак нельзя. Потому что вдруг придет какой-нибудь Валера, который снял снепшот в 2007-м году, отключился от интернета, добавил единичку и потом пришел синкаться обратно только в 2022-м. То есть CRDT даже для одного числа это по сути неограничено растущее множество. Это еще одна причина, почему CRDT до сих пор не в каждой дырке.
Кстати, множество без удаления это тоже CRDT, очевидно. Тут любят приводить в пример корзину на Амазоне (а то, что из такой корзины нельзя удалять, так бизнес даже не против).
Еще один дегенератский вид CRDT это Last Write Wins. К каждому значению прикрепляем таймстемп и при мерже оставляем только то значение, у которого таймстемп больше. Ходит как CRDT, крякает как CRDT, значит может им называться. Полезность такого CRDT под большим вопросом, как осмысленно определять время между распределенными узлами не знает никто, но как escape hatch, когда ничего стоящего придумать не получается, а гарантий _хоть чего-нибудь_ хочется, сойдет. В конце концов, большинство систем сегодня так и так это Last Write Wins, только тут он математически формализован, получается.
Из полезного, для чего нет осмысленного CRDT (насколько я знаю) это линейный список. Например слайды в презентации, сделать так, чтобы их можно было переупорядочивать-удалять-добавлять вроде как на CRDT хорошо нельзя.
Но самое практичное это, конечно, текст. Как это ни странно, но для редактируемого текста есть хороший CRDT, и не один. И да, он обеспечивает бесконфликтный мерж любых изменений. Но на практике, при всех концептуальных плюсах, как-то не особо видно продуктов, основанных на CRDT. Может что-то с ним и не так, хотя я сходу не отвечу, что именно. Даже готовые библиотеки уже есть, а продуктов все никто не строит!
Еще мы как-то прикидывали, получится ли сделать на CRDT систему контроля версий. Из интересных свойств — CRDT отслеживает авторство каждой буквы в тексте. Побуквенный blame!
Кроме того, любой снепшот хранит всю историю редактирования, включая ответвления. То есть можно брать изменения Васяна и галочкой включать-выключать их прямо по ходу разработки. Или отматывать назад историю прям побуквенно, по ходу набора текста. Все это получается считай бесплатно.
Ну и отсутствие конфликтов. Кто не хотел бы Git без конфликтов? Я бы хотел.
Засада только, что для CRDT нужен специальный редактор. Нельзя поредактировать текстовый файлик в Vim-е и потом засунуть его в CRDT. Все это довольно плохо встраивается в сегодняшнюю plain text-ориентированную инфраструктуру.
Так что будущее конечно светлое, ждем, когда же наконец наступит. Может найдут применение когда Линукс завоюет десктопы.
