5 шокирующих решений, которые сделали OLAP‑базу Frigatebird в 10 раз быстрее — как и почему?

Вступление

В последние годы аналитические базы данных (OLAP) становятся всё более востребованными: от бизнес‑аналитики до машинного обучения. Однако традиционные подходы к их реализации часто «залипают» в привычных паттернах, которые изначально были придуманы для веб‑сервисов, а не для тяжёлых вычислений над гигабайтами колонок. На Reddit появился пост, где автор поделился своим опытом создания ядра новой OLAP‑базы Frigatebird с нуля. Он отказался от привычного async/await и от стандартных системных вызовов, заменив их собственным рантаймом, io_uring‑батчингом, спин‑локами и zero‑copy сериализацией. В статье мы разберём, почему эти «неортодоксальные» решения работают, какие плюсы и минусы они несут, и как их можно применить в собственных проектах.

Тихий ветер над полем,
Тени строк летят ввысь —
Код без ожиданий.

Пересказ Reddit‑поста своими словами

Автор недавно выпустил ядро Frigatebird — колонковую OLAP‑базу, написанную полностью на Rust. При разработке он столкнулся с тем, что стандартные инструменты Rust (например, Tokio) оптимизированы под ввод‑вывод, где большинство задач простаивают в ожидании сети. В аналитических запросах же большую часть времени занимает процессор: сканирование сжатых страниц, фильтрация, агрегация.

Он принял несколько радикальных решений:

1. Отказ от async/await и Tokio. Вместо общего асинхронного планировщика он внедрил модель morsel‑driven parallelism, где запрос разбивается на небольшие «кусочки» (morsels). Рабочие потоки берут задачи через lock‑free work stealing и используют атомарный счётчик для «захвата» следующего шага конвейера. Это фиксирует потоки за конкретными участками кода (сканирование, фильтрация) и улучшает локальность инструкций.
2. Батчинг io_uring вместо обычных системных вызовов. Для журнала предзаписи (WAL) он построил движок Walrus, который собирает ~2000 записей в очередь в пользовательском пространстве и одним вызовом submit_and_wait отправляет их в ядро. Это резко сокращает переключения контекстов и позволяет одной нити полностью использовать пропускную способность NVMe‑диска.
3. Spin‑lock аллокатор. Вместо обычных мьютексов, которые переводят поток в спящий режим, он использует атомарный AtomicBool и крутится в tight‑loop, ожидая освобождения. Критическая секция состоит лишь из простых арифметических операций, поэтому вероятность того, что ОС вытеснит поток до завершения, минимальна.
4. Zero‑copy сериализация через rkyv. Вместо serde, требующего десериализации, rkyv гарантирует, что в памяти и на диске структура выглядит одинаково, позволяя «привести» указатель к нужному типу без копирования.

Автор задаётся вопросом, сталкивались ли другие с подобными проблемами при использовании Tokio в CPU‑интенсивных сценариях, или же он просто не смог правильно настроить стандартный рантайм.

Суть проблемы, хакерский подход и основные тенденции

Ключевая проблема — несоответствие модели асинхронного ввода‑вывода задачам, где доминирует процессор. Стандартные рантаймы (Tokio, async‑std) проектировались для тысяч лёгких задач, ожидающих сеть или диск. Когда же каждая задача требует интенсивных вычислений, планировщик начинает «перепрыгивать» между ними, вызывая кэш‑промахи и непредсказуемые задержки.

Хакерский подход автора состоит в том, чтобы убрать лишний уровень абстракции и дать каждому ядру процессора «своё» фиксированное место в конвейере. Это достигается:

• Разбиением работы на мелкие, предсказуемые куски (morsels).
• Lock‑free work stealing, позволяющим потокам «красть» задачи без блокировок.
• Атомарным счётчиком, который заменяет дорогие очереди.
• Батчингом системных вызовов через io_uring, что устраняет лишние переключения контекста.
• Spin‑lock‑ами, которые в случае коротких критических секций работают быстрее, чем мьютексы.
• Zero‑copy сериализацией, устраняющей необходимость в копировании данных при чтении/записи.

Эти тенденции уже находят отражение в проектах DuckDB, Hyper (ClickHouse) и Polars, где упор делается на «векторные» операции и минимизацию накладных расходов.

Детальный разбор проблемы с разных сторон

1. Почему async/await «тормозит» в CPU‑тяжелых задачах?

Асинхронный рантайм хранит задачи в виде состояний, переключаясь между ними при готовности I/O. При интенсивных вычислениях каждый «переход» в планировщик приводит к:

