dmedovich notes: “honey@lab:~$ cat amber/dev-blog/01 🏠Bitmap, ribbon, posting list

honey@lab:~$ cat amber/dev-blog/01

🏠Bitmap, ribbon, posting list — или как усидеть на трёх стульях и получить максимум от поиска и хранения

Когда я добавлял индексы в amber, trace_id попал в bitmap по умолчанию, я понимал что вешать битмапку на высококардинальныe поле в целом затея весьма плохая, но мне было инетерсно насколько(спойлер очень плохо).
Собственно попытался сделать "лучше", потом понял что "лучше" тоже неполное, и сделал правильно.

С чего все начиналось: bitmap на trace_id
Bitmap-индекс хорошо работает для полей с малым числом уникальных значений. Для level с пятью значениями (DEBUG, INFO, WARN, ERROR, FATAL):

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

Пять компактных битмапов, хорошо сжимаются RLE, пересечение двух условий — AND двух битмапов. Дёшево.
Для trace_id ситуация другая. Trace_id — уникальное поле, почти одно значение на запись. Индекс:

a1b2c3d4... -> [1, 0, 0, 0, ...] // один бит на 100К
e5f6a7b8... -> [0, 1, 0, 0, ...]
f9c0d1e2... -> [0, 0, 1, 0, ...]
... (ещё 99 997 таких)

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

✈️Собственно мы тут: ribbon filter

почитать про ribon filter: part1 part2 part3 part4
Ribbon filter — вероятностная структура (~2 бита на ключ). Отвечает на вопрос "есть ли X в этом сегменте?" без false negatives. Занимает несколько килобайт для сегмента в 100K записей.
Для trace_id запроса executor теперь делал так:

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

Ribbon отвечает "нет" — пропускаем сегмент. Ribbon отвечает "возможно да" — сканируем.
Это лучше, чем bitmap. Индексы для 10M записей стали занимать 340 KiB вместо сотен MB. Запросы по trace_id ускорились — большинство сегментов пропускались.

🥴А что сломалось:

Запрос service=api AND trace_id=X до ribbon filter работал через bitmap intersection:

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

После ribbon filter: bitmap(trace_id=X) нет — intersection невозможен.
allowedIDs = только bitmap(service=api) = ~20K кандидатов из 100K.
Скан 20K записей вместо 1.
Для чистых trace_id=X запросов — ribbon + scan работает нормально. Для комбинированных запросов с trace_id — amber потерял пересечение.

💪И куда это нас привело: posting list

Posting list — inverted index для высококардинальных полей. Структура: trace_id --> []record_id.
Если в сегменте 2000 уникальных trace_id и у каждого в среднем 50 записей — это 2000 × 50 × 8 байт = 800 KB. Намного меньше раздутого bitmap.
Теперь lookup для trace_id:

ribbon filter -> пропускаем 99 из 101 сегментов

posting list -> получаем точный список record IDs для этого trace_id

roaring64.And(bitmap(service=api), posting_list(trace_id=X)) -> intersection

Комбинированные запросы снова работают правильно.Posting list хранится в .pidx sidecar рядом с сегментом, строится при запечатывании, загружается lazy через LRU при первом запросе к сегменту.

🚽Детали реализации:

Первый вариант builder использовал map[string][]uint64. Для 100K уникальных trace_id: map overhead (~12 bytes/entry) + string keys (~32 bytes) + slice headers (~32 bytes) = ~7.6 MB на сегмент во время build. Умножить на количество параллельных sealing — GC передаст тебе привет.
Поэтому перешел на flat sorted slice пар (key [16]byte, id uint64):

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

🫰Итог:

Bitmap и posting list отвечают на один и тот же вопрос, но bitmap делает это через битовый вектор длиной N (дорого при высокой кардинальности), posting list — через явный список (дёшево при высокой кардинальности, дорого при низкой).
Ribbon filter отвечает на другой вопрос — и поэтому они не конкуренты, а дополняют друг друга.