CRDT: различия между версиями
| (не показаны 4 промежуточные версии этого же участника) | |||
| Строка 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>: |
* Приложение может обновлять любую реплику самостоятельно, одновременно и без координации с другими репликами. | * Приложение может обновлять любую реплику самостоятельно, одновременно и без координации с другими репликами. | ||
| Строка 7: | Строка 7: | ||
Концепция CRDT была официально определена в 2011 году Марком Шапиро, Нуно Прегуисой, Карлосом Бакеро и Мареком Завирски. | Концепция CRDT была официально определена в 2011 году Марком Шапиро, Нуно Прегуисой, Карлосом Бакеро и Мареком Завирски. | ||
| − | Первоначальная разработка была мотивирована целями совместного редактирования текста и задачами, связанными с мобильными компьютерами. | + | Первоначальная разработка была мотивирована целями совместного редактирования текста, для которых CRDT выглядит более совершенной версией предшествующей техники [[Операционная трансформация|операционной трансформации]]<ref>[https://habr.com/ru/companies/ruvds/articles/780356/ Проектирование аналога Google Docs]</ref> и задачами, связанными с мобильными компьютерами. |
CRDT также использовались в системах онлайн-чатов, социальных сетей, онлайн-азартных играх и на платформе распространения звука SoundCloud. | CRDT также использовались в системах онлайн-чатов, социальных сетей, онлайн-азартных играх и на платформе распространения звука SoundCloud. | ||
Распределенные базы данных [[NoSQL]] [[Redis]], [[Riak]] и [[Cosmos DB]] напрямую поддерживают типы данных CRDT. | Распределенные базы данных [[NoSQL]] [[Redis]], [[Riak]] и [[Cosmos DB]] напрямую поддерживают типы данных CRDT. | ||
| + | |||
| + | == Бэкграунд == | ||
| + | Одновременные обновления нескольких [[Реплика данных|реплик]] одних и тех же данных без координации между узлами<ref>Компьютерами, виртуальными машинами и т.д.</ref>, на которых размещены реплики, могут привести к несогласованности между репликами, которые в общем случае могут оказаться неразрешимыми. В | ||
| + | |||
| + | осстановление согласованности и целостности данных при возникновении конфликтов между обновлениями может потребовать полного или частичного удаления некоторых или всех обновлений. | ||
| + | |||
| + | Соответственно, большая часть распределенных вычислений сосредоточена на проблеме предотвращения одновременных обновлений реплицируемых данных. Но другой возможный подход — это [[оптимистическая репликация]], при которой все одновременные обновления могут выполняться с возможным возникновением несоответствий, а результаты объединяются или «разрешаются» позже. В этом подходе согласованность между репликами [[Согласованность в конечном счёте|в конечном итоге]] восстанавливается посредством «слияния» разных реплик. Хотя оптимистичная репликация может не работать в общем случае, существует важный и практически полезный класс структур данных, CRDT, где она работает. Для таких структур всегда можно без конфликтов объединить или разрешить одновременные обновления в разных репликах структуры данных. | ||
| + | |||
| + | Это делает CRDT идеальными для оптимистического репликации. Например, односторонний логический флаг события представляет собой тривиальный CRDT: один бит со значением true или false. True означает, что какое-то конкретное событие произошло хотя бы один раз. False означает, что событие не произошло. Если флаг установлен в значение true, его нельзя вернуть обратно в значение false (произошедшее событие не может повториться). Метод разрешения — «истинный выигрыш»: при слиянии реплики, где флаг имеет значение true (эта реплика наблюдала событие), и другой реплики, где флаг имеет значение false (эта реплика не наблюдала событие), решенный результат true — событие наблюдалось. | ||
| + | |||
| + | == Примечания == | ||
[[Категория:Структуры данных]] | [[Категория:Структуры данных]] | ||
[[Категория:Типы данных]] | [[Категория:Типы данных]] | ||
[[Категория:Распределённые системы]] | [[Категория:Распределённые системы]] | ||
Текущая версия от 02:13, 3 марта 2024
|
Это незавершённая статья. Вы можете помочь проекту, исправив и дополнив её. |
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 — событие наблюдалось.
ПримечанияПравить
- ↑ 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.
- ↑ Проектирование аналога Google Docs
- ↑ Компьютерами, виртуальными машинами и т.д.