Redis получил битмапы Roaring: до 185 раз быстрее

Битмапы в Redis есть давно, но у них была неприятная особенность: память и время работы зависели от самого большого выставленного бита, а не от того, сколько битов реально установлено. Скоро это лечится одной настройкой. Андре Виджиано (@aviggiano) встроил в Redis сжатые битмапы Roaring, изменения уже влиты в основную ветку и должны выйти в Redis 8.12. Даниэль Лемир, один из авторов формата Roaring, собрал Redis из коммита слияния и замерил разницу. На некоторых операциях она измеряется сотнями раз.

Классический битмап в Redis живёт внутри обычной строки. Команда SETBIT key offset 1 выставляет бит, и бит номер i в битмапе совпадает с битом номер i в строке. Схема простая и быстрая, но строка занимает один байт на каждые восемь позиций вплоть до максимального offset, сколько бы битов ни было выставлено на самом деле.

На практике это выглядит так. Выставили один-единственный бит на позиции четыре миллиарда, и Redis выделил 512 МБ. Дальше каждый BITCOUNT или BITOP сканирует все эти 512 МБ целиком. Пока ID пользователей идут плотно с нуля, проблем нет. Как только в ключах оказываются хеши, разреженные идентификаторы или большие смещения, битмап превращается в дорогую и медленную структуру.

Roaring не пытается сжать длинную ленту битов. Он делит пространство 32-битных чисел на блоки по 65 536 значений и для каждого блока выбирает подходящий контейнер. Разреженные участки хранятся коротким отсортированным массивом чисел, плотные обычным битсетом, а длинные серии подряд идущих значений парами «начало и длина». Подсчёт, пересечение и объединение выполняются прямо над контейнерами, без распаковки.

Из-за этого Roaring часто получается одновременно компактнее и быстрее несжатого битсета. Формат давно стал стандартом в индустрии: его используют Elasticsearch, Apache Spark, ClickHouse и десятки других систем. Для Redis существовал отдельный модуль redis-roaring от того же Виджиано, теперь поддержка появится в самом ядре.

В Redis появится новый тип данных. Для такого ключа TYPE вернёт bitmap, а OBJECT ENCODING покажет bitmap-roaring. Функция включается явно, одной настройкой, после чего новые битмапы будут создаваться в формате Roaring:

CONFIG SET bitmap-default-roaring yes SETBIT active:2026-10-17 4000000000 1 TYPE active:2026-10-17 # bitmap OBJECT ENCODING active:2026-10-17 # bitmap-roaring BITCOUNT active:2026-10-17 BITOP AND active:both active:2026-10-16 active:2026-10-17

Чтобы настройка пережила перезапуск, её стоит прописать в redis.conf или выполнить CONFIG REWRITE. До выхода 8.12 попробовать функцию можно, собрав Redis из исходников основной ветки.

Лемир запускал сервер на одном ядре Intel Xeon Gold 6548N. Для каждого сценария он создавал два битмапа a и b дважды, в виде строки и в виде Roaring с одинаковым содержимым, и засекал время команд. Сценарии такие: 100 тысяч случайных ID из 100 миллионов (условно, пользователи, которые сегодня открывали какую-то функцию), 50 миллионов случайных ID из тех же 100 миллионов, десять серий по миллиону подряд идущих ID в диапазоне 100 миллионов (когорты пользователей, зарегистрированных в одну неделю) и 100 тысяч случайных 32-битных значений, для которых строка занимает 512 МБ.

Результаты по командам. BITCOUNT: на 0,1% и 50% случайных ID 350 мкс у строки против 12 мкс у Roaring, на сериях 319 мкс против 2,2 мкс. BITOP AND: 5,5 мс против 1,3 мс на разреженных данных, 5,5 мс против 3,6 мс на плотных, 4,8 мс против 30 мкс на сериях. BITOP OR: 5,4 мс против 1,2 мс, 5,5 мс против 3,4 мс и 4,8 мс против 26 мкс. На хешированных 32-битных ID BITOP AND занимает 343 мс у строки и 13 мс у Roaring.

Картина понятная. Подсчёт битов ускоряется почти в 30 раз даже на плотных случайных данных: Roaring хранит количество элементов в контейнерах и не перебирает биты заново. На сериях подряд идущих ID выигрыш доходит до сотен раз, потому что миллион значений подряд хранится как одна пара чисел. Самый показательный случай с хешированными ID: строке приходится покрывать все четыре миллиарда позиций и сканировать 512 МБ на каждый BITOP, а Roaring работает только с реально существующими значениями и укладывается в 13 мс.

Слабее всего результат на половине случайных битов, где AND и OR быстрее лишь в 1,5 раза. Это ожидаемо: такие данные плохо сжимаются, и Roaring сводится к тем же плотным битсетам.

Сам Лемир прямо пишет, что сжатые битмапы не всегда лучше и у них хватает компромиссов. Если ваши ID плотные и начинаются с нуля, обычная строка уже работает почти оптимально, а одиночные SETBIT и GETBIT в ней сводятся к прямому обращению по адресу. Кроме того, Roaring появляется как новый тип данных, поэтому код, который читает битмап как строку через GET или GETRANGE или передаёт его сырые байты в другие системы, стоит проверить перед включением настройки.

Зато для аналитики активных пользователей, когортного анализа, фильтров по тегам и сегментам, учёта просмотренных объектов, а особенно для всего, что адресуется хешами и разреженными ID, Roaring выглядит очень выгодной заменой. Тем более что включается он одной строкой конфигурации и не требует менять команды.

Полная версия с таблицей замеров на UPROGER. Ссылки: исходный пост Даниэля Лемира с замерами, сайт формата Roaring, модуль redis-roaring, Redis.