kestrel

Движок реляционной базы данных с нуля на Kotlin: парсер SQL, хранилище на B-дереве, исполнитель, транзакции с WAL и CLI. Выполняет реальные SQL-запросы и покрыт полным набором тестов.

TL;DR

Движок реляционной базы данных, написанный с нуля на Kotlin: собственный парсер SQL, исполнитель запросов, хранилище на B-дереве и транзакции с журналом WAL. Плюс CLI и полный набор тестов.

Обзор

kestrel - это движок реляционной базы данных, написанный с нуля на Kotlin. В нём есть всё, что делает из базы базу, а не только склад для данных: собственный парсер SQL, исполнитель запросов, хранилище на B-дереве, транзакции с журналом WAL, плюс CLI и полный набор тестов. Он выполняет настоящие SQL-запросы, а не имитирует их обработку.

В повседневности база - это одна строка: выполнить запрос, получить строки. Написание её с нуля сдирает это удобство и показывает, как много всего происходит под низом, - и именно этот путь вниз и есть смысл этого проекта.

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

Каждый из этих вопросов в повседневности скрыт за удобством готовой базы. Написание движка с нуля вытаскивает их наружу по очереди и заставляет решить по-настоящему, а не отмахнуться. Именно поэтому база данных - один из лучших проектов, какой можно себе поставить, чтобы понять компьютер глубже.

Полный путь запроса

kestrel берёт обычный запрос и пропускает его по полному пути - от текста до байтов на диске. Каждый этап решает одну задачу и передаёт результат следующему, а весь путь можно провести пальцем от строки SQL до места, куда попадают данные.

demo.sql · sql

CREATE TABLE users (id INTEGER PRIMARY KEY, name TEXT);
INSERT INTO users VALUES (1, 'ada');
SELECT name FROM users WHERE id = 1;

Парсер

текст SQL превращается в дерево запроса.

Исполнитель

дерево становится планом: что читать и в каком порядке.

Хранилище

данные лежат в B-дереве, чтобы поиск по ключу был быстрым.

WAL

каждое изменение сначала попадает в журнал, только потом на место.

Слои движка

Слой	Задача
Парсер	SQL в дерево запроса
Исполнитель	дерево в план выполнения
Хранилище	данные в B-дереве для быстрого поиска
WAL	журнал намерений перед реальной записью

WAL, или почему вы не теряете данные

Самая трудная часть базы невидима, пока что-то не пойдёт не так. Журнал WAL - это механизм, который решает, вернётся ли база после внезапного отключения к согласованному состоянию или вы останетесь с наполовину записанной транзакцией. Правило простое и нерушимое: сначала запись намерения в журнал, потом реальное изменение - никогда наоборот.

Внимание

Журнал WAL - не украшение. Именно он решает, вернётся ли база после внезапного отключения к согласованному состоянию или вы останетесь с наполовину записанной транзакцией. Сначала запись намерения в журнал, потом реальное изменение - каждый разворот этого порядка это потенциальная потеря данных.

Эффект: знание, которое остаётся

Это проект, который после завершения меняет то, как вы смотрите на любую другую базу данных, - ведь вдруг вы знаете, что сидит под этим одним SELECT. kestrel выполняет настоящие запросы, проходит полный набор тестов и имеет CLI, так что это не набросок, а работающий движок. А знание, которое от него остаётся, ценнее самого кода.

Больше проектов

Другие работы из той же категории - посмотрите, как мы решаем похожие задачи.

Есть похожий проект?

Напишите нам - смета бесплатна и приходит в течение часа.