Своя СУБД на Haskell · урок 3: куча и записи

Кому это. Ты прошёл урок 2: страницы ходят через буферный пул, withPage держит pin ровно на время действия. Пока страницы хранят безымянные байты. Сегодня они научатся хранить строки таблицы. Тот же шаг есть в TS-треке, и формат кортежа байт в байт тот же. В Haskell-порте этот урок самый “чистый”: схема, значение и кортеж это алгебраические типы, сериализация это чистая функция Schema -> Tuple -> Either DbError ByteString на Builder, а разбор байтов это маленькая монада Get с проверкой границ. В IO остаётся только куча, которая раскладывает кортежи по страницам.

Важно про код. Своя монада разбора в этом уроке написана руками, без библиотек. Если instance Monad над функцией из состояния в результат выглядит непривычно, освежи урок про монады и урок про парсер-комбинаторы: Get это тот же парсер, только над байтами вместо символов.

Где мы в движке

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

Четыре новые сущности

Куча держится на четырёх модулях, и порядок тут важен.

• OurDb.Bytes это чистые кодеки чисел: разбор ByteString с проверкой границ и сборка байтов через Builder. Он не знает ни про кортежи, ни про страницы.
• OurDb.Schema описывает форму строки: имена и типы колонок по порядку. Без неё байты не разобрать: чтобы прочитать int, надо знать, что в этом месте именно int.
• OurDb.Tuple это одна строка (список значений плюс заголовок версии) и две чистые функции: в байты по схеме и обратно. Здесь живёт null bitmap.
• OurDb.Heap это таблица: набор страниц поверх пула, вставка ищет место, scan обходит всё, удаление помечает слот.

Первые три модуля чистые. Ни одна их функция не живёт в IO, и все они тестируются без файлов.

Контракт байтов кортежа

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

смещение  размер  поле
0         4       xmin       u32   xid транзакции, создавшей версию
4         4       xmax       u32   xid транзакции, удалившей версию (0 если живая)
8         2       infomask   u16   биты-флаги: HAS_NULL (0x0001), XMIN_FROZEN (0x0002)
10        2       nattrs     u16   число колонок
12        ...     null_bitmap      по биту на колонку, ceil(nattrs / 8) байт
...       ...     data             значения ненулевых колонок по порядку

int   8 байт, знаковый, little-endian
bool  1 байт, 0 или 1
text  u32 длина в байтах, затем байты UTF-8

Заголовок это 12 байт. Поля xmin и xmax несут метаданные MVCC: номер транзакции, вставившей строку, и номер удалившей (0, пока строка жива). До транзакций они значат мало, но место под них резервируем сразу, чтобы в уроке 8 не переписывать формат каждого кортежа на диске. Бит XMIN_FROZEN понадобится vacuum в уроке 10: пока его нет ни в константах, ни в кортеже, и мы всегда пишем его нулём.

NULL это бит, а не значение

Ключевая тонкость формата это null bitmap. NULL это не специальное значение в данных, а поднятый бит в карте. NULL-колонка в области данных не занимает ничего. Это компактнее и честнее: NULL это отсутствие значения, а не нуль и не пустая строка.

Повозись с раскладкой вживую. Переключай колонки в NULL и обратно, правь имя. Следи за областью данных (NULL-колонка исчезает из неё целиком), битом в null bitmap и флагом HAS_NULL в infomask.

Если повозился, ты увидел три факта, на которых стоит сериализация. Заголовок и bitmap фиксированной длины, плавает только область данных. NULL-колонка не пишет ни байта данных, её выдаёт только бит. text растёт ровно на длину UTF-8, и кириллица это 2 байта на символ, поэтому имя из русских букв вдвое длиннее, чем кажется по числу символов.