В эпоху больших данных и стремительного роста приложений, способных обрабатывать огромные массивы информации, становится крайне важным использование высокопроизводительных и экономных по памяти структур данных. Approximate Membership Query (AMQ) фильтры — одна из таких технологий, которые позволяют быстро определять принадлежность элемента множеству с небольшой вероятностью ошибки, что существенно ускоряет многие процессы в распределенных системах, базах данных и других приложениях. На стыке новейших решений с 2022 года появилась инновационная структура — Binary Fuse Filters, на базе которой была построена современная C++ библиотека Binfuse, способная значительно повысить эффективность работы с большими наборами данных. Binary Fuse Filters представляют собой дальнейшее развитие XOR-фильтров и предлагают улучшенную производительность при гораздо меньших затратах памяти по сравнению с классическими аналогами, такими как Bloom и Cuckoo фильтры. Это достигается благодаря уникальному подходу к построению и хранению фильтра, который позволяет сократить размер данных и увеличить скорость как построения, так и выполнения запросов.
Основное преимущество Binary Fuse Filters в их способности не просто эффективно работать с большими объемами информации, но и сохранять высокую точность при минимальных значениях false positive rate. Binfuse реализует полный функционал Binary Fuse Filters на C++, предоставляя удобный интерфейс, совместимый с современными стандартами языка. В отличие от низкоуровневых реализаций, библиотека фокусируется на универсальности и практичности: наличие механизмов для (де)сериализации фильтров на диск позволяет эффективно работать с большими объемами данных без необходимости удерживать весь фильтр оперативно, а поддержка memory-mapped файлов обеспечивается посредством кроссплатформенной библиотеки mio. Такая архитектура позволяет запускать запросы как из оперативной памяти, так и напрямую с диска, что значительно расширяет сценарии использования и оптимизирует потребление ресурсов. Однако использование Binary Fuse Filters сопряжено с некоторыми ограничениями, связанными с их неизменяемостью после заполнения.
По сути, фильтр не поддерживает инкрементальное добавление элементов. Добавление новых данных требует создания нового фильтра, что может сопровождаться значительными пиковыми нагрузками на память — для сотен миллионов ключей рекомендуется иметь в распоряжении до 64 ГБ оперативной памяти. Именно это ограничение накладывало барьер для применения таких фильтров с размахом на очень больших наборах данных. Binfuse решает эту проблему с помощью составляющей sharded_filter, которая позволяет разбивать огромный набор ключей на отдельные шардированные части. Каждая часть формируется и сохраняется отдельно на диске, индексируясь по наиболее значимым битам ключей.
Такой подход не только позволяет контролировать объем потребляемой оперативной памяти во время заполнения, но и облегчает работу с фильтрами, насчитывающими десятки миллиардов записей. При этом запросы к таким шардированным фильтрам остаются очень быстрыми — при выполнении каждого запроса происходит всего несколько операций обращения к памяти через mmap. Скорость запроса зависит от дисковой подсистемы и условий кэширования, но может достигать порядка 50 наносекунд, что ставит Binfuse в ряды одних из самых быстрых решений на современном рынке. Практическое применение возможностей Binfuse и Binary Fuse Filters разнообразно. Одним из мотивирующих примеров использования стала база скомпрометированных паролей, для которой нужно быстро определять, имеется ли конкретное значение в огромном списке, без необходимости полного сканирования.
Но в целом подобные фильтры востребованы в распределенных и базовых системах, где ускорение запросов критично. AMQ-фильтры служат своего рода прокси для наборов ключей баз данных или удаленного кэша, предсказывая вероятность наличия ключа и избегая задержек, вызванных обращением к медленным хранилищам или сетевым ресурсам. Этот подход оптимизирует пакетообразование, обмен ресурсами в пиринговых сетях и систему распределенного кэширования. В программном обеспечении Binfuse представлены как односегментные фильтры filter, так и persistent_filter для хранения на диске (с возможностью выбора режима чтения или записи), а также реализация шардированных фильтров sharded_filter, где задачи разделяются между отдельными частями фильтра. Библиотека реализована с учётом современных возможностей C++20 и поддерживает сборку как на POSIX-системах, так и на Windows через MinGW, что делает её доступной широкой аудитории разработчиков.
Удобство использования Binfuse дополнено примерами, которые демонстрируют создание фильтра, сохранение на диск и последующую загрузку. Возможна и работа с шардированными фильтрами, где каждый шард создается и загружается независимо, либо можно применять потоковый API для последовательного добавления ключей. Интерфейс позволяет выбирать между версиями с 8-битными и 16-битными отпечатками (fingerprints), что влияет на скорость работы и вероятность ложных срабатываний — 1/256 и 1/65536 соответственно. Параметры бинарного формата файлов фильтров защищаются записью первых 16 байт с информацией о конфигурации, что исключает их неправильное или некорректное открытие. Для удобства разработчика предусмотрена гибкая система обработки исключений при ошибках загрузки фильтров или несоответствии параметров.
В сравнении с классическими AMQ-фильтрами, Binfuse демонстрирует впечатляющие показатели производительности на больших наборах данных. Результаты тестов при 100 миллионах ключей показывают время запроса в диапазоне 46–52 наносекунд и ложноположительную вероятность около 0.39% для 8-битных фильтров и 0.0015% для 16-битных. При масштабировании до 10 миллиардов ключей достигаются весьма стабильные скорости при использовании шардирования.
При этом задержки сильно зависят от конкретной конфигурации оборудования, однако сами данные убедительно демонстрируют преимущества подхода. Особое внимание стоит уделить менеджменту памяти при работе Binfuse. Начальные этапы построения фильтра с малым количеством шардов требуют значительного объема оперативной памяти (до 1–2 гигабайт и больше). Однако в режиме работы с множеством шардов эта нагрузка существенно снижается. Итоговый размер mmap-файла, хранящего фильтр, сопоставим с размером фильтра на диске, а ОС выступает в роли интеллектуального кеша, динамически освобождая или загружая страницы в зависимости от текущих условий.
