CRDT

Материал из in.wiki
Перейти к навигации Перейти к поиску
800px-T64 and pencil.jpg Это незавершённая статья.
Вы можете помочь проекту, исправив и дополнив её.

CRDT, Conflict-free replicated data type, бесконфликтный реплицируемый тип данных - это структура данных, которая реплицируется на несколько компьютеров в сети и имеет следующие свойства[1][2][3][4][5][6][7][8]:

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

Концепция CRDT была официально определена в 2011 году Марком Шапиро, Нуно Прегуисой, Карлосом Бакеро и Мареком Завирски.

Первоначальная разработка была мотивирована целями совместного редактирования текста, для которых CRDT выглядит более совершенной версией предшествующей техники операционной трансформации[9] и задачами, связанными с мобильными компьютерами.

CRDT также использовались в системах онлайн-чатов, социальных сетей, онлайн-азартных играх и на платформе распространения звука SoundCloud.

Распределенные базы данных NoSQL Redis, Riak и Cosmos DB напрямую поддерживают типы данных CRDT.

Бэкграунд[править | править код]

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

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

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

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

Примечания[править | править код]

  1. ↑ Shapiro, Marc. Conflict-Free Replicated Data Types // Stabilization, Safety, and Security of Distributed Systems / Marc Shapiro, Nuno Preguiça, Carlos Baquero … [и др.]. — Grenoble, France : Springer Berlin Heidelberg, 2011. — Vol. 6976. — P. 386–400. — ISBN 978-3-642-24549-7. — doi:10.1007/978-3-642-24550-3_29.
  2. ↑ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (13 January 2011). "A Comprehensive Study of Convergent and Commutative Replicated Data Types". Rr-7506.
  3. ↑ Shapiro, Marc; Preguiça, Nuno (2007). "Designing a Commutative Replicated Data Type". arXiv:0710.1784 [cs.DC].
  4. ↑ Oster, Gérald. Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work - CSCW '06 / Gérald Oster, Pascal Urso, Pascal Molli … [и др.]. — 2006. — P. 259. — ISBN 978-1595932495. — doi:10.1145/1180875.1180916.
  5. ↑ 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 (June 2009), "A Commutative Replicated Data Type for Cooperative Editing" (PDF), Proc 29th IEEE International Conference on Distributed Computing Systems, Montreal, Quebec, Canada: IEEE Computer Society, pp. 395–403, doi:10.1109/ICDCS.2009.20, ISBN 978-0-7695-3659-0, S2CID 8956372
  7. ↑ Baquero, Carlos; Moura, Francisco (1997), Specification of Convergent Abstract Data Types for Autonomous Mobile Computing, Universidade do Minho
  8. ↑ Schneider, Fred (December 1990). "Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial". ACM Computing Surveys. 22 (4): 299–319. doi:10.1145/98163.98167. S2CID 678818.
  9. ↑ Проектирование аналога Google Docs
  10. ↑ Компьютерами, виртуальными машинами и т.д.
Источник — https://in.wiki/w/index.php?title=CRDT&oldid=517174