Learning index still cooking...
Во время бенчмарков и профилирования Amber я много перебираю индексов, иногда даже
приходится делать свои — писал об этом тут.
И в какой-то момент я наткнулся на
learned index,
и он меня впечатлил. Идея простая и красивая: вместо того чтобы городить дерево или хэш
поверх отсортированных ключей, ты смотришь на пары (ключ, позиция) как на точки на графике
и аппроксимируешь их функцией — линейной, кусочно-линейной или вовсе прикрутить маленькую
LLM. По сути весь индекс сжимается в пару коэффициентов, а lookup превращается в вычисление
f(key) ≈ position вместо обхода структуры данных. Модель почти никогда не
угадывает позицию идеально, поэтому сразу за предсказанием идёт короткий уточняющий поиск
в окрестности. По сути индекс из структуры превращается в функцию.
И конечно я сразу решился на эксперимент и добавить такой индекс в Amber — вместо или в пару к уже устоявшемуся бинарному интервальному индексу. Идея интересная, но по факту learning index не столько побеждает бинарный поиск, сколько выходит с ним на паритет — на части датасетов чуть быстрее, на части чуть медленнее, местами в пределах шума измерений. А вот за что приходится реально платить — так это за стоимость построения: она у learning index стабильно самая высокая из всех кандидатов, местами вдвое дороже бинарного индекса. Так что за примерно тот же lookup ты переплачиваешь построением — и пока эта плата не отбивается, индекс still «cooking».
Вопрос
Чего мы ждём от неизменяемого индекса над диапазонами времени запечатанных сегментов?
Правильный ответ — отвечать всего на один вопрос: «какие сегменты пересекаются с
[from, to)», и желательно быстро. Текущая реализация в Amber сканирует все
сегменты и сортирует совпадения — корректно, но линейно по их числу. Так что рассмотрим
кандидатов, обещающих сублинейный поиск:
Первый — точный бинарный интервальный поиск по сегментам, отсортированным по
MinTS, с монотонным префиксным максимумом MaxTS.
И второй, наш сегодняшний герой — ограниченная кусочно-линейная ранговая модель по
мотивам PGM-index и RadixSpline, которая предсказывает коридор поиска и уточняет его
точным поиском нижней границы. Далее именуемый как piecewise_linear.
Методология эксперимента следует наставлениям и предостережениям из статьи выше (увлекательное чтиво, рекомендую): поиск и уточнение позиции измеряются раздельно, стоимость построения и размер индекса учитываются отдельно, разные формы CDF прогоняются раздельно, стоимость скана диапазона не путается со стоимостью поиска границы.
Гарантия корректности
Оба наших кандидата обязаны отдавать ровно те же ID сегментов, что и линейный скан, при
любом порядке вставки, дубликатах таймстампов, разрывах, перекрытиях и границах
int64. Для learned-модели это работает так: модель предсказывает только
ограниченный коридор поиска, а точный поиск нижней границы его уточняет. Если инвариант
коридора когда-либо нарушается, реализация откатывается на глобальный бинарный поиск.
Значит, ошибка модели может стоить времени, но не может потерять совпадающий сегмент.
Эксперимент прошёл:
- полную матрицу из 45 кейсов с 59 610 oracle-запросами;
- детерминированные тесты на дубликаты таймстампов, разрывы, перекрытия, перемешанный порядок вставки и границы
int64; - рандомизированные тесты на перекрывающихся интервалах;
- Go fuzz-таргет, чей seed corpus гоняется в обычном test suite.
Отдельная fuzz-кампания выполнила 240 412 прогонов без единого расхождения. Во всей матрице — ноль откатов learned-поиска на бинарный.
Датасеты и нагрузка
Каждый датасет детерминирован и генерируется на 10k, 100k и 1M сегментов:
| Датасет | Что моделирует |
|---|---|
monotonic | гладкая CDF таймстампов |
bursty | плотные всплески, резкие маленькие и большие разрывы, переменная ширина |
gaps | регулярные большие «дыры» во времени событий |
late_arrivals | старые таймстампы и длинные перекрывающиеся интервалы сегментов |
out_of_order | монотонное время события, вставленное в перемешанном порядке |
Микс запросов: 60% точечных/узких попаданий, 25% диапазонов до 32 стартов сегментов,
10% запросов вокруг разрывов, 5% промахов. out_of_order намеренно даёт то же
распределение запросов после сортировки, что и monotonic — это изолирует
стоимость сортировки при bulk-построении.
Бинарный интервальный индекс сортирует по MinTS и хранит и MinTS,
и монотонный префиксный максимум MaxTS. Он находит безопасное окно:
lo = lower_bound(prefixMax, query.From)
hi = upper_bound(minTS, query.To)
Каждый интервал в [lo, hi) затем проверяется точно. Длинные перекрывающиеся
интервалы из late_arrivals могут расширить это окно, но не могут породить
ложноотрицательный результат.
Результаты
Таблица ниже — медиана трёх Go-бенчмарков с фиксированным числом итераций на 1M сегментов. Это сравнение для операций суб-микросекундного масштаба; меньше — лучше.
| Датасет | Линейный скан | Бинарный интервальный | Кусочно-линейный | Learned vs binary |
|---|---|---|---|---|
| monotonic | 8 338 µs | 0.703 µs | 0.327 µs | быстрее в 2.15× |
| bursty | 8 290 µs | 1.074 µs | 1.169 µs | медленнее в 1.09× |
| gaps | 8 342 µs | 0.738 µs | 0.329 µs | быстрее в 2.24× |
| late arrivals | 8 264 µs | 166.636 µs | 168.748 µs | медленнее в 1.01× |
| out of order | 8 344 µs | 0.693 µs | 0.495 µs | быстрее в 1.40× |
Модель и правда ускоряет сам поиск границы: 84–133 нс против 130–165 нс у бинарного
поиска на 1M ключей. На гладких распределениях (monotonic, gaps, out_of_order) это
чувствуется в итоговом lookup — быстрее в 1.4–2.24×. На bursty и
late_arrivals преимущество исчезает — но здесь результаты в пределах шума
измерений. Так что на этих двух датасетах — паритет
Амплификация числа кандидатов на скан объясняет результат late_arrivals:
| Датасет | 10k сегментов | 100k сегментов | 1M сегментов |
|---|---|---|---|
| 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 |
Бинарный и learned-варианты сканируют ровно одно и то же безопасное окно. Другой
предиктор не решит амплификацию на late_arrivals — для этого нужна другая
структура данных для интервалов или более узкие временные диапазоны сегментов.
Стоимость построения и размер индекса
На 1M сегментов медианное время холодного построения:
| Датасет | Клон для линейного | Бинарный интервальный | Кусочно-линейный |
|---|---|---|---|
| monotonic | 7.26 ms | 17.15 ms | 39.33 ms |
| bursty | 7.11 ms | 18.79 ms | 38.18 ms |
| gaps | 7.26 ms | 17.03 ms | 42.61 ms |
| late arrivals | 7.72 ms | 167.98 ms | 176.54 ms |
| out of order | 7.77 ms | 258.55 ms | 283.51 ms |
Общий массив диапазонов оценивается в 40 байт на сегмент. Метаданные бинарного интервального индекса добавляют 16 байт на сегмент. Learned-прототип добавляет сверх этого ещё около 0.22–0.44 байта на сегмент под свои модели.
Вывод
Особого выигрыша мы не получили: по lookup в лучшем случае паритет, местами — прямо в пределах шума измерений. А вот с построением всё однозначно: learned- модель строится дороже бинарного индекса на каждом датасете без исключений, а на гладких данных — вообще в 2–2.5 раза. Для нашего кейса это пока не имеет смысла — переплачивать за построение ради индекса, который просто не хуже соседа. Но поэкспериментировать было интересно, идея того стоила. Кто знает, может в будущем мы еще вернемся к нему...