dmedovich
all posts

ENGINEERING NOTES

Битовая карта, Ribbon-фильтр и список postings

devlog

Когда я добавил индексы в amber, trace_id по умолчанию попал в bitmap. Я знал, что bitmap для поля высокой кардинальности обычно плохая идея, но хотел понять насколько. Спойлер: очень плохая.

Bitmap для trace_id

Bitmap-индексы хорошо работают для полей с небольшим числом уникальных значений. У level всего пять вариантов:

INFO  -> [1, 1, 0, 1, 0, ...]
ERROR -> [0, 0, 1, 0, 1, ...]

Пять компактных bitmap, хорошее RLE-сжатие, пересечение двух условий — один AND. Дёшево.

С trace_id всё иначе: почти у каждой записи своё значение.

a1b2c3d4... -> [1, 0, 0, 0, ...]  // один установленный бит на 100 тысяч
e5f6a7b8... -> [0, 1, 0, 0, ...]
f9c0d1e2... -> [0, 0, 1, 0, ...]
... (ещё 99 997)

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

Ribbon-фильтр

Ribbon-фильтр — вероятностная структура (около 2 бит на ключ). Он отвечает на вопрос «есть ли в сегменте значение X?» без ложноотрицательных ответов. Для сегмента со 100 тысячами записей он занимает несколько килобайт.

Для запроса по trace_id исполнитель стал работать так:

if ribbon, ok := e.logRibbon(seg.FileName); ok {
    if !ribbon.Contains(q.TraceID[:]) {
        return 0, nil // в сегменте точно нет этого trace_id
    }
}
// сканирование сегмента

Ribbon ответил «нет» — пропускаем сегмент. Ответил «возможно» — сканируем. Для 10 млн записей размер индексов упал с сотен мегабайт до 340 КиБ. При запросах по trace_id большинство сегментов удавалось пропустить.

Что сломалось

До Ribbon запрос service=api AND trace_id=X выполнялся пересечением bitmap:

allowedIDs = bitmap(service=api) AND bitmap(trace_id=X)  // 1 запись

После замены bitmap для trace_id пересекать стало нечего:

allowedIDs = bitmap(service=api) only  // около 20 тысяч кандидатов из 100 тысяч

Вместо одной записи приходилось просматривать 20 тысяч. Запросы только с trace_id=X работали нормально: Ribbon плюс линейное сканирование. Но в составных запросах пересечение пропало.

Posting list

Для полей высокой кардинальности подходит posting list — инвертированный индекс вида trace_id -> []record_id.

Если в сегменте 2 000 уникальных trace ID со средним числом 50 записей на каждый, список занимает 2000 × 50 × 8 байт, то есть 800 КиБ. Это намного меньше раздутого bitmap и при этом даёт точные ID записей.

Теперь поиск по trace_id состоит из трёх шагов:

Ribbon-фильтр -> пропустить 99 из 101 сегмента
posting list   -> получить точный список записей для trace_id
roaring64.And(bitmap(service=api), posting_list(trace_id=X)) -> пересечь результаты

Составные запросы снова работают корректно. Posting list хранится в sidecar-файле .pidx рядом с сегментом. Он строится при запечатывании и лениво загружается через LRU-кэш при первом запросе к сегменту.

Деталь реализации

Первый вариант builder-а использовал map[string][]uint64. Для 100 тысяч уникальных trace ID накладные расходы map (около 12 байт на запись), строковых ключей (32 байта) и заголовков срезов (32 байта) составляли примерно 7,6 МБ на сегмент во время построения. Умножаем на число параллельно запечатываемых сегментов — и сборщик мусора уже здесь.

Вместо этого я перешёл на плоский отсортированный срез пар:

type rawPair struct {
    key [16]byte
    id  uint64
}

Итог

Bitmap и posting list отвечают на один вопрос — «какие записи соответствуют этому значению?» — но делают это с противоположными компромиссами. Bitmap использует битовый вектор длины N: он дёшев при низкой кардинальности и дорог при высокой. Posting list хранит явный список: он дёшев при высокой кардинальности и дорог при низкой.

Ribbon-фильтр отвечает на другой вопрос: «может ли это значение вообще быть в сегменте?» Поэтому он не заменяет ни bitmap, ни posting list. В amber используются все три: каждый решает задачу, с которой два других не справляются.

all posts