Своя СУБД на TS · урок 1: страницы и свой файловый слой

Кому это. Ты прошёл серию про PostgreSQL: знаешь, что строка живёт на 8K-странице, что у кортежа есть xmin/xmax, что vacuum убирает мёртвые версии. Но всё это ты видел снаружи, через EXPLAIN и pg_stat. Теперь мы перевернём картинку и построим маленькую честную СУБД снизу вверх, своими руками, на чистом Node и TypeScript. Никакой магии: только Buffer, node:fs и понимание того, как байты ложатся на диск.

Зачем. Знать, что Postgres хранит данные страницами по 8 КБ, и уметь самому уложить кортеж на такую страницу так, чтобы её прочитала другая программа, это две очень разные степени понимания. Первая помогает на собеседовании, вторая помогает чинить прод в три часа ночи. Мы идём за второй. К концу воркшопа у тебя будет движок, который принимает SQL по своему бинарному протоколу и отдаёт строки, с индексами, транзакциями, WAL и MVCC внутри. Не игрушка на один SELECT, а ядро, в котором видно, почему настоящие СУБД устроены именно так.

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

Что мы строим за десять уроков

ourdb это однонодовая дисковая реляционная СУБД в духе Postgres, урезанная до обучаемого ядра. На входе SQL, на выходе строки. Внутри полный путь запроса: разбор, планирование, исполнение поверх страничного хранилища с индексами, транзакциями и MVCC. Слои снизу вверх, и справа номер урока, который этот слой добавляет:

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 10
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Планировщик, binder, парсер, лексер             │  уроки 5, 6
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 9
│  MVCC (видимость, снимки)                        │  урок 8
│  Блокировки (2PL), менеджер транзакций           │  уроки 7, 8
│  WAL (журнал, redo, recovery)                    │  урок 7
├────────────────────────────────────────────────┤
│  B+Tree индекс                                   │  урок 4
│  Куча (slotted pages, seq scan)                  │  урок 3
├────────────────────────────────────────────────┤
│  Буферный пул (кэш страниц, вытеснение)           │  урок 2
│  DiskManager (страницы поверх файла)              │  урок 1  ← мы здесь
└────────────────────────────────────────────────┘

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

Зачем базе своя файловая раскладка

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

Причин несколько, и все они про контроль.

• Фиксированный размер блока даёт предсказуемый ввод-вывод. Диск и ОС всё равно работают блоками. Если наш минимальный кусок данных это страница фиксированного размера, то чтение и запись это всегда ровно один блок по известному смещению. Никаких частичных чтений на полстроки.
• Адресация по номеру страницы стабильна. Кортеж адресуется парой RID вида (номер страницы, номер слота). Пока кортеж жив, его адрес не меняется, и на него можно ссылаться из индекса. Если бы мы дописывали строки в файл как попало, любой сдвиг ломал бы все ссылки.
• Кэширование становится возможным. В уроке 2 мы поставим между движком и диском буферный пул: страница один раз прочитана, дальше живёт в памяти. Кэшировать имеет смысл единицы фиксированного размера, а не строки произвольной длины.
• Журнал и восстановление опираются на страницы. WAL в уроке 7 будет писать “страница номер N изменилась так-то”. Без понятия страницы нечего журналировать.

Поэтому почти каждая СУБД строит поверх сырого файла свою адресацию страницами. Это и есть та самая “своя ФС”: мы не доверяем файловой системе ОС вопрос раскладки данных, а берём его на себя. Наш самый нижний слой называется DiskManager, и его работа ровно одна: представить один файл как массив страниц фиксированного размера с операциями “прочитай страницу N”, “запиши страницу N”, “выдели новую страницу”.

Страница: контракт байтов

Прежде чем писать код, договоримся о формате. Это важнее, чем кажется: пять реализаций ourdb на разных языках читают файлы друг друга, а значит формат страницы зафиксирован раз и одинаков для всех. Числа на диске мы пишем little-endian, родным порядком для x86 и ARM.

Почему 8192 и почему фиксированный размер

Размер страницы PAGE_SIZE = 8192 байта, фиксированный, как у Postgres. Почему именно столько?

Это компромисс. Слишком маленькая страница (скажем, 512 байт) означает, что под крупную строку нужно много страниц, и накладные расходы на заголовки растут. Слишком большая (64 КБ) означает, что ради одной короткой строки мы тянем с диска и держим в кэше много лишнего. 8 КБ исторически хорошо ложатся на размер блока файловых систем и на страницы памяти, поэтому это разумный дефолт. Для нас важнее другое: размер фиксированный. Страница с номером N всегда лежит по смещению N * PAGE_SIZE. Зная номер, мы за одно арифметическое действие получаем место на диске.

Анатомия slotted page

Внутри страницы мы используем раскладку slotted page, ту же, что в Postgres. Идея в том, чтобы развести две вещи, которые тянут в разные стороны: указатели фиксированного размера и данные переменной длины.

Заголовок страницы лежит в первых 16 байтах:

смещение  размер  поле     тип    смысл
0         8       lsn      u64    LSN последней записи WAL, изменившей страницу (урок 7)
8         2       lower    u16    конец массива слотов (растёт вправо, к большим смещениям)
10        2       upper    u16    начало области данных (растёт влево, к меньшим смещениям)
12        2       special  u16    начало special-области (метаданные узла B+Tree, урок 4)
14        2       flags    u16    тип и флаги страницы
16        ...     slots[]         массив слотов: на слот u16 со смещением кортежа
...                                свободное место между lower и upper
upper     ...     tuples[]        кортежи растут от конца страницы к началу

Картинка целиком выглядит так. Слева заголовок, дальше массив слотов растёт вправо, кортежи растут влево от конца страницы, посередине свободное место:

0        16        lower                upper                  8192
│ header │ slot0 slot1 slot2 ->    ←  tuple2 tuple1 tuple0 │
│ 16 B   │ растут вправо    free   растут влево            │
                         space = upper - lower

Ключевая величина это свободное место, и оно ровно upper - lower. Вставка нового кортежа делает два движения навстречу: кладёт данные кортежа у upper (сдвигая upper влево, к меньшим смещениям) и добавляет слот у lower (сдвигая lower вправо). Когда lower догоняет upper, свободного места не осталось.

Зачем такая раздвоенность? Слот это маленький указатель фиксированного размера (2 байта). Кортеж это данные переменной длины. Если хранить их вперемешку, удаление кортежа в середине двигало бы всё, что за ним, и ломало бы RID соседей. А так слот всегда на своём месте по своему номеру, кортеж лежит где угодно в области данных, и удаление просто помечает слот, не трогая остальные. Физически место мёртвого кортежа вернёт vacuum в уроке 9.

Поиграй с этим вживую. Кнопка INSERT кладёт кортеж, клик по слоту помечает его мёртвым, VACUUM уплотняет страницу. Смотри за тремя числами внизу: lower, upper и свободным местом. Обрати внимание на главный сюрприз: удаление кортежа не возвращает свободное место сразу.

Если ты повозился с виджетом, ты уже заметил две вещи, которые и есть мораль урока про страницу. Первая: DELETE двигает не данные, а только статус слота, поэтому свободное место не растёт. Вторая: VACUUM возвращает место, двигая upper вверх, но lower оставляет на месте. Номера живых слотов сохраняются, а значит RID остаётся стабильным и индекс не протухает. Запомни это, в уроке 9 мы это запрограммируем.