📄Работа №193589

Тема: СОЗДАНИЕ ОТКАЗОУСТОЙЧИВОГО ХРАНИЛИЩА НА ОСНОВЕ ПАР КЛЮЧ-ЗНАЧЕНИЕ

📝
Тип работы Магистерская диссертация
📚
Предмет информатика
📄
Объем: 49 листов
📅
Год: 2020
👁️
Просмотров: 41
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
ℹ️ Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.

📋 Содержание

Введение 3
1 Постановка задачи 6
2 Поиск решения согласно требованиям 8
2.1 Библиотека LMDB 8
2.2 Библиотека LevelDB 9
2.3 Проверка библиотек на набор свойств ACID 10
2.4 Сравнение производительности LevelDB и LMDB 12
2.5 Выбор отказоустойчивого протокола для распределенной системы 12
2.5.1 Протокол Paxos 13
2.5.2 Алгоритм RAFT 18
2.5.3 Сравнение Paxos и Raft 21
3 Программный прототип 24
3.1 Файловая структура проекта 24
3.2 Сценарий работы приложения 25
3.3 Руководство по установке 27
3.4 Руководство по эксплуатации 27
4 Библиотека LMDB-RAFT 30
4.1 Создание разделяемой библиотеки 30
4.2 Файловая структура библиотеки 30
4.3 Процесс создания и тестирования библиотеки 31
4.4 Создание deb-пакета 32
4.4.1 Создание файловой директории debian 33
4.4.2 Г енерация deb-пакета 3 4
4.5 Руководство по установке 35
4.6 Руководство по эксплуатации 35
Заключение 36
Список использованной литературы 37
Приложение А Структура Makefile 41

📖 Введение

Нереляционные базы данных на основе пар ключ-значение применяются при проектировании хранилищ больших данных, для обеспечения кэширования web-серверов, хранения пользовательских данных, в решениях, где ключевую роль играет быстрое и легкое масштабирование и пр. Как ключи, так и значения могут представлять собой что угодно: от простых до сложных составных объектов. При этом очень важной является задача обеспечения высокой доступности, невзирая на возможный сбой такого хранилища, с сохранением консистентности данных согласно теореме CAP [7]. Сами хранилища на основе пар “ключ-значение” в большинстве случаев не обладают встроенными механизмами обеспечения отказоустойчивости. Одним из решений является организация отказоустойчивого хранилища в кластер на основе алгоритмов принятия консенсуса. Эти алгоритмы позволяют строить надежные системы из ненадежных компонентов, поэтому являются основой многих распределенных систем [2].
В рамках данной работы ставилась задача предложить и создать вариант отказоустойчивого хранилища данных на кластере из нескольких узлов, используя концепцию конечного автомата. Настоящая работа посвящена разработке программного прототипа отказоустойчивого хранилища на основе пар ключ-значение (первой исследовательской версии хранилища), и разделяемой библиотеки на его основе.
Разделяемые библиотеки - это механизм размещения библиотечных функций в едином файле, доступном сразу нескольким выполняющимся процессам. Такую библиотеку можно использовать в любом проекте, где требуется наличие распределенного отказоустойчивого хранилища по типу ключ-значение, поскольку она содержит набор необходимых для этой цели функций из прототипа, созданного ранее.
В процессе работы выбрана программная библиотека LMDB, отвечающая набору заданных критериев производительности и позволяющая легко создавать хранилище типа "ключ-значение". Найдена технология организации этого хранилища в кластер - протокол консенсуса RAFT.
Одним из результатов работы является разделяемая библиотека на основе созданного программного прототипа, позволяющая запускать хранилище на нескольких серверах, образовывать отказоустойчивый кластер и далее выполнять функции хранилища данных на основе пар "ключ-значение". В тексте данной работы приводится описание процесса проектирования отказоустойчивого кластерного хранилища на основе библиотеки LMDB и консенсус-протокола RAFT, а также обзор созданного прототипа. В конце работы приводится заключение и обзор достигнутых результатов.

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

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

👨‍🎓 Помощь в написании

✅ Заключение

