stringtranslate.com

Бесконфликтный реплицируемый тип данных

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

  1. Приложение может обновлять любую реплику независимо, одновременно и без координации с другими репликами.
  2. Алгоритм (который сам является частью типа данных) автоматически устраняет любые несоответствия, которые могут возникнуть.
  3. Хотя реплики могут иметь разное состояние в любой конкретный момент времени, в конечном итоге они гарантированно сойдутся.

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

Фон

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

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

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

Типы CRDT

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

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

CRDT на основе состояний (также называемые конвергентными реплицированными типами данных , или CvRDT ) определяются двумя типами, типом для локальных состояний и типом для действий над состоянием, вместе с тремя функциями: функцией для создания начального состояния , функцией слияния состояний и функцией для применения действия для обновления состояния. CRDT на основе состояний просто отправляют свое полное локальное состояние другим репликам при каждом обновлении, где полученные новые состояния затем объединяются в локальное состояние. Для обеспечения окончательной сходимости функции должны удовлетворять следующим свойствам: Функция слияния должна вычислять соединение для любой пары состояний реплик и должна образовывать полурешетку с начальным состоянием в качестве нейтрального элемента. В частности, это означает, что функция слияния должна быть коммутативной , ассоциативной и идемпотентной . Интуиция, лежащая в основе коммутативности, ассоциативности и идемпотентности, заключается в том, что эти свойства используются для того, чтобы сделать CRDT инвариантным при переупорядочении и дублировании пакетов. Кроме того, функция обновления должна быть монотонной относительно частичного порядка, определяемого указанной полурешеткой.

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

CRDT на основе операций

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

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

Сравнение

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

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

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

Известные CRDT

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

полезная нагрузка  целое число [ n ]  P  начальное  [ 0 , 0 ,..., 0 ] обновление  приращения ()  пусть  g  =  myId ()  P [ g ]  :=  P [ g ]  +  1 запрос  значение ()  :  целое число  v  пусть  v  =  Σi  P [ i ] сравнение  ( X ,  Y )  :  логическое значение  b  пусть  b  =  ( ∀i  ∈  [ 0 ,  n  -  1 ]  :  X . P [ i ]  ≤  Y . P [ i ]) слияние  ( X ,  Y )  :  полезная нагрузка  Z  пусть  ∀i  ∈  [ 0 ,  n  -  1 ]  :  Z . P [ i ]  =  max ( X . P [ i ],  Y . P [ i ])

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

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

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

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

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

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

G-Set (grow-only set) — это набор, который допускает только добавления. Элемент, однажды добавленный, не может быть удален. Слияние двух G-Set — это их объединение. [2]

2P-Set (двухфазный набор)

 полезная нагрузка набор  A ,  набор  R  начальный  ∅ ,  ∅ запрос  поиск ( элемент  e )  :  логическое  значение b  пусть  b  =  ( e  ∈  A  ∧  e  ∉  R ) обновление  добавить ( элемент  e )  A  : =  A  ∪  { e } обновление  удалить ( элемент  e )  предварительный  поиск ( e )  R  : =  R  ∪  { e } сравнение  ( S ,  T )  :  логическое  значение b  пусть  b  =  ( S.A ⊆ T.A  ∧ S.R ⊆ T.R ) слияние (  S , T ) : полезная нагрузка U пусть U.A = S.A ∪ T.A пусть U.R = S.R ∪ T.R​​​​​​​​​​​​​​

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

LWW-Element-Set (Последний-Записанный-Выигрывает-Элемент-Набор)

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

OR-Set (наблюдаемый-удаляемый набор)

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

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

Последовательность, список или упорядоченный набор CRDT можно использовать для создания совместного редактора в реальном времени в качестве альтернативы операционному преобразованию (OT).

Некоторые известные Sequence CRDTs: Treedoc, [5] RGA, [17] Woot, [4] Logoot, [18] и LSEQ. [19] CRATE [20] — это децентрализованный редактор в реальном времени, созданный на основе LSEQSplit (расширение LSEQ) и работающий в сети браузеров с использованием WebRTC . LogootSplit [21] был предложен как расширение Logoot с целью сокращения метаданных для CRDTs последовательностей. MUTE [22] [23] — это онлайн-редактор для совместной работы в реальном времени на основе одноранговой сети, работающий на основе алгоритма LogootSplit.

Известно, что промышленные последовательности CRDT, включая версии с открытым исходным кодом, превосходят академические реализации благодаря оптимизации и более реалистичной методологии тестирования. [24] Основным популярным примером является Yjs CRDT, пионер в использовании простого списка вместо дерева (как автослияние Клеппмана ). [25]

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

Смотрите также

