Раздел 10 · Databases

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

senior~90 мин

без входаВойди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти

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

Кому это. В уроке 1 ты сделал страницу: slotted page умеет принять сырые байты кортежа, выдать слот и пометить слот мёртвым. В уроке 2 ты поставил поверх диска буферный пул: горячие страницы живут в памяти, грязные безопасно доезжают до диска. Но пока движок умеет хранить только безымянные байты. Страница не знает, что в ней лежит строка с колонками id, name, active. Этот урок вводит понятие таблицы и записи.

Зачем. Таблица в реляционной СУБД это не одна структура, а два слоя, которые легко спутать. Нижний это куча: физический набор страниц, в которых строки лежат как попало, без всякого порядка. Верхний это индексы, которые наводят на кучу порядок и быстрый поиск (урок 4). Сегодня мы строим кучу: как разложить строку по байтам, как адресовать её через RID, как вставить и как обойти всю таблицу sequential-сканом. Без этого слоя не на чем строить ни SQL, ни индексы, ни транзакции.

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

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

┌────────────────────────────────────────────────┐
│  Бинарный протокол + 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
└────────────────────────────────────────────────┘

Куча ляжет ровно поверх буферного пула. Когда нужна страница, куча зовёт fetchPage, поработав с буфером зовёт unpinPage. На диск напрямую куча не ходит вообще: за неё это делает пул. Так слои и собираются один над другим.

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

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

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

Идём снизу вверх: схема, потом кортеж, потом куча.

Schema: форма строки

Минимальный набор типов из контракта: int (8 байт, знаковый), text (UTF-8 переменной длины), bool (1 байт). Этого хватает на весь воркшоп, расширение типов вынесено в упражнения. Схема это просто упорядоченный список колонок.

// src/schema.ts
export type ColumnType = 'int' | 'text' | 'bool';

export interface Column {
  readonly name: string;
  readonly type: ColumnType;
}

export class Schema {
  readonly columns: readonly Column[];

  constructor(columns: readonly Column[]) {
    if (columns.length === 0) {
      throw new RangeError('schema must have at least one column');
    }
    this.columns = columns;
  }

  /** Число колонок (nattrs в заголовке кортежа). */
  get size(): number {
    return this.columns.length;
  }

  /** Индекс колонки по имени, бросает при отсутствии. */
  columnIndex(name: string): number {
    const index = this.columns.findIndex((column) => column.name === name);
    if (index === -1) {
      throw new RangeError(`unknown column "${name}"`);
    }
    return index;
  }
}

Порядок колонок это часть контракта, а не деталь. Сериализация пишет значения в порядке колонок, разбор читает в том же порядке. Поменяешь местами две колонки в схеме, и старые байты прочитаются неверно. columnIndex понадобится в уроке 6, когда binder будет переводить имя колонки из SQL в её позицию, но завести его удобно сразу.

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

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

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

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

Два слова про числа. int это знаковое 64-битное число, и в JavaScript обычный number его не вместит без потери точности (number теряет точность за пределами 2^53). Поэтому значение int у нас это bigint, не number. В коде это значит 42n, а не 42.

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

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

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

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

Константы заголовка кортежа

Добавь к constants.ts, который ты завёл в уроке 1 (там уже лежат PAGE_SIZE, HEADER_SIZE, SLOT_SIZE и смещения заголовка страницы), смещения заголовка кортежа.

// src/constants.ts (добавляем к написанному в уроке 1)

/** Размер заголовка кортежа до null bitmap (см. контракт). */
export const TUPLE_HEADER_SIZE = 12;

/** Смещения полей заголовка кортежа. */
export const TupleOffset = {
  xmin: 0,
  xmax: 4,
  infomask: 8,
  nattrs: 10,
  nullBitmap: 12,
} as const;

/** Бит infomask: в кортеже есть хотя бы один NULL, значит null bitmap значим. */
export const INFOMASK_HAS_NULL = 0x00_01;

infomask это набор битовых флагов про кортеж. Пока флаг один, HAS_NULL. В уроке 9 здесь появится второй бит (заморозка версии для vacuum), поэтому держим это битовой маской, а не булевым полем.

Tuple: значения плюс заголовок

Теперь сам кортеж. Значения строки плюс заголовок версии, и методы сериализации в обе стороны. Сначала каркас класса.

// src/tuple.ts
import { INFOMASK_HAS_NULL, TUPLE_HEADER_SIZE, TupleOffset } from '~/constants.ts';
import type { ColumnType, Schema } from '~/schema.ts';

/** Идентификатор транзакции. До урока 7 это просто число, которым штампуют xmin. */
export type Xid = number;

