kestrel

Silnik relacyjnej bazy danych od zera w Kotlinie: parser SQL, magazyn na B-drzewie, executor, transakcje z WAL oraz CLI. Wykonuje realne zapytania SQL i jest pokryty kompletem testów.

TL;DR

Silnik relacyjnej bazy danych napisany od zera w Kotlinie: własny parser SQL, executor zapytań, magazyn na B-drzewie i transakcje z dziennikiem WAL. Do tego CLI i komplet testów.

Wprowadzenie

kestrel to silnik relacyjnej bazy danych napisany od zera w Kotlinie. Ma wszystko, co robi z bazy bazę, a nie tylko skład na dane: własny parser SQL, executor zapytań, magazyn oparty na B-drzewie, transakcje z dziennikiem WAL, a do tego CLI i komplet testów. Wykonuje realne zapytania SQL, a nie udaje ich obsługi.

Na co dzień baza to jedna linijka: wykonaj zapytanie, dostań wiersze. Napisanie jej od zera zdziera tę wygodę i pokazuje, ile rzeczy dzieje się pod spodem - i właśnie ta droga w dół jest sensem tego projektu.

Za jednym niewinnym SELECT-em kryje się ciąg trudnych pytań. Jak trzymać dane na dysku, żeby szybko je znaleźć? Jak przełożyć tekst SQL na plan wykonania, który wie, co przeczytać i w jakiej kolejności? I najtrudniejsze: jak nie stracić zapisu, gdy prąd zniknie w połowie operacji?

Każde z tych pytań na co dzień jest ukryte za wygodą gotowej bazy. Napisanie silnika od zera wyciąga je na wierzch po kolei i każe rozwiązać naprawdę, a nie machnąć ręką. To dlatego baza danych jest jednym z najlepszych projektów, jakie można sobie postawić, żeby zrozumieć komputer głębiej.

Pełna droga zapytania

kestrel bierze zwykłe zapytanie i przepuszcza je przez pełną ścieżkę - od tekstu aż po bajty na dysku. Każdy etap ma jedno zadanie i podaje wynik następnemu, a całość da się przejść palcem od linijki SQL do miejsca, w które trafiają dane.

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;

Parser

tekst SQL zamienia się w drzewo zapytania.

Executor

drzewo staje się planem: co przeczytać i w jakiej kolejności.

Magazyn

dane leżą w B-drzewie, żeby wyszukiwanie po kluczu było szybkie.

WAL

każda zmiana najpierw trafia do dziennika, dopiero potem na miejsce.

Warstwy silnika

Warstwa	Zadanie
Parser	SQL na drzewo zapytania
Executor	drzewo na plan wykonania
Magazyn	dane w B-drzewie dla szybkich wyszukań
WAL	dziennik intencji przed realnym zapisem

WAL, czyli dlaczego nie tracisz danych

Najtrudniejsza część bazy nie jest widoczna, dopóki coś nie pójdzie nie tak. Dziennik WAL to mechanizm, który decyduje, czy po nagłym wyłączeniu baza wróci do spójnego stanu, czy zostaniesz z połową zapisanej transakcji. Zasada jest prosta i nienaruszalna: najpierw zapis intencji do dziennika, potem realna zmiana - nigdy odwrotnie.

Ostrzeżenie

Dziennik WAL to nie ozdoba. To on decyduje, czy po nagłym wyłączeniu baza wróci do spójnego stanu, czy zostaniesz z połową zapisanej transakcji. Najpierw zapis intencji do dziennika, potem realna zmiana - każde odwrócenie tej kolejności to potencjalna utrata danych.

Efekt: wiedza, która zostaje

To projekt, który po skończeniu zmienia sposób, w jaki patrzysz na każdą inną bazę danych - bo nagle wiesz, co siedzi pod tym jednym SELECT-em. kestrel wykonuje realne zapytania, przechodzi komplet testów i ma CLI, więc nie jest szkicem, tylko działającym silnikiem. A wiedza, która przy nim zostaje, jest cenniejsza niż sam kod.

Więcej projektów

Inne realizacje z tej samej kategorii - zobacz, jak podchodzimy do podobnych wyzwań.

Masz podobny projekt?

Napisz do nas - wycena jest bezpłatna i wraca w godzinę.