Своя СУБД на Effect · урок 10: vacuum, заморозка и сборка мёртвых версий

Кому это. В уроке 8 удаление стало MVCC-пометкой, а в уроке 9 транзакции стали конкурировать. Движок честно версионирует строки: DELETE ставит xmax (слот остаётся живым), UPDATE это пометка старой версии плюс вставка новой. У этой схемы есть цена, которую мы до сих пор не платили: мёртвые версии копятся на страницах и таблица распухает.

Зачем. Сегодня пишем vacuum: проход по куче, который находит мёртвые версии, физически уплотняет страницу (возвращая место), и замораживает очень старые живые версии. Заодно станет видно, зачем в уроке 3 удаление было логическим, а в уроке 8 у снимка завёлся xmin: горизонт удаляемости считается ровно по нему.

Зачем именно Effect. Vacuum это первый код в воркшопе, где Effect одновременно делает три вещи разом: страница берётся через withPin под Effect.scoped (как в куче и B+Tree), markDirty (Ref-based из урока 2) сообщает пулу, что изменили, и onRemove (колбэк чистки индекса) тоже Effect, потому что BTree.delete живёт в Effect. Получается естественный композит трёх уроков: ресурс-страница, изменяемое состояние через Ref, и Effect-callback как способ передать чужую процедуру в свой проход. А вот classify, которая считает судьбу каждой версии, остаётся чистой функцией без Effect: ввода-вывода и сбоев у неё нет, ей нужны только Tuple, CommitStatus и horizon. Это и есть граница, к которой мы привыкаем уже десятый урок: Effect там, где ресурс или сбой, чистая функция там, где их нет.

Важно про объём. Vacuum опирается на всё, что мы уже построили: версии и видимость из урока 8, снимки и горизонт из урока 9, перепись слотов из урока 1. Новый файл всего один (vacuum.ts), остальное это небольшие добавки: бит frozen в кортеже, одна ветка в видимости, метод горизонта в менеджере транзакций, примитив переписи страницы. Наш vacuum, как и checkpoint, требует, чтобы не было открытых транзакций: так горизонт и no-steal остаются простыми. Конкурентный vacuum, не мешающий читателям, вынесен в упражнение. Базовая линия урока подаётся без чистки индекса и без подсказки о свободном месте: BTree-delete и FSM это упражнения уроков 4 и 3 соответственно, и vacuum здесь не зависит от их выбора.

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

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

Vacuum это верхний слой транзакционной части. Он читает кучу через буферный пул, решает судьбу каждой версии по снимку-горизонту и переписывает страницу примитивом, который мы добавим в Page.

Идея vacuum

Главная мысль в трёх определениях.

Мёртвая версия это кортеж, который не виден и уже не станет виден никакому живому снимку. Таких два рода. Первый: вставка откатанной транзакции (xmin транзакции, которая получила ROLLBACK). Второй: версия, удалённая зафиксированной транзакцией, чьё удаление видят уже все (xmax зафиксирован и ушёл за горизонт). Их можно физически стереть.

Горизонт удаляемости это та граница, относительно которой считается “давно”. Если открытых транзакций нет, горизонт это следующий xid: всё зафиксированное удаляемо. Если есть, горизонт это минимальный xmin среди их снимков: старая открытая транзакция держит горизонт и не даёт убрать версии, которые она ещё вправе увидеть.

Заморозка решает отдельную, коварную проблему. xid это счётчик конечной разрядности (у нас 32 бита). Рано или поздно он переполнится и пойдёт по кругу. Тогда древний xmin, который раньше был “маленьким и давно зафиксированным”, вдруг окажется “большим”, то есть будто из будущего, и видимость спрячет вечно живую строку. Это xid-wraparound, и в больших базах это реальная авария. Защита проста: версию, чей xmin старше горизонта (её видят все), помечаем битом frozen, и видимость перестаёт сравнивать её xmin со снимком.

Итак, vacuum обходит каждую живую версию и выносит вердикт: удалить (мёртвая), заморозить (давно зафиксированная живая) или оставить.

Бит frozen в кортеже

Сначала научим кортеж нести бит заморозки. Он живёт в infomask заголовка кортежа, рядом с битом HAS_NULL из урока 3. Чистый код, без Effect: байтовый контракт совпадает с TS-треком.

// src/constants.ts (добавляем бит infomask рядом с INFOMASK_HAS_NULL)

/** xmin кортежа заморожен vacuum-ом: версия видна всегда, без сравнения со снимком (урок 10). */
export const INFOMASK_XMIN_FROZEN = 0x00_02;

Теперь поддержим этот бит в Tuple (src/tuple.ts). Заголовок версии получает необязательное поле frozen, появляется метод freeze, а сериализация и разбор учат бит в infomask.

// src/tuple.ts (правки)
import {
  INFOMASK_HAS_NULL,
  INFOMASK_XMIN_FROZEN, // новый импорт
  TUPLE_HEADER_SIZE,
  TupleOffset,
} from '~/constants.ts';

export interface TupleHeader {
  readonly xmin: Xid;
  readonly xmax: Xid;
  /** Заморожена ли версия vacuum-ом (урок 10). По умолчанию false. */
  readonly frozen?: boolean;
}

// в классе Tuple: новое поле и его инициализация в конструкторе
  /** xmin заморожен vacuum-ом: версия видна по xmin всегда (урок 10). */
  readonly frozen: boolean;
  // constructor(...) { ...; this.frozen = header.frozen ?? false; }

  /** Замороженная копия версии: xmin/xmax/values те же, бит frozen поднят. */
  freeze(): Tuple {
    return new Tuple(this.values, { xmin: this.xmin, xmax: this.xmax, frozen: true });
  }