/** Значение колонки. int это bigint (8 байт знаковый), text это string, bool это boolean. */
export type Value = bigint | string | boolean | null;

export interface TupleHeader {
  readonly xmin: Xid;
  readonly xmax: Xid;
}

const EMPTY_HEADER: TupleHeader = { xmin: 0, xmax: 0 };

export class Tuple {
  readonly values: readonly Value[];
  readonly xmin: Xid;
  readonly xmax: Xid;

  constructor(values: readonly Value[], header: TupleHeader = EMPTY_HEADER) {
    this.values = values;
    this.xmin = header.xmin;
    this.xmax = header.xmax;
  }

  /** Та же строка с новым заголовком версии. Удобно при вставке (проставить xmin). */
  withHeader(header: TupleHeader): Tuple {
    return new Tuple(this.values, header);
  }

  // serialize и deserialize ниже
}

Tuple иммутабелен: значения и заголовок только для чтения. Чтобы проставить xmin при вставке, мы не мутируем кортеж, а делаем новый через withHeader. Это пригодится в уроке 8, где версия строки не должна меняться под читающей транзакцией.

serialize: строка в байты

  /** Сериализовать кортеж в байты по схеме. */
  serialize(schema: Schema): Buffer {
    const nattrs = schema.size;
    if (this.values.length !== nattrs) {
      throw new RangeError(`tuple has ${this.values.length} values, schema expects ${nattrs}`);
    }

    const bitmapBytes = Math.ceil(nattrs / 8);
    const bitmap = Buffer.alloc(bitmapBytes);
    const dataChunks: Buffer[] = [];
    let hasNull = false;

    for (const [index, column] of schema.columns.entries()) {
      const value = this.values[index];
      if (value === null || value === undefined) {
        hasNull = true;
        bitmap[Math.floor(index / 8)]! |= 1 << (index % 8);
        continue;
      }
      dataChunks.push(encodeValue(column.type, value));
    }

    const infomask = hasNull ? INFOMASK_HAS_NULL : 0;
    const header = Buffer.alloc(TUPLE_HEADER_SIZE);
    header.writeUInt32LE(this.xmin >>> 0, TupleOffset.xmin);
    header.writeUInt32LE(this.xmax >>> 0, TupleOffset.xmax);
    header.writeUInt16LE(infomask, TupleOffset.infomask);
    header.writeUInt16LE(nattrs, TupleOffset.nattrs);

    return Buffer.concat([header, bitmap, ...dataChunks]);
  }

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

  1. Проверка. Число значений обязано совпадать с числом колонок схемы. Несовпадение это ошибка вызывающего, и лучше упасть тут, чем записать кривой кортеж.
  2. Bitmap. На nattrs колонок нужно ceil(nattrs / 8) байт (по биту на колонку). Аллоцируем нулями.
  3. Проход по колонкам. Для каждой колонки берём её значение. Если NULL, поднимаем флаг hasNull и зажигаем бит колонки в bitmap: bitmap[index / 8] |= 1 << (index % 8). Байт по индексу index / 8, бит по позиции index % 8 внутри байта. В data ничего не кладём. Если значение есть, кодируем его по типу колонки (encodeValue ниже) и копим чанк.
  4. Заголовок. 12 байт. xmin/xmax как u32 LE. infomask поднимает HAS_NULL, если был хоть один NULL. nattrs это число колонок, оно понадобится при разборе, чтобы знать размер bitmap, не имея схемы под рукой.
  5. Склейка. Buffer.concat сшивает заголовок, bitmap и все чанки данных в один буфер.

Восклицательный знак в bitmap[...]! это non-null assertion: индекс Math.floor(index / 8) гарантированно в пределах bitmapBytes, потому что index < nattrs, а байт мы выделили под все колонки. С noUncheckedIndexedAccess компилятор об этом не знает, поэтому мы говорим ему явно. this.xmin >>> 0 приводит число к беззнаковому 32-битному, страхуясь от отрицательных или дробных значений в xmin.

encodeValue: одно значение по типу

/** Закодировать одно ненулевое значение по типу колонки. */
function encodeValue(type: ColumnType, value: Exclude<Value, null>): Buffer {
  switch (type) {
    case 'int': {
      if (typeof value !== 'bigint') {
        throw new TypeError(`int column expects bigint, got ${typeof value}`);
      }
      const buffer = Buffer.alloc(8);
      buffer.writeBigInt64LE(value);
      return buffer;
    }
    case 'bool': {
      if (typeof value !== 'boolean') {
        throw new TypeError(`bool column expects boolean, got ${typeof value}`);
      }
      return Buffer.from([value ? 1 : 0]);
    }
    case 'text': {
      if (typeof value !== 'string') {
        throw new TypeError(`text column expects string, got ${typeof value}`);
      }
      const utf8 = Buffer.from(value, 'utf8');
      const length = Buffer.alloc(4);
      length.writeUInt32LE(utf8.byteLength);
      return Buffer.concat([length, utf8]);
    }
  }
}

