CRDT — распределенная консистентная магия

Начало

Когда-то в 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)