Ссылки

  1. ^ abc Шапиро, Марк; Прегиса, Нуно; Бакеро, Карлос; Завирски, Марек (2011). «Бесконфликтные реплицированные типы данных». Стабилизация, безопасность и защищенность распределенных систем (PDF) . Конспект лекций по информатике. Том 6976. Гренобль, Франция: Springer Berlin Heidelberg. С. 386–400. doi :10.1007/978-3-642-24550-3_29. ISBN 978-3-642-24549-7. S2CID  51995307.
  2. ^ abcdefg Шапиро, Марк; Прегиса, Нуно; Бакеро, Карлос; Завирски, Марек (13 января 2011 г.). «Комплексное исследование конвергентных и коммутативных реплицируемых типов данных». Рр-7506 .
  3. ^ Шапиро, Марк; Прегиса, Нуно (2007). «Проектирование коммутативного реплицируемого типа данных». arXiv : 0710.1784 [cs.DC].
  4. ^ ab Oster, Gérald; Urso, Pascal; Molli, Pascal; Imine, Abdessamad (2006). Труды конференции 20-й годовщины 2006 года по компьютерной поддержке кооперативной работы - CSCW '06 . стр. 259. CiteSeerX 10.1.1.554.3168 . doi :10.1145/1180875.1180916. ISBN  978-1595932495. S2CID  14596943.
  5. ^ ab Letia, Mihai; Preguiça, Nuno; Shapiro, Marc (2009). "CRDTs: Consistency without Concurrency Control". Computing Research Repository . arXiv : 0907.0929 .
  6. ^ Preguiça, Nuno; Marques, Joan Manuel; Shapiro, Marc; Letia, Mihai (июнь 2009 г.), «Коммутативный реплицированный тип данных для кооперативного редактирования» (PDF) , Proc 29th IEEE International Conference on Distributed Computing Systems , Монреаль, Квебек, Канада: IEEE Computer Society, стр. 395–403, doi :10.1109/ICDCS.2009.20, ISBN 978-0-7695-3659-0, S2CID  8956372
  7. ^ Бакеро, Карлос; Моура, Франциско (1997), Спецификация конвергентных абстрактных типов данных для автономных мобильных вычислений , Университет Минью.
  8. ^ Шнайдер, Фред (декабрь 1990 г.). «Реализация отказоустойчивых служб с использованием подхода конечного автомата: учебное пособие». ACM Computing Surveys . 22 (4): 299–319. doi : 10.1145/98163.98167 . S2CID  678818.
  9. ^ «Бесконфликтные реплицированные типы данных» (PDF) . inria.fr. 19 июля 2011 г.
  10. ^ Бакеро, Карлос; Моура, Франциско (1 октября 1999 г.). «Использование структурных характеристик для автономной работы». SIGOPS Oper. Syst. Rev. 33 ( 4): 90–96. doi :10.1145/334598.334614. hdl : 1822/34984 . S2CID  13882850.
  11. ^ ab Almeida, Paulo Sérgio; Shoker, Ali; Baquero, Carlos (2015-05-13). "Эффективные CRDTS на основе состояний с помощью дельта-мутации". В Bouajjani, Ahmed; Fauconnier, Hugues (ред.). Сетевые системы . Конспект лекций по информатике. Том 9466. Springer International Publishing. стр. 62–76. arXiv : 1410.2803 . doi :10.1007/978-3-319-26850-7_5. ISBN 9783319268491. S2CID  7852769.
  12. ^ Летиа, Михай; Прегиса, Нуно; Шапиро, Марк (1 апреля 2010 г.). «Согласованность без управления параллелизмом в больших динамических системах» (PDF) . SIGOPS Oper. Syst. Rev. 44 ( 2): 29–34. doi :10.1145/1773912.1773921. S2CID  6255174.
  13. ^ ab Baquero, Carlos; Almeida, Paulo Sérgio; Shoker, Ali (2014-06-03). «Создание CRDTS на основе операций». В Magoutis, Kostas; Pietzuch, Peter (ред.). Distributed Applications and Interoperable Systems . Lecture Notes in Computer Science. Vol. 8460. Springer Berlin Heidelberg. pp. 126–140. CiteSeerX 10.1.1.492.8742 . doi :10.1007/978-3-662-43352-2_11. ISBN  9783662433515.
  14. ^ Алмейда, Пауло Сержио; Шокер, Али; Бакеро, Карлос (04 марта 2016 г.). «Типы реплицируемых данных дельта-состояния». Журнал параллельных и распределенных вычислений . 111 : 162–173. arXiv : 1603.01529 . дои : 10.1016/j.jpdc.2017.08.003. S2CID  7990602.
  15. ^ Буркхардт, Себастьян; Гоцман, Алексей; Ян, Хонгсок; Завирски, Марек (23 января 2014 г.). «Реплицированные типы данных: спецификация, проверка, оптимальность». Труды 41-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (PDF) . стр. 271–284. doi :10.1145/2535838.2535848. ISBN 9781450325448. S2CID  15023909.
  16. ^ Биениуса, Аннетт; Завирски, Марек; Прегиса, Нуно; Шапиро, Марк; Бакеро, Карлос; Балегас, Вальтер; Дуарте, Сержио (2012). «Оптимизированный бесконфликтный реплицируемый набор». arXiv : 1210.3368 [cs.DC].
  17. ^ Ро, Хён-Гуль; Чон, Мёнджае; Ким, Джин-Су; Ли, Джунвон (2011). «Реплицированные абстрактные типы данных: строительные блоки для совместных приложений». Журнал параллельных и распределенных вычислений . 71 (2): 354–368. doi :10.1016/j.jpdc.2010.12.006.
  18. ^ Вайс, Стефан; Урсо, Паскаль; Молли, Паскаль (2010). «Logoot-Undo: Распределенная система совместного редактирования в сетях P2P». Труды IEEE по параллельным и распределенным системам . 21 (8): 1162–1174. doi :10.1109/TPDS.2009.173. ISSN  1045-9219. S2CID  14172605.
  19. ^ Nédelec, Brice; Molli, Pascal; Mostefaoui, Achour; Desmontils, Emmanuel (2013). "LSEQ: Адаптивная структура для последовательностей в распределенном совместном редактировании". Труды симпозиума ACM 2013 года по проектированию документов (PDF) . стр. 37–46. doi :10.1145/2494266.2494278. ISBN 9781450317894. S2CID  9215663.
  20. ^ Nédelec, Brice; Molli, Pascal; Mostefoui, Achour (2016). «CRATE: Writing Stories Together with our Browsers». Труды 25-й Международной конференции Companion on World Wide Web. стр. 231. doi :10.1145/2872518.2890539. S2CID  5096789. Архивировано из оригинала 01.01.2020 . Получено 01.01.2020 .
  21. ^ Андре, Люк; Мартин, Стефан; Остер, Жеральд; Игнат, Клаудия-Лавиния (2013). «Поддержка адаптивной детализации изменений для массового совместного редактирования». Труды Международной конференции по совместным вычислениям: сетевые технологии, приложения и совместное использование ресурсов – CollaborateCom 2013. стр. 50–59. doi : 10.4108/icst.collaboratecom.2013.254123 . ISBN 978-1-936968-92-3.
  22. ^ "MUTE". Coast Team. 24 марта 2016 г.
  23. ^ Николя, Матье; Эльвингер, Викториен; Остер, Джеральд; Игнат, Клавдия-Лавиния; Шаруа, Франсуа (2017). «MUTE: одноранговый веб-редактор для совместной работы в режиме реального времени». Материалы панелей, демонстраций и плакатов ECSCW 2017 . doi : 10.18420/ecscw2017_p5. S2CID  43984228.
  24. ^ Джентл, Сеф. «Быстрые CRDT: приключения в оптимизации». josephg.com . Получено 1 августа 2021 г.
  25. ^ "yjs/yjs: Общие типы данных для создания программного обеспечения для совместной работы". GitHub .
  26. ^ "О CRDTs" . Получено 2020-06-18 .
  27. ^ "Погружение в CRDT". Redis . 17 марта 2022 г. Получено 22 мая 2024 г.
  28. ^ Бургон, Питер (9 мая 2014 г.). «Roshi: система CRDT для событий с временными метками». SoundCloud.
  29. ^ «Представляем Riak 2.0: типы данных, строгая согласованность, полнотекстовый поиск и многое другое». Basho Technologies, Inc. 29 октября 2013 г.
  30. ^ Хофф, Тодд (13 октября 2014 г.). «Как League of Legends масштабировала чат до 70 миллионов игроков — для этого нужно много миньонов». Высокая масштабируемость .
  31. ^ Маклин, Дэн. «bet365: Почему bet365 выбрал Риак». Басё.
  32. ^ Иванов, Дмитрий. «Практическая демистификация ЦРДТ».
  33. ↑ МакКорд, Крис (25 марта 2016 г.). «Что делает Phoenix Presence особенным».
  34. ^ Мак, Сандер. «Facebook объявляет об Apollo на QCon NY 2014» .
  35. ^ «FlightTracker: Согласованность в оптимизированных для чтения интернет-магазинах Facebook». research.facebook.com . Получено 8 декабря 2022 г. .
  36. ^ «Совместное кодирование в реальном времени с помощью Teletype для Atom». Atom.io. 15 ноября 2017 г.
  37. ^ "OrbitDB/ipfs-log на Github". GitHub . Получено 2018-09-07 .
  38. ^ "Заголовки IOS Objective-C, полученные из интроспекции времени выполнения: NST/IOS-Runtime-Headers". GitHub . 2019-07-25.
  39. ^ "Понимание служб каталогов NetWare". support.novell.com . Получено 2024-11-02 .
  40. ^ "Синхронизация eDirectory и фоновые процессы". support.novell.com . Получено 2024-11-02 .

Внешние ссылки