Прунинг сегментов в Amber: Ribbon, CQF и SuRF 😴

Хватит пока с нас индексов — поговорим немного о фильтрах и о том, где и как они позволяют отсекать максимум сегментов до полного скана.

Сегменты у нас append-only и запечатываются один раз. Запрос проходит по ним каскадом: на каждом шаге можно отсечь сегмент целиком.

Step 1: отсечение по времени

SparseIndex хранит для каждого сегмента [MinTS, MaxTS]. Time-bounded-запрос отсечёт всё, что не пересекается по времени, ещё до открытия индексного файла — достаточно простой проверки метаданных в памяти:

// Lookup returns the segments whose span overlaps [from, to].
func (s *SparseIndex) Lookup(from, to int64) []SegmentTimeRange {
    result := make([]SegmentTimeRange, 0)
    for _, r := range s.ranges {
        if r.MaxTS < from || r.MinTS > to {
            continue // сегмент вне диапазона — пропускаем
        }
        result = append(result, r)
    }
    return result
}

Step 2: membership-проверка по полю

Здесь уже подключаются sidecar-индексы, а то, какие именно индексы будут построены, зависит от кардинальности поля. level, service, host — поля низкой кардинальности, представленные инвертированными битмапами (MultiFieldIndex).

А вот trace_id из битмапа был исключён. Узнать о причинах можно тут, но если в двух словах: почти каждый trace_id имеет df = 1, а значит, хранить битмап для каждого trace_id попросту невыгодно. Вместо этого используются RibbonFilter и posting list для точных ID, если фильтр вернул ложноположительный результат.

В executor это выглядит как цепочка ранних выходов:

if !model.IsZeroTraceID(q.TraceID) {
    if ribbon, ok := e.logRibbon(seg.FileName); ok {
        if !ribbon.Contains(q.TraceID[:]) {
            return 0, nil // сегмент целиком мимо, дальше не читаем
        }
    }
    if pl, ok := e.logPosting(seg.FileName); ok {
        ids := pl.Lookup(q.TraceID[:])
        if len(ids) == 0 {
            return 0, nil
        }
        // ...
    }
}

Для токенов FTS работает тот же принцип.

Step 3: пропустить декомпрессию там, где сегмент всё равно придётся читать

Зачем читать то, что мы всё равно будем читать при совпадении? Давайте просто пропустим этот этап.

Для trace-summary-запросов (service / operation / duration) есть CoverIndex (.cidx) — колоночная, страйдовая проекция нужных полей в том же отсортированном порядке, что и posting list по service. Она отвечает на агрегирующий запрос без обращения к основному row store.

Все эти sidecar-индексы строятся за один проход при запечатывании сегмента. Изначально Bitmap, FTS, Ribbon и FTSRibbon строились каждый своим отдельным сканом. При пяти независимых декодированиях одних и тех же данных (и особенно при двойных токенизации и стемминге для FTS) это стало узким местом: seal не успевал за ingest.

Сейчас один проход кормит все индексы сразу, а Ribbon для FTS переиспользует токены непосредственно из состояния построения FTS-индекса, без повторной токенизации.

Ribbon Filter

Про Ribbon можно почитать подробнее тут и тут. Тем более что именно его, с небольшой модификацией, я и использую у себя в БД (подкрутил ширину окна — just for my case).

Counting Quotient Filter (CQF)

Ribbon и Bloom по сути умеют только одно: сказать, встречался ключ или нет. CQF идёт чуть дальше — он добавляет счётчик кратности ключа. А еще можно добавлять и удалять записи без полной пересборки.

В чём идея: ключ хешируется и режется на две части — quotient (q бит, индекс слота в массиве) и remainder (r бит, то, что реально хранится в этом слоте):

func (qf *CountingQF) split(key []byte) (q0, r0 uint64) {
    h := hashKey(key) & maskBits(qf.q+qf.r)
    return h >> qf.r, h & maskBits(qf.r)
}

Дальше — массив слотов размером 2^q, и на каждый слот три метабита вместо привычных Bloom-битов:
- occupied[i] — у quotient i где-то в массиве есть свой run;
- used[i] — слот i физически занят;
- runend[i] — слот i последний в своём run.

