Бесконфликтный реплицированный тип данных - Conflict-free replicated data type

В распределенных вычислений, а бесконфликтный реплицированный тип данных (CRDT) это структура данных который может быть воспроизведен на нескольких компьютерах в сеть, где реплики можно обновлять самостоятельно и одновременно без координация между репликами и где всегда можно математически разрешить несоответствия, которые могут возникнуть.[1][2][3][4][5][6][7][8]

Концепция CRDT была официально определена в 2011 году Марком Шапиро, Нуно Прегуичей, Карлосом Бакеро и Мареком Завирски. Первоначально мотивом разработки была совместное редактирование текста и Мобильные вычисления. CRDT также использовались в онлайн чат системы, азартные игры онлайн, а в SoundCloud Платформа распространения звука. В NoSQL распределенные базы данных Redis, Риак и Cosmos DB имеют типы данных CRDT.

Фон

Одновременные обновления нескольких реплик одних и тех же данных без координации между компьютерами, на которых размещены реплики, могут привести к несоответствия между репликами, что в общем случае может быть неразрешимым. Для восстановления согласованности и целостности данных при конфликтах между обновлениями может потребоваться полное или частичное удаление некоторых или всех обновлений.

Соответственно, большая часть распределенных вычислений сосредоточена на проблеме предотвращения одновременных обновлений реплицированных данных. Но другой возможный подход оптимистическая репликация, где разрешено выполнение всех одновременных обновлений с возможным возникновением несоответствий, а результаты объединяются или «разрешаются» позже. В этом подходе согласованность между репликами в итоге восстанавливается путем «слияния» разных реплик. Хотя оптимистическая репликация может не работать в общем случае, оказывается, что существует значительный и практически полезный класс структур данных, CRDT, где она действительно работает - где математически всегда возможно объединить или разрешить одновременные обновления на разных репликах структура данных без конфликтов. Это делает CRDT идеальным вариантом для оптимистичной репликации.

Например, односторонний Булево Флаг события - это тривиальная CRDT: один бит со значением true или false. Истина означает, что какое-то конкретное событие произошло хотя бы один раз. Ложь означает, что событие не произошло. После установки в значение true флаг не может быть снова установлен в значение false. (Событие, которое произошло, не может не произойти.) Метод разрешения - «истинно выигрывает»: при слиянии реплики, где флаг истинен (эта реплика наблюдала событие), и другой реплики, где флаг ложен (что реплика не наблюдала событие), разрешенный результат - истина - событие наблюдалось.

Типы CRDT

Есть два подхода к CRDT, каждый из которых может обеспечить сильный возможная последовательность: операционные CRDT[9][10] и государственные CRDT.[11][12]

Две альтернативы теоретически эквивалентны, поскольку одна может имитировать другую.[1]Однако есть практические различия. CRDT на основе состояний часто проще разработать и реализовать; их единственное требование от коммуникационной подложки - это какое-то протокол сплетен Их недостатком является то, что все состояние каждой CRDT в конечном итоге должно передаваться на каждую другую реплику, что может быть дорогостоящим. Напротив, операционные CRDT передают только операции обновления, которые обычно невелики. Однако для операционных CRDT требуется гарантии от связующее ПО; что операции не удаляются и не дублируются при передаче другим репликам, и что они доставляются в причинный порядок.[1]

Операционные CRDT

CRDT на основе эксплуатации также называют коммутативные реплицированные типы данных, или же CmRDT. Реплики CmRDT передают состояние, передавая только операцию обновления. Например, CmRDT из одного целого числа может транслировать операции (+10) или (-20). Реплики получают обновления и применяют их локально. Операции коммутативный. Однако они не обязательно идемпотент. Таким образом, коммуникационная инфраструктура должна гарантировать, что все операции с репликой доставляются другим репликам без дублирования, но в любом порядке.

Чистый операционные CRDT[10] представляют собой вариант CRDT на основе операций, который уменьшает размер метаданных.

Государственные CRDT

Государственные CRDT называются конвергентные реплицированные типы данных, или же CvRDT. В отличие от CmRDT, CvRDT отправляют свое полное локальное состояние другим репликам, где состояния объединяются функцией, которая должна быть коммутативный, ассоциативный, и идемпотент. В слияние функция обеспечивает присоединиться для любой пары состояний реплики, поэтому набор всех состояний образует полурешетка. В Обновить функция должна монотонно возрастать внутреннее состояние, согласно тому же частичный заказ правила как полурешетка.

