Содержание
Начало
Когда-то в 2012 я услышал что в google Jeff Dean сделал сихнронизацию времени между датацентрами с точностью до нано-секунд. Говорилось, что это было задумано, чтобы повысить качество «синхронизации» стуктур данных. На тот момент звучало как загадка.
Ответ я понял только сейчас, и он довольно простой: если раньше структуры данных были в памяти — список, дерево, слоеный список, суффиксное дерево… То теперь появились «распределенные» структуры.
Что такое CRDT
Если кратко то:
в eventually consistent базах данных доминирует 2 подхода
- либо это Last Write Wins (кто последний тот и прав)
- либо это запись в любую переменную всех конфликтующих изменений, и отложенное «исправление» конфликтов при чтении (подробнее в Riak manual в разделе Data Versioning and Consistency)
Пользователям тяжело писать код который исправляет конфликты в записях, этот код тяжело тестировать.
Поэтому БД вроде Riak приняли на вооружение новый подход — структуры данных которые даже при конфликтах постепенно «сходятся» к целевому состоянию, при условии что пакеты между узлами не теряются, и сама синхронизация не происходит мгновенно.
Называются они Convergent Replicated Data Types или по-простому Eventually Consistent Data Structures.
- G-Set — Set, допускает только добавление
- 2P-Set — Set, однократное добавление, однократное удаление
- LWW-Element-Set — Set, позволяет многократное удаление и добавление
- OR-Set — Set, добавление и удаление на узле «поддерживает happens-before»
- Max-Change-Set — Set, оптимизирующий объединение по большому числу элементов, нельзя удалить несуществующий элемент и добавить существующий
- G-Counter — Counter, только возрастает
- PN-Counter — Counter, можно увеличивать и уменьшать
На основе базовых можно делать более сложные — графы итд..
Плюсы и Минусы
Плюсы:
- бесплатная eventually constistency при использовании таких структур
Минусы:
- ограниченный \ «урезанный» функционал
- при длительном использовании эффективность падает, и надо делать распределенную сборку мусора на всех узлах (что требует 2-х фазный коммит)
- больше расход памяти
Как же это работает подробно есть или в видео или в doc к этой библиотеке на ruby
https://github.com/aphyr/meangirls
Презентация по CRDT
Автор — ведущий разработчик Riak (40мин)
Sean Cribbs — Eventually Consistent Data Structures from newthinking on Vimeo.
Исходная научная работа по CRDT
CRDTs: Consistency without concurrency control by Marc Shapiro (2009)