Масштабована розподілена комп’ютерна система побудови фільтра Блума
Дата
2025
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
Актуальність теми. Стрімке зростання обсягів даних у сучасних інформаційних системах, сервісах електронної комерції, рекламних платформах, системах рекомендацій та аналітики призводить до підвищених вимог до швидкості й ефективності обробки запитів. Одним із базових завдань у таких системах є перевірка належності елемента до великої множини даних, що має виконуватися з мінімальними затримками та за обмежених ресурсів пам’яті. Класичні підходи, засновані на збереженні повних наборів даних, стають малопридатними через їхню високу вартість з точки зору оперативної пам’яті та часу доступу.
Фільтр Блума є однією з ключових і широко вживаних структур даних для розв’язання подібних задач, оскільки забезпечує високу пропускну здатність запитів належності за рахунок компактного представлення множин. Однак із зростанням обсягів даних та навантаження виникає проблема вертикального масштабування: один фізичний вузол обмежений фізичними характеристиками та не здатний вмістити фільтр необхідного розміру та обробити потрібну кількість запитів на секунду. Це обумовлює потребу у розробці розподілених рішень, що дають змогу розміщувати фільтр Блума на кількох вузлах, забезпечуючи балансування навантаження, доступність системи та можливість як вертикального, так і горизонтального масштабування. Таким чином, дослідження та побудова масштабованої розподіленої системи фільтра Блума є актуальним завданням, яке має як теоретичну, так і практичну значущість для сучасних високонавантажених сервісів.
Мета і завдання дослідження. Метою дисертаційної роботи є дослідження та розробка масштабованої розподіленої системи побудови фільтра Блума, яка забезпечує ефективну перевірку належності елементів в умовах великих обсягів даних та обмежених ресурсів окремих вузлів.
Для досягнення поставленої мети в дисертації вирішуються такі задачі:
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 слайдів презентації.
У вступі роботи розглянуто сучасний стан проблеми масштабування фільтра Блума, обґрунтовано актуальність використання цієї структури даних у високонавантажених системах, сформульовано мету, задачі дослідження, а також підкреслено наукову новизну й практичне значення отриманих результатів.
У першому розділі проведено аналіз теоретичних основ фільтра Блума, сфер його застосування та проблем, що виникають при роботі з великими обсягами даних, розглянуто існуючі підходи до масштабування та оглянуто програмні рішення, які реалізують фільтр Блума в розподілених системах, з визначенням їх переваг і недоліків.
У другому розділі сформульовано модель масштабованої розподіленої системи фільтра Блума, розглянуто використання консистентного хешування для розподілу єдиного бітового масиву між вузлами, проаналізовано вплив параметрів фільтра та конфігурації вузлів на ймовірність хибно позитивних спрацьовувань, використання пам’яті та пропускну здатність, а також запропоновано підхід до оцінки можливостей перебалансування системи.
У третьому розділі розроблено архітектуру та програмний прототип розподіленої системи фільтра Блума, описано взаємодію між координатором і вузлами, механізми додавання та видалення вузлів, а також засоби моніторингу стану системи та збору метрик продуктивності.
У четвертому розділі проведено експериментальні дослідження роботи розробленої системи: виміряно пропускну здатність і затримки при перевірці належності елементів, досліджено поведінку системи при додаванні та видаленні вузлів, проаналізовано вплив перебалансування на продуктивність, а також виконано порівняння з класичним одно-вузловим варіантом фільтра Блума.
У висновках представлені результати роботи.
Опис
Ключові слова
фільтр Блума, розподілені системи, консистентне хешування, MurmurHash3, масштабування., Bloom filter, distributed systems, consistent hashing
Бібліографічний опис
Жовтанюк, М. В. Масштабована розподілена комп’ютерна система побудови фільтра Блума : магістерська дис. : 123 Комп'ютерна інженерія / Жовтанюк Максим Вʼячеславович. – Київ, 2025. – 121 с.