Daniil Medovich

Плоский инвертированный индекс для данных высокой кардинальности

EN RU

Коротко. В изменяемом инвертированном индексе для данных высокой кардинальности значительная часть памяти уходит не на сами данные, а на способ их представления. Плоская раскладка уменьшает эти расходы: байты термов лежат в одной arena, метаданные — в индексируемом массиве, первый posting хранится прямо внутри entry, а позиции выделяются только тогда, когда действительно нужны. Точный поиск остаётся хешированным, а префиксный использует небольшой лексикографический индекс, который строится лениво.

Нагрузка определяет устройство индекса

Инвертированный индекс связывает терм с документами, в которых он встречается:

"timeout"       -> [{doc: 4, count: 2}, {doc: 19, count: 1}]
"trace.7f31..." -> [{doc: 9, count: 1}]

Обычный текст и observability-данные дают совершенно разное распределение термов. У естественного языка словарь относительно стабилен, а posting lists часто длинные. В логах и трассировках встречаются request ID, trace ID, IP-адреса, имена атрибутов, сгенерированные пути и тексты ошибок. Значительная часть таких термов присутствует ровно в одном документе.

Из-за этого меняется цель оптимизации. Глубина обхода дерева по-прежнему важна, но не меньше значат байты и аллокации на каждый уникальный терм. Поиск может быть быстрым, а индекс всё равно дорогим, если миллион термов с одним документом создаёт миллион backing arrays и большой граф объектов в куче.

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

Почему map[string][]Posting на самом деле не плоский

Очевидное представление на Go выглядит лаконично:

type Index struct {
    terms map[string][]Posting
}

Логически модель верна, но её физическое представление становится дорогим при высокой кардинальности. Map хранит string header и slice header для каждого терма. Байты строк находятся в отдельном backing storage. Каждому непустому postings slice нужен ещё один массив. При росте появляются новые массивы и копируются старые данные, а сборщик мусора должен обходить весь получившийся граф объектов.

Когда большинство posting lists состоит из одного элемента, инфраструктура slice может стоить столько же, сколько сам posting. Проблема не в асимптотике, а в накладных расходах представления, умноженных на кардинальность термов.

HAMT, radix tree и плоское хранение

Hash array mapped trie делит хеш на небольшие фрагменты и проходит дерево фиксированной глубины. Это даёт предсказуемый точный поиск и хорошо работает с распределением хешей. Sliced radix tree сжимает общие префиксы и естественно поддерживает префиксный обход. Обе раскладки полезны, но обе поддерживают структурные объекты, выгода от которых редко проявляется в exact-heavy нагрузке с высокой кардинальностью.

Плоский индекс следует другому правилу: основное представление должно быть плотным, а вторичные проекции появляются только для тех операций, которым они нужны. Такой индекс не лучше во всех случаях. Он рассчитан на большой набор термов, высокую долю df=1 и append-ориентированную изменяемую фазу.

Раскладка памяти: arena, entries и цепочки коллизий

В индексе пять областей хранения:

                         map[uint64]int32
байты терма -> FNV-1a -> начало цепочки коллизий
                              |
                              v
                    entries[] по int32-индексу
                   +-------------------------+
                   | offset / длина терма    |
                   | первый posting          |
                   | остальные postings      |
                   | следующая коллизия      |
                   +-------------------------+
                         |              |
                         v              v
                  общая byte arena   optional positions[entry]

вторичная проекция: termOrder[]int32 (строится по требованию)

Байты всех термов последовательно добавляются в одну []byte arena. Entry ссылается на терм через 32-битные offset и length. Map для точного поиска хранит 64-битный хеш и 32-битный индекс entry, а не строку и не указатель на отдельный объект терма.

type entry struct {
    first    Posting
    rest     []Posting
    tokenOff uint32
    tokenLen uint32
    next     int32
}

Хеш используется только для маршрутизации. Несколько термов могут иметь одно значение, поэтому map указывает на цепочку коллизий. Каждый кандидат проверяется точным сравнением с исходными байтами в arena. Семантика остаётся точной: коллизия может замедлить lookup, но не может дать ложное совпадение.

