Во время бенчмарков и профилирования amber я перебираю много индексов и иногда строю собственные — об одном я уже писал. В какой-то момент я наткнулся на так называемый обучаемый индекс, и идея меня впечатлила. Она проста и элегантна: вместо дерева или хеша поверх отсортированных ключей мы рассматриваем пары (ключ, позиция) как точки на графике и подбираем функцию — линейную, кусочно-линейную или даже небольшой LLM. Индекс сжимается до нескольких коэффициентов, а поиск сводится к вычислению f(key) ≈ position вместо обхода структуры данных. Модель почти никогда не угадывает точную позицию, поэтому за предсказанием следует короткий локальный поиск. По сути, индекс превращается из структуры в функцию.
Я сразу решил проверить идею и добавил такой индекс в amber вместо существующего бинарного индекса диапазонов или рядом с ним. На практике обучаемый индекс не столько выигрывает у бинарного поиска, сколько идёт с ним вровень: немного быстрее на одних данных, немного медленнее на других, а часть разницы укладывается в погрешность измерений. Платить приходится за построение: среди кандидатов оно стабильно самое дорогое, иногда вдвое дороже бинарного индекса. При примерно одинаковой скорости поиска мы переплачиваем на этапе построения — пока эта стоимость не снизится, индекс ещё «готовится».
Задача
Что должен делать неизменяемый индекс временных диапазонов запечатанных сегментов? Правильный ответ — быстро и точно отвечать на один вопрос: «какие сегменты пересекаются с [from, to)». Текущая реализация amber просматривает все сегменты и сортирует совпадения — корректно, но линейно по их числу.
Рассмотрим два варианта с поиском быстрее линейного. Первый — точный бинарный поиск по сегментам, отсортированным по MinTS, с монотонным префиксным максимумом MaxTS. Второй, главный герой статьи, — ограниченная кусочно-линейная модель ранга в духе PGM-index и RadixSpline. Она предсказывает коридор поиска, который уточняется точным поиском нижней границы. Далее будем называть её piecewise_linear.
Методика эксперимента учитывает предостережения из статьи (очень увлекательное чтение, рекомендую): поиск и уточнение позиции измеряются отдельно, стоимость построения и размер индекса учитываются отдельно, разные формы CDF тестируются раздельно, а стоимость сканирования диапазона не смешивается со стоимостью поиска границ.
Гарантия корректности
Оба варианта должны возвращать ровно те же ID сегментов, что и линейное сканирование, независимо от порядка вставки, повторяющихся временных меток, пропусков, пересечений и границ int64. Для обучаемой модели схема такая: модель предсказывает только ограниченный коридор поиска, затем точный поиск нижней границы его уточняет. Если инвариант коридора нарушен, реализация переходит к глобальному бинарному поиску. Ошибка модели может увеличить время работы, но никогда не потеряет подходящий сегмент.
Эксперимент прошёл:
- полную матрицу из 45 сценариев с 59 610 эталонными запросами;
- детерминированные тесты на повторяющихся метках, пропусках, пересечениях, перемешанном порядке вставки и границах
int64; - случайные тесты на пересекающихся интервалах;
- Go fuzz-тест, начальные примеры которого входят в обычный набор тестов.
Отдельная кампания fuzzing выполнила 240 412 запусков без единого расхождения. Во всей матрице не было ни одного перехода от обучаемого поиска к бинарному.
Данные и нагрузка
Каждый детерминированный набор генерируется для 10 тысяч, 100 тысяч и 1 млн сегментов:
| Набор | Назначение |
|---|---|
monotonic | гладкая CDF временных меток |
bursty | плотные всплески, резкие малые и большие пропуски, переменная ширина |
gaps | регулярные большие пропуски во времени событий |
late_arrivals | старые временные метки и длинные пересекающиеся интервалы сегментов |
out_of_order | монотонное время событий, вставленное в перемешанном порядке |
Состав запросов: 60% точечных или узких попаданий, 25% диапазонов длиной до 32 начал сегментов, 10% запросов рядом с пропусками и 5% промахов. У out_of_order распределение после сортировки такое же, как у monotonic; это позволяет отдельно измерить стоимость сортировки при пакетном построении.
Бинарный индекс интервалов сортирует сегменты по MinTS и хранит MinTS вместе с монотонным префиксным максимумом MaxTS. Он находит безопасное окно:
lo = lower_bound(prefixMax, query.From)
hi = upper_bound(minTS, query.To)Затем каждый интервал в [lo, hi) проверяется точно. Длинные перекрывающиеся интервалы из late_arrivals могут расширить окно, но не приведут к пропуску результатов.
Результаты
Таблица показывает медиану трёх Go-бенчмарков с фиксированным числом итераций для 1 млн сегментов. Это сравнение операций длительностью меньше микросекунды; меньше — лучше.
| Набор | Линейный проход | Бинарный интервал | Кусочно-линейный | Обучаемый против бинарного |
|---|---|---|---|---|
| monotonic | 8 338 мкс | 0,703 мкс | 0,327 мкс | в 2,15 раза быстрее |
| bursty | 8 290 мкс | 1,074 мкс | 1,169 мкс | в 1,09 раза медленнее |
| gaps | 8 342 мкс | 0,738 мкс | 0,329 мкс | в 2,24 раза быстрее |
| late arrivals | 8 264 мкс | 166,636 мкс | 168,748 мкс | в 1,01 раза медленнее |
| out of order | 8 344 мкс | 0,693 мкс | 0,495 мкс | в 1,40 раза быстрее |
Сама модель ускоряет поиск границы: 84–133 нс против 130–165 нс у бинарного поиска на 1 млн ключей. На гладких распределениях (monotonic, gaps, out_of_order) это даёт ускорение полного поиска в 1,4–2,24 раза. На bursty и late_arrivals преимущество исчезает, но результаты находятся в пределах погрешности измерений — на этих наборах можно говорить о паритете.
Результат late_arrivals объясняется усилением сканирования кандидатов:
| Набор | 10 тыс. | 100 тыс. | 1 млн |
|---|---|---|---|
| monotonic | 5,16 | 5,08 | 4,81 |
| bursty | 24,62 | 24,67 | 24,44 |
| gaps | 5,16 | 5,08 | 4,81 |
| late arrivals | 4 726,17 | 12 130,82 | 11 963,00 |
| out of order | 5,16 | 5,08 | 4,81 |
Бинарный и обучаемый варианты сканируют одно и то же безопасное окно. Другой предсказатель не устранит усиление на late_arrivals — для этого нужна иная структура интервалов или более узкие временные диапазоны сегментов.
Стоимость построения и размер индекса
Медианное холодное построение для 1 млн сегментов:
| Набор | Копирование для линейного поиска | Бинарный интервал | Кусочно-линейный |
|---|---|---|---|
| monotonic | 7,26 мс | 17,15 мс | 39,33 мс |
| bursty | 7,11 мс | 18,79 мс | 38,18 мс |
| gaps | 7,26 мс | 17,03 мс | 42,61 мс |
| late arrivals | 7,72 мс | 167,98 мс | 176,54 мс |
| out of order | 7,77 мс | 258,55 мс | 283,51 мс |
Общий массив диапазонов занимает примерно 40 байт на сегмент. Метаданные бинарного индекса добавляют 16 байт на сегмент. Прототип обучаемого индекса добавляет поверх этого ещё примерно 0,22–0,44 байта на сегмент для моделей.
Вывод
Выигрыш оказался небольшим: поиск в лучшем случае на уровне бинарного, а в паре случаев разница уверенно укладывается в погрешность измерения. Со стоимостью построения всё однозначно: обучаемая модель на каждом наборе строится медленнее бинарного индекса, без исключений, а на гладких данных — в 2–2,5 раза медленнее. Для нашей задачи это пока не оправдано: переплачивать за построение ради индекса, который лишь не хуже соседнего, — плохой компромисс. Но эксперимент был интересным, и идея того заслуживает. Может быть, мы ещё к ней вернёмся.