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

Кому это. Ты знаешь Effect: понимаешь, что такое Effect<A, E, R>, заводил сервис через Context.Service и слои, открывал ресурс под Scope. Теперь мы возьмём этот инструмент и построим им что-то весомое: маленькую честную реляционную СУБД снизу вверх. Это тот же воркшоп ourdb, что и в TS-треке, но переложенный на Effect. Если ты уже прошёл его на чистом TypeScript, этот урок покажет ту же механику под другим углом: где у голого node:fs был ручной close(), у нас будет финалайзер scope, а где было исключение, будет размеченная ошибка в канале E.

Зачем именно Effect. Движок базы это сплошные ресурсы, которые нельзя забыть закрыть: файловые дескрипторы, кадры буферного пула, локи транзакций. Утечка любого из них это либо повисший файл, либо вечная блокировка. В голом коде за этим следят руками, и одна ветка с ранним return или необработанным исключением всё ломает. Effect переносит эту дисциплину в тип: Scope гарантирует размотку финалайзеров при любом исходе, размеченные ошибки не дают молча проглотить сбой, Stream сканирует кучу без загрузки в память, транзакционная память (TxRef плюс Effect.tx) держит менеджер блокировок. Этот урок закладывает первый камень: DiskManager, чей файловый дескриптор закрывается сам.

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

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

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + TCP-сервер                  │  урок 11
├────────────────────────────────────────────────┤
│  Исполнитель (Volcano) + EXPLAIN                 │  урок 6
│  Планировщик, binder, парсер, лексер             │  уроки 5, 6
├────────────────────────────────────────────────┤
│  Vacuum                                          │  урок 10
│  MVCC (видимость, снимки)                        │  уроки 8, 9
│  Блокировки (2PL), менеджер транзакций           │  уроки 8, 9
│  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 в уроке 10.

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

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

Класс Page: чистые байты, без Effect

Вот первое важное решение порта, и оно тонкое. Страница это обёртка над буфером ровно PAGE_SIZE байт с типизированным доступом к заголовку и слотам. Она не делает ввода-вывода (читать и писать буфер на диск это дело DiskManager) и не держит ресурсов. У неё нет ни одной операции, которая может сбойнуть из-за внешнего мира: всё, что она делает, это арифметика над байтами в памяти.

А раз нет ни ресурсов, ни сбоев из-за окружения, то и Effect тут нечего добавить. Effect<A, E, R> платит за управление ресурсами, размеченными ошибками и контекстом. У чистой работы с байтами ничего из этого нет, поэтому оборачивать её в Effect было бы шумом без пользы. Поэтому класс Page в Effect-порте дословно совпадает с эталоном на голом TypeScript. Это общий принцип всего воркшопа: Effect появляется ровно там, где есть ресурс, сбой или зависимость, и не раньше. Чистое ядро остаётся чистым.

Константы: один раз и навсегда

Сначала вынесем все размеры и смещения в отдельный файл constants.ts. Когда у тебя пять реализаций на разных языках, единственный способ их синхронизировать это держать раскладку в одном месте на каждую.

// src/constants.ts

/** Размер страницы в байтах. Фиксированный, как у Postgres. */
export const PAGE_SIZE = 8192;

/** Размер заголовка slotted page до массива слотов. */
export const HEADER_SIZE = 16;

/** Размер одного слота: u16 со смещением кортежа внутри страницы. */
export const SLOT_SIZE = 2;

/** Смещения полей заголовка страницы. */
export const PageOffset = {
  lsn: 0,
  lower: 8,
  upper: 10,
  special: 12,
  flags: 14,
} as const;

/**
 * Сентинел мёртвого слота. Удаление кортежа пишет в слот 0: живой кортеж всегда
 * лежит по смещению не меньше HEADER_SIZE, поэтому 0 не пересекается с реальным.
 * Физически место освобождает vacuum (урок 10).
 */
export const DEAD_SLOT = 0;

Заметь сентинел DEAD_SLOT = 0. Слот хранит смещение кортежа внутри страницы. Живой кортеж не может лежать в первых 16 байтах, там заголовок, значит его смещение всегда не меньше HEADER_SIZE. Поэтому значение 0 в слоте мы используем как метку “слот мёртв”, не вводя отдельный бит. Удаление это запись нуля в слот.