При коллизии по q (два разных ключа попали в один и тот же i) элементы физически сдвигаются вправо, формируя непрерывный run — отсортированный по r участок массива:

func (qf *CountingQF) locate(qIdx uint64) uint64 {
    if !qf.isUsed(qIdx) {
        return qIdx
    }
    start := qf.findClusterStart(qIdx)
    runsBefore := 0
    for k := start; k < qIdx; k++ {
        if qf.isOccupied(k) {
            runsBefore++
        }
    }
    pos := start
    for runsBefore > 0 {
        for !qf.isRunEnd(pos) {
            pos++
        }
        pos++
        runsBefore--
    }
    return pos
}

locate считает, сколько занятых q находится перед искомым внутри кластера, и проходит мимо ровно такого количества run. Отсюда и требование: run физически никогда не может оказаться левее своего канонического индекса. Иначе locate его просто не найдёт — он ищет только вправо.

Реализовал CQF с двумя упрощениями относительно статьи три метабита на слот вместо двух битов, получаемых через rank/select в RSQF, unary-счётчик вместо escape-кодирования.
В обоих случаях гарантии сохраняютс, структура получается немного дороже по памяти, но проще в реализации и тестах. И если с основными операциями проблем не возникло, то вот с Delete пришлость повозиться, ибо руки из жопы

Succinct Range Filter (SuRF)

Второе ограничение Ribbon — точное совпадение, prefix-поиск отсутствует. Поэтому рассмотрим еще и структуру, которая обещает range-фильтрацию почти по цене обычного membership-фильтра.

SuRF — это сжатое префиксное дерево над отсортированным множеством ключей, усечённое до минимально необходимой глубины.

В чём идея:
- Строим обычный trie по байтам ключей.
- Урезаем каждую ветку в точке, где ключ уже однозначно отличим от соседних: дальше можно ничего не хранить, оставшийся хвост ключа для membership-проверки не нужен.
- Кодируем получившееся дерево в succinct-представлении. Для структуры дерева используем битовые последовательности LOUDS, а метки рёбер храним отдельно — по одному байту на символ. Дальше rank/select позволяют быстро перемещаться по этой компактной структуре.

По памяти получается порядка 10! бит на узел в зависимости от конфигурации, вместо десятков байт на узел в обычном trie с указателями. ! - размер сильно зависит от глубины усечения и того как именно у вас хранятся labels и доп суффикс/хэш биты

Дальше есть три варианта:
SuRF-Base — просто усечённое дерево, без дополнительных гарантий для точечных запросов. Дешёвый вариант, но false positive rate при membership-проверке зависит от того, насколько глубоко пришлось урезать дерево.

SuRF-Hash — добавляет к каждому листу несколько бит хеша полного ключа, чтобы довести false positive rate до нужного уровня для точечных запросов. По сути, это замена Bloom/Ribbon-фильтру.

SuRF-Real — вместо хеша хранит реальные оставшиеся байты ключа. Что делает возможными range-запросы типа: («все ключи между X и Y»), а не только membership-проверку.

У обычного Bloom/Ribbon-фильтра ключи представлены только хешами: порядок и структура исходного ключа полностью теряются. SuRF сохраняет порядок — а значит, в теории может быть одновременно и компактным (как Ribbon), и полезным для диапазонных и префиксных запросов, чего Ribbon не может в принципе, ни при каком бюджете памяти.

Итог:🛑

CQF добавляет возможность менять фильтр после построения.
SuRF добавляет поддержку prefix- и range-запросов. Оба закрывают ограничения Ribbon.

Но для нас это не то чтобы проблема. В Amber сегменты append-only и запечатываются один раз, поэтому после построения их уже не нужно менять. А большая часть полей — короткие структурированные ключи умеренной кардинальности, где точного совпадения вполне достаточно.

Оба фильтра — тяжёлые и сложные, и оба платят за возможности, которых у Ribbon нет, но которые нам, по-хорошему, не особо то и нужны. Возможно SuRF сможет подружиться с FTS, ибо последний работает с токенами, а не с лексикографическим порядком исходных ключей, но пока такого запроса нет, но карандашиком запишу😶‍🌫️😶‍🌫️