Тип работы:
 Предмет:
 Язык работы:


Исследование возможностей использования технологии Conflict-free Replicated Data Types (CRDT) в разработке горизонтально масштабированных веб-приложений

Работа №103654

Тип работы

Магистерская диссертация

Предмет

информатика

Объем работы94
Год сдачи2022
Стоимость4880 руб.
ПУБЛИКУЕТСЯ ВПЕРВЫЕ
Просмотрено
23
Не подходит работа?

Узнай цену на написание


Введение 4
Глава 1 Анализ проблем распределенной синхронизации данных 7
1.1 Анализ проблем распределенной синхронизации данных в веб-приложениях 7
1.2 Анализ существующих подходов к решению проблемы эффективной
синхронизации данных горизонтально масштабированных веб-приложений 10
1.3 Выбор подхода к решению проблемы обеспечения синхронизации
данных между горизонтально распределенными экземплярами веб-приложения 19
1.4 Подход алгоритмов CRDT к решению проблемы синхронизации
данных горизонтально масштабированных веб-приложений 23
1.5 Постановка задачи исследования 27
Глава 2 Анализ применимости CRDT для решения проблемы эффективной синхронизации данных в горизонтально масштабированных веб-приложениях 29
2.1 Теоретические основы алгоритмов CRDT 29
2.2 Текущее применение алгоритмов CRDT 38
2.3 Выбор предметной области использования веб-приложения для
внедрения алгоритмов CRDT 40
2.4 Постановка задачи обеспечения работы корзины товаров 43
2.5 Выбор алгоритма CRDT для внедрения в веб-приложение интернет-
магазина 46
2.6 Постановка задачи на реализацию синхронизации данных с
использованием алгоритма CRDT «OR Set» 52
Глава 3 Проектирование и реализация решения проблемы синхронизации данных горизонтально масштабированных веб-приложений с использованием алгоритмов CRDT на примере веб-приложения интернет-магазина 54
3.1 Разработка алгоритма эффективной синхронизации корзины товаров с
использованием алгоритма CRDT OR Set 54
3.2 Проверка работоспособности полученной реализации в условиях
сетевых разделений 61
Глава 4 Анализ результатов решения проблемы эффективной синхронизации данных горизонтально масштабированных приложений с использованием алгоритмов CRDT 68
4.1 Развёртывание стенда для тестирования 68
4.1.1 Подход «CRDT» 69
4.1.2 Подход «Классический» 70
4.1.3 Подход «CRDT Master-Replica» 71
4.1.4 Подход «Кластерная нереляционная СУБД» 73
4.2 Анализ производительности альтернативных вариантов решения
проблемы эффективной синхронизации данных в горизонтально масштабированных веб-приложениях 76
4.3 Ограничения проведённого тестирования 82
Заключение 86
Список используемой литературы 89

