#common #highload
Иногда я замахиваюсь на что-то, что не могу скушать за один присест. Как сейчас. Я хотел просто написать небольшой постик про базу CRDT, а когда пошёл вникать, понял, что базово не получится. Получится скорее душно; придётся потратить больше времени, чем я готов; а чтобы нормально разобраться и объяснить, по-хорошему бы что-нибудь сесть покодить. Потому вместо готового текста сегодня сборка материалов по одной теме (я видел у людей, так делают).
Материалы, помеченные звёздочками, скипабельны, но могут помочь в более глубоком понимании.
Что впитать по CRDT.
На всякий случай я дам вам критерий, который поможет вам отсеять душные тексты от дворового контента (если вы любитель читать формальные статьи, то скипайте этот абзац): если в статье про CRDT вы встречаете слово "полурешётка", то закрывайте её. Вероятно это очередная статья на хабре, в которой формализм есть только для потешения эго автора. Всё, что нам нужно помнить про требования к свойствам операций для CRDT, -- это идемпотентность и коммутативность. Из них следует, что если у вас есть одинаковые множества операций над объектами (в любом порядке), то и стейты объектов будут одинаковыми. Больше пацанам и дамам ничего знать не надо.
А теперь ссылочки.
[*articles] Можно начать с нескольких статей Matthew Weidner:
-
Introduction -
Semantic Techniques-
Algorithmic Techniques-
Further TopicsОни немного душноватые, но если посидеть и подумать, а не смотреть тикток параллельно с чтением, можно что-нибудь понять.
[*articles] Если у вас много-много времени, то можно почитать
12 статей от Bartosz Sypytkowski. Каждая из них поменьше, так что может пойдёт легче.
Если прочитаете и то, и это, будете совсем большими молодцами и, много всего поймёте.
[*talk] Или может вам больше нравится видеоформат, так что можете послушать ликбез по основным структурам данных в CRDT концепции:
CRDT: Datatype for the Apocalypse. Правда сумейте вовремя остановиться, а то с какого-то момента начинаются Elixir-специфичные вещи, а мы всё-таки с вами на C++ пишем.
[talk] Теперь слушаем рассказал Martin Kleppman:
CRDTs and the Quest for Distributed Consistency. Тут он рассказывает и про Operational Transformation (OT), и про CRDT, и про очень важный в этой сфере Automerge. Есть много примеров, которые сильно качают понималку.
[*talk] Дальше можно посмотреть старенький
доклад про зачатки Google Docs и увидеть (если внимательно присмотреться) некоторые проблемы OT. Примерно так гуглодоки сейчас и реализованы.
[*article] Ну и тут вы можете почитать про то, как потенциально могут работать Google Sheets:
Conflict-free Replicated Spread Sheets.
Дальше можно посмотреть отличный доклад того же Martin Kleppman:
CRDTs: The Hard Parts. Тут вы узнаете, почему из "Hello Alice!" и "Hello Charlie!" может получится "Hello Al Ciharcliee!", про [открытые] проблемы перемещения элементов/символов/поддеревьев.
[*article] Интересно, что в докладе выше Kleppman говорит, что у LSeq есть проблемы, т.к. этот подход interleaving. А вот Bartosz Sypytkowski
писал про non-interleaving версию. Что-то там проапдейтил, лис.
[*article] Опять же в докладе Kleppman рассказывал про проблемы оверхеда CRDT. И это то, из-за чего CRDT иногда недолюбливают. Тут статья оптимизацию частных случаев:
Making CRDTs 98% More Efficient.
[*article] Тут есть очень прикольная (и жирная)
статья про то, как в каком-то Loro реализовывали свой очереднярский CRDT алгоритм для текста. Понравилось, потому что в начале есть интерактивная штука потыкаться и очень много букав. Прям фундаментально тему осветили.
[talk] Ещё есть вот такой несложный
докладик про то, как работает delta -- коллаборативный сервис для ведения заметок в Яндексе. Я вот им прям каждый день пользуюсь и очень довольный.
[*site] И если вдруг вам не хватило контента, идите на
crdt.tech. Там ещё тыща тыща постов, докладов и настоящих статей.
Что-то люди напридумали себе проблем и сидят их решают. Коллаборативное редактирование какое-то. Консенсус. Раньше вот угольком по очереди на камне мамонтов рисовали и всё норм было. Чего завелись.