Своя СУБД на TS · урок 7: журнал упреждающей записи и восстановление

Кому это. К этому уроку у тебя собран целый движок. В уроке 6 появилась верхняя половина: каталог, binder, планировщик, исполнитель. Из встроенного REPL уже бегут CREATE TABLE, INSERT, SELECT ... WHERE, и EXPLAIN печатает план. Но у движка есть дыра, и ты её, наверное, уже почувствовал.

Зачем. Убей процесс посреди работы и перезапусти. Что осталось на диске? Часть данных лежит только в буферном пуле, в памяти, и при падении испаряется. Хуже того: одна логическая операция может затронуть несколько страниц, и если упасть между ними, на диске останется полузапись. Сегодня мы закрываем половину этой дыры. Появится журнал упреждающей записи (WAL) и восстановление после падения. К концу урока INSERT будет переживать kill процесса: старт прочитает журнал и воспроизведёт потерянное.

Важно про объём. Это первый из двух уроков про долговечность и транзакции. Сегодня мы делаем механику журнала и восстановления на самом простом пути: одиночная вставка в режиме autocommit. Транзакций, отката и удаления через версии ещё нет, это следующий урок. Мы честно проговорим, что именно пока не долговечно, и почему для удаления нужно сначала научить кортежи версионированию. Хорошая новость: исполнитель из урока 6 сегодня не меняется вообще. Вся работа в новом слое журнала и в проводке его к диску.

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

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

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

Что теряется при падении

Вспомни путь вставки из уроков 3 и 6. INSERT зовёт heap.insertTuple, та кладёт кортеж в страницу буферного пула и помечает её грязной. Грязная страница на диск не идёт сразу: буферный пул сбрасывает её лениво, при вытеснении или при flushAll. Это правильно для скорости (диск медленный, в память пишем часто), но смертельно для долговечности: между вставкой и сбросом страница живёт только в оперативной памяти. Питание выключили, процесс убили, и кортеж исчез, хотя клиенту мы уже сказали “готово”.

Решение не в том, чтобы форсить страницу данных на диск на каждой вставке (это вернуло бы нас к медленному диску и не спасло бы от полузаписей на несколько страниц). Решение в журнале. Идея write-ahead такая: перед тем как менять данные, опиши изменение маленькой записью в отдельный журнал и форсни журнал на диск. Журнал пишется только в конец (это дёшево, диск любит последовательную запись), а страницы данных пусть сбрасываются лениво как раньше. Если упали, при старте читаем журнал и заново применяем (redo) всё, что журнал успел зафиксировать, а данные не успели.

Константы журнала

Запись журнала это самоописывающий блок: заголовок фиксированной формы, переменный payload и контрольная сумма. Добавь в src/constants.ts (числа на диске little-endian, как и всё в нашем формате).

// src/constants.ts (добавляем)

/**
 * Константы WAL (см. SPEC.md, раздел "Запись WAL"). Журнал это последовательность
 * самоописывающих записей переменной длины, числа little-endian.
 */

/** Заголовок записи WAL до payload: lsn u64, prev_lsn u64, xid u32, type u16, length u32. */
export const WAL_RECORD_HEADER_SIZE = 26;

/** Смещения полей заголовка записи WAL. */
export const WalOffset = {
  lsn: 0,
  prevLsn: 8,
  xid: 16,
  type: 20,
  length: 22,
} as const;

/**
 * Типы записей WAL. Сегодня нужны create и insert; begin/commit/abort/setXmax/checkpoint
 * появятся в следующем уроке вместе с транзакциями. Тип 6 (физический DELETE) сознательно
 * пропущен: удаление будет журналироваться через setXmax, поэтому номер 6 не занимаем.
 */
export const WalRecordType = {
  begin: 1,
  commit: 2,
  abort: 3,
  create: 4,
  insert: 5,
  checkpoint: 7,
  setXmax: 8,
} as const;

Разберём заголовок. lsn это номер записи, он растёт монотонно. prev_lsn пригодится в следующем уроке для цепочки записей одной транзакции (сегодня пишем туда 0). xid это номер транзакции; сегодня все вставки идут под одним фиктивным xid, и при восстановлении мы его игнорируем, но поле в формате уже есть. type это код типа записи, length это длина payload. Мы сразу заводим полный набор типов, хотя сегодня используем только create и insert: формат байтов это контракт, и менять его задним числом дороже, чем определить с запасом.

Журнал: WalManager

Теперь сам журнал. Положи в src/wal.ts. Начнём с кодека записи: как байты записи кодируются и декодируются. Это самая ответственная часть, потому что на ней стоит восстановление.

// src/wal.ts
import {
  closeSync,
  constants,
  fstatSync,
  fsyncSync,
  openSync,
  readSync,
  writeSync,
} from 'node:fs';
import { crc32 } from 'node:zlib';