Актуальности темы исследования: С каждым годом Интернет все больше проникает в различные сферы экономики [8]. Для существования на современном рынке практически каждой организации необходимо создавать и поддерживать веб-приложения. Поскольку разработка и поддержка веб-приложений представляет собой непростую задачу, в настоящий момент для ее упрощения было выработано несколько подходов и конкретных программных продуктов (фреймворки, конструкторы приложений и т. д.). Тем не менее, появляются новые требования пользователей к отказоустойчивости и синхронизации данных — возникает необходимость разрабатывать веб-приложения с поддержкой распределенного хранения данных с оперативной синхронизацией. К реализации подобной синхронизации можно подойти по-разному, с использованием различных алгоритмов балансировки нагрузки и репликации (например, использование балансировщиков нагрузки, использование распределенных СУБД типа master-master или синхронной репликацией). Однако, построение корректных и производительных распределенных систем хранения данных является одной из сложнейших задач прикладной информатики. В связи с этим наиболее актуальной является задача использования новейших теоретических достижений в разработке и поддержке веб-приложений на практике.
Научная проблема: констрадикция научной проблемы проявляется в том, что современные рыночные условия требуют отказоустойчивых веб-приложений с динамической синхронизацией состояния между сессиями, что требует распределенного хранения данных. При этом проектирование и поддержка распределенной системы хранения данных является сложной задачей, требующей значительных ресурсов и поэтому часто является недоступной для малых организаций. В то же время, существуют новые подходы к синхронизации данных, которые могут обеспечивать математически доказанную корректность синхронизации а также потенциально более высокую производительность и простоту разработки и поддержки. Одним из перспективных семейств алгоритмов являются алгоритмы CRDT. Однако, несмотря на их перспективность в настоящее время алгоритмы CRDT слабо внедрены в практическую разработку типичных веб-приложений.
Финитизация данной научной проблемы заключается в радикальном упрощении разработки и поддержки широкого спектра типичных веб-приложений, используемых в различных сферах экономики; удешевлении процессов поддержки веб-приложения и повышении производительности веб-приложений.
Цель исследования: разработать подходы к практическому внедрению алгоритмов CRDT в современные веб-приложения, оценить корректность и производительность полученной реализации по сравнению с альтернативными реализациями и существующими решениями в области хранения данных.
Область исследования: архитектура веб-приложений, алгоритмы синхронизации данных, распределенные системы хранения данных.
Гипотеза: процесс разработки и поддержки современных веб-приложений будет значительно упрощён и удешевлён если будут решены следующие задачи:
- Проанализированы актуальные подходы и программные решения для распределенного хранения и синхронизации данных.
- Изучены текущее использование алгоритмов CRDT в различных видах веб-приложений.
- Разработаны стратегии внедрения CRDT в распространённые типы веб-приложений.
- Разработана Proof-of-Concept реализация CRDT
- оценена производительность, скорость внедрения и корректность полученной реализации по сравнению с альтернативными решениями.
Задачи исследования:
Проанализировать текущее состояние предметной области.
Разработать подходы к внедрению алгоритмов CRDT в различные типы веб-приложений (включая типичные веб-приложения для малого и среднего бизнеса).
Проанализировать свойства практической реализации алгоритмов CRDT по сравнению с альтернативными решениями.
Практическая значимость: Упрощение и удешевление разработки отказоустойчивых распределенных веб-приложений для широкого круга организаций (включая малый и средний бизнес) в соответствии с требованиями пользователей и контрагентов. Упрощение и удешевление эксплуатации полученных веб-приложений с распределенным хранением данных.


Возникли сложности?

Нужна помощь преподавателя?

Помощь в написании работ!
ДИПЛОМНЫЕ МАГИСТЕРСКИЕ ДИССЕРТАЦИИ
КУРСОВЫЕ СТАТЬИ ВКР

Даже с учётом ограничений алгоритмы CRDT обладают большим потенциалом для внедрения в некоторые подвиды веб-приложений, в особенности в веб-приложения интернет-магазинов для решения задачи синхронизации пользовательской корзины товаров горизонтально масштабированного веб-приложения.
Кроме того, при успешном внедрении алгоритмов CRDT можно ожидать улучшение производительности по сравнению с альтернативными вариантами решения проблемы распределенной синхронизации данных.
В рамках исследования была проанализирована проблема распределенной синхронизации данных в современных горизонтально масштабированных веб-приложениях. Существующие подходы к решению данной проблемы обладают серьёзными недостатками. Для решения проблемы и борьбы с недостатками существующих решений хорошо подходит использование алгоритмов CRDT. Однако стоит учитывать, что при использовании алгоритмов CRDT в общем случае не обеспечивается строгая согласованность данных, как в классических реляционных СУБД. Поэтому алгоритмы CRDT применимы лишь в отдельном подмножестве веб-приложений, в которых нестрогая согласованность данных является приемлемой. Были разработаны подходы к определению таких веб-приложений, а также классификация веб-приложений в зависимости от потенциала применения алгоритмов CRDT.
По результатам анализа, одной из самых подходящих сфер для использования алгоритмов CRDT в качестве решения проблемы распределенной синхронизации горизонтально масштабированных веб-приложений является сфера электронной коммерции, а конкретно веб-приложения интернет-магазинов. При проработке применения алгоритмов CRDT в задаче синхронизации пользовательской корзины товаров удалось спроектировать корректную реализацию корзины с использованием алгоритмов CRDT. Был предложен способ достичь автоматической синхронизации узлов распределенного кластера с помощью использования балансировщика нагрузки. Полученная реализация показывает хорошие результаты с точки зрения производительности по сравнению с альтернативными подходами, а также обладает рядом нефункциональный преимуществ.



