CRDT: различия между версиями

Материал из in.wiki
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 
{{Болванка}}
 
{{Болванка}}
−
'''CRDT, Conflict-free replicated data type, бесконфликтный реплицируемый тип данных'''  - это структура данных, которая реплицируется на несколько компьютеров в сети и имеет следующие свойства:
+
'''CRDT, Conflict-free replicated data type, бесконфликтный реплицируемый тип данных'''  - это структура данных, которая реплицируется на несколько компьютеров в сети и имеет следующие свойства<ref name="2011CRDT">{{cite book|last1=Shapiro|series=Lecture Notes in Computer Science|s2cid=51995307|pages=386–400|publisher=Springer Berlin Heidelberg|doi=10.1007/978-3-642-24550-3_29|isbn=978-3-642-24549-7|location=Grenoble, France|issue=Proc 13th International Symposium, SSS 2011|volume=6976|title=Stabilization, Safety, and Security of Distributed Systems|first1=Marc|chapter=Conflict-Free Replicated Data Types|year=2011|first4=Marek|last4=Zawirski|first3=Carlos|last3=Baquero|first2=Nuno|last2=Preguiça|url=https://hal.inria.fr/hal-00932836/file/CRDTs_SSS-2011.pdf}}</ref><ref name="2011CRDTSurvey">{{cite journal|last1=Shapiro|first1=Marc|last2=Preguiça|first2=Nuno|last3=Baquero|first3=Carlos|last4=Zawirski|first4=Marek|date=13 January 2011|title=A Comprehensive Study of Convergent and Commutative Replicated Data Types|journal=Rr-7506}}</ref><ref name="2007CRDTOriginal">{{cite arXiv|title=Designing a Commutative Replicated Data Type|last1=Shapiro|first1=Marc|last2=Preguiça|first2=Nuno|year=2007|class=cs.DC|eprint=0710.1784}}</ref><ref name="OsterUrso2006">{{cite book|last1=Oster|first1=Gérald|title=Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work - CSCW '06|last2=Urso|first2=Pascal|last3=Molli|first3=Pascal|last4=Imine|first4=Abdessamad|year=2006|pages=259|doi=10.1145/1180875.1180916|isbn=978-1595932495|citeseerx=10.1.1.554.3168|s2cid=14596943}}</ref><ref name="2009CRDT">{{cite journal|last1=Letia|first1=Mihai|last2=Preguiça|first2=Nuno|last3=Shapiro|first3=Marc|year=2009|title=CRDTs: Consistency without Concurrency Control|journal=Computing Research Repository|arxiv=0907.0929}}</ref><ref name="2009CRDTTreedoc">{{citation|chapter=A Commutative Replicated Data Type for Cooperative Editing|title=Proc 29th IEEE International Conference on Distributed Computing Systems|s2cid=8956372|doi=10.1109/ICDCS.2009.20|isbn=978-0-7695-3659-0|pages=395–403|publisher=IEEE Computer Society|location=Montreal, Quebec, Canada|date=June 2009|last1=Preguiça|first4=Mihai|last4=Letia|first3=Marc|last3=Shapiro|first2=Joan Manuel|last2=Marques|first1=Nuno|chapter-url=https://hal.inria.fr/inria-00445975/file/icdcs09-treedoc.pdf}}</ref><ref name="1997scadt">{{citation|title=Specification of Convergent Abstract Data Types for Autonomous Mobile Computing|last1=Baquero|first1=Carlos|last2=Moura|first2=Francisco|year=1997|publisher=Universidade do Minho}}</ref><ref name="Schneider">{{cite journal|title=Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial|first=Fred|last=Schneider|journal=ACM Computing Surveys|volume=22|issue=4|date=December 1990|pages=299–319|doi=10.1145/98163.98167|s2cid=678818|doi-access=free}}</ref>:
  
 
* Приложение может обновлять любую реплику самостоятельно, одновременно и без координации с другими репликами.     
 
* Приложение может обновлять любую реплику самостоятельно, одновременно и без координации с другими репликами.     

Версия от 11:32, 24 декабря 2023

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

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

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

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

Первоначальная разработка была мотивирована целями совместного редактирования текста и задачами, связанными с мобильными компьютерами.

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

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

Примечания

  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.
Источник — https://in.wiki/w/index.php?title=CRDT&oldid=342483