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

Коротко. Прунинг сегментов в Amber устроен каскадом: сначала время, затем membership-фильтры, затем точные posting lists или sidecar-проекция, если она может ответить на запрос без чтения основного row store. Ribbon здесь естественный default для точной membership-проверки. CQF добавляет счётчики и изменения структуры, SuRF — prefix и range-семантику. Поскольку сегменты Amber append-only и после seal не меняются, большая часть этих дополнительных возможностей по умолчанию не оправдывает свою стоимость.

Шаг 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
}

Это самый дешёвый этап прунинга: metadata уже лежит в памяти. Никаких фильтров строить не нужно и никакой файл открывать тоже: если временной диапазон сегмента никак не пересекается с запросом, сегмент просто исчезает из множества кандидатов.

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

После времени возникает следующий вопрос: может ли сегмент вообще содержать нужное значение. Какой sidecar index строить, зависит от кардинальности поля.

level, service и host — поля низкой кардинальности, поэтому для них подходят инвертированные bitmap-индексы вроде MultiFieldIndex.

trace_id устроен иначе. Если почти каждый trace ID имеет df = 1, bitmap на каждое значение в основном превращается в overhead. Поэтому Amber может использовать RibbonFilter как дешёвую отрицательную проверку, а затем — точный posting list, если фильтр говорит, что ключ потенциально присутствует.

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
        }
        // ...
    }
}

Та же идея работает для full-text поиска: дешёвая membership-структура может отбросить целый сегмент до того, как executorу понадобится распаковывать и сканировать строки.

Шаг 3: не распаковывать сегмент, если sidecar уже может ответить

Есть и второй тип прунинга: иногда сегмент всё равно придётся посмотреть, но полный row store читать уже не нужно.

Для trace-summary запросов по service, operation или duration у Amber есть CoverIndex (.cidx). Это колоночная, страйдовая проекция нужных полей, хранящаяся в том же отсортированном порядке, что и posting list по service. Благодаря этому executor может посчитать aggregation, не распаковывая основной row store.

Получается такой каскад:

временной диапазон
      ↓
membership filter
      ↓
точный posting / sidecar index
      ↓
row store только если он всё ещё нужен

Один проход на seal для всех sidecar

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

Решение — один проход, который кормит все структуры. Для FTS Ribbon может переиспользовать токены, уже полученные в процессе построения FTS-индекса, вместо повторной токенизации того же текста.

В итоге family sidecar-индексов начинает выглядеть как набор проекций одного seal-прохода, а не как пять независимых потребителей одного и того же CPU и memory bandwidth.

Ribbon Filter

Ribbon здесь — рабочая лошадка, потому что его задача узкая: дешёво ответить на один вопрос — может ли этот ключ вообще присутствовать?

Для append-only sealed segments это очень удобная форма: компактный отрицательный фильтр, которому не нужны delete, update или дальнейшее обслуживание после seal.

У себя я использую Ribbon с небольшой модификацией ширины окна, подстроенной под эту БД. Важна здесь роль, а не конкретный параметр: это дешёвый gate перед точным posting list.

Подробнее: часть первая и часть вторая.

Counting Quotient Filter

CQF идёт дальше Ribbon и Bloom. Membership-фильтр умеет сказать «был» или «не был»; Counting Quotient Filter ещё хранит кратность ключа и допускает вставки и удаления без полной пересборки структуры.

Базовая схема хеширует ключ и делит хеш на quotient и remainder:

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 слотов. Вместо хранения полного хеша в каждом слоте используются служебные биты, которые описывают наличие run для quotient, занятость слота и конец run.

occupied[i] — где-то в массиве есть run для quotient i
used[i]     — слот i занят
runend[i]   — слот i последний в своём run

Если несколько ключей получают один quotient, их remainder физически образуют непрерывный отсортированный run. Lookup проходит по cluster и пропускает целые runs, пока не доберётся до run нужного quotient.

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
}