В serialize бит подмешивается в infomask рядом с HAS_NULL, а в deserialize читается обратно:

// src/tuple.ts (serialize: формирование infomask)
    const infomask =
      (hasNull ? INFOMASK_HAS_NULL : 0) | (this.frozen ? INFOMASK_XMIN_FROZEN : 0);

// src/tuple.ts (deserialize: чтение бита и передача в конструктор)
    const frozen = (infomask & INFOMASK_XMIN_FROZEN) !== 0;
    // ...
    return new Tuple(values, { xmin, xmax, frozen });

Бит занимает место, которое в infomask уже было зарезервировано: формат страницы не меняется, только смысл одного флага. Поэтому замороженная версия на диске занимает столько же байт, сколько незамороженная, и старые файлы (где бит не выставлен) читаются как frozen: false.

Видимость замороженной версии

Замороженный кортеж виден всегда. Это ровно одна вставка в isVisible из урока 8: создатель версии считается видимым либо потому, что версия заморожена, либо как раньше (своя вставка или зафиксирован к снимку). В src/snapshot.ts.

// src/snapshot.ts (isVisible, изменённая первая проверка)

export function isVisible(
  tuple: Tuple,
  snapshot: Snapshot,
  self: Xid,
  status: CommitStatus,
): boolean {
  const inserterVisible =
    tuple.frozen || tuple.xmin === self || committedAsOf(tuple.xmin, snapshot, status);
  if (!inserterVisible) {
    return false;
  }
  if (tuple.xmax === 0) {
    return true;
  }
  const deleted = tuple.xmax === self || committedAsOf(tuple.xmax, snapshot, status);
  return !deleted;
}

Всё остальное в isVisible без изменений: бит frozen влияет только на видимость создателя, а удаление (xmax) проверяется как прежде. Замороженная, но потом удалённая версия по-прежнему скрывается её xmax. Заморозка это про “вставка видна вечно”, а не “версия бессмертна”.

Горизонт удаляемости

Vacuum должен знать горизонт, и менеджер транзакций его уже почти умеет считать: у каждого открытого снимка есть xmin (самый старый активный xid), который мы завели в уроке 8 как раз “для vacuum в будущем”. Добавь метод в src/transaction.ts. Это синхронный метод (как flushableLsn, openXids, watermark): доступ к active Map и сравнение xid не требуют ни ввода-вывода, ни сбоев, поэтому Effect ничего не добавит.

// src/transaction.ts (метод TransactionManager)

  /**
   * Горизонт vacuum (RecentGlobalXmin): наименьший xid, ещё релевантный живому снимку.
   * Без открытых транзакций это следующий xid (всё зафиксированное удаляемо). Иначе
   * минимум snapshot.xmin по открытым транзакциям. Версия с xmax ниже горизонта (и
   * зафиксированным удалением) мертва для всех; версия с xmin ниже горизонта (зафиксированная
   * вставка) видна всем и её можно заморозить.
   */
  const vacuumHorizon = (): Xid => {
    if (active.size === 0) {
      return nextXid;
    }
    let horizon = nextXid;
    for (const txn of active.values()) {
      if (txn.snapshot.xmin < horizon) {
        horizon = txn.snapshot.xmin;
      }
    }
    return horizon;
  };

И прокидываем в публичный интерфейс TransactionManager (рядом с watermark и openXids):

// src/transaction.ts (расширение TransactionManager)

export interface TransactionManager extends Journal {
  // ... как было в уроке 8 ...
  readonly vacuumHorizon: () => Xid;
}

// в return makeTransactionManager
  return {
    // ... прежние поля ...
    vacuumHorizon,
  };

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

Перепись страницы

Куча хранит только смещение слота, не длину кортежа, поэтому “прочитать версии, решить судьбу, переупаковать” будет жить в vacuum.ts, а Page получит лишь примитив переписи данных. Чистый код, как и весь Page, без Effect.

// src/page.ts (примитив переписи для vacuum)

  /**
   * Переписать область данных страницы из живых кортежей, освободив место мёртвых.
   * Массив слотов сохраняет длину slotCount: живой кортеж остаётся в своём слоте (RID
   * стабилен, индекс не протухает), мёртвый слот становится DEAD_SLOT. Данные
   * переупаковываются от конца страницы к началу, поэтому upper поднимается и свободное
   * место растёт. Сами байты кортежей передаёт vacuum (страница не знает их длины), он же
   * гарантирует, что live помещаются в slotCount слотов.
   */
  vacuumRewrite(slotCount: number, live: ReadonlyArray<{ slot: number; data: Buffer }>): void {
    this.lower = HEADER_SIZE + slotCount * SLOT_SIZE;
    this.upper = PAGE_SIZE;
    for (let slot = 0; slot < slotCount; slot++) {
      this.setSlot(slot, DEAD_SLOT);
    }
    for (const { slot, data } of live) {
      const tupleOffset = this.upper - data.byteLength;
      data.copy(this.buffer, tupleOffset);
      this.upper = tupleOffset;
      this.setSlot(slot, tupleOffset);
    }
  }

Ключевой инвариант здесь: номер слота живого кортежа сохраняется. RID это пара (pageId, slot), и индекс хранит ключ -> RID, поэтому, если бы vacuum переназначил слоты, все индекс-указатели протухли бы разом. Вместо этого массив слотов остаётся той же длины (slotCount), живые кортежи возвращаются в свои слоты, а слоты мёртвых становятся DEAD_SLOT и больше не переиспользуются (insertTuple всегда дописывает слот в конец). Поэтому даже если в индексе остался указатель на освобождённый слот, это безопасно: IndexScan читает мёртвый слот как Option.none() и пропускает его. Переупаковываются только данные: upper поднимается к концу страницы, свободное место между lower и upper растёт.