#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. Там ещё тыща тыща постов, докладов и настоящих статей.

Что-то люди напридумали себе проблем и сидят их решают. Коллаборативное редактирование какое-то. Консенсус. Раньше вот угольком по очереди на камне мамонтов рисовали и всё норм было. Чего завелись.