Представьте распределённое аналитическое хранилище: запросы ищут редкие значения идентификатора, но данные физически разбросаны по блокам. Как вероятностный фильтр может сократить чтение?
Вероятностный фильтр, обычно фильтр Блума, хранит компактное приближённое представление значений блока или файла. Перед чтением хранилище проверяет искомый идентификатор: если фильтр точно показывает его отсутствие, блок можно пропустить; если показывает наличие, блок читают. Ложные срабатывания возможны, но при корректном построении не должно быть пропусков существующих значений.
Индексы ускоряют поиск, но их хранение и обслуживание могут быть дорогими, особенно для больших аналитических наборов, разбитых на множество сегментов. Для чтения отчётов важно не только быстро найти строку, но и заранее исключить как можно больше ненужных файлов или блоков.
Вероятностные структуры появились как компромисс между точностью полного индекса и стоимостью хранения. Они занимают мало памяти, быстро проверяются и хорошо подходят для предварительного отсечения данных перед основным чтением.
Без такого фильтра система может проверять каждый блок, даже если искомый идентификатор встречается только в одном из них. При большом числе сегментов это увеличивает объём чтения, сетевой обмен и нагрузку на декодирование данных.
Полный индекс решает задачу точнее, но требует больше места, обновления при изменении данных и дополнительных операций записи. Неверное применение вероятностного фильтра опасно: если он разрешает пропустить блок при ошибочном отрицательном результате, запрос может вернуть неполные данные.
При построении фильтра каждое значение преобразуется несколькими хеш-функциями в позиции битового массива. Для проверки значения система вычисляет те же позиции: если хотя бы один соответствующий бит не установлен, значение точно отсутствует в данном блоке. Если все проверяемые биты установлены, значение может присутствовать, но может оказаться ложным совпадением.
Фильтр обычно связывают с конкретным файлом, сегментом или группой строк. Планировщик или слой чтения проверяет фильтры до загрузки самих данных, поэтому блоки с гарантированно отсутствующим идентификатором не декодируются.
Точность зависит от размера фильтра, числа хеш-функций и количества записей. При слишком маленьком фильтре растёт доля ложных срабатываний: корректность не нарушается, но экономия чтения уменьшается. Увеличение фильтра снижает ложные срабатывания, однако повышает расход памяти и метаданных.
Такой механизм особенно полезен для равенств по высокоселективным полям: идентификаторам клиента, заказа или устройства. Для диапазонных условий по времени чаще эффективнее минимальные и максимальные значения, сортировка или кластеризация; фильтр Блума не описывает диапазон компактно.
Для неизменяемых сегментов фильтр строится один раз и надёжен. При обновлениях нужно корректно обслуживать новые версии сегментов. Устаревший фильтр, в котором сохранилось удалённое значение, обычно приводит лишь к лишнему чтению, но фильтр, не включивший добавленное значение, может вызвать пропуск данных, если система не учитывает новые дельты отдельно.
В хранилище событий было несколько десятков тысяч файлов. Запросы по редкому идентификатору устройства читали почти все файлы, поскольку время события в условии не всегда давало достаточное отсечение.
Рассматривались три варианта. Полный индекс давал бы точный поиск, но потребовал бы значительного места и сложного обслуживания при регулярных загрузках. Перестройка физической сортировки по идентификатору ускорила бы такие запросы, однако ухудшила бы загрузку и запросы по времени. Фильтры Блума добавляли небольшой объём метаданных и не меняли логическую модель хранения, но не гарантировали отсутствие ложных чтений.
Выбрали фильтры Блума на уровне файлов, сохранив кластеризацию по времени. Система сначала отбрасывала файлы по временным метаданным, затем применяла фильтры по идентификатору. Это уменьшило чтение для точечных запросов без существенного усложнения загрузки; запросы по диапазонам времени по-прежнему обслуживались преимущественно средствами временной кластеризации.
Вопрос: Может ли фильтр Блума доказать, что значение присутствует в блоке?
Ответ: Нет. Он доказывает только отсутствие, когда хотя бы один проверяемый бит не установлен. Положительный результат означает лишь возможность наличия значения, поэтому блок нужно прочитать и проверить точным предикатом. Это и есть причина ложных срабатываний.
Вопрос: Что произойдёт, если фильтр настроен на поле с низкой селективностью?
Ответ: Большинство блоков будет содержать хотя бы одно значение из небольшого множества возможных значений. Фильтры станут положительными почти для каждого блока, поэтому чтение почти не сократится. Механизм наиболее полезен, когда искомые значения редки относительно числа блоков.
Вопрос: Почему увеличение размера фильтра не гарантирует пропорционального ускорения запроса?
Ответ: Больший фильтр уменьшает число ложных срабатываний, но не исключает блоки, где значение действительно присутствует. Если запрос выбирает распространённое значение, большая часть блоков всё равно должна быть прочитана. Кроме того, проверка фильтра не устраняет стоимость чтения самих подходящих блоков, сетевых обменов и последующей обработки результата.