Масштабована розподілена комп’ютерна система побудови фільтра Блума
| dc.contributor.advisor | Молчанов, Олексій Андрійович | |
| dc.contributor.author | Жовтанюк, Максим В`ячеславович | |
| dc.date.accessioned | 2026-01-19T12:49:50Z | |
| dc.date.available | 2026-01-19T12:49:50Z | |
| dc.date.issued | 2025 | |
| dc.description.abstract | Актуальність теми. Стрімке зростання обсягів даних у сучасних інформаційних системах, сервісах електронної комерції, рекламних платформах, системах рекомендацій та аналітики призводить до підвищених вимог до швидкості й ефективності обробки запитів. Одним із базових завдань у таких системах є перевірка належності елемента до великої множини даних, що має виконуватися з мінімальними затримками та за обмежених ресурсів пам’яті. Класичні підходи, засновані на збереженні повних наборів даних, стають малопридатними через їхню високу вартість з точки зору оперативної пам’яті та часу доступу. Фільтр Блума є однією з ключових і широко вживаних структур даних для розв’язання подібних задач, оскільки забезпечує високу пропускну здатність запитів належності за рахунок компактного представлення множин. Однак із зростанням обсягів даних та навантаження виникає проблема вертикального масштабування: один фізичний вузол обмежений фізичними характеристиками та не здатний вмістити фільтр необхідного розміру та обробити потрібну кількість запитів на секунду. Це обумовлює потребу у розробці розподілених рішень, що дають змогу розміщувати фільтр Блума на кількох вузлах, забезпечуючи балансування навантаження, доступність системи та можливість як вертикального, так і горизонтального масштабування. Таким чином, дослідження та побудова масштабованої розподіленої системи фільтра Блума є актуальним завданням, яке має як теоретичну, так і практичну значущість для сучасних високонавантажених сервісів. Мета і завдання дослідження. Метою дисертаційної роботи є дослідження та розробка масштабованої розподіленої системи побудови фільтра Блума, яка забезпечує ефективну перевірку належності елементів в умовах великих обсягів даних та обмежених ресурсів окремих вузлів. Для досягнення поставленої мети в дисертації вирішуються такі задачі: 1. Оглянути існуючі підходи до побудови та масштабування фільтра Блума, а також програмні рішення для роботи з великими обсягами даних. 2. Виконати теоретичний аналіз моделі розподіленого фільтра Блума, формалізувати її основні параметри та оцінити вплив цих параметрів на імовірність хибно позитивних результатів перевірки і використання ресурсів. 3. Розробити архітектуру та модель масштабованої розподіленої системи фільтра Блума з урахуванням особливостей розподілу даних між вузлами, балансування навантаження та доступності. 4. Реалізувати масштабовану компʼютерну систему розподіленого фільтра Блума для роботи в умовах великих обсягів даних і високої інтенсивності запитів. 5. Провести експериментальні дослідження продуктивності та масштабованості розробленої системи. Об’єктом дослідження процес побудови розподіленого фільтра Блума для обробки великих обсягів даних. Предметом дослідження є моделі, методи та способи побудови й масштабування розподіленого фільтра Блума для ефективної перевірки належності елементів у системах з великими обсягами даних. Для розв’язання поставлених наукових завдань використані такі методи дослідження: пошук та аналіз — для вивчення існуючих підходів до побудови й масштабування фільтра Блума та розподілених систем зберігання даних; формалізація — для побудови математичної моделі розподіленого фільтра Блума, визначення його параметрів та характеристик надійності; моделювання, експеримент, спостереження, вимірювання, аналогія та тестування — для розробки й дослідження програмного прототипу системи, оцінки її продуктивності, масштабованості та ефективності в умовах великих обсягів даних. Наукова новизна полягає в наступному: 1. Запропоновано покращений спосіб побудови масштабованої розподіленої комʼютерної системи фільтра Блума, який відрізняється від наявних тим, що елементи заданої множини розподіляються між різними вузлами системи з використанням консистентного хешування, за рахунок чого система функціонує як єдиний логічний фільтр Блума. Практична цінність отриманих у роботі результатів полягає в комплексному аналізі існуючих підходів до побудови та масштабування фільтра Блума. На основі цього аналізу реалізовано масштабовану розподілену комʼютерну систему побудови фільтра Блума, яка дає змогу працювати з такими обсягами даних, що перевищують можливості одного фізичного сервера за обсягом оперативної пам’яті, забезпечуючи при цьому високу швидкодію перевірки належності елементів. Розроблена система дає змогу гнучко масштабувати обчислювальні ресурси шляхом додавання або видалення вузлів із мінімальним впливом на доступність сервісу та пропускну здатність, що є важливим для високонавантажених застосунків, таких як рекламні платформи, системи аналітики, кешування та виявлення дублікатів. Наявність засобів моніторингу продуктивності та стану вузлів дає змогу оцінювати ефективність розподілу навантаження, своєчасно виявляти «вузькі місця» та адаптувати конфігурацію системи під поточні вимоги. Отримані результати можуть бути використані як основа для впровадження розподіленого фільтра Блума у реальних промислових системах, де критичною є комбінація високої швидкодії, обмежених ресурсів пам’яті та необхідності горизонтального масштабування. Це дає змогу підвищити ефективність обробки великих обсягів даних, знизити вартість інфраструктури та забезпечити більш передбачувану роботу сервісів у умовах зростаючого навантаження. Апробація результатів дисертації. Основні положення і результати роботи були представлені та обговорювались на XVIII науково-практичній конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг» ПМК-2025 (Київ, 19-21 листопада 2025 р.) та на другій міжнародній науково-практичній конференції «Innovative Research in Science and Economy» (Брюссель, Бельгія, 3-5 грудня 2025 р.). Публікації. 1. Жовтанюк, М.В., Молчанов, О.А. (2025). Спосіб побудови розподіленого фільтра Блума з консистентним хешуванням // XVIII Науково-практична конференція магістрантів та аспірантів "Прикладна математика та комп’ютинг" (ПМК-2025) (м. Київ, Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського», 19-21 листопада 2025 р.), С. 207 – 211. 2. Zhovtaniuk, M., Molchanov, O., (2025). A method for constructing a distributed bloom filter with consistent hashing, Innovative Research in Science and Economy: Collection of Scientific Papers with Proceedings of the 2nd International Scientific and Practical Conference. International Scientific Unity, December 3-5, 2025, pp. 264—267. DOI: https://doi.org/10.70286/ISU-03.12.2025.004 Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів, висновків до кожного розділу, загальних висновків та списку використаних літературних джерел (13 найменувань). Повний обсяг дисертації — 122 сторінки, у тому числі 85 сторінок основного тексту, 37 рисунків, 21 слайдів презентації. У вступі роботи розглянуто сучасний стан проблеми масштабування фільтра Блума, обґрунтовано актуальність використання цієї структури даних у високонавантажених системах, сформульовано мету, задачі дослідження, а також підкреслено наукову новизну й практичне значення отриманих результатів. У першому розділі проведено аналіз теоретичних основ фільтра Блума, сфер його застосування та проблем, що виникають при роботі з великими обсягами даних, розглянуто існуючі підходи до масштабування та оглянуто програмні рішення, які реалізують фільтр Блума в розподілених системах, з визначенням їх переваг і недоліків. У другому розділі сформульовано модель масштабованої розподіленої системи фільтра Блума, розглянуто використання консистентного хешування для розподілу єдиного бітового масиву між вузлами, проаналізовано вплив параметрів фільтра та конфігурації вузлів на ймовірність хибно позитивних спрацьовувань, використання пам’яті та пропускну здатність, а також запропоновано підхід до оцінки можливостей перебалансування системи. У третьому розділі розроблено архітектуру та програмний прототип розподіленої системи фільтра Блума, описано взаємодію між координатором і вузлами, механізми додавання та видалення вузлів, а також засоби моніторингу стану системи та збору метрик продуктивності. У четвертому розділі проведено експериментальні дослідження роботи розробленої системи: виміряно пропускну здатність і затримки при перевірці належності елементів, досліджено поведінку системи при додаванні та видаленні вузлів, проаналізовано вплив перебалансування на продуктивність, а також виконано порівняння з класичним одно-вузловим варіантом фільтра Блума. У висновках представлені результати роботи. | |
| dc.description.abstractother | Relevance of the topic. The rapid growth of data volumes in modern information systems, e-commerce services, advertising platforms, recommendation and analytics systems leads to increased requirements for the speed and efficiency of query processing. One of the fundamental tasks in such systems is checking whether an element belongs to a large dataset, which must be performed with minimal latency and under limited memory resources. Classical approaches based on storing complete data sets become impractical due to their high cost in terms of RAM consumption and access time. The Bloom filter is one of the key and widely used data structures for solving such tasks, as it provides high throughput for membership queries due to the compact representation of sets. However, as data volumes and load grow, the problem of vertical scaling arises: a single physical node is limited by its hardware characteristics and is unable to hold a Bloom filter of the required size and process the required number of queries per second. This necessitates the development of distributed solutions that enable placing a Bloom filter on multiple nodes, ensuring load balancing, system availability, and the possibility of both vertical and horizontal scaling. Thus, the research and construction of a scalable distributed Bloom filter system is a relevant task that has both theoretical and practical significance for modern high-load services. The aim and objectives of the research. The aim of this thesis is to investigate and develop a scalable distributed Bloom filter system that provides efficient membership checking under conditions of large data volumes and limited resources of individual nodes. To achieve this aim, the dissertation solves the following tasks: 1. To review existing approaches to the construction and scaling of Bloom filters, as well as software solutions for working with large data volumes. 2. To perform a theoretical analysis of a distributed Bloom filter model, formalize its main parameters, and evaluate the impact of these parameters on the probability of false positives and resource usage. 3. To design the architecture and model of a scalable distributed Bloom filter system, taking into account data distribution between nodes, load balancing, and availability. 4. To implement a scalable computer system of a distributed Bloom filter for operation under conditions of large data volumes and high query intensity. 5. To carry out experimental studies of the performance and scalability of the developed system. The object of the research is the process of constructing a distributed Bloom filter for processing large volumes of data. The subject of the research is the models, methods, and techniques for constructing and scaling a distributed Bloom filter for efficient membership checking in systems with large data volumes. To solve the stated scientific problems, the following research methods are used: search and analysis – to study existing approaches to constructing and scaling Bloom filters and distributed data storage systems; formalization – to build a mathematical model of the distributed Bloom filter, define its parameters and reliability characteristics; modelling, experiment, observation, measurement, analogy and testing – to develop and study the software prototype of the system and to evaluate its performance, scalability and efficiency under conditions of large data volumes. The scientific novelty lies in the following: 1. An improved method for constructing a scalable distributed Bloom filter computer system is proposed, which differs from existing approaches in that the elements of the given set are distributed among different nodes of the system using consistent hashing, whereby the system operates as a single logical Bloom filter. The practical significance of the results obtained in the thesis consists of a comprehensive analysis of existing approaches to the construction and scaling of Bloom filters. Based on this analysis, a scalable distributed computer Bloom filter system has been implemented, which makes it possible to work with data volumes that exceed the capabilities of a single physical server in terms of RAM, while ensuring high speed of membership checking. The developed system enables flexible scaling of computing resources by adding or removing nodes with minimal impact on service availability and throughput, which is important for high-load applications such as advertising platforms, analytics systems, caching, and duplicate detection. The presence of tools for monitoring performance and node state makes it possible to assess the efficiency of load distribution, promptly detect bottlenecks, and adapt the system configuration to current requirements. The obtained results can be used as a basis for the deployment of a distributed Bloom filter in real industrial systems where the combination of high performance, limited memory resources and the need for horizontal scaling is critical. This makes it possible to increase the efficiency of processing large data volumes, reduce infrastructure costs, and ensure more predictable service operation under conditions of increasing load. Approbation of the thesis results. The main propositions and results of the work were presented and discussed at the 18th scientific and practical conference of master’s and postgraduate students “Applied Mathematics and Computing” AMC-2025 (Kyiv, 19–21 November 2025) and at the 2nd international scientific and practical conference “Innovative Research in Science and Economy” (Brussels, Belgium, 3–5 December 2025). Publications. 1. Zhovtaniuk, M.V., Molchanov, O.A. (2025). A method for constructing a distributed Bloom filter with consistent hashing // XVIII Scientific and Practical Conference of Master’s Students and Postgraduates "Applied Mathematics and Computing" (PMC-2025) (Kyiv, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”, November 19–21, 2025), pp. 207–211. 2. Zhovtaniuk, M., Molchanov, O., (2025). A method for constructing a distributed bloom filter with consistent hashing, Innovative Research in Science and Economy: Collection of Scientific Papers with Proceedings of the 2nd International Scientific and Practical Conference. International Scientific Unity, December 3-5, 2025, pp. 264—267. DOI: https://doi.org/10.70286/ISU-03.12.2025.004 Structure and scope of the thesis. The master’s thesis consists of an introduction, four chapters, conclusions to each chapter, general conclusions, and a list of references (13 items). The total volume of the thesis is 122 pages, including 85 pages of main text, 37 figures, and 21 presentation slides. The introduction examines the current state of the Bloom filter scaling problem, substantiates the relevance of using this data structure in high-load systems, formulates the aim and objectives of the study, and emphasizes the scientific novelty and practical significance of the obtained results. The first chapter presents an analysis of the theoretical foundations of the Bloom filter, its application areas and the problems that arise when working with large data volumes. It also reviews existing approaches to scaling and software solutions that implement the Bloom filter in distributed systems, with identification of their advantages and disadvantages. The second chapter formulates a model of a scalable distributed Bloom filter system, considers the use of consistent hashing to distribute a single bit array across nodes, analyses the impact of filter parameters and node configuration on the probability of false positives, memory usage and throughput, and proposes an approach to assessing the possibilities of system rebalancing. The third chapter develops the architecture and software prototype of the distributed Bloom filter system, describes the interaction between the coordinator and the nodes, the mechanisms for adding and removing nodes, as well as tools for monitoring the system state and collecting performance metrics. The fourth chapter presents experimental studies of the developed system: measuring throughput and latency for membership checks, investigating system behavior when adding and removing nodes, analysing the impact of rebalancing on performance, and comparing the results with a classical single-node Bloom filter implementation. The conclusions summarize the results of the work. | |
| dc.format.extent | 121 с. | |
| dc.identifier.citation | Жовтанюк, М. В. Масштабована розподілена комп’ютерна система побудови фільтра Блума : магістерська дис. : 123 Комп'ютерна інженерія / Жовтанюк Максим Вʼячеславович. – Київ, 2025. – 121 с. | |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/78230 | |
| dc.language.iso | uk | |
| dc.publisher | КПІ ім. Ігоря Сікорського | |
| dc.publisher.place | Київ | |
| dc.subject | фільтр Блума | |
| dc.subject | розподілені системи | |
| dc.subject | консистентне хешування | |
| dc.subject | MurmurHash3 | |
| dc.subject | масштабування. | |
| dc.subject | Bloom filter | |
| dc.subject | distributed systems | |
| dc.subject | consistent hashing | |
| dc.subject.udc | 004.421.2 : 004.75 | |
| dc.title | Масштабована розподілена комп’ютерна система побудови фільтра Блума | |
| dc.type | Master Thesis |
Файли
Контейнер файлів
1 - 1 з 1
Вантажиться...
- Назва:
- Zhovtaniuk_MV_KV42mp_magistr_2025.pdf
- Розмір:
- 4.27 MB
- Формат:
- Adobe Portable Document Format
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 8.98 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: