Эксперимент по ускорению SQLite

SQLite быстра, но можно ли сделать её ещё быстрее? Исследователи из Университетов Хельсинки и Кембриджа задались этим вопросом и опубликовали работу Serverless Runtime / Database Co-Design With Asynchronous I/O. В ней они продемонстрировали возможность 100-кратного снижения времени задержки, и ниже я в общих чертах эту их работу прокомментирую.

Речь пойдёт об исследовании возможностей Limbo — переписанной на Rust версии SQLite.

Обратите внимание, что это довольно короткий доклад. Акцент в нём сделан на бессерверных и периферийных вычислениях. Тем не менее полученную информацию можно применить в более широких областях.

Основная идея: ускорить работу SQLite можно с помощью асинхронного ввода/вывода и разделения хранилища.

▍ io_uring

В этом докладе мне больше всего понравилось два момента: то, как авторы объяснили выполнение запросов и принцип работы io_uring.

Подсистема io_uring в ядре Linux предоставляет интерфейс для асинхронного ввода/вывода. Её название происходит от кольцевых буферов (ring buffers), совместно используемых пространством пользователя и пространством ядра для сокращения вычислительных издержек при копировании между ними [3]. Подсистема io_uring позволяет приложению отправить запрос ввода/вывода и продолжить параллельно выполнять другие задачи, пока от ОС не поступит уведомление о завершении запрошенной операции.

Используя io_uring, приложение сначала производит системный вызов io_uring_setup() для настройки двух областей памяти: очереди отправки и очереди завершения. После этого приложения отправляют в первую из них запросы ввода/вывода и вызывают io_uring_enter(), чтобы ОС начала обработку этих запросов. Тем не менее, в отличие от блокирующих выполнение вызовов read() и write(), вызов io_uring_enter() не блокирует поток, возвращая управление пространству пользователя. Это позволяет приложению параллельно выполнять другую работу, периодически опрашивая очередь завершения на предмет окончания обработки его запроса ввода/вывода.

Авторы также описывают процесс выполнения SQLite запроса, что станет актуально позже:

Сначала приложение открывает базу данных с помощью функции sqlite3_open(). Поскольку в SQLite для хранения данных используются файлы, эта функция для их открытия вызывает низкоуровневую функцию ввода/вывода open() из POSIX. После этого приложение подготавливает SQL-команду, используя функцию sqlite3_prepare(), которая преобразует команды SQL, такие как SELECT и INSERT, в последовательности инструкций байткода. Далее оно выполняет эту команду с помощью функции sqlite3_step(). Эта функция выполняет последовательность инструкций байткода, пока в рамках запроса не перестанут создаваться строки для считывания, после чего завершается. Когда присутствует строка данных, функция возвращает SQLITE_ROW, а при завершении команды — SQLITE_DONE.

Внутренне sqlite3_step() вызывает бэкенд-модуль постраничного вывода (pager), обходя B-деревья базы данных, представляющие таблицы и строки. Если страница B-дерева в кэше страниц SQLite отсутствует, её приходится считывать с диска. Для считывания содержимого страницы в память SQLite использует синхронный ввод/вывод в виде системного вызова read() из POSIX. Это означает, что функция sqlite3_step() блокирует поток ядра, вынуждая приложения задействовать больше потоков для параллельного выполнения работы во время ожидания завершения ввода/вывода.

▍ Вводная часть

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

Одним из решений является колокация данных на самой периферии. Но лучше будет встроить базу данных в среду выполнения этого периферийного приложения. Тогда задержка связи с БД станет нулевой — мечта в реальности.

Это уже реализовано в механизме Cloudflare Workers, но он предоставляет интерфейс KV (в виде пар ключ-значение). Однако авторы работы утверждают, что KV подходит не для всех предметных областей. Отображение табличных данных в модель KV создаёт сложности для разработчиков и накладывает издержки в виде (де)сериализации. SQL может справиться намного лучше, и решит эту задачу встраиванием SQLite непосредственно в бессерверную среду.

SQLite использует синхронный ввод/вывод. Традиционные системные вызовы POSIX read() и write() блокируют поток, пока операция не будет завершена. Для небольших приложений это нормально, но когда на сервере работают сотни баз данных, такой механизм становится узким местом. В этом случае крайне важна максимальная эффективность использования ресурсов.

Но SQLite имеет собственные недостатки: конкурентность и мультиарендность. Поскольку ввод/вывод синхронен, а значит сопряжён с блокировками, это ведёт к конкурированию приложений за ресурсы, что также повышает задержку.

Почему нельзя просто перенести SQLite в io_uring?

Заменить системные вызовы ввода/вывода из POSIX на io_uring не так просто, и архитектуру приложений, использующих блокирующий ввод/вывод, придётся перестроить под асинхронную модель io_uring. В частности, приложениям нужно будет обрабатывать отправку запросов ввода/вывода в своём потоке управления. В случае SQLite библиотеке потребуется возвращать управление приложению, пока выполняется ввод/вывод.

Иными словами, придётся переписать львиную долю SQLite. Исследователи же пошли другим путём: переписали SQLite на Rust, используя io_uring.

▍ Limbo

Они перестроили уровни «Virtual machine» и «B-tree» для поддержки асинхронного ввода/вывода, заменив синхронные инструкции байткода их асинхронной альтернативой:

Рассмотрим в качестве примера одну инструкцию — Next. Что она делает? Она продвигает курсор и может запрашивать следующую страницу. Во время выполнения дискового ввода/вывода она блокируется. База данных отправляет вызов Next виртуальной машине и блокируется, пока страница не будет получена с диска и возвращена вызывающему коду.

В асинхронной же версии сначала отправляется NextAsync, которая тут же возвращает результат. Теперь вызывающий код может блокироваться или выполнять другие операции. Асинхронный ввод/вывод исключает блокировку и минимизирует конкурентность. Вот сравнение двух этих подходов в байткоде:

Тем не менее для оптимизации использования ресурсов авторы предлагают ещё кое-что: разделение механизмов запроса и хранения, то есть «Разделённое хранилище». Я расписал основы этой идеи в статье «Disaggregated Storage — a brief introduction».

▍ Анализ и результаты

В целях тестирования авторы симулировали мультиарендную бессерверную среду, где каждый арендатор получает собственную встроенную базу данных. Количество арендаторов в тестировании варьировалось от 1 до 100 с шагом в 10. На каждого арендатора SQLite получала по одному потоку, в котором выполнялся оцениваемый запрос. Далее авторы 1 000 раз выполнили SELECT * FROM users LIMIT 100. В отношении Limbo они проделали то же самое, но использовали корутины Rust.

Результат показывает выдающееся 100-кратное уменьшение задержки выполнения при p999. Также было зафиксировано, что задержка запросов SQLite с ростом числа потоков не растёт.

График изменения задержки запросов в SQLite (оранжевый — это limbo). Меньше — лучше.

Но исследование продолжается, и в работе упоминается пара вопросов, на которые ещё предстоит ответить. Эти вопросы авторы озвучивают в разделе «Future Work», где говорят о выполнении дополнительных бенчмарков со множеством операций чтения и записи. Преимущества становятся заметны только при p999 и выше. При p90 и p99 производительность практически та же, что и в SQLite. (Может ли дело быть в том, что выполняется всего по одному запросу?)

Код Limbo является открытым и лежит здесь.