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

Кому это. Ты пишешь на Haskell: отделяешь чистое ядро от IO, знаешь, чем ByteString отличается от String, заворачивал ресурсы в bracket. Теперь возьмём этот инструмент и построим им что-то весомое: маленькую честную реляционную СУБД снизу вверх. Это тот же воркшоп ourdb, что и в TS-треке, но переложенный на Haskell. Если ты уже прошёл его на TypeScript или на Effect, этот урок покажет ту же механику под новым углом: где в TS был Buffer и DataView, у нас будет изменяемый буфер за ForeignPtr с проверкой границ, а где в TS летело исключение, у нас тип скажет, что функция живёт в IO или возвращает Either.

Зачем именно Haskell. Движок базы это байты, которые должны лечь на диск ровно так, как записано в контракте, и логика поверх них, которую хочется проверять без диска. Haskell хорошо режет одно от другого. Разбор SQL, проверка типов запроса, выбор плана, сериализация кортежа в байты: всё это чистые функции, которые тестируются одной строкой в GHCi. Страница, файл и кэш живут в IO, и это видно в подписи каждой функции. Ошибки разбора это Either DbError, а не исключение, которое надо помнить поймать. Этот урок закладывает первый камень: страницу и DiskManager.

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

Что мы строим за одиннадцать уроков

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

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

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

Проект: один cabal-пакет

Весь движок живёт в одной библиотеке ourdb. Зависимости только из boot-пакетов GHC: base, bytestring, containers, stm, text. Песочница курса собирает код без сети, а заодно ты увидишь, что для базы данных стандартного набора хватает. Как устроен cabal-файл, разобрано в уроке про cabal и документацию. Главное из него:

-- ourdb.cabal (выдержка)
common extensions
    default-language:   GHC2021
    default-extensions: LambdaCase
                        OverloadedStrings
                        BangPatterns

library
    import:           warnings, extensions
    hs-source-dirs:   src
    exposed-modules:  OurDb.Error
                      OurDb.Constants
                      OurDb.Page
                      OurDb.Disk
    build-depends:    base >=4.18 && <5
                    , bytestring
                    , containers
                    , stm
                    , text

test-suite ourdb-test
    type:             exitcode-stdio-1.0
    hs-source-dirs:   test
    main-is:          Spec.hs
    other-modules:    TestUtil
                      Lesson01PagesSpec
    build-depends:    base, ourdb, bytestring, text, directory, filepath, hspec

Три расширения включены на весь пакет. LambdaCase даёт \case без лишней переменной, OverloadedStrings разрешает писать "..." там, где ждут Text или ByteString, BangPatterns нужен для строгих аккумуляторов в циклах по байтам. С каждым уроком в exposed-modules прибавится пара модулей, а в тестах новый LessonNNSpec.

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

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

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

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

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

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

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

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

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

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

Анатомия 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 в уроке 10.

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

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