В работе проведено исследование двух библиотек хранилищ на основе пар ключ-значение. Библиотеки исследованы на набор свойств ACID, проанализирована их производительность, и способность отвечать архитектурным требованиям искомого хранилища.
Путем анализа возможных подходов к построению распределенной системы, найден способ организации серверов в кластер. Используемый для этой цели протокол интуитивно понятен, достаточно прост в реализации, корректность его работы формально доказана.
Предложена реализация разделяемой библиотеки на основе первой исследовательской версии(прототипа) отказоустойчивого хранилища на основе пар ключ-значение. Созданное хранилище образует отказоустойчивый кластер, способный сохранять данные в виде пары по типу ключ-значение на всех узлах. Отказ части узлов не приводит к потере работоспособности кластера.
Программный код хранилища оформлен в виде разделяемой библиотеки и упакована в установочный пакет с расширением *.deb. Библиотека протестирована на работу в операционных системах семейства Debian.

Нужна своя уникальная работа?
Срочная разработка под ваши требования
Рассчитать стоимость
ИЛИ

📕 Список литературы

1. Определение базы данных на основе пар «ключ-значение» [Электронный ресурс] // AWS. - Электрон. дан. - [Б. м.], 2019. - URL: https://aws.amazon.com/ru/nosql/key-value(дата обращения: 12.01.2019).
2. Ланцов А. В. Исследование алгоритмов принятия консенсуса в сети
надежных вычислений [Электронный ресурс] : выпускная квалификационная работа : (магистерская диссертация). - Электрон. дан. - М., 2015. - URL: http://w27001 .vdi.mipt.ru/wp/wp-content/uploads/2016/03/diplom.pdf (дата
обращения: 23.01.2019).
3. Design Review: Key-Value Storage [Electronic resource] // Project Lists. Web Development. - Electronic data. - [S. l.], 2018. - URL: https://mozilla.github.io/firefox-browser-architecture/text/0015-rkv/html (access date: 23.01.2019).
4. Foote K. D. In-Memory Database Architecture: An Overview [Electronic resource] // Dataversity. - Electronic data. - [S. l.], 2019. - URL: https://www.dataversity.net/in-memory-database-architecture-overview (access date: 04.02.2019).
5. LMDB vs. LevelDB [Electronic resource] // Project Lists. Web
Development. - Electronic data. - [S. l.], 2019. - URL:
https://mozilla.github.io/firefox-browser-architecture/text/0017-lmdb-vs-leveldb.html (access date: 29.01.2019).
6. RocksDB. A persistent key-value store for fast storage environments [Electronic resource]. - Electronic data. - [S. l., s. a.]. - URL: https://rocksdb.org (access date: 16.02.2019).
7. CAP theorem [Electronic resource] // Wikipedia : free ensiclopedia. - Electronic data. - [S. l.], 2020. - URL: https://en.wikipedia.org/wiki/CAP_theorem (access date: 18.02.2020).
8. Design Review: Key-Value Storage [Electronic resource] // Project Lists. Web Development. - Electronic data. - [S. l.], 2018. - URL: https://mozilla.github.io/firefox-browser-architecture/text/0015-rkv.html (access date: 23.01.2019).
9. LMDB [Electronic resource]. - Electronic data. - [S. l., s. a.]. - URL: https://lmdb.readthedocs.io/en/release (access date: 28.03.2019).
10. Lightning Memory-Mapped Database [Electronic resource] // Wikipedia : free ensiclopedia. - Electronic data. - [S. l.], 2020. - URL: https://en.wikipedia.org/wiki/Lightning_Memory-Mapped_Database (access date: 28.03.2020).
11. Chu H. Lightning memory-mapped database manager (LMDB) [Electronic resource] / H. Chu. - Electronic data. - [S. l.], 2011-2015. - URL: http://www.lmdb.tech/doc/index.html (access date: 02.04.2019).
12. LevelDB [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://github.com/google/leveldb (access date: 31.03.2019).
13. Dean J. LevelDB [Electronic resource] / J. Dean, S. Ghemawat //
GitHub. - Electronic data. - [S. l.], 2019. - URL:
https://github.com/google/leveldb/blob/master/doc/index.md (access date: 01.04.2019).
14. LMDB. Getting started [Electronic resource]. - Electronic data. - [S. l., s. a.]. - URL: http://www.lmdb.tech/doc/starting.html (access date: 08.04.2019).
15. Lightning memory-mapped database maneger (LMDB). Introduction [Electronic resource]. - Electronic data. - [S. l., s. a.]. - URL: http://www.lmdb.tech/doc (access date: 09.04.2019).
16. Shadow paging [Electronic resource] // Wikipedia : free ensiclopedia. - Electronic data. - [S. l.], 2020. - URL: https://en.wikipedia.org/wiki/Shadow_paging (access date: 01.04.2020).
17. Basic concepts [Electronic resource] // MDN web doc. - Electronic data.
- [S. l., s. a.]. - URL: https://developer.mozilla.org/en-
US/docs/Web/API/IndexedDB_API/Basic_Concepts_Behind_IndexedDB#durable (access date: 21.04.2019).
18. Libmdbx. Performance comparison [Electronic resource] // GitHub. -
Electronic data. - [S. l.], 2019. - URL: https://github.com/leo-
yuriev/libmdbx#performance-comparison (access date: 22.04.2019).
19. Dix P. Benchmarking LevelDB vs. RocksDB vs. HyperLevelDB vs. LMDB Performance for InfluxDB [Electronic resource] // Influxdata. - Electronic data. - [S. l.], 2014. - URL: https://www.influxdata.com/blog/benchmarking-leveldb- vs-rocksdb-vs-hyperleveldb-vs-lmdb-performance-for-influxdb (access date: 23.04.2019).
20. Kvbench [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://github.com/mykmelez/kvbench (access date: 26.04.2019).
21. Database microbenchmarks [Electronic resource] // Symas. - Electronic data. - [S. l.], 2012. - URL: http://www.lmdb.tech/bench/microbench (access date: 26.04.2019).
22. Saini V. ConsensusPedia: An Encyclopedia of 30+ Consensus
Algorithms [Electronic resource] // Hackernoon. - Electronic data. - [S. l.], 2018. - URL: https://hackernoon.com/consensuspedia-an-encyclopedia-of-29-consensus-
algorithms-e9c4b4b7d08f (access date: 29.04.2019).
23. Ongaro D. In Search of an Understandable Consensus Algorithm (Extended Version) [Electronic resource] / D. Ongaro, J. Ousterhout. - Electronic data. - [S. l., s. a.]. - URL: https://raft.github.io/raft.pdf (access date: 03.05.2019).
24. Distributed systems cheat sheet [Electronic resource] // Dimafeng. - Electronic data. - [S. l.], 2016. - URL: http://dimafeng.com/2016/12/04/distributed- systems (access date: 03.05.2019).
25. Consensus: Bridging Theory and Practice [Electronic resource] //
GitHub. - Electronic data. - [S. l.], 2019. - URL:
https://github.com/ongardie/dissertation#readme (access date: 05.05.2019).
26. Saini V. ConsensusPedia: An Encyclopedia of 30+ Consensus
Algorithms [Electronic resource] // Hackernoon. - Electronic data. - [S. l.], 2018. - URL: https://hackernoon.com/consensuspedia-an-encyclopedia-of-29-consensus-
algorithms-e9c4b4b7d08f (access date: 29.04.2019).
27. Ongaro D. Designing for Understandability: the Raft Consensus Algorithm [Electronic resource] / D. Ongaro, J. Ousterhout. - Electronic data. - [S.
I. ], 2016. - URL: https://raft.github.io/slides/uiuc2016.pdf (access date: 11.05.2019).
28. Liblmdb [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://github.com/LMDB/lmdb/tree/mdb.master/libraries/liblmdb (access date: 14.05.2019).
29. Libuv [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019.
- URL: https://github.com/libuv/libuv (access date: 16.05.2019).
30. RAFT [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019.
- URL: https://github.com/willemt/raft (access date: 20.05.2019).
31. RAFT Description [Electronic resource] // The secret lives of Data. - Electronic data. - [S. l., s. a.]. - URL: http://thesecretlivesofdata.com/raft (access date: 20.05.2019).
32. Косяков М. С. Введение в распределенные вычисления [Электронный ресурс] : учеб. пособие. - СПб. : ИТМО, 2014. - 155 с. - Электрон. версия печат. публ. - URL: http://books.ifmo.ru/file/pdf71551.pdf(дата обращения: 19.05.2019).
33. CMake project [Electronic resource]. - Electronic data. - New York, 2019. - URL: https://cmake.org/ (access date: 29.05.2019).
34. Lamport L. The Byzantine Generals Problem [Electronic resource] / L.
Lamport, R. Shostak, M. Pease // ACM Transactions on Programming Languages and Systems. - 1982. - Vol. 4, № 3. - P. 382-401. - The electronic version of the printing publication. - URL: https://www.microsoft.com/en-
us/research/uploads/prod/2016/12/The-Byzantine-Generals-Problem.pdf (access date:
II. 03.2020).
35. Lamport L. The Part-Time Parliament [Electronic resource] // ACM Transactions on Computer Systems. - 1998. - Vol. 16, № 2. - P. 133-169. - The electronic version of the printing publication. - URL: https://www.microsoft.com/en- us/research/publication/part-time-parliament (access date: 11.03.2020).
36. Lamport L. Paxos made simple [Electronic resource] // ACM SIGACT News (Distributed Computing Column). - 2001. - Vol. 32, № 4. - P. 51-58. - The electronic version of the printing publication. - URL: https://www.microsoft.com/en- us/research/publication/paxos-made-simple (access date: 11.03.2020).
37. Lamport L. Fast Paxos [Electronic resource] / L. Lamport. - Electronic data. - Redmond, 2005. - 40 p. - URL: https://www.microsoft.com/en- us/research/wp-content/uploads/2016/02/tr-2005-112.pdf (access date: 15.03.2020).
38. Lamport L. Generalized Consensus and Paxos [Electronic resource] / L. Lamport. - Electronic data. - [S. l.], 2005. - 59 p. - URL: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-2005- 33.pdf (access date: 15.03.2020).
39. Fischer M. J. Impossibility of Distributed Consensus with One Faulty Process [Electronic resource] / M. J. Fischer, N. A. Lynch, M. S. Paterson // Journal of the Assccktion for Computing Machinery - 1985. - Vol. 32, № 2. - P. 374-382. - The electronic version of the printing publication. - URL: https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf (access date: 17.03.2020).
40. Lessons Learned from Implementing Paxos [Electronic resource] // Will
portnoy. - Electronic data. - [S. l.], 2012. - URL:
http://blog.willportnoy.com/2012/06/lessons-learned-from-paxos.html (access date: 20.03.2020).
41. ScyllaDB, NoSQL data store using the seastar framework, compatible with Apache Cassandra [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://github.com/scylladb/scylla/tree/master/service/paxos (access date: 24.03.2020).
42. LibPaxos [Electronic resource] // Sourceforge. - Electronic data. - [S. l.], 2013. - URL: http://libpaxos.sourceforge.net/paxos_projects.php (access date: 28.03.2020).
43. The Raft consensus algorithm [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://raft.github.io (access date: 29.03.2020).
44. Derecho [Electronic resource] // GitHub. - Electronic data. - [S. l.], 2019. - URL: https://github.com/Derecho-Project/derecho (access date: 02.04.2020).
45. Lamport L. Fast Paxos [Electronic resource] / L. Lamport. - Electronic data. - Redmond, 2005. - 40 p. - URL: https://www.microsoft.com/en- us/research/wp-content/uploads/2016/02/tr-2005-112.pdf (access date: 02.04.2020).
46. Chandra T. Paxos Made Live - an engineering perspective [Electronic resource] / T. Chandra, R. Griesemer, J. Redstone // PODC 2007 : proceedings. - [S. l.], 2007. - The electronic version of the printing publication. - URL: https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1 .pdf (access date: 02.04.2020).
47. Moraru I. There Is More Consensus in Egalitarian Parliaments
[Electronic resource] / I. Moraru, D. G. Andersen, M. Kaminsky // SOSP’13, 3-6 november 2013, Farmington. - [S. l.], 2013. - URL:
https://www.cs.cmu.edu/~dga/papers/epaxos-sosp2013.pdf (access date: 04.04.2020).
48. Lampson B. W. How to build a highly available system using consensus // Lecture Notes in Computer Science. - 1996. - Vol. 1151. - P. 1-17.
49. Lampson B. W. The ABCD’s of Paxos // Proceeding PODC’01, ACM Symposium on Principles of Distributed Computing. - [S. l.], 2001. - P. 13-13.
50. Часто задаваемые вопросы о Debian GNU/Linux [Electronic resource]
// Debian. - Электрон. дан. - [Б. м.], 2019. - URL:
https://www.debian.org/doc/manuals/debian-faq/index.ru.html(дата обращения: 04.04.2020).
51. Родин Д. Руководство начинающего разработчика Debian / Д. Родин, О. Аоки // Debian. - Электрон. дан. - [Б. м.], 2019. - URL: https://www.debian.org/doc/manuals/maint-guide/index.ru.html(дата обращения: 04.04.2020).
52. Kerrisk M. The Linux Programming Interface: A Linux and UNIX System Programming Handbook / M. Kerrisk. - [S. l.], 2010. - 1552 p.

🛒 Оформить заказ

Работу высылаем в течении 5 минут после оплаты.

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