Bitmap, ribbon filter и posting list

Когда я добавлял индексы в 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, ...]  // один установленный бит на 100K
e5f6a7b8... -> [0, 1, 0, 0, ...]
f9c0d1e2... -> [0, 0, 1, 0, ...]
... (ещё 99 997)

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

Ribbon filter

Ribbon filter — вероятностная структура, занимающая около двух бит на ключ. Она отвечает на вопрос «может ли этот сегмент содержать значение X?» без false negative и требует всего несколько килобайт для сегмента на 100 тысяч записей.

Для запроса по trace_id executor стал выглядеть так:

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

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

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

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

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

После перехода на ribbon filter значения bitmap(trace_id=X) больше нет, поэтому пересечение невозможно:

allowedIDs = только bitmap(service=api)  // ~20K кандидатов из 100K

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

Posting list

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

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

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

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

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

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

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

Поэтому представление заменили плоским отсортированным slice пар:

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

Итог

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

Ribbon filter отвечает на другой вопрос — «может ли этот сегмент содержать такое значение?» — поэтому он не конкурирует ни с одной из этих структур. Все три сосуществуют в amber, и каждая выполняет работу, которую не могут выполнить две другие.