Три типа, три кодека. int это 8 байт через writeBigInt64LE, знаковый little-endian, без ручной разбивки на половины. bool это один байт, 0 или 1. text это самое интересное: сначала длина в байтах как u32, потом сами байты UTF-8. Длину храним в байтах, а не в символах, потому что разбору важно знать, сколько байт прочитать, а один символ это не один байт (кириллица занимает два, эмодзи четыре). Проверки типа в каждой ветке ловят рассогласование между схемой и значением рано: положишь строку в int, упадёшь с понятным сообщением, а не запишешь мусор.

switch по type исчерпывающий: три варианта ColumnType покрыты, и компилятор это видит. В порт-языках ту же роль играет match (Rust, Haskell), Match в Effect, type switch в Go. В эталоне (см. examples/our-db/ts/README.md) ветвление по таким union-типам идёт через ts-pattern, мы держим обычный switch ради прозрачности листинга.

deserialize: байты в строку

Разбор это зеркало. Дано: буфер, смещение начала кортежа в нём и схема. Надо собрать Tuple.

  /** Разобрать кортеж из буфера, начиная со смещения offset, по схеме. */
  static deserialize(buffer: Buffer, offset: number, schema: Schema): Tuple {
    const xmin = buffer.readUInt32LE(offset + TupleOffset.xmin);
    const xmax = buffer.readUInt32LE(offset + TupleOffset.xmax);
    const infomask = buffer.readUInt16LE(offset + TupleOffset.infomask);
    const nattrs = buffer.readUInt16LE(offset + TupleOffset.nattrs);
    if (nattrs !== schema.size) {
      throw new RangeError(`tuple has ${nattrs} attrs, schema expects ${schema.size}`);
    }

    const hasNull = (infomask & INFOMASK_HAS_NULL) !== 0;
    const bitmapStart = offset + TUPLE_HEADER_SIZE;
    const bitmapBytes = Math.ceil(nattrs / 8);
    let cursor = bitmapStart + bitmapBytes;

    const values: Value[] = [];
    for (const [index, column] of schema.columns.entries()) {
      const isNull =
        hasNull && (buffer[bitmapStart + Math.floor(index / 8)]! & (1 << (index % 8))) !== 0;
      if (isNull) {
        values.push(null);
        continue;
      }
      const [value, next] = decodeValue(column.type, buffer, cursor);
      values.push(value);
      cursor = next;
    }

    return new Tuple(values, { xmin, xmax });
  }

Шаги такие же, в обратную сторону.

  1. Заголовок. Читаем xmin, xmax, infomask, nattrs по смещениям от offset. Сверяем nattrs со схемой: если кортеж записан под другую схему, лучше упасть, чем выдать мусор.
  2. Курсор. Данные начинаются сразу за заголовком и bitmap. cursor это где мы сейчас читаем в области данных, он ползёт вперёд по мере чтения колонок.
  3. Проход по колонкам. Для каждой колонки сначала проверяем бит в bitmap (только если hasNull, иначе бит точно погашен). NULL значит в data ничего не было, кладём null и не двигаем курсор. Иначе читаем значение через decodeValue, который возвращает само значение и смещение сразу за ним, и сдвигаем курсор туда.

Заметь, как важна тут проверка NULL первой. Если бы мы попытались прочитать значение NULL-колонки из data, мы бы прочитали байты следующей колонки и сбили курсор на всё остальное. Bitmap говорит, какие колонки в data вообще присутствуют.

/** Декодировать одно значение, вернуть его и смещение сразу за ним. */
function decodeValue(type: ColumnType, buffer: Buffer, offset: number): [Value, number] {
  switch (type) {
    case 'int': {
      return [buffer.readBigInt64LE(offset), offset + 8];
    }
    case 'bool': {
      return [buffer.readUInt8(offset) !== 0, offset + 1];
    }
    case 'text': {
      const length = buffer.readUInt32LE(offset);
      const start = offset + 4;
      return [buffer.toString('utf8', start, start + length), start + length];
    }
  }
}

Каждый кодек возвращает пару: значение и новое смещение. Для int это offset + 8, для bool это offset + 1, для text это start + length (за длиной и за байтами строки). Возврат смещения из декодера это и есть то, что двигает курсор в deserialize: декодер сам знает, сколько байт он съел.

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

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

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

войти