Состояние дельты CRDT[12][13] (или просто Delta CRDT) - это оптимизированные CRDT на основе состояний, в которых распространяются только недавно примененные изменения к состоянию, а не все состояние.

Сравнение

Хотя CmRDT предъявляет больше требований к протоколу передачи операций между репликами, они используют меньшую полосу пропускания, чем CvRDT, когда количество транзакций мало по сравнению с размером внутреннего состояния. Однако, поскольку функция слияния CvRDT является ассоциативной, слияние с состоянием некоторой реплики приводит ко всем предыдущим обновлениям этой реплики. Протоколы сплетен хорошо работают для распространения состояния CvRDT на другие реплики, сокращая использование сети и обрабатывая изменения топологии.

Некоторые нижние оценки[14] о сложности хранения состояний CRDT известны.

Известные CRDT

G-Counter (счетчик только для роста)

целое число полезной нагрузки [n] P начальное [0,0, ..., 0] обновление приращение() пусть g = мой ID() P [g]: = P [g] + 1 запрос ценить(): целое v пусть v = Σя P [i] compare (X, Y): логическое b let b = (∀i ∈ [0, n - 1]: XP [i] ≤ YP [i]) merge (X, Y): полезная нагрузка Z let ∀i ∈ [0, n - 1]: ZP [i] = Максимум(X.P [i], Y.P [i])

Этот CvRDT реализует счетчик для кластера п узлы. Каждому узлу в кластере присваивается идентификатор от 0 до п - 1, который извлекается при вызове мой ID(). Таким образом, каждому узлу назначается собственный слот в массиве. п, который увеличивается локально. Обновления распространяются в фоновом режиме и объединяются с помощью Максимум() каждого элемента в п. Функция сравнения включена, чтобы проиллюстрировать частичный порядок состояний. Функция слияния коммутативна, ассоциативна и идемпотентна. Функция обновления монотонно увеличивает внутреннее состояние в соответствии с функцией сравнения. Таким образом, это правильно определенный CvRDT, который в конечном итоге обеспечит сильную согласованность. Эквивалент CmRDT передает операции увеличения по мере их получения.[2]

PN-счетчик (положительно-отрицательный счетчик)

полезная нагрузка целое число [n] P, целое число [n] N начальное [0,0, ..., 0], [0,0, ..., 0] обновление приращение() пусть g = мой ID() P [g]: = P [g] + 1обновить декремент() пусть g = мой ID() N [g]: = N [g] + 1 запрос ценить(): целое v пусть v = Σя P [i] - Σя N [i] compare (X, Y): логическое b let b = (∀i ∈ [0, n - 1]: XP [i] ≤ YP [i] ∧ ∀i ∈ [0, n - 1]: XN [i] ≤ YN [i]) merge (X, Y): полезная нагрузка Z пусть ∀i ∈ [0, n - 1]: ZP [i] = Максимум(X.P [i], Y.P [i]) пусть ∀i ∈ [0, n - 1]: Z.N [i] = Максимум(X.N [i], Y.N [i])

Распространенной стратегией при разработке CRDT является объединение нескольких CRDT для создания более сложной CRDT. В этом случае два G-счетчика объединяются для создания типа данных, поддерживающего операции увеличения и уменьшения. G-счетчик «P» считает приращения; а G-счетчик «N» считает декременты. Значение PN-счетчика - это значение счетчика P минус значение счетчика N. Слияние обрабатывается, позволяя объединенному счетчику P быть объединением двух счетчиков P G, и аналогично для N счетчиков. Обратите внимание, что внутреннее состояние CRDT должно монотонно увеличиваться, даже если его внешнее состояние отображается через запрос может вернуться к предыдущим значениям.[2]

G-Set (набор только для выращивания)

набор полезных данных Начальное ∅обновление Добавить(элемент e) A: = A ∪ {e} запрос искать(элемент e): логическое b let b = (e ∈ A) compare (S, T): логическое b let b = (S.A ⊆ T.A) merge (S, T): полезная нагрузка U let U.A = S.A ∪ T.A

G-Set (набор только для выращивания) - это набор, который позволяет только добавлять. После добавления элемент не может быть удален. Слияние двух G-Set - это их союз.[2]

2P-Set (двухфазный комплект)

набор полезной нагрузки A, начальный набор R ∅, ∅query искать(элемент e): boolean b let b = (e ∈ A ∧ e ∉ R) обновить Добавить(элемент e) A: = A ∪ {e} обновить удалять(элемент е) предварительно искать(e) R: = R ∪ {e} compare (S, T): логическое b let b = (SA ⊆ TA ∧ SR ⊆ TR) merge (S, T): полезная нагрузка U let UA = SA ∪ TA let UR = SR ∪ TR

