Roaring Bitmaps¶

Roaring Bitmaps — это компактная структура данных для хранения и обработки битовых множеств (битмапов), предназначенная для эффективного выполнения операций над большими наборами целых чисел. Она сочетает в себе преимущества разреженных и плотных представлений, обеспечивая высокую скорость операций (объединение, пересечение, разность) при относительно небольшом потреблении памяти.

¶Принцип работы

Основная идея Roaring Bitmaps заключается в разделении всего диапазона возможных значений (например, 32-битных целых чисел от 0 до 2³²−1) на блоки фиксированного размера — контейнеры. Каждый контейнер отвечает за диапазон из 2¹⁶ (65 536) последовательных значений. Внутри каждого контейнера данные хранятся в одном из трёх форматов, выбор которого зависит от плотности заполнения:

1. Массив (Array Container): используется для разреженных данных. Хранит отсортированный список 16-битных значений, присутствующих в данном диапазоне. Применяется, когда количество элементов в контейнере не превышает 4096.
2. Битмап (Bitmap Container): используется для плотных данных. Хранит битовую карту фиксированного размера (8 КБ) для всех 65 536 возможных значений. Применяется, когда количество элементов превышает 4096.
3. Заполненный контейнер (Run Container): используется для данных, содержащих длинные последовательности подряд идущих чисел. Хранит пары «начало — длина» для каждой серии. Этот формат был добавлен в 2016 году и особенно эффективен для данных, содержащих диапазоны значений.

Выбор формата происходит динамически: при добавлении или удалении элементов контейнер может автоматически конвертироваться из одного типа в другой. Порог в 4096 элементов выбран из соображений баланса: битмап занимает фиксированные 8 КБ, в то время как массив из 4096 16-битных целых чисел занимает ровно столько же (4096 × 2 байта = 8 КБ). Таким образом, массив используется только тогда, когда он занимает меньше памяти, чем битмап.

¶Преимущества и недостатки

¶Преимущества

• Высокая производительность: операции над битмапами (AND, OR, XOR, ANDNOT) выполняются быстро благодаря тому, что контейнеры одного типа обрабатываются векторными инструкциями (SIMD), а контейнеры разных типов — с помощью оптимизированных алгоритмов слияния.
• Экономия памяти: в отличие от классических битмапов, которые всегда занимают фиксированный объём (например, 512 МБ для 32-битного диапазона), Roaring Bitmaps потребляют память пропорционально количеству хранимых элементов.
• Быстрая сериализация и десериализация: структура может быть эффективно упакована в бинарный формат и восстановлена без потери производительности.

¶Недостатки

• Сложность реализации: структура данных значительно сложнее классического битмапа, что увеличивает риск ошибок при самостоятельной реализации.
• Накладные расходы на маленьких множествах: для множеств, содержащих менее нескольких сотен элементов, использование Roaring Bitmaps может быть избыточным по сравнению с простым отсортированным массивом или хеш-таблицей.
• Неоптимальность для случайных данных: если данные распределены хаотично по всему 32-битному диапазону, количество контейнеров может стать большим, что увеличит потребление памяти.

¶Применение

Roaring Bitmaps широко используются в системах, где требуется эффективное хранение и обработка больших множеств целочисленных идентификаторов. Основные области применения:

• Поисковые движки: для хранения инвертированных индексов, где каждому термину (слову) соответствует множество идентификаторов документов. Операции пересечения и объединения таких множеств выполняются при обработке логических запросов.
• Базы данных: в аналитических СУБД (например, Apache Druid, ClickHouse) для хранения битовых индексов и ускорения фильтрации по колонкам.
• Графовые базы данных: для хранения рёбер и смежности вершин.
• Аналитика больших данных: в системах Apache Spark и Apache Kylin для оптимизации операций над наборами данных.
• Компьютерная графика: для управления видимостью объектов и отсечением.

¶Реализации

Наиболее известная эталонная реализация — библиотека RoaringBitmap на языке Java, разработанная Даниэлем Лемером (Daniel Lemire) и его коллегами. Также существуют официальные или портированные версии для других языков программирования:

• C — библиотека CRoaring.
• C++ — библиотека roaring.
• Python — модуль pyroaring.
• Go — библиотека roaring.
• Rust — библиотека roaring-rs.
• JavaScript — библиотека roaring.

¶Сравнение с альтернативами

Основными альтернативами Roaring Bitmaps являются:

• Классические битмапы (WAH, EWAH, Concise): сжатые битмапы, использующие кодирование длин серий. Roaring Bitmaps обычно превосходят их по скорости операций и по памяти на разреженных данных.
• Отсортированные массивы: просты в реализации, но операции объединения и пересечения требуют O(n) времени и памяти.
• Хеш-таблицы: обеспечивают быстрый доступ к отдельным элементам, но неэффективны для операций над множествами целиком.

Исследования показывают, что Roaring Bitmaps, как правило, обеспечивают лучший компромисс между скоростью и потреблением памяти для большинства реальных рабочих нагрузок, что привело к их широкому внедрению в индустрии.

¶Источники

• Lemire, D., Ssi-Yan-Kai, G., Kaser, O. (2016). "Consistently faster and smaller compressed bitmaps with Roaring".
• Lemire, D., Kaser, O. (2018). "Roaring Bitmaps: Implementation of an Optimized Software Library".
• Chambi, S., Lemire, D., Kaser, O., Godin, R. (2016). "Better bitmap performance with Roaring bitmaps".