import { PAGE_SIZE, WAL_RECORD_HEADER_SIZE, WalOffset, WalRecordType } from '~/constants.ts';

export interface WalRecord {
  readonly lsn: bigint;
  readonly prevLsn: bigint;
  readonly xid: number;
  readonly type: number;
  readonly payload: Buffer;
}

const CRC_SIZE = 4;

export function encodeRecord(
  lsn: bigint,
  previousLsn: bigint,
  xid: number,
  type: number,
  payload: Buffer,
): Buffer {
  const body = Buffer.alloc(WAL_RECORD_HEADER_SIZE + payload.byteLength);
  body.writeBigUInt64LE(lsn, WalOffset.lsn);
  body.writeBigUInt64LE(previousLsn, WalOffset.prevLsn);
  body.writeUInt32LE(xid, WalOffset.xid);
  body.writeUInt16LE(type, WalOffset.type);
  body.writeUInt32LE(payload.byteLength, WalOffset.length);
  payload.copy(body, WAL_RECORD_HEADER_SIZE);

  const full = Buffer.alloc(body.byteLength + CRC_SIZE);
  body.copy(full, 0);
  full.writeUInt32LE(crc32(body) >>> 0, body.byteLength);
  return full;
}

encodeRecord собирает запись: заголовок, payload, и в хвост CRC32 по всему телу (заголовок плюс payload). Контрольная сумма ловит оборванную или побитую запись: если процесс убили посреди write, последняя запись окажется неполной, CRC не сойдётся, и мы её отбросим. Это критично, ведь журнал это последняя линия обороны, и доверять ему можно, только если он сам себя проверяет.

// src/wal.ts (продолжение)

/**
 * Разобрать все целые записи. Останавливается на первой оборванной или повреждённой
 * (один последовательный писатель, поэтому рваная запись всегда последняя). validEnd
 * это смещение сразу за последней целой записью, туда пойдут будущие дозаписи.
 */
export function decodeWal(buffer: Buffer): { records: WalRecord[]; validEnd: number } {
  const records: WalRecord[] = [];
  let offset = 0;
  while (offset + WAL_RECORD_HEADER_SIZE <= buffer.byteLength) {
    const length = buffer.readUInt32LE(offset + WalOffset.length);
    if (length > PAGE_SIZE) {
      break;
    }
    const bodyEnd = offset + WAL_RECORD_HEADER_SIZE + length;
    const recordEnd = bodyEnd + CRC_SIZE;
    if (recordEnd > buffer.byteLength) {
      break;
    }
    const body = buffer.subarray(offset, bodyEnd);
    if (crc32(body) >>> 0 !== buffer.readUInt32LE(bodyEnd)) {
      break;
    }
    records.push({
      lsn: buffer.readBigUInt64LE(offset + WalOffset.lsn),
      prevLsn: buffer.readBigUInt64LE(offset + WalOffset.prevLsn),
      xid: buffer.readUInt32LE(offset + WalOffset.xid),
      type: buffer.readUInt16LE(offset + WalOffset.type),
      payload: Buffer.from(buffer.subarray(offset + WAL_RECORD_HEADER_SIZE, bodyEnd)),
    });
    offset = recordEnd;
  }
  return { records, validEnd: offset };
}

decodeWal идёт по буферу запись за записью и останавливается на первой проблемной. Три проверки до того, как поверить записи. Длина больше размера страницы это явный мусор (поле длины побилось), останавливаемся, не пытаясь выделить гигантский буфер. Запись не помещается до конца файла, значит её оборвали на полуслове, останавливаемся. CRC не сошёлся, останавливаемся. Поскольку писатель один и пишет только в конец, испорченной может быть лишь последняя запись, поэтому остановка на первой проблеме безопасна. validEnd это смещение конца последней целой записи: с него продолжит писать WalManager, затерев огрызок.

Теперь payload-кодеки. Сегодня нужны два: для CREATE (DDL воспроизводится при старте, чтобы пересобрать каталог) и для INSERT (образ кортежа плюс его адрес).

// src/wal.ts (продолжение)

const RELID_SIZE = 4;
const PAGE_ID_SIZE = 4;
const SLOT_SIZE_BYTES = 2;

export function encodeCreatePayload(relationId: number, sql: string): Buffer {
  const head = Buffer.alloc(RELID_SIZE);
  head.writeUInt32LE(relationId, 0);
  return Buffer.concat([head, Buffer.from(sql, 'utf8')]);
}

export function decodeCreatePayload(payload: Buffer): { relationId: number; sql: string } {
  return { relationId: payload.readUInt32LE(0), sql: payload.toString('utf8', RELID_SIZE) };
}

