Своя СУБД на TS · урок 8: транзакции, откат и видимость
Кому это. В прошлом уроке у движка появился журнал упреждающей записи. INSERT и CREATE переживают падение: старт проигрывает журнал и догоняет потерянное. Но мы честно оставили дыру: настоящих транзакций нет, ROLLBACK движок не знает, а DELETE работает на честном слове и падение не переживает.
Зачем. Сегодня закрываем дыру целиком. Появятся транзакции: BEGIN, COMMIT, ROLLBACK, и каждая будет атомарной (всё или ничего). Чтобы это заработало и чтобы починить удаление, кортеж научится версиям: вместо стирания слота удаление будет помечать версию полем xmax, а видимость строки начнёт решать движок по тому, какая транзакция её создала и зафиксировалась ли она. Это MVCC, многоверсионная модель, на которой стоит Postgres. Заодно COMMIT начнёт форсить журнал (вечная фиксация), а ROLLBACK и падение незавершённой транзакции, наоборот, будут делать её версии невидимыми.
Важно про объём. Это второй из двух уроков про долговечность, и самый плотный во всём воркшопе: транзакции, версии, видимость, откат и восстановление сходятся вместе. Но почти всё опирается на готовое: журнал из прошлого урока, исполнитель из шестого. Сегодня движок остаётся однопользовательским: одна транзакция за раз (плюс autocommit). Конкуренция, когда несколько транзакций открыты одновременно и видят разные снимки, блокировки и дедлоки, это следующий урок. Поэтому снимок транзакции у нас сегодня тривиален (других живых транзакций нет), но мы заложим его форму правильно, чтобы конкуренция встала сверху без переделок.
Где мы в движке
┌────────────────────────────────────────────────┐
│ Бинарный протокол + 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
└────────────────────────────────────────────────┘Два новых слоя: менеджер транзакций (выдаёт xid, ведёт состояния, undo-лог) и MVCC (видимость версий по снимку). Они пронизывают исполнитель: каждый скан теперь фильтрует версии по видимости, а удаление и обновление пишут версии вместо стирания.
Идея версий
Главная мысль урока в одном абзаце. У кортежа из урока 3 уже есть два поля заголовка, которые до сих пор ничего не значили: xmin и xmax. xmin это xid транзакции, создавшей версию. xmax это xid транзакции, удалившей версию, или 0 если версия жива. Удаление больше не стирает слот: оно ставит xmax. Обновление это удаление старой версии плюс вставка новой. А видна ли строка конкретной транзакции, решает функция видимости: смотрит на xmin (зафиксирован ли создатель) и xmax (зафиксирован ли удаливший). Так одно удаление становится обычной журналируемой пометкой, которую можно воспроизвести при recovery и откатить при rollback. Та самая дыра прошлого урока закрывается ровно этим.
Версии в странице: setXmax
Сначала научим страницу читать и писать xmax кортежа на месте. В уроке 1 у Page были аксессоры заголовка страницы; добавим пару для поля xmax кортежа в слоте. Добавь в src/page.ts.
// src/page.ts (добавляем методы в класс Page)
/**
* Записать xmax кортежа в слоте на месте (MVCC-удаление). Слот остаётся живым;
* видимость скрывает версию после фиксации удалившей транзакции. Заголовок кортежа
* лежит по смещению слота, xmax это u32 LE по TupleOffset.xmax.
*/
setXmax(slot: number, xmax: number): void {
this.buffer.writeUInt32LE(xmax >>> 0, this.getSlot(slot) + TupleOffset.xmax);
}
/** Прочитать xmax кортежа в слоте. */
getXmax(slot: number): number {
return this.buffer.readUInt32LE(this.getSlot(slot) + TupleOffset.xmax);
}Важно: setXmax не трогает сам слот, только заголовок кортежа по его смещению. Слот остаётся живым (isSlotLive по-прежнему true), поэтому seq scan кортеж увидит, и дальше уже видимость решит, показывать ли его. Это принципиальное отличие от deleteSlot из урока 3: тот зануляет слот (физическое удаление), а setXmax оставляет версию на месте, лишь помечая её удалённой. Импорт TupleOffset из ~/constants.ts у тебя уже есть с урока 1.
Видимость: снимок и правило
Теперь сердце MVCC: функция видимости. Положи в src/snapshot.ts. Начнём с реестра статусов транзакций.
// src/snapshot.ts
import type { Tuple, Xid } from '~/tuple.ts';
export type TxnState = 'in-progress' | 'committed' | 'aborted';
/**
* Реестр статусов транзакций для проверки видимости. Явные статусы открытых и недавних
* транзакций; незнакомый xid считается откатанным. Плюс floor: водяной знак последнего
* checkpoint, ниже которого xid считается зафиксированным без явной записи (нужно после
* ротации журнала: старые commit-записи усечены, но версии с xid ниже floor на диске
* принадлежат зафиксированным транзакциям). Аналог обрезания CLOG в Postgres.
*/
export class CommitStatus {
private readonly states = new Map<Xid, TxnState>();
private floorXid: Xid = 0;
constructor(entries: Iterable<readonly [Xid, TxnState]> = []) {
for (const [xid, state] of entries) {
this.states.set(xid, state);
}
}
/** Статус транзакции. Явная запись приоритетна; всё ниже floor это committed. */
get(xid: Xid): TxnState {
const explicit = this.states.get(xid);
if (explicit !== undefined) {
return explicit;
}
return xid !== 0 && xid < this.floorXid ? 'committed' : 'aborted';
}
set(xid: Xid, state: TxnState): void {
this.states.set(xid, state);
}
get floor(): Xid {
return this.floorXid;
}
/** Поднять floor (после checkpoint или recovery): xid ниже считаются committed. */
raiseFloorTo(watermark: Xid): void {
if (watermark > this.floorXid) {
this.floorXid = watermark;
}
}
/** Перенять floor и явные статусы из другого реестра (после recovery). */
absorb(other: CommitStatus): void {
this.raiseFloorTo(other.floorXid);
for (const [xid, state] of other.states) {
this.states.set(xid, state);
}
}
}CommitStatus отвечает на вопрос “зафиксирована ли транзакция xid”. Обычно по явной записи (in-progress, committed, aborted), а незнакомый xid считается откатанным (консервативно: если мы про транзакцию ничего не знаем, считаем, что она не дошла до commit). Тонкость это floor: после checkpoint старые commit-записи журнала усекаются, и тогда любой xid ниже водяного знака считается зафиксированным без явной записи. Это спасает от бесконечного роста реестра, как обрезание CLOG в Postgres. Дальше сам снимок и видимость.
// src/snapshot.ts (продолжение)
export interface Snapshot {
/** Самый старый активный xid (понадобится vacuum в уроке 10). */
readonly xmin: Xid;
/** Верхняя граница (эксклюзивно): xid >= xmax ещё не начинались на момент снимка. */
readonly xmax: Xid;
/** Активные (незафиксированные) транзакции на момент снимка, кроме самой себя. */
readonly active: ReadonlySet<Xid>;
}
/** Зафиксирована ли транзакция x к моменту снимка (committed-as-of-snapshot). */
export function committedAsOf(x: Xid, snapshot: Snapshot, status: CommitStatus): boolean {
return x !== 0 && status.get(x) === 'committed' && x < snapshot.xmax && !snapshot.active.has(x);
}
/**
* Видна ли версия кортежа транзакции self под её снимком. Собственные записи (xmin или
* xmax === self) транзакция видит сразу. Иначе смотрим на зафиксированность к снимку.
*/
export function isVisible(
tuple: Tuple,
snapshot: Snapshot,
self: Xid,
status: CommitStatus,
): boolean {
const inserterVisible = 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;
}Снимок это три числа: xmin (самый старый активный xid, пригодится vacuum в уроке 10), xmax (граница: xid не меньше неё ещё не начинались на момент снимка) и active (множество открытых на тот момент транзакций, кроме самой себя). Сегодня active всегда пуст: транзакция одна. В уроке про конкуренцию он наполнится, и тогда заработает изоляция снимков, но форму мы закладываем уже сейчас.
isVisible это правило в пять строк, и его стоит прочитать медленно. Версия видна, если выполнены два условия. Первое: её создатель виден, то есть либо это моя собственная вставка (xmin === self), либо создатель зафиксировался к моему снимку. Если создатель не виден (его транзакция откатилась или ещё не зафиксировалась), версия невидима сразу. Второе: версия не удалена видимым образом. xmax === 0 значит жива. Иначе версия удалена, если удаливший это я сам (xmax === self) или он зафиксировался к снимку. committedAsOf собирает воедино: транзакция зафиксирована к снимку, если её статус committed, она началась до снимка (x < xmax) и не была активной на момент снимка. Именно эта функция делает так, что незафиксированная или откатанная вставка невидима, а зафиксированное удаление скрывает строку.
Покрути это вживую. Виджет показывает одну транзакцию на таймлайне: BEGIN, INSERT, DELETE (ставит xmax), и три исхода: COMMIT, ROLLBACK, падение. Видно, как xmin, xmax и статус транзакции вместе решают, видна ли строка в каждом исходе.
Менеджер транзакций
Теперь тот, кто выдаёт xid, ведёт состояния, цепочку записей журнала и undo-лог. Сначала расширим контракт журналирования: в прошлом уроке у Journal был один метод, добавим второй для удаления. В src/wal.ts.
// src/wal.ts (меняем интерфейс Journal и добавляем payload-кодек)
export interface Journal {
logInsert(xid: number, relationId: number, pageId: number, slot: number, image: Buffer): bigint;
logSetXmax(xid: number, relationId: number, pageId: number, slot: number, xmax: number): bigint;
}
const XMAX_SIZE = 4;
export function encodeSetXmaxPayload(
relationId: number,
pageId: number,
slot: number,
xmax: number,
): Buffer {
const buffer = Buffer.alloc(RELID_SIZE + PAGE_ID_SIZE + SLOT_SIZE_BYTES + XMAX_SIZE);
buffer.writeUInt32LE(relationId, 0);
buffer.writeUInt32LE(pageId, RELID_SIZE);
buffer.writeUInt16LE(slot, RELID_SIZE + PAGE_ID_SIZE);
buffer.writeUInt32LE(xmax >>> 0, RELID_SIZE + PAGE_ID_SIZE + SLOT_SIZE_BYTES);
return buffer;
}
export function decodeSetXmaxPayload(payload: Buffer): {
relationId: number;
pageId: number;
slot: number;
xmax: number;
} {
return {
relationId: payload.readUInt32LE(0),
pageId: payload.readUInt32LE(RELID_SIZE),
slot: payload.readUInt16LE(RELID_SIZE + PAGE_ID_SIZE),
xmax: payload.readUInt32LE(RELID_SIZE + PAGE_ID_SIZE + SLOT_SIZE_BYTES),
};
}AutocommitJournal из прошлого урока уходит: его место займёт TransactionManager, который реализует тот же Journal, но с цепочкой и откатом. Положи в src/transaction.ts.
// src/transaction.ts
import { WalRecordType } from '~/constants.ts';
import { EngineError } from '~/engine/errors.ts';
import { CommitStatus, type Snapshot } from '~/snapshot.ts';
import type { Xid } from '~/tuple.ts';
import { encodeInsertPayload, encodeSetXmaxPayload, type Journal, type WalManager } from '~/wal.ts';
/** Undo вставки: пометить слот мёртвым. */
export interface InsertUndo {
readonly kind: 'insert';
readonly relationId: number;
readonly pageId: number;
readonly slot: number;
}
/** Undo MVCC-удаления: вернуть xmax кортежа в 0 (версия снова жива). */
export interface SetXmaxUndo {
readonly kind: 'setXmax';
readonly relationId: number;
readonly pageId: number;
readonly slot: number;
}
export type UndoEntry = InsertUndo | SetXmaxUndo;
interface ActiveTransaction {
readonly xid: Xid;
readonly beginLsn: bigint;
readonly snapshot: Snapshot;
prevLsn: bigint;
readonly undoLog: UndoEntry[];
}
const EMPTY_PAYLOAD = Buffer.alloc(0);
export class TransactionManager implements Journal {
private readonly wal: WalManager;
private nextXid = 1;
private readonly active = new Map<Xid, ActiveTransaction>();
private readonly status: CommitStatus = new CommitStatus();
constructor(wal: WalManager) {
this.wal = wal;
}
/** Глобальный статус транзакций для проверки видимости версий. */
get commitStatus(): CommitStatus {
return this.status;
}
/** xid всех открытых транзакций (для отката всех при close). */
openXids(): Xid[] {
return [...this.active.keys()];
}
/** Следующий xid к выдаче. На checkpoint это водяной знак: всё выданное завершилось. */
get watermark(): Xid {
return this.nextXid;
}
snapshotFor(xid: Xid): Snapshot {
return this.require(xid).snapshot;
}
/** Лёгкий снимок для чтения вне транзакции (autocommit SELECT): без записи в журнал. */
readSnapshot(): { xid: Xid; snapshot: Snapshot } {
return { xid: this.nextXid, snapshot: this.captureSnapshot(this.nextXid) };
}
/** Продолжить нумерацию xid и перенять commit-status после восстановления. */
resumeFrom(nextXid: number, recovered: CommitStatus): void {
this.nextXid = Math.max(this.nextXid, nextXid);
this.status.absorb(recovered);
}
/** Открыть транзакцию: присвоить xid, записать BEGIN, взять снимок. */
begin(): Xid {
const xid = this.nextXid;
this.nextXid += 1;
const beginLsn = this.wal.append(xid, WalRecordType.begin, EMPTY_PAYLOAD, 0n);
const snapshot = this.captureSnapshot(xid);
this.active.set(xid, { xid, beginLsn, snapshot, prevLsn: beginLsn, undoLog: [] });
this.status.set(xid, 'in-progress');
return xid;
}
commit(xid: Xid): void {
const txn = this.require(xid);
this.wal.append(xid, WalRecordType.commit, EMPTY_PAYLOAD, txn.prevLsn);
this.wal.flush(); // durability: COMMIT durable на диске до возврата управления
this.status.set(xid, 'committed');
this.active.delete(xid);
}
/** Откатить транзакцию: применить undo-лог в обратном порядке, пометить aborted. */
abort(xid: Xid, applyUndo: (entry: UndoEntry) => void): void {
const txn = this.require(xid);
for (let index = txn.undoLog.length - 1; index >= 0; index--) {
applyUndo(txn.undoLog[index]!);
}
this.wal.append(xid, WalRecordType.abort, EMPTY_PAYLOAD, txn.prevLsn);
this.status.set(xid, 'aborted');
this.active.delete(xid);
}
logInsert(xid: Xid, relationId: number, pageId: number, slot: number, image: Buffer): bigint {
const txn = this.require(xid);
const lsn = this.wal.append(
xid,
WalRecordType.insert,
encodeInsertPayload(relationId, pageId, slot, image),
txn.prevLsn,
);
txn.prevLsn = lsn;
txn.undoLog.push({ kind: 'insert', relationId, pageId, slot });
return lsn;
}
logSetXmax(xid: Xid, relationId: number, pageId: number, slot: number, xmax: Xid): bigint {
const txn = this.require(xid);
const lsn = this.wal.append(
xid,
WalRecordType.setXmax,
encodeSetXmaxPayload(relationId, pageId, slot, xmax),
txn.prevLsn,
);
txn.prevLsn = lsn;
txn.undoLog.push({ kind: 'setXmax', relationId, pageId, slot });
return lsn;
}
/**
* Граница no-steal: минимум (beginLsn - 1) по всем открытым транзакциям, иначе текущий
* максимум. Страница с lsn выше границы тронута незафиксированной транзакцией и на диск
* не сбрасывается.
*/
flushableLsn(): bigint {
if (this.active.size === 0) {
return this.wal.currentLsn;
}
let min: bigint | undefined;
for (const txn of this.active.values()) {
const candidate = txn.beginLsn - 1n;
if (min === undefined || candidate < min) {
min = candidate;
}
}
return min!;
}
/** Снимок: активны все открытые транзакции кроме самой себя; xmax это следующий xid. */
private captureSnapshot(self: Xid): Snapshot {
const active = new Set<Xid>(this.active.keys());
active.delete(self);
let xmin = self;
for (const xid of active) {
if (xid < xmin) {
xmin = xid;
}
}
return { xmin, xmax: self, active };
}
private require(xid: Xid): ActiveTransaction {
const txn = this.active.get(xid);
if (txn === undefined) {
throw new EngineError(`нет открытой транзакции ${xid}`);
}
return txn;
}
}Это много кода, но он распадается на ясные части. begin присваивает xid, пишет в журнал запись BEGIN, снимает снимок текущих открытых транзакций и заводит активную транзакцию с пустым undo-логом. commit пишет COMMIT и форсит журнал: вот она, долговечность фиксации, после commit изменения переживут падение. abort идёт по undo-логу в обратном порядке, отменяя каждую запись (как именно, решит вызывающий через колбэк), пишет ABORT и помечает транзакцию откатанной.
logInsert и logSetXmax это реализация Journal: куча зовёт их при вставке и удалении. Каждая дописывает запись в журнал, продляет цепочку prev_lsn и кладёт запись в undo-лог: чтобы при откате знать, что отменять. flushableLsn это граница no-steal, к ней вернёмся в буферном пуле. captureSnapshot собирает снимок: сегодня active почти всегда пуст, потому что транзакция одна.
MVCC-удаление в куче
Теперь куча умеет удалять через версию. Добавь в src/heap-file.ts метод рядом с insertTuple и deleteTuple из прошлых уроков.
// src/heap-file.ts (добавляем метод markDeleted)
/**
* MVCC-удаление: записать xmax = xid в кортеж на месте, не трогая слот. Версия станет
* невидимой после фиксации xid. Журналируется записью setXmax. Слот остаётся живым.
*/
markDeleted(rid: Rid, xid: Xid): void {
const page = this.pool.fetchPage(rid.pageId);
if (!page.isSlotLive(rid.slot)) {
this.pool.unpinPage(rid.pageId, false);
throw new Error(`markDeleted: слот ${rid.pageId}:${rid.slot} уже мёртв`);
}
page.setXmax(rid.slot, xid);
if (this.journal !== undefined) {
page.lsn = this.journal.logSetXmax(xid, this.relationId, rid.pageId, rid.slot, xid);
}
this.pool.unpinPage(rid.pageId, true);
}Симметрично logInsertion из прошлого урока: меняем кортеж на странице (setXmax), журналируем (logSetXmax) и штампуем page.lsn. Старый deleteTuple (физическое стирание) остаётся как низкоуровневый примитив, но движок его больше не зовёт: удаление теперь это markDeleted. Гард на мёртвый слот защищает примитив от записи xmax по смещению 0 (то есть в чужой заголовок), хотя исполнитель удаляет только видимые строки и сюда мёртвый слот не доводит.
дальше после входа
Урок целиком открыт всем, кто вошёл. Войди по своему email, чтобы читать дальше.
Вход пока по приглашению. Если хочешь учиться, напиши Vassiliy.