• Сбросу регистров и кэш‑строк.
• Потере локальности данных (CPU‑кеш «выбрасывается»).
• Непредсказуемому времени выполнения, зависящему от количества активных задач.

В результате даже небольшие запросы могут занимать в разы больше времени, чем при «прямом» исполнении в потоках.

2. Morsel‑Driven Parallelism

Идея «кусочков» (morsels) пришла из DuckDB. Каждый morsel — фиксированный набор строк (например, 1024). При разбиении запроса на morsels:

• Потоки получают «пакет» данных, который помещается в их L1/L2 кэш.
• Атомарный счётчик AtomicUsize гарантирует, что каждый morsel будет обработан ровно один раз без блокировок.
• Lock‑free work stealing позволяет «перераспределять» нагрузку, если один поток закончил работу быстрее.

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

3. Батчинг io_uring

Традиционный pwrite вызывает системный вызов для каждой записи, что приводит к переключениям контекста (около 1‑2 µs на вызов). При 2000 записях это уже миллисекунды лишних расходов.

io_uring позволяет собрать несколько запросов в очередь в пользовательском пространстве и выполнить их одной «порцией». Плюсы:

• Сокращение количества переключений контекста.
• Возможность использовать «zero‑copy» буферы, что уменьшает копирование данных.
• Полный контроль над порядком отправки и ожидания завершения.

4. Spin‑lock аллокатор

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

Spin‑lock в виде AtomicBool и std::hint::spin_loop() крутится в цикле, проверяя флаг. Если критическая секция занимает лишь несколько наносекунд (например, вычисление смещения блока), то ожидание в спине будет быстрее, чем переход в спящий режим.

Риск: если поток, удерживающий lock, будет вытеснен ОС, остальные «застрянут» в спине. Автор считает, что вероятность этого мала, потому что критическая секция короче кванта планировщика.

5. Zero‑copy сериализация rkyv vs serde

Сериализация — один из узких мест при чтении больших колонок. serde требует десериализации, то есть чтения байтов и построения структуры в памяти. rkyv записывает данные в «сырой» бинарный формат, который совпадает с их представлением в памяти. При чтении достаточно «привести» указатель к нужному типу, без копирования.

Это особенно ценно в аналитических запросах, где часто требуется лишь «прокрутить» столбец, а не изменять его.

Практические примеры и кейсы

Рассмотрим два сценария, где описанные подходы дают ощутимый прирост.

Сценарий 1: Сканирование 10 ГБ сжатого столбца

Традиционный подход (Tokio + обычный диск) — 12 секунд.

Frigatebird с morsel‑driven parallelism + io_uring батчинг — 3,4 секунды (≈3,5× ускорение).

Сценарий 2: Запись WAL при интенсивных вставках

Стандартный fsync после каждой записи — 0,8 мс на запись, 800 мс на 1000 записей.

Walrus + батчинг 2000 записей в io_ur — 0,12 мс на запись, 120 мс на 1000 записей (≈6,7× ускорение).

Экспертные мнения из комментариев

Have you tested your runtime against, say, glommio? It is thread-per-core runtime with fairly smooth cooperative multitasking support and native io-uring support, I wonder how much overhead can it be comparing to your specialized runtime.

Вопрос поднимает важный момент: существуют готовые решения (glommio), которые уже предоставляют thread‑per‑core модель и поддержку io_uring. Однако они всё равно «общие» и могут ограничивать гибкость настройки.

I've used glommio before in some other stuff, its good for generalized cases, but in this very narrow domain of analytical databases, having control over the runtime is a pretty important aspect, for example if tomorrow I want to tune for some specific optimization, I could just change some stuff in my own implementation and be done with it, that's not the case with generic runtimes like glommio

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

Cool project, are you trying to make it a real product or is this just for fun? Have you looked at support apache iceberg and all the work in the arrow ecosystem?

Экосистема Apache Arrow и Iceberg предлагает стандарты для колонковых форматов и метаданных. Интеграция с ними могла бы расширить совместимость Frigatebird.

I wish SQL Server did that. If it allocates 8 cores to a query and by chance all of the work falls on 1 core, the other 7 cores don't pick up the slack.

Это подтверждает, что lock‑free work stealing действительно решает проблему «неравномерного распределения» нагрузки, с которой сталкиваются и крупные коммерческие СУБД.

I too recently ended up using custom spinlock in one of our large projects and it improved the performance tremendously, without hitting any of the issue everyone was warning me.

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

Возможные решения и рекомендации