export function encodeInsertPayload(
  relationId: number,
  pageId: number,
  slot: number,
  image: Buffer,
): Buffer {
  const head = Buffer.alloc(RELID_SIZE + PAGE_ID_SIZE + SLOT_SIZE_BYTES);
  head.writeUInt32LE(relationId, 0);
  head.writeUInt32LE(pageId, RELID_SIZE);
  head.writeUInt16LE(slot, RELID_SIZE + PAGE_ID_SIZE);
  return Buffer.concat([head, image]);
}

export function decodeInsertPayload(payload: Buffer): {
  relationId: number;
  pageId: number;
  slot: number;
  image: Buffer;
} {
  const imageStart = RELID_SIZE + PAGE_ID_SIZE + SLOT_SIZE_BYTES;
  return {
    relationId: payload.readUInt32LE(0),
    pageId: payload.readUInt32LE(RELID_SIZE),
    slot: payload.readUInt16LE(RELID_SIZE + PAGE_ID_SIZE),
    image: Buffer.from(payload.subarray(imageStart)),
  };
}

CREATE несёт id отношения и DDL-строку (тот самый канонический SQL, который печатает prettyPrint из урока 5). INSERT несёт id отношения, адрес (pageId, slot) и сам образ сериализованного кортежа. Образ это физическое логирование: мы пишем целые байты кортежа, и redo просто положит их обратно. Это самый простой и надёжный способ, ценой объёма журнала; экономичный вариант в упражнениях.

Осталось ядро: сам менеджер журнала.

// src/wal.ts (продолжение)

export class WalManager {
  private readonly fileDescriptor: number;
  private writeOffset: number;
  private nextLsn: bigint;
  private flushedLsn: bigint;
  private pending: Buffer[] = [];

  private constructor(
    fileDescriptor: number,
    writeOffset: number,
    nextLsn: bigint,
    flushedLsn: bigint,
  ) {
    this.fileDescriptor = fileDescriptor;
    this.writeOffset = writeOffset;
    this.nextLsn = nextLsn;
    this.flushedLsn = flushedLsn;
  }

  /** Открыть журнал, продолжить нумерацию после существующих записей. */
  static open(filePath: string): WalManager {
    const fileDescriptor = openSync(filePath, constants.O_RDWR | constants.O_CREAT, 0o644);
    const { records, validEnd } = decodeWal(readFile(fileDescriptor));
    const last = records.at(-1);
    const maxLsn = last === undefined ? 0n : last.lsn;
    return new WalManager(fileDescriptor, validEnd, maxLsn + 1n, maxLsn);
  }

  /** Прочитать все целые записи журнала (для recovery). */
  readAll(): WalRecord[] {
    return decodeWal(readFile(this.fileDescriptor)).records;
  }

  /** Дописать запись, вернуть присвоенный lsn. Журнал на диск пока не идёт. */
  append(xid: number, type: number, payload: Buffer, previousLsn: bigint): bigint {
    const lsn = this.nextLsn;
    this.nextLsn += 1n;
    this.pending.push(encodeRecord(lsn, previousLsn, xid, type, payload));
    return lsn;
  }

  /** Сбросить накопленные записи на диск и форсировать (fsync). */
  flush(): void {
    if (this.pending.length > 0) {
      const batch = Buffer.concat(this.pending);
      writeSync(this.fileDescriptor, batch, 0, batch.byteLength, this.writeOffset);
      this.writeOffset += batch.byteLength;
      this.pending = [];
    }
    fsyncSync(this.fileDescriptor);
    this.flushedLsn = this.nextLsn - 1n;
  }

  /** Правило write-ahead: гарантировать, что журнал durable до указанного lsn. */
  flushUpTo(lsn: bigint): void {
    if (this.flushedLsn < lsn) {
      this.flush();
    }
  }

  /** Наибольший присвоенный lsn (включая ещё не сброшенные записи). */
  get currentLsn(): bigint {
    return this.nextLsn - 1n;
  }

  close(): void {
    closeSync(this.fileDescriptor);
  }
}

function readFile(fileDescriptor: number): Buffer {
  const size = fstatSync(fileDescriptor).size;
  const buffer = Buffer.alloc(size);
  if (size > 0) {
    readSync(fileDescriptor, buffer, 0, size, 0);
  }
  return buffer;
}

Разберём по методам. open читает уже существующий журнал (если файл был), берёт validEnd для дозаписи и продолжает нумерацию lsn с последней записи: журнал переживает перезапуски, нумерация не сбрасывается. append не пишет на диск, а копит запись в pending: множество вставок подряд соберутся в один write, это дешевле, чем дёргать диск на каждой. flush сбрасывает накопленное одним write и форсит fsync, гарантируя durability. После flush обновляем flushedLsn: до какого номера журнал точно на диске. flushUpTo это и есть правило write-ahead в одну строку: если просят durable до некоторого lsn, а мы туда ещё не дотянулись, форсим. Этот метод позовёт буферный пул перед записью грязной страницы.