Два G-набора (наборы только для выращивания) объединяются для создания 2P-набора. С добавлением набора удаления (называемого набором «надгробий») элементы можно добавлять, а также удалять. После удаления элемент не может быть повторно добавлен; то есть однажды элемент е находится в наборе надгробий, запрос никогда больше не вернет True для этого элемента. 2P-набор использует семантику "удаляет-выигрывает", поэтому удалять(е) имеет приоритет над Добавить(е).[2]

LWW-Element-Set (набор-элементов-победителей последней записи)

LWW-Element-Set похож на 2P-Set в том, что он состоит из «набора добавления» и «набора удаления» с отметкой времени для каждого элемента. Элементы добавляются в LWW-Element-Set путем вставки элемента в добавляемый набор с меткой времени. Элементы удаляются из набора LWW-Element-Set путем добавления в набор удаления, снова с меткой времени. Элемент является членом LWW-Element-Set, если он находится в наборе добавления, но либо не в наборе удаления, либо в наборе удаления, но с более ранней отметкой времени, чем последняя отметка времени в наборе добавления. Слияние двух реплик LWW-Element-Set состоит из объединения добавляемых наборов и объединения удаляемых наборов. Когда временные метки равны, в игру вступает «смещение» LWW-Element-Set. LWW-Element-Set может быть смещен в сторону добавления или удаления. Преимущество LWW-Element-Set над 2P-Set состоит в том, что, в отличие от 2P-Set, LWW-Element-Set позволяет повторно вставить элемент после его удаления.[2]

OR-Set (Наблюдаемый-Удалить набор)

OR-Set похож на LWW-Element-Set, но использует уникальные теги вместо меток времени. Для каждого элемента в наборе поддерживается список дополнительных тегов и список удаляемых тегов. Элемент вставляется в OR-Set путем создания нового уникального тега и добавления его в список дополнительных тегов для элемента. Элементы удаляются из OR-Set путем добавления всех тегов из списка добавленных тегов элемента в список удаления тегов (надгробных камней). Чтобы объединить два OR-Set для каждого элемента, пусть его список add-tag будет объединением двух списков add-tag, и то же самое для двух списков remove-tag. Элемент является членом набора тогда и только тогда, когда список добавляемых тегов за вычетом списка удаляемых тегов не пуст.[2] Возможна оптимизация, которая избавляет от необходимости поддерживать набор надгробий; это позволяет избежать потенциально неограниченного роста набора надгробий. Оптимизация достигается за счет сохранения вектора временных меток для каждой реплики.[15]

Последовательность CRDT

Последовательность, список или заказанный набор CRDT можно использовать для создания Коллективный редактор в реальном времени, как альтернатива Операционная трансформация (ОТ).

Некоторые известные CRDT последовательности - Treedoc,[5] RGA,[16] Woot,[4] Логоот,[17] и LSEQ.[18]ЯЩИК[19] это децентрализованный редактор реального времени, построенный на основе LSEQSplit (расширение LSEQ) и запускаемый в сети браузеров, использующих WebRTC.LogootSplit [20] был предложен как расширение Logoot, чтобы уменьшить количество метаданных для CRDT последовательностей. НЕМОЙ [21][22] представляет собой интерактивный веб-редактор для совместной работы в режиме реального времени, основанный на алгоритме LogootSplit.

Промышленное использование

Нимбус Нота это приложение для совместной работы, которое использует Yjs CRDT для совместного редактирования. [23]

Redis - это распределенная, высокодоступная и масштабируемая база данных в памяти, которая использует CRDT для реализации глобально распределенных баз данных на основе открытого исходного кода Redis и полностью совместима с ним. SoundCloud с открытым исходным кодом Роши, CRDT с набором элементов LWW для потока SoundCloud, реализованный поверх Redis.[24]

Риак - это распределенное хранилище данных типа "ключ-значение" NoSQL, основанное на CRDT.[25] Лига Легенд использует реализацию Riak CRDT для своей внутриигровой системы чата, которая обрабатывает 7,5 миллионов одновременных пользователей и 11 000 сообщений в секунду.[26] Bet365, хранит сотни мегабайт данных в Риак реализация OR-Set.[27]

TomTom использует CRDT для синхронизации навигационных данных между устройствами пользователя.[28]

Феникс, веб-фреймворк, написанный на Эликсир, использует CRDT для поддержки обмена информацией между несколькими узлами в реальном времени в версии 1.2.[29]