Буфер и DataView

Теперь сам класс. В Node байты живут в Buffer, это наследник Uint8Array. Читать и писать многобайтовые числа удобнее через DataView: у него есть методы getUint16, setBigUint64 и так далее с явным указанием порядка байтов.

// src/page.ts
import {
  DEAD_SLOT,
  HEADER_SIZE,
  PAGE_SIZE,
  PageOffset,
  SLOT_SIZE,
} from '~/constants.ts';

export class Page {
  /** Сырой буфер страницы. DiskManager пишет на диск именно его. */
  readonly buffer: Buffer;

  private readonly view: DataView;

  private constructor(buffer: Buffer) {
    this.buffer = buffer;
    this.view = new DataView(buffer.buffer, buffer.byteOffset, buffer.byteLength);
  }

  /** Свежая страница с инициализированным дефолтами заголовком. */
  static empty(): Page {
    const page = new Page(Buffer.alloc(PAGE_SIZE));
    page.lsn = 0n;
    page.lower = HEADER_SIZE;
    page.upper = PAGE_SIZE;
    page.special = PAGE_SIZE;
    page.flags = 0;
    return page;
  }

  /** Обернуть уже прочитанный буфер. Длина обязана быть PAGE_SIZE. */
  static from(buffer: Buffer): Page {
    if (buffer.byteLength !== PAGE_SIZE) {
      throw new RangeError(`page buffer must be ${PAGE_SIZE} bytes, got ${buffer.byteLength}`);
    }
    return new Page(buffer);
  }

  // ... аксессоры и методы дальше
}

Конструктор приватный, а создаём страницы мы через два статических метода: Page.empty() для новой страницы с проинициализированным заголовком, Page.from(buffer) чтобы обернуть буфер, который DiskManager только что прочитал с диска. Снаружи нельзя случайно создать страницу неправильного размера.

DataView мы строим над тем же куском памяти, что и Buffer: buffer.buffer это нижележащий ArrayBuffer, а byteOffset/byteLength нужны потому, что Buffer в Node может быть срезом большого общего пула. Без них DataView смотрел бы не туда. Это классическая засада с Buffer, держи её в голове.

Заголовок: геттеры и сеттеры

Каждое поле заголовка это пара геттер плюс сеттер поверх DataView. Второй аргумент true означает little-endian.

  get lsn(): bigint {
    return this.view.getBigUint64(PageOffset.lsn, true);
  }
  set lsn(value: bigint) {
    this.view.setBigUint64(PageOffset.lsn, value, true);
  }

  get lower(): number {
    return this.view.getUint16(PageOffset.lower, true);
  }
  set lower(value: number) {
    this.view.setUint16(PageOffset.lower, value, true);
  }

  get upper(): number {
    return this.view.getUint16(PageOffset.upper, true);
  }
  set upper(value: number) {
    this.view.setUint16(PageOffset.upper, value, true);
  }

  get special(): number {
    return this.view.getUint16(PageOffset.special, true);
  }
  set special(value: number) {
    this.view.setUint16(PageOffset.special, value, true);
  }

  get flags(): number {
    return this.view.getUint16(PageOffset.flags, true);
  }
  set flags(value: number) {
    this.view.setUint16(PageOffset.flags, value, true);
  }

Обрати внимание: lsn это bigint, а не number. LSN это u64, 8 байт, и значения там легко выходят за Number.MAX_SAFE_INTEGER. В JavaScript единственный честный способ работать с 64-битными целыми это bigint, поэтому методы getBigUint64/setBigUint64 возвращают и принимают bigint. Остальные поля заголовка это u16, для них хватает обычного number.

Зачем заголовок вообще нужен, нельзя ли хранить lower/upper в самом объекте Page? Нельзя, и это принципиально. Эти числа должны лежать в байтах страницы, потому что именно эти байты уйдут на диск и вернутся при следующем чтении. Объект Page живёт только в памяти и исчезнет. Истина это буфер, а геттеры и сеттеры лишь типизированный вид на него.

Слоты и свободное место