[1] Active-Active Geo-Distribution (CRDTs-Based), [Электронный ресурс], URL: https://www.redislabs.com/redis-enterprise/technology/active- active-geo-distribution/(дата обращения: 07.05.2022)
[2] Apps Are Becoming Distributed, What about Your Infra?, F5 Blog, 2020, [Электронный ресурс], URL: https://www.f5.com/company/blog/apps-are- becoming-distributed-what-about-your_infra(дата обращения: 07.05.2022)
[3] Automerge: A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically., [Электронный ресурс], URL: https://github.com/automerge/automerge(дата обращения: 07.05.2022)
[4] Bieniusa A. и другие, An optimized conflict-free replicated set [Research Report] RR-8083, Inria - Centre Paris-Rocquencourt; INRIA. 2012, стр. 3.
[5] Cabrita G. M. Non-uniform replication for replicated objects : дис. - 2017.
[6] C. Ellis and S. J. Gibbs, Concurrency control in groupware systems, //ACM International Conference on Management of Data (SIGMOD), May 1989. - С. 399-407.
[7] Dharma Shukla, Azure Cosmos DB: Pushing the frontier of globally distributed databases, [Электронный ресурс], URL: https://azure.microsoft.com/en-us/blog/azure-cosmos-db-pushing-the-frontier-of- globally-distributed-databases/(дата обращения: 07.05.2022)
[8] Digital Adoption Index, World Bank, [Электронный ресурс], URL: https://www.worldbank.org/en/publication/wdr2016/Digital-Adoption-Index(дата обращения: 07.05.2022)
[9] Dmitry Ivanov, Practical Data Synchronization with CRDTs, StrangeLoop Conference 2016, [Электронный ресурс], URL: https://speakerdeck.com/ajantis/practical-data-synchronization-with-crdts- strangeloop-2016(дата обращения: 07.05.2022)
[10] Dmitry Vyukov, Andrew Gerrand, Introducing the Go Race Detector, [Электронный ресурс], URL: https://go.dev/blog/race-detector(дата обращения: 07.05.2022)
[11] Doug Woos и другие, Planning for Change in a Formal Verification of the Raft Consensus Protocol, Proceedings of the 5th ACM SIGPLAN Conference on Certified Programs and Proofs, стр. 154-165
[12] etcd3 API - Transaction, Официальная документация etcd,
[Электронный ресурс], URL:
https://github.com/etcd-io/website/blob/v3.5.0/content/en/docs/v3.5/learning/ api.md#transaction (дата обращения: 07.05.2022)
[13] etcd. Distributed reliable key-value store for the most critical data of a distributed system. [Электронный ресурс]. URL: https://github.com/etcd-io/etcd(дата обращения: 07.05.2022)
[14] Evan Wallace, How Figma’s multiplayer technology works, [Электронный ресурс], URL: https://www.figma.com/blog/how-figmas- multiplayer-technology-works/(дата обращения: 07.05.2022)
[15] Faiz M., Shanker U. Data synchronization in distributed client-server applications //2016 IEEE International Conference on Engineering and Technology (ICETECH). - IEEE, 2016. - С. 611-616.
[16] Galera Cluster for MySQL, [Электронный ресурс], URL: https://galeracluster.com/(дата обращения: 07.05.2022)
[17] Gene T. J. Wuu и Arthur J. Bernstein. Efficient solutions to the replicated log and dictionaryproblems. InSymp. on Principles of Dist. Comp. (PODC), стр. 233-242, Vancouver, BC, Canada, 1984.
[18] Giuseppe DeCandia и другие, Dynamo: amazon's highly available key-value store, ACM SIGOPS Operating Systems Review, Vol. 41, No. 6 (2007), стр. 205-220
[19] G. Oster, P. Urso, P. Molli, and A. Imine, Data consistency for P2P collaborative editing, //ACM Conference on Computer Supported Cooperative Work (CSCW), Banff, Alberta, Canada, ACM Press, 2006. - С. 399-407.
[20] He W., Da Xu L. Integration of distributed enterprise applications: A survey //IEEE Transactions on industrial informatics. - 2012. - Т. 10. - №. 1. - С. 35-42.
[21] Jepsen. A framework for distributed systems verification, with fault injection, [Электронный ресурс], URL: https://github.com/jepsen-io/jepsen(дата обращения: 07.05.2022)
[22] Jepsen. Analyses, [Электронный ресурс], URL: http://jepsen.io/analyses(дата обращения: 07.05.2022)
[23] Marc Shapiro и другие, Convergent and Communicative Replicated Data Types, Bulletin - European Association for Theoretical Computer Science (2011), стр. 67-88
[24] Michal Ptaszek, Scaling LoL Chat to 70M Players, StrangeLoop
Conference 2014, [Электронный ресурс], URL: https://www.slideshare.net/michalptaszek/strange-loop-presentation (дата
обращения: 07.05.2022)
[25] MySQL 8.0 Reference Manual: Chapter 17 Replication, Официальная документация MySQL, [Электронный ресурс], URL: https://dev.mysql.com/doc/refman/8.0/en/replication.html
[26] MySQL 8.0 Reference Manual: XA Transactions, Официальная документация MySQL, [Электронный ресурс], URL: https://dev.mysql.Com/doc/refman/8.0/en/xa.html
[27] Nuno Preguica и другие, Conflict-free Replicated Data Types, Symposium on Self-Stabilizing Systems 2011: Stabilization, Safety, and Security of Distributed Systems (2011), стр. 386-400
[28] Online editor providing collaborative editing in really real-time using CRDTs and IPFS., [Электронный ресурс], URL: https://github.com/peer-base/peer-pad(дата обращения: 07.05.2022)
[29] Operating etcd clusters for Kubernetes, Официальная документация
Kubernetes, [Электронный ресурс], URL:
https://kubernetes.io/docs/tasks/administer-cluster/configure-upgrade-etcd/(дата обращения: 07.05.2022)
[30] Peter Bourgon, Roshi: a CRDT system for timestamped events, [Электронный ресурс], URL: https://developers.soundcloud.com/blog/roshi-a- crdt-system-for-timestamped-events(дата обращения: 07.05.2022)
[31] Pew Research Center, Spring 2018 Global Attitudes Survey Q46
[Электронный ресурс] URL:
https://www.pewresearch.org/ global/2019/02/05/smartphone-ownership-is- growing-rapidly-around-the-world-but-not-always-equally/ (дата обращения 07.05.2022)
[32] PostgreSQL 14 Documentation: 27.2. Log-Shipping Standby Servers, Официальная документация PostgreSQL, [Электронный ресурс], URL: https://www.postgresql.org/docs/current/warm-standby.html
[33] P. R. Johnson and R. H. Thomas. The maintenance of duplicate databases. Internet Request for Comments RFC 677, Information Sciences Institute, Jan. 1976.
[34] Rana Asif Rehman, Bilal Khan и др, loT Elements, Layered Architectures and Security Issues: A Comprehensive Survey, Sensors 18(9), 2018, стр.1-37
[35] Shapiro M. И другие. Conflict-free replicated data types //Symposium on Self-Stabilizing Systems. - Springer, Berlin, Heidelberg, 2011. - С. 386-400.
[36] Statista, Mobile Internet & Apps, [Электронный ресурс], URL: https://www.statista.com/markets/424/topic/538/mobile-internet-apps/#overview(дата обращения: 07.05.2022)
[37] String-wise sequence CRDT powering peer-to-peer collaborative editing in Teletype for Atom., [Электронный ресурс], URL: https://github.com/atom/teletype-crdt(дата обращения: 07.05.2022)
[38] The Go Programming Language, Официальный сайт Go, [Электронный ресурс], URL: https://go.dev/(дата обращения: 07.05.2022)
[39] The Open Group, Distributed Transaction Processing: The XA Specification, официальный сайт публикаций The Open Group, [Электронный ресурс], URL: https://pubs.opengroup.org/onlinepubs/009680699/toc.pdf
[40] Why gRPC gateway, Официальная документация etcd,
[Электронный ресурс], URL:
https://github.com/etcd-io/website/blob/v3.5.0/content/en/docs/v3.5/dev-guide/ api_grpc_gateway.md (дата обращения: 07.05.2022)
[41] Yjs: Peer-to-peer shared types, [Электронный ресурс], URL: https://github.com/yjs/yjs(дата обращения: 07.05.2022)
[42] Документация MariaDB, (официальный сайт MariaDB Foundation), [Электронный ресурс], URL: https://mariadb.org/documentation/
[43] Репозиторий исходного кода. [Электронный ресурс], URL: https://github.com/nikitakalyanov/crdt-cart(дата обращения: 07.05.2022)
[44] Репозиторий исходного кода Jepsen-теста, [Электронный ресурс], URL: https://github.com/nikitakalyanov/jepsen.crdtcart(дата обращения: 07.05.2022)

Работу высылаем на протяжении 30 минут после оплаты.




©2025 Cервис помощи студентам в выполнении работ
.