Отсечение сегментов в Amber: Ribbon, CQF и SuRF

Кратко. Отсечение сегментов в Amber происходит каскадом: сначала по времени, затем фильтрами принадлежности, потом точными postings или боковой проекцией, если она позволяет ответить на запрос без чтения хранилища строк. Ribbon — естественный вариант по умолчанию для проверки наличия ключа. CQF добавляет подсчёт кратности и обновления, SuRF — семантику префиксов и диапазонов. Сегменты Amber только дополняются и запечатываются один раз, поэтому дополнительные возможности обычно не оправдывают свою цену.

Шаг 1: отсечь по времени

SparseIndex хранит [MinTS, MaxTS] для каждого сегмента. Запрос с временными границами может отбросить все сегменты, которые не пересекают нужный интервал, ещё до открытия файлов индексов.

// Lookup возвращает сегменты, диапазон которых пересекается с [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
}

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

Шаг 2: проверить наличие значения в поле

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

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

С trace_id иначе. Если у большинства trace ID df = 1, bitmap на каждое значение — в основном накладные расходы. Вместо него 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
        }
        // ...
    }
}

Тот же принцип работает для полнотекстового поиска: дешёвые структуры принадлежности могут отбрасывать целые сегменты, прежде чем исполнителю придётся распаковывать и сканировать строки.

Шаг 3: не распаковывать данные, если ответит боковой индекс

Есть и второй вид отсечения: сегмент точно нужно прочитать, но всё хранилище строк читать необязательно.

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

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

временной диапазон
    ↓
фильтр принадлежности
    ↓
точный posting / боковой индекс
    ↓
хранилище строк, только если необходимо

Один проход запечатывания для всех sidecar-индексов

Все эти боковые индексы строятся при запечатывании сегмента. Изначально Bitmap, FTS, Ribbon и FTSRibbon строились отдельными проходами по одним данным. Несколько независимых декодирований сегмента, особенно повторная токенизация и стемминг для FTS, начали конкурировать с приёмом данных.

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

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

Ribbon Filter

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

Для дополняемых и затем запечатанных сегментов это подходящая форма: компактный фильтр с отрицательными ответами, без удаления, обновления и необходимости поддерживать изменяемую структуру после запечатывания.

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

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

Counting Quotient Filter

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

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

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

occupied[i] — существует серия для частного i
used[i]     — слот i содержит остаток
runend[i]   — слот i завершает серию

Если у нескольких ключей одинаковое частное, их остатки образуют непрерывную отсортированную серию. Поиск проходит по кластеру и пропускает целые серии, пока не дойдёт до серии нужного частного.

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
}

Я сознательно упростил две детали относительно статьи: использую три бита метаданных на слот вместо двух битов с rank/select в RSQF и унарный счётчик вместо escape-кодирования. Оба решения немного ухудшают эффективность по памяти, но упрощают реализацию и тестирование.

Для Amber важно не столько то, что CQF мощнее. Возможно, дополнительные возможности просто не нужны запечатанным сегментам. После запечатывания нет постоянной нагрузки на удаление и обновление, поэтому изменяемая часть CQF в основном оказывается избыточной, если будущая задача действительно не потребует её.

Succinct Range Filter

У Ribbon есть ещё одно ограничение: это фильтр принадлежности, а не диапазоновый фильтр. Как ни настраивай бюджет памяти, исходный порядок ключей он не сохраняет.

SuRF устроен иначе. Он строит сжатое префиксное дерево по отсортированному набору ключей, обрезает ветви, как только ключи становятся различимыми, и хранит дерево в компактном представлении. LOUDS кодирует структуру, метки хранятся отдельно, а операции rank/select используются для навигации.

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

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

SuRF-Base хранит только усечённое дерево. Он экономичен, но вероятность ложных совпадений при проверке принадлежности зависит от места усечения дерева.

SuRF-Hash хранит в листьях несколько дополнительных битов хеша. Это снижает число ложных совпадений, не сохраняя полный суффикс.

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

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

Что подходит Amber?

Здесь рабочая нагрузка важнее списка возможностей.

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

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

SuRF интереснее тем, что добавляет семантику запросов, а не только изменяемость. Его сложность оправдается, если слой запросов начнёт поддерживать префиксные условия или лексикографические диапазоны. Пока этого нет, держать компактное trie «на всякий случай» — значит платить за невостребованные возможности.

Для FTS я пока оставляю вопрос открытым. Полнотекстовый поиск работает с токенами, а не с исходным лексикографическим пространством ключей, поэтому неочевидно, даст ли порядок SuRF что-то полезное. Возможно, но пока нет запроса, который это оправдывает.

Каскад отсечения

                 запрос
                   │
           ┌───────▼───────┐
           │ временной диапазон │
           └───────┬───────┘
                   │
           ┌───────▼───────┐
           │ Ribbon / FTS   │
           │ принадлежность │
           └───────┬───────┘
                   │
          ┌────────▼────────┐
          │ posting / cidx  │
          │ точный поиск    │
          └────────┬────────┘
                   │
            ┌──────▼──────┐
            │ хранилище   │
            │ строк — если│
            │ необходимо  │
            └─────────────┘

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

Зачем тогда CQF и SuRF?

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

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

Для отсечения сегментов в целом я придерживаюсь такого принципа: строить минимальный фильтр, который позволяет уверенно отсеять данные, и не платить за семантику, которую движок запросов не использует.