Число слотов выводится из lower: массив слотов начинается с HEADER_SIZE, каждый слот занимает SLOT_SIZE байт, поэтому (lower - HEADER_SIZE) / SLOT_SIZE это сколько слотов уже есть.

  /** Число слотов в массиве слотов (выводится из lower). */
  get slotCount(): number {
    return (this.lower - HEADER_SIZE) / SLOT_SIZE;
  }

  /** Свободное место между концом слотов и началом данных. */
  get freeSpace(): number {
    return this.upper - this.lower;
  }

  /** Смещение кортежа, на которое указывает слот index. */
  getSlot(index: number): number {
    return this.view.getUint16(this.slotOffset(index), true);
  }

  /** Записать в слот index смещение кортежа. */
  setSlot(index: number, offset: number): void {
    this.view.setUint16(this.slotOffset(index), offset, true);
  }

  /** Живой ли слот (указывает на кортеж, а не помечен как мёртвый). */
  isSlotLive(slot: number): boolean {
    return this.getSlot(slot) !== DEAD_SLOT;
  }

  private slotOffset(index: number): number {
    return HEADER_SIZE + index * SLOT_SIZE;
  }

slotCount и freeSpace не хранят ничего своего: они каждый раз пересчитываются из заголовка. Так не бывает рассинхрона между “что мы думаем” и “что в байтах”.

Вставка кортежа в страницу

Главный метод. Он кладёт сырые байты кортежа в страницу: данные у upper (сдвигая его влево), слот у lower (сдвигая его вправо). О формате этих байтов страница ничего не знает, для неё кортеж это непрозрачный кусок данных. Сериализацию кортежа мы напишем в уроке 3.

  /**
   * Положить сырые байты кортежа в страницу. Данные ложатся у upper (сдвигая его
   * влево), слот добавляется у lower (сдвигая его вправо). Возвращает номер слота
   * или null, если свободного места меньше, чем нужно под данные плюс слот.
   */
  insertTuple(data: Buffer): number | null {
    const required = data.byteLength + SLOT_SIZE;
    if (required > this.freeSpace) {
      return null;
    }
    const tupleOffset = this.upper - data.byteLength;
    data.copy(this.buffer, tupleOffset);
    this.upper = tupleOffset;
    const slot = this.slotCount;
    this.setSlot(slot, tupleOffset);
    this.lower = this.lower + SLOT_SIZE;
    return slot;
  }

  /** Пометить слот мёртвым. Место не уплотняется, это работа vacuum (урок 10). */
  deleteSlot(slot: number): void {
    this.setSlot(slot, DEAD_SLOT);
  }

Разберём insertTuple по шагам, это смысловой центр всего урока.

Считаем, сколько места нужно: байты кортежа плюс один новый слот (SLOT_SIZE). Если это больше свободного места, страница полна, возвращаем null. Вызывающий код (слой кучи в уроке 3) поймёт, что надо взять другую страницу.
Считаем смещение, куда лягут данные: upper - data.byteLength.
data.copy(this.buffer, tupleOffset) копирует байты кортежа в буфер страницы.
Двигаем upper влево, на новое начало области данных.
Номер нового слота это текущий slotCount. Пишем в этот слот смещение кортежа.
Двигаем lower вправо на один слот.

Заметь: insertTuple возвращает number | null, а не бросает и не оборачивается в Effect. “Места не хватило” это не сбой и не ошибка, а ожидаемый ответ, на который у вызывающего кода есть план (взять другую страницу). Размечать его в канал ошибок было бы перебором. Это та же логика, по которой точечные промахи в Effect-порте мы будем отдавать через Option, а не через E: отсутствие результата это нормальный исход, ошибка это сбой окружения.

deleteSlot теперь читается тривиально: пишем DEAD_SLOT (то есть 0) в слот. Данные остаются в области данных, upper не двигается, свободное место не растёт. Это ровно то, что ты видел в виджете: удаление логическое, физическое уплотнение откладывается до vacuum. Почему так? Потому что физическое уплотнение дорого, а ещё потому, что в уроке 8 появится MVCC: “удалённый” кортеж может быть ещё виден старой транзакции, и трогать его рано нельзя.

дальше после входа

Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.

Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.

войти