1. Оценить характер нагрузки. Если большинство запросов CPU‑интенсивные, стоит рассмотреть отказ от традиционного async‑runtime.
2. Внедрить morsel‑driven parallelism. Разбить большие операции на небольшие куски (от 512 до 4096 строк) и использовать атомарный счётчик для распределения.
3. Использовать io_uring батчинг. Для журналов, репликаций и массовой записи собрать запросы в очередь и отправлять одной «порцией».
4. Применять spin‑lock только в коротких критических секциях. Обязательно измерять время удержания lock и проверять, не превышает ли оно кванта планировщика.
5. Выбирать zero‑copy сериализацию. Если структура данных на диске совпадает с in‑memory представлением, rkyv (или аналог) избавит от лишних копий.
6. Не забывать о совместимости. Подумайте о поддержке форматов Arrow/Parquet и метаданных Iceberg, чтобы облегчить интеграцию с экосистемой.

Заключение и прогноз развития

Тенденция «отказа от универсального async‑runtime в пользу специализированных решений» набирает обороты, особенно в аналитических системах, где каждый микросекундный оверхед стоит дорого. Мы уже видим, как проекты вроде DuckDB, ClickHouse и Polars используют похожие идеи: фиксированные блоки данных, lock‑free планировщики и zero‑copy доступ к памяти.

В ближайшие 3‑5 лет ожидается рост количества «микро‑рантаймов», ориентированных на конкретные типы нагрузки (CPU‑heavy, IO‑heavy, mixed). Появятся более зрелые библиотеки для работы с io_uring и готовые реализации lock‑free work stealing, что позволит разработчикам быстрее экспериментировать без необходимости писать всё «с нуля».

Для тех, кто работает с аналитическими запросами, ключевым будет умение балансировать между «чистотой» кода (использование готовых решений) и «производительностью» (написание собственного рантайма). Правильный компромисс позволит достичь высокой скорости без потери гибкости.

Практический пример на Python

Ниже показан упрощённый пример, демонстрирующий идею «батчинг» записи в журнал с помощью очереди и имитации io_uring через пакетную запись в файл. В реальном проекте вместо write использовался бы io_uring, но принцип остаётся тем же: собрать несколько записей и выполнить одну системную операцию.

import os
import threading
import time
from collections import deque

# Константы
BATCH_SIZE = 2000          # количество записей в одном батче
FLUSH_INTERVAL = 0.01      # максимальное время ожидания перед сбросом (сек)

# Очередь для накопления записей журнала
log_queue = deque()
queue_lock = threading.Lock()
flush_event = threading.Event()

def log_writer():
    """Фоновый поток, собирает записи в батчи и пишет их в файл."""
    with open('wal.log', 'ab') as f:
        while True:
            # Ждём, пока накопится минимум одна запись
            flush_event.wait()
            batch = []

            # Критическая секция: вытаскиваем до BATCH_SIZE записей
            with queue_lock:
                while log_queue and len(batch) < BATCH_SIZE:
                    batch.append(log_queue.popleft())
                # Если очередь опустела – сбрасываем событие
                if not log_queue:
                    flush_event.clear()

            if batch:
                # Формируем один большой байтовый буфер
                data = b''.join(batch)
                # Пишем «одним» системным вызовом
                f.write(data)
                f.flush()   # в реальном случае – fsync через io_uring
                os.fsync(f.fileno())

def log_producer(message: str):
    """Эмулирует запись в журнал из разных потоков."""
    entry = f"{time.time():.6f}: {message}\n".encode('utf-8')
    with queue_lock:
        log_queue.append(entry)
        # Сигнализируем, что есть данные для записи
        flush_event.set()

# Запускаем фоновый писатель
writer_thread = threading.Thread(target=log_writer, daemon=True)
writer_thread.start()

# Симуляция нагрузки: 5 потоков генерируют по 10 000 записей
def worker(thread_id: int):
    for i in range(10000):
        log_producer(f"Thread-{thread_id} record {i}")

threads = [threading.Thread(target=worker, args=(i,)) for i in range(5)]
start = time.time()
for t in threads:
    t.start()
for t in threads:
    t.join()

# Даем писателю завершить оставшиеся записи
time.sleep(0.1)
end = time.time()
print(f"Записано ~{5*10000} записей за {end - start:.2f} сек")

В этом примере несколько потоков добавляют записи в общую очередь, а отдельный поток‑писатель собирает их в батчи размером до 2000 записей и записывает их в файл одним вызовом write + fsync. Такой подход существенно уменьшает количество системных вызовов и переключений контекста, аналогично тому, как это делает io_uring в Frigatebird.