Facebook реализует CRDT в своей базе данных Apollo с «согласованностью в масштабе» с малой задержкой.[30]

Телетайп для Атом использует CRDT, чтобы разработчики могли делиться своим рабочим пространством с членами команды и совместно работать над кодом в режиме реального времени.[31]

OrbitDB от Haja Networks использует операционные CRDT в своей основной структуре данных, IPFS-Log.[32]

яблоко реализует CRDT в приложении Notes для синхронизации автономных изменений между несколькими устройствами.[33]

Рекомендации

  1. ^ а б c Шапиро, Марк; Прегуиса, Нуно; Бакеро, Карлос; Завирски, Марек (2011), Бесконфликтные реплицированные типы данных (PDF), Конспект лекций по информатике, 6976, Гренобль, Франция: Springer Berlin Heidelberg, стр. 386–400, Дои:10.1007/978-3-642-24550-3_29, ISBN  978-3-642-24549-7
  2. ^ а б c d е ж грамм Шапиро, Марк; Прегуиса, Нуно; Бакеро, Карлос; Завирски, Марек (13 января 2011 г.). «Комплексное исследование конвергентных и коммутативных реплицированных типов данных». Rr-7506.
  3. ^ Шапиро, Марк; Прегуиса, Нуно (2007). «Разработка коммутативного реплицированного типа данных». Репозиторий компьютерных исследований (CoRR). абс / 0710.1784. arXiv:0710.1784. Bibcode:2007arXiv0710.1784S.
  4. ^ а б Остер, Жеральд; Урсо, Паскаль; Молли, Паскаль; Имин, Абдессамад (2006). Материалы 20-й юбилейной конференции 2006 года по совместной работе с компьютерной поддержкой - CSCW '06. п. 259. CiteSeerX  10.1.1.554.3168. Дои:10.1145/1180875.1180916. ISBN  978-1595932495.
  5. ^ а б Летия, Михай; Прегуиса, Нуно; Шапиро, Марк (2009). «CRDT: согласованность без контроля параллелизма». Репозиторий компьютерных исследований (CoRR). абс / 0907.0929. arXiv:0907.0929. Bibcode:2009arXiv0907.0929L.
  6. ^ Прегуиса, Нуно; Маркес, Жоан Мануэль; Шапиро, Марк; Летия, Михай (июнь 2009 г.), Коммутативный реплицированный тип данных для совместного редактирования (PDF), Монреаль, Квебек, Канада: Компьютерное общество IEEE, стр. 395–403, Дои:10.1109 / ICDCS.2009.20, ISBN  978-0-7695-3659-0
  7. ^ Бакеро, Карлос; Моура, Франциско (1997). «Спецификация конвергентных абстрактных типов данных для автономных мобильных вычислений». Universidade do Minho. Цитировать журнал требует | журнал = (помощь)
  8. ^ Шнайдер, Фред (декабрь 1990). «Внедрение отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие». Цитировать журнал требует | журнал = (помощь)
  9. ^ Летия, Михай; Прегуиса, Нуно; Шапиро, Марк (1 апреля 2010 г.). «Согласованность без контроля параллелизма в больших динамических системах» (PDF). SIGOPS Oper. Syst. Rev. 44 (2): 29–34. Дои:10.1145/1773912.1773921.
  10. ^ а б Бакеро, Карлос; Алмейда, Пауло Сержио; Шокер, Али (2014-06-03). Магутис, Костас; Пицух, Питер (ред.). Создание CRDT на основе эксплуатации на основе эксплуатации. Конспект лекций по информатике. Springer Berlin Heidelberg. С. 126–140. CiteSeerX  10.1.1.492.8742. Дои:10.1007/978-3-662-43352-2_11. ISBN  9783662433515.
  11. ^ Бакеро, Карлос; Моура, Франсиско (1 октября 1999 г.). «Использование структурных характеристик для автономной работы». SIGOPS Oper. Syst. Ред.: 90–96.
  12. ^ а б Алмейда, Пауло Сержио; Шокер, Али; Бакеро, Карлос (13 мая 2015 г.). Буаджани, Ахмед; Фоконье, Hugues (ред.). Эффективные основанные на состоянии CRDT с помощью дельта-мутации. Конспект лекций по информатике. Издательство Springer International. С. 62–76. arXiv:1410.2803. Дои:10.1007/978-3-319-26850-7_5. ISBN  9783319268491.
  13. ^ Алмейда, Пауло Сержио; Шокер, Али; Бакеро, Карлос (4 марта 2016 г.). «Типы реплицированных данных дельта-состояния». Журнал параллельных и распределенных вычислений. 111: 162–173. arXiv:1603.01529. Bibcode:2016arXiv160301529S. Дои:10.1016 / j.jpdc.2017.08.003.
  14. ^ Буркхардт, Себастьян; Гоцман Алексей; Ян, Хонгсок; Завирски, Марек (23 января 2014 г.). «Типы реплицированных данных: спецификация, проверка, оптимальность». Материалы 41-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования. С. 271–284. Дои:10.1145/2535838.2535848. ISBN  9781450325448.
  15. ^ Аннетт Биениуса, Марек Завирски, Нуно Прегуиса, Марк Шапиро, Карлос Бакеро, Вальтер Балегас, Серхио Дуарте, «Оптимизированный бесконфликтный тиражируемый набор» (2012) arXiv:1210.3368
  16. ^ Ро, Хуйн-Гуль; Чон, Мёнджэ; Ким, Джин-Су; Ли, Джунвон (2011). «Реплицированные абстрактные типы данных: строительные блоки для совместных приложений». Журнал параллельных и распределенных вычислений. 71 (2): 354–368. Дои:10.1016 / j.jpdc.2010.12.006.
  17. ^ Вайс, Стефан; Урсо, Паскаль; Молли, Паскаль (2010). «Logoot-Undo: Распределенная система совместного редактирования в P2P-сетях». Транзакции IEEE в параллельных и распределенных системах. 21 (8): 1162–1174. Дои:10.1109 / TPDS.2009.173. ISSN  1045-9219.
  18. ^ Неделек, Брайс; Молли, Паскаль; Мостефауи, Ачур; Desmontils, Эммануэль (2013). «LSEQ». LSEQ - адаптивная структура для последовательностей в распределенном совместном редактировании. п. 37. Дои:10.1145/2494266.2494278. ISBN  9781450317894.
  19. ^ Неделек, Брайс; Молли, Паскаль; Mostefaoui, Achour (2016). «CRATE: пишем истории вместе с нашими браузерами». Материалы 25-й Международной конференции Companion в World Wide Web. п. 231. Дои:10.1145/2872518.2890539. Архивировано из оригинал на 2020-01-01. Получено 2020-01-01.
  20. ^ Андре, Люк; Мартин, Стефан; Остер, Жеральд; Игнат, Клаудиа-Лавиния (2013). «Поддержка адаптируемой детализации изменений для крупномасштабного совместного редактирования». Труды Международной конференции по совместным вычислениям: сети, приложения и совместная работа - CollaborateCom 2013. С. 50–59. Дои:10.4108 / icst.collaboratecom.2013.254123.
  21. ^ "НЕМОЙ". Команда побережья. 24 марта 2016 г.
  22. ^ Николя, Матье; Эльвингер, Викториан; Остер, Жеральд; Игнат, Клаудиа-Лавиния; Чарой, Франсуа (2017). «MUTE: одноранговый веб-редактор для совместной работы в реальном времени». Материалы панелей, демонстраций и плакатов ECSCW 2017. Дои:10.18420 / ecscw2017_p5.
  23. ^ «О CRDT». Получено 2020-06-18.
  24. ^ Бургон, Питер (9 мая 2014 г.). «Роши: CRDT-система для событий с отметками времени». SoundCloud.
  25. ^ «Представляем Riak 2.0: типы данных, строгая согласованность, полнотекстовый поиск и многое другое». Basho Technologies, Inc. 29 октября 2013 г.
  26. ^ Хофф, Тодд (13 октября 2014 г.). «Как League of Legends расширила чат до 70 миллионов игроков - нужно много миньонов». Высокая масштабируемость.
  27. ^ Маклин, Дэн. «bet365: Почему bet365 выбрала Риака». Басё.
  28. ^ Иванов Дмитрий. «Практическая демистификация CRDT».
  29. ^ МакКорд, Крис. "Что делает присутствие Феникса особенным".
  30. ^ Мак, Сандер. «Facebook анонсирует Apollo на QCon NY 2014».
  31. ^ «Кодируйте вместе в реальном времени с Teletype для Atom». Atom.io. 15 ноября 2017 года.
  32. ^ "OrbitDB / ipfs-log на Github". Получено 2018-09-07.
  33. ^ «Заголовки IOS Objective-C, полученные в результате самоанализа во время выполнения: NST / IOS-Runtime-Headers». 2019-07-25.

внешняя ссылка