Относительно статьи я сознательно оставил две упрощённые вещи: три metadata-бита на слот вместо двух битов, получаемых через rank/select в RSQF, и unary-счётчик вместо escape coding. В обоих случаях мы платим частью memory efficiency за более простую реализацию и меньшую поверхность тестов.

Для Amber интереснее другое: CQF мощнее не потому, что лучше фильтрует. Он просто умеет больше. А для immutable sealed segments это может оказаться лишней возможностью. После seal у нас нет постоянных delete/update, поэтому значительная часть CQF-capability может просто не использоваться.

Succinct Range Filter

У Ribbon есть ещё одна жёсткая граница: это membership filter, а не range filter. Никакой бюджет памяти не вернёт исходному ключу лексикографический порядок, если внутри остались только хеши.

SuRF идёт от обратного. Он строит сжатое prefix tree над отсортированным множеством ключей, обрезает ветви, как только ключи уже можно различить, и хранит результат в succinct-представлении. Для topology используется LOUDS, labels рёбер хранятся отдельно, а rank/select позволяют перемещаться по компактному дереву.

За счёт этого SuRF сохраняет то, чего у чистого hash-фильтра нет: достаточно лексикографического порядка, чтобы поддерживать prefix и range-проверки.

Три варианта SuRF

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

SuRF-Hash добавляет к листьям несколько бит хеша полного ключа. Это уменьшает false positives, не сохраняя полный suffix.

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

Иными словами, Ribbon или Bloom теряют порядок ключей, потому что внутри хранят только хеши. SuRF специально сохраняет часть порядка. Поэтому он может обслуживать prefix и range predicates, которые membership-фильтр в принципе выразить не может.

Что на самом деле подходит Amber

Здесь workload важнее списка возможностей.

Сегменты Amber append-only и после seal становятся неизменяемыми. Нам не нужно удалять записи или обновлять фильтр на месте. Это снимает большую часть причин платить за динамические возможности CQF.

Большинство интересующих нас полей — короткие, структурированные ключи умеренной кардинальности, где обычное равенство — основной тип запроса. Для такого профиля Ribbon плюс точный posting list выглядит очень чисто.

SuRF интереснее тем, что добавляет именно семантику, а не просто mutable state. Он становится оправданным, если query layer действительно начинает спрашивать prefix или лексикографические range predicates. До этого момента компактное prefix tree — это плата за возможности, которых никто не использует.

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

Каскад прунинга

                  запрос
                    │
            ┌───────▼───────┐
            │   time range  │
            └───────┬───────┘
                    │
            ┌───────▼───────┐
            │ Ribbon / FTS  │
            │  membership   │
            └───────┬───────┘
                    │
           ┌────────▼────────┐
           │ posting / cidx  │
           │  exact lookup   │
           └────────┬────────┘
                    │
             ┌──────▼──────┐
             │  row store  │
             │ only if    │
             │ necessary   │
             └─────────────┘

Смысл не в том, чтобы накопить все известные индексы. Смысл в том, чтобы поставить сначала самый дешёвый и решающий тест и перестать читать байты сразу, как только ответ уже известен.

Тогда зачем вообще CQF и SuRF?

CQF закрывает ограничение Ribbon «только статическая membership-проверка», добавляя счётчики и изменения. SuRF закрывает ограничение Ribbon «только membership», сохраняя порядок для prefix и range-проверок.

Но ни один из них автоматически не лучше для Amber. Сегменты неизменяемы после seal, а текущему workload в основном нужна точная проверка равенства. Поэтому Ribbon остаётся простым default. CQF и SuRF — это инструменты на случай, если workload вырастет именно в те сценарии, для которых они хороши.

Мне в целом нравится такой принцип для segment pruning: строить минимальный фильтр, который умеет сделать решающий ранний выход, и не платить за семантику, которой query engine никогда не просит.