Плоский инвертированный индекс для нагрузки с высокой кардинальностью

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

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

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

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

У обычного текста и данных наблюдаемости совершенно разное распределение терминов. У текста словарь относительно стабилен, а списки postings длинные. В логах и трассировках встречаются ID запросов и трассировок, IP-адреса, имена атрибутов, сгенерированные пути и значения ошибок. Большая часть таких терминов встречается ровно в одном документе.

Из-за этого важна не только глубина обхода дерева, но и число байтов и аллокаций на уникальный термин. Индекс может быстро искать и всё равно быть дорогим: миллион терминов из одного документа создают миллион массивов и огромный граф объектов в куче.

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

Почему map[string][]Posting — не плоская структура

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

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

Логически всё верно, но при высокой кардинальности физическое представление дорого. Для каждого термина map хранит заголовки строки и среза. Байты термина лежат отдельно. Для каждого непустого списка postings нужен ещё один массив. При росте создаются новые массивы и копируются старые. Сборщику мусора приходится обходить весь граф объектов.

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

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

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

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

Память: арена, записи и цепочки коллизий

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

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

вторичный вид: termOrder[]int32 (создаётся при необходимости)

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

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

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

Первый posting хранится внутри записи

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

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

Это оптимизация для коротких списков: она убирает аллокацию базового массива в самом частом сценарии, сохраняя обычное поведение среза для растущих терминов. Повторные появления в том же документе увеличивают Posting.Count, а не добавляют дублирующие ссылки.

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

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

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

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

Хранение позиций без увеличения каждой записи

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

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

Insert не выделяет память под позиции. InsertAt расширяет таблицу и записывает позицию. Если документ вставлен не по порядку, его список позиций перемещается вместе с posting. Позиции внутри документа тоже отсортированы — сегмент можно экспортировать напрямую.

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

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

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

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

Поиск по префиксу без radix tree

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

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

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

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

Параллельный доступ и неизменяемые сегменты

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

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

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

FLT2: снимок, способный отклонить некорректные данные

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

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

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

Новые снимки используют FLT2; загрузчик по-прежнему принимает снимки FLT1 без позиций. Версионировать формат лучше, чем угадывать, являются ли байты после числа postings позициями или началом следующего термина.

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

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

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

В наборе также есть сценарий с 10 000 терминами высокой кардинальности; параллельные пути запускаются с детектором гонок Go. Тесты sequence повторяют поведение HAMT и radix-реализаций, чтобы сравнивать backend-ы по одному контракту.

Бенчмарки — с обычной оговоркой

Три изменяемых backend-а используют одинаковые синтетические данные: 500 терминов, 500 документов и 20 вхождений на документ. Бенчмарки вставки создают уникальный термин на каждой итерации. Результаты получены на 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
Точный поиск          165–176 ns    171–191 ns         446–455 ns
Поиск по позициям     399–426 ns    403–448 ns         381–412 ns
Поиск по префиксу     159–171 us    172–187 us         —

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

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

Выбор по нагрузке

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

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