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

compare nosql db

Начало

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

Презентация по CRDT

Автор — ведущий разработчик Riak (40мин)


Sean Cribbs — Eventually Consistent Data Structures from newthinking on Vimeo.

Исходная научная работа по CRDT

CRDTs: Consistency without concurrency control by Marc Shapiro (2009)

Другие записи...

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

* Please Enter the Output

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>