CRDT
|
Это незавершённая статья. Вы можете помочь проекту, исправив и дополнив её. |
CRDT, Conflict-free replicated data type, бесконфликтный реплицируемый тип данных - это структура данных, которая реплицируется на несколько компьютеров в сети и имеет следующие свойства[1][2][3][4][5][6][7][8]:
- Приложение может обновлять любую реплику самостоятельно, одновременно и без координации с другими репликами.
- Алгоритм (который сам является частью типа данных) автоматически устраняет любые несоответствия, которые могут возникнуть.
- Хотя реплики могут иметь разное состояние в любой конкретный момент времени, в конечном итоге они гарантированно сходятся.
Концепция CRDT была официально определена в 2011 году Марком Шапиро, Нуно Прегуисой, Карлосом Бакеро и Мареком Завирски.
Первоначальная разработка была мотивирована целями совместного редактирования текста, для которых CRDT выглядит более совершенной версией предшествующей техники операционной трансформации и задачами, связанными с мобильными компьютерами.
CRDT также использовались в системах онлайн-чатов, социальных сетей, онлайн-азартных играх и на платформе распространения звука SoundCloud.
Распределенные базы данных NoSQL Redis, Riak и Cosmos DB напрямую поддерживают типы данных CRDT.
Примечания
- ↑ 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.
- ↑ Shapiro, Marc; Preguiça, Nuno; Baquero, Carlos; Zawirski, Marek (13 January 2011). "A Comprehensive Study of Convergent and Commutative Replicated Data Types". Rr-7506.
- ↑ Shapiro, Marc; Preguiça, Nuno (2007). "Designing a Commutative Replicated Data Type". arXiv:0710.1784 [cs.DC].
- ↑ 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.
- ↑ Letia, Mihai; Preguiça, Nuno; Shapiro, Marc (2009). "CRDTs: Consistency without Concurrency Control". Computing Research Repository. arXiv:0907.0929.
- ↑ 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
- ↑ Baquero, Carlos; Moura, Francisco (1997), Specification of Convergent Abstract Data Types for Autonomous Mobile Computing, Universidade do Minho
- ↑ 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.