Первый posting внутри entry

Первый posting хранится прямо в entry. Slice rest остаётся nil, пока терм не встретится во втором документе:

df = 1  -> entry.first
df = 2  -> entry.first + entry.rest[0]
df = N  -> entry.first + entry.rest[0:N-1]

Это small-object optimization для posting lists. В самом частом high-cardinality случае исчезает аллокация backing array, а для растущих термов сохраняется обычное поведение slice. Повторные вхождения в одном документе увеличивают Posting.Count, а не добавляют дублирующие ссылки на документ.

Упорядоченные postings без сортировки на каждом поиске

Обычно ordinals документов приходят по возрастанию. На этом пути новый документ добавляется через O(1) append, а ещё одно вхождение в текущем документе — через O(1) обновление счётчика.

Библиотечный индекс не может требовать такой порядок от всех вызывающих сторон. Если приходит меньший ordinal, индекс находит его место бинарным поиском. Существующий posting обновляется на месте, новый вставляется в отсортированный slice. Этот холодный путь стоит O(df), потому что при вставке приходится сдвигать элементы, зато цена платится один раз. Search, snapshot и export больше не сортируют одну и ту же posting list повторно.

Значение sequence выводится из ordinal документа, поэтому упорядоченные postings сохраняют стабильный порядок результатов между термами и после сериализации с последующим восстановлением.

Позиции без увеличения каждого entry

Для поиска фраз нужны позиции токенов внутри документа. Поле [][]uint32 в каждом entry добавило бы slice header даже exact-only индексу. Поэтому позиции находятся в отдельной параллельной таблице, которая растёт только до тех entries, где они действительно используются:

entries[42]        -> postings для "timeout"
positions[42][0]  -> позиции в первом документе
positions[42][1]  -> позиции во втором документе

Insert никогда не выделяет positional metadata. InsertAt расширяет таблицу и записывает позицию. При out-of-order вставке список позиций перемещается вместе со своим posting. Позиции внутри документа тоже остаются отсортированными, поэтому те же данные можно сразу экспортировать в sealed segment.

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

Точный поиск остаётся простым

Точный поиск состоит из четырёх шагов:

  1. Вычислить хеш искомого терма.
  2. Прочитать начало цепочки коллизий из map[uint64]int32.
  3. Сравнить байты запроса с байтами каждого кандидата в arena.
  4. Вернуть копию уже упорядоченных postings.

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

Префиксный поиск без префиксного дерева

У плоского хеш-индекса нет естественного префиксного обхода. Можно проверять каждый терм при каждом запросе, но это игнорирует возможность один раз упорядочить байты термов и затем переиспользовать результат.

Вторичная проекция termOrder содержит только 32-битные индексы entries, отсортированные по байтам в arena. Она лениво строится при первом префиксном поиске, сериализации или экспорте сегмента. Новый терм неявно инвалидирует проекцию: её длина перестаёт совпадать с массивом entries.

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

termOrder: api, apple, apply, trace, tracing
запрос:    "app"
                 ^ lower bound
совпали:  apple, apply
стоп:                 trace

Postings совпавших термов объединяются по ordinal документа, а их счётчики складываются. Первый запрос после появления новых термов платит за сортировку, последующие используют готовую проекцию. Это не превращает плоский индекс в radix tree: структура radix tree по-прежнему лучше приспособлена к нагрузке, в которой преобладают префиксные запросы. Вторичная проекция — компактный компромисс для смешанного профиля.

Конкурентный доступ и неизменяемые сегменты

Изменяемый индекс использует RWMutex. Вставки берут write lock, точный и позиционный поиск — read lock. Перестроение termOrder ненадолго захватывает write lock, после чего префиксный поиск продолжается под read lock.

Экспорт сегмента тоже работает с лексикографической проекцией под read lock. Callback получает байты терма, упорядоченные postings и копии списков позиций из одного согласованного состояния. Записывающие операции ждут завершения экспорта, поэтому sealing не может увидеть половину вставки.

Так появляется полезная граница жизненного цикла: flat index оптимизирован для построения и запросов к активному изменяемому набору, а sealed segment отвечает за компактное представление только для чтения, контрольные суммы и file-backed режимы доступа.

FLT2: snapshot, способный отвергнуть плохие данные

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

magic "FLT2"
число термов
для каждого терма:
    длина токена
    байты токена
    число postings
    для каждого posting:
        delta-encoded ordinal документа
        частота терма
        число позиций
        позиции
CRC32

Термы записываются лексикографически, postings — по ordinal. Delta encoding делает типичные промежутки между ordinals короткими. Перед публикацией индекса loader проверяет общий размер snapshot, число термов, длину токена, число postings, границы целых чисел, строгий порядок ordinals, порядок позиций, дубликаты термов, лишние байты в конце и контрольную сумму.

Новые snapshots используют FLT2, но loader продолжает читать FLT1 без позиций. Версионирование формата надёжнее попытки угадать, являются ли байты после posting count позициями или началом следующего терма.

Тесты должны описывать инварианты

Одних feature tests для индекса недостаточно. Важны отношения между данными, которые должны сохраняться на любом пути выполнения:

  • ordinals в postings остаются строго упорядоченными при любом порядке вставки;
  • изменение частоты терма не меняет sequence;
  • positions остаются выровненными с postings при вставке и сериализации;
  • перестроенная префиксная проекция включает термы, добавленные после прошлого запроса;
  • конкурентные префиксные запросы и вставки видят согласованные snapshots;
  • изменяемый snapshot и sealed segment возвращают одинаковые postings;
  • неверные контрольные суммы и некорректные длины приводят к ошибке, а не к частичному результату.

В наборе также есть high-cardinality сценарий с 10 000 термов, а конкурентные пути запускаются под race detector Go. Sequence-тесты повторяют проверки HAMT и radix-реализаций, чтобы все реализации сравнивались по одному поведенческому контракту.

Бенчмарки и обычная оговорка

Три изменяемых индекса используют один синтетический набор: 500 термов, 500 документов и 20 вхождений на документ. Insert-бенчмарки создают уникальный терм на каждой итерации. Результаты ниже получены на AMD Ryzen 5 2600 с Go 1.26.4:

операция              flat          sliced radix       HAMT
Insert                692-709 ns    949-1068 ns        1161-1359 ns
InsertAt              917-999 ns    1037-1151 ns       1079-1207 ns
Точный Search         165-176 ns    171-191 ns         446-455 ns
Позиционный Search    399-426 ns    403-448 ns         381-412 ns
Префиксный Search     159-171 us    172-187 us         -

При вставке уникальных термов flat index использовал 419–485 байт и две аллокации на операцию. Sliced radix использовал 579–638 байт и три аллокации, HAMT — 589–661 байт и шесть аллокаций.

Это микробенчмарки, а не рейтинг для любого набора данных. Они прежде всего показывают, что префиксный и позиционный поиск удалось добавить без отказа от компактного exact-path. Настоящий выбор должен учитывать распределение словаря приложения, длины posting lists, долю префиксных запросов, частоту sealing и профиль памяти.

Выбор по профилю нагрузки

Плоская раскладка хорошо подходит активному индексу с большим числом уникальных термов, преобладанием точного поиска, добавлением документов преимущественно по возрастанию ordinals и периодическим sealing. Radix tree остаётся привлекательным, когда префиксный обход — основная операция, а общих префиксов много. HAMT полезен там, где нагрузке соответствуют хеш-разбиение и фиксированная схема обхода.

Главный вывод шире конкретной реализации: индекс — это не только алгоритм поиска. Раскладка памяти определяет количество объектов, соседство байтов в линиях кэша, объём работы сборщика мусора и цену перехода от изменяемого состояния к неизменяемому сегменту. При высокой кардинальности эти свойства становятся частью алгоритма.