Своя СУБД на TS · урок 9: конкуренция, блокировки и дедлоки

Кому это. В прошлом уроке у движка появились транзакции и MVCC-версии кортежа. Удаление стало журналируемой пометкой xmax, видимость считает функция isVisible по снимку, COMMIT форсит журнал, ROLLBACK откатывает по undo-логу. Но движок был честно однопользовательский: одна транзакция за раз. Снимок мы заложили правильно, но множество active всегда было пустым, потому что других открытых транзакций не существовало.

Зачем. Сегодня даём транзакциям работать одновременно. Появится db.begin(), который открывает явную транзакцию и возвращает хэндл; несколько таких хэндлов могут чередовать операторы. Тогда заработает snapshot isolation: транзакция A видит стабильный снимок, пока B рядом коммитит. Чтобы запись осталась корректной, добавим менеджер блокировок с эксклюзивным локом строки, проверку write-write конфликтов и детект дедлоков через граф ожидания.

Важно про объём. Почти весь фундамент готов с прошлого урока: версии, видимость, снимок, менеджер транзакций. Сегодня мы не переписываем их, а снимаем ограничение и достраиваем сбоку: новый файл lock-manager.ts, пара методов в операторах, хэндл транзакции в Database. Среда у нас по-прежнему однопоточная: настоящего параллелизма потоков нет, конкуренция это чередование операторов нескольких открытых транзакций под управлением вызывающего (в тесте мы сами решаем, чей оператор выполнить следующим). Этого достаточно, чтобы воспроизвести все интересные сценарии: стабильный снимок, конфликт записи, дедлок. Порты на Effect, Go и Rust получат настоящее блокирование через STM, RWMutex и parking_lot, но логика конфликтов одна и та же.

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

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

Один новый слой между транзакциями и MVCC: менеджер блокировок. Он не трогает чтение (оно идёт по снимку), но встаёт на пути записи: перед тем как пометить строку удалённой или вставить новую версию, оператор берёт эксклюзивный лок строки.

Две стороны конкуренции

У безопасной конкуренции две стороны, и важно их не путать.

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

Вторая это запись. Тут MVCC недостаточно: если две транзакции меняют одну строку, кто-то должен проиграть, иначе одно изменение потеряется (lost update). Решение в два слоя. Эксклюзивный лок строки сериализует одновременных писателей: пока A держит строку, B на ней ждёт. А write-write конфликт (строку уже изменила транзакция, зафиксировавшаяся после моего снимка) ловится проверкой xmax и откатывается. Вместе это даёт корректную запись поверх snapshot isolation.

Снимок наконец наполняется

Начнём с приятного: чтобы заработала изоляция снимков, в коде менеджера транзакций менять нечего. Вспомни captureSnapshot из прошлого урока:

// src/transaction.ts (этот код уже написан в уроке 8, читаем заново)

  /** Снимок: активны все открытые транзакции кроме самой себя; 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 };
  }

Он всегда собирал active из всех открытых транзакций. В прошлом уроке открытая транзакция была одна (она сама), поэтому после active.delete(self) множество оставалось пустым. Стоит открыть две транзакции одновременно, и снимок второй из них честно запишет первую в active. Дальше committedAsOf уже умеет это учитывать:

// src/snapshot.ts (тоже из урока 8, ключевая строка)

export function committedAsOf(x: Xid, snapshot: Snapshot, status: CommitStatus): boolean {
  return x !== 0 && status.get(x) === 'committed' && x < snapshot.xmax && !snapshot.active.has(x);
}

!snapshot.active.has(x) это и есть изоляция: даже если транзакция x уже зафиксировалась, но на момент моего снимка она была активной, я считаю её невидимой. Её изменения не пролезут в мой согласованный снимок. Так A, начавшая раньше B, не увидит то, что B вставила и закоммитила позже, потому что B попала в active снимка A (если A взяла снимок до старта B, то B вообще за границей xmax; если после, то B в active). Вся изоляция снимков это одна строчка, которую мы написали заранее. Нам осталось дать транзакциям сосуществовать.

Менеджер блокировок

Теперь сторона записи. Заведи новый файл src/lock-manager.ts. Это сердце сегодняшнего урока, и он на удивление компактный.

// src/lock-manager.ts
import { DeadlockError, LockWaitError } from '~/engine/errors.ts';
import type { Xid } from '~/tuple.ts';

export class LockManager {
  /** Ресурс -> владелец (эксклюзивно). Один владелец на ресурс. */
  private readonly owners = new Map<string, Xid>();
  /** Транзакция -> ресурсы, которыми она владеет. */
  private readonly held = new Map<Xid, Set<string>>();
  /** Граф ожидания: ожидающий -> множество тех, кого он ждёт. */
  private readonly waitsFor = new Map<Xid, Set<Xid>>();

  /**
   * Взять эксклюзивный лок на ресурс. Повторный захват своим же владельцем это no-op.
   * Конфликт с другим владельцем: цикл ожидания -> DeadlockError, иначе LockWaitError.
   */
  acquire(xid: Xid, resource: string): void {
    const owner = this.owners.get(resource);
    if (owner === undefined || owner === xid) {
      this.owners.set(resource, xid);
      this.addHeld(xid, resource);
      return;
    }

    this.addEdge(xid, owner);
    if (this.hasCycle(xid)) {
      this.removeEdge(xid, owner);
      throw new DeadlockError(`deadlock: транзакция ${xid} откатывается (ждала ${owner})`);
    }
    throw new LockWaitError(`ресурс ${resource} занят транзакцией ${owner}`);
  }

  /** Освободить все локи и рёбра ожидания транзакции (на commit/abort). */
  release(xid: Xid): void {
    const resources = this.held.get(xid);
    if (resources !== undefined) {
      for (const resource of resources) {
        if (this.owners.get(resource) === xid) {
          this.owners.delete(resource);
        }
      }
      this.held.delete(xid);
    }
    this.waitsFor.delete(xid);
    for (const waiters of this.waitsFor.values()) {
      waiters.delete(xid);
    }
  }

  private addHeld(xid: Xid, resource: string): void {
    let resources = this.held.get(xid);
    if (resources === undefined) {
      resources = new Set();
      this.held.set(xid, resources);
    }
    resources.add(resource);
  }

  private addEdge(waiter: Xid, holder: Xid): void {
    let targets = this.waitsFor.get(waiter);
    if (targets === undefined) {
      targets = new Set();
      this.waitsFor.set(waiter, targets);
    }
    targets.add(holder);
  }

  private removeEdge(waiter: Xid, holder: Xid): void {
    this.waitsFor.get(waiter)?.delete(holder);
  }

  /** Есть ли цикл в графе ожидания, достижимый из start (поиск в глубину). */
  private hasCycle(start: Xid): boolean {
    const visited = new Set<Xid>();
    const stack = [start];
    while (stack.length > 0) {
      const node = stack.pop()!;
      const targets = this.waitsFor.get(node);
      if (targets === undefined) {
        continue;
      }
      for (const next of targets) {
        if (next === start) {
          return true;
        }
        if (!visited.has(next)) {
          visited.add(next);
          stack.push(next);
        }
      }
    }
    return false;
  }
}

Три структуры данных. owners отвечает на вопрос “кто держит этот ресурс”. held это обратный индекс “какими ресурсами владеет транзакция”, чтобы release отпустил всё разом. waitsFor это граф ожидания: ребро A -> B значит “A ждёт ресурс, занятый B”.

acquire это вся логика. Свободный ресурс или свой же повторный захват это успех. Чужой ресурс это конфликт: добавляем ребро ожидания и проверяем, не появился ли цикл. Цикл значит дедлок, и запросившая транзакция назначается жертвой (бросаем DeadlockError, ребро убираем, чтобы граф не врал после отката). Конфликт без цикла это LockWaitError: ресурс занят, но взаимного ожидания нет.

Здесь стоит остановиться на том, чем наша однопоточная модель отличается от настоящей. В многопоточном движке acquire на занятом ресурсе заблокировал бы поток до освобождения лока. У нас потоков нет, блокировать некого, поэтому LockWaitError просто валит текущий statement, а транзакция остаётся открытой, и её ребро ожидания продолжает жить в графе. Когда вызывающий продолжит чередовать операторы и приведёт к взаимному ожиданию, hasCycle это заметит. То есть LockWaitError это “сейчас не вышло, попробуй позже или откатись”, а DeadlockError это “так не выйдет никогда, откатываю тебя”.

Ошибки конкуренции

Менеджер бросает две новые ошибки, а оператор записи третью. Добавь их в src/engine/errors.ts рядом с EngineError и UniquenessError из прошлых уроков.

// src/engine/errors.ts (добавляем три ошибки)

/**
 * Конфликт сериализации (урок 9): write-write конфликт под snapshot isolation. Строку уже
 * изменила другая транзакция, невидимая моему снимку. Транзакция откатывается.
 */
export class SerializationError extends EngineError {
  constructor(message: string) {
    super(message);
    this.name = 'SerializationError';
  }
}

/**
 * Лок занят другой транзакцией без цикла ожидания (урок 9). В многопоточном движке
 * транзакция бы заблокировалась; здесь падает только этот statement, транзакция жива.
 */
export class LockWaitError extends EngineError {
  constructor(message: string) {
    super(message);
    this.name = 'LockWaitError';
  }
}

/** Обнаружен цикл в графе ожидания (урок 9): запросившая транзакция это жертва. */
export class DeadlockError extends EngineError {
  constructor(message: string) {
    super(message);
    this.name = 'DeadlockError';
  }
}

Все три наследуют EngineError, поэтому ловятся общим обработчиком, но различаются по типу: тест проверяет, что write-write конфликт это именно SerializationError, а цикл это DeadlockError.

Операторы берут локи

Теперь операторы записи из урока 6 научатся брать лок и проверять конфликт. Контексту транзакции нужен доступ к менеджеру блокировок. Расширь TxnContext в src/engine/operators.ts:

// src/engine/operators.ts (TxnContext получает менеджер блокировок)
import type { LockManager } from '~/lock-manager.ts';
import { EngineError, SerializationError, UniquenessError } from '~/engine/errors.ts';

/** Контекст транзакции для видимости и блокировок (урок 9). */
export interface TxnContext {
  readonly xid: Xid;
  readonly snapshot: Snapshot;
  readonly status: CommitStatus;
  readonly locks: LockManager;
}

Лок берётся на конкретную строку, поэтому нужен её ключ. Строка адресуется через RID (страница плюс слот), но один и тот же RID в разных таблицах это разные строки, поэтому в ключ входит ещё relationId. Добавь два помощника:

// src/engine/operators.ts (помощники для локов)

/** Ключ лока строки: таблица, страница, слот. */
function lockKey(relationId: number, rid: Rid): string {
  return `${relationId}:${rid.pageId}:${rid.slot}`;
}

/**
 * Взять эксклюзивный лок строки и проверить write-write конфликт: если xmax уже выставлен
 * другой транзакцией, это first-updater-wins, откатываемся через SerializationError.
 */
function lockAndCheckWrite(heap: HeapFile, ctx: TxnContext, relationId: number, rid: Rid): void {
  ctx.locks.acquire(ctx.xid, lockKey(relationId, rid));
  const xmax = heap.readXmax(rid);
  if (xmax !== 0 && xmax !== ctx.xid) {
    throw new SerializationError(`строка ${lockKey(relationId, rid)} изменена другой транзакцией`);
  }
}

Порядок важен: сначала acquire. Если лок занят, мы тут же падаем (ожидание или дедлок), не дойдя до проверки xmax. Если лок взят, читаем xmax строки прямо из кучи. xmax === 0 значит строку никто не удалял, конфликта нет. xmax === ctx.xid значит её удалил я сам в этой же транзакции, тоже не конфликт. А вот xmax, выставленный кем-то другим, означает, что строку уже изменила транзакция, которой нет в моём снимке: это и есть потерянное обновление, и мы откатываемся.

Почему проверка xmax корректна именно так? Оператор удаления и обновления работает только над видимыми строками (скан их отфильтровал по снимку). Видимая строка по определению ещё не удалена видимым мне образом. Значит, если на ней оказался ненулевой xmax от чужой транзакции, эта транзакция зафиксировалась после моего снимка (иначе строка была бы мне невидима и скан бы её не отдал). Это ровно конфликт first-updater-wins.

Дальше расставляем эти вызовы по операторам. Insert берёт лок на новую строку сразу после вставки (новый RID никто не держит, но лок нужен, чтобы её не тронул другой писатель до нашего commit):

// src/engine/operators.ts (Insert.next, фрагмент после уникальности)

    const tuple = new Tuple(this.values, { xmin: this.ctx.xid, xmax: 0 });
    const rid = this.heap.insertTuple(tuple, this.ctx.xid);
    this.ctx.locks.acquire(this.ctx.xid, lockKey(this.relationId, rid));
    maintainIndex(this.index, this.indexedColumn, this.values, rid);
    return countRow(1n);

Delete берёт лок и проверяет конфликт на каждой строке до мутаций (statement остаётся атомарным: либо все строки помечаются удалёнными, либо ни одна, если кто-то конфликтует):

// src/engine/operators.ts (Delete.next)

    this.done = true;
    const rids = this.drainRids();
    for (const rid of rids) {
      lockAndCheckWrite(this.heap, this.ctx, this.relationId, rid);
    }
    for (const rid of rids) {
      this.heap.markDeleted(rid, this.ctx.xid);
    }
    return countRow(BigInt(rids.length));

Update (помним, это markDeleted старой версии плюс вставка новой) делает то же самое: сначала ловит все конфликты, потом мутирует, и берёт лок на каждую новую версию:

// src/engine/operators.ts (Update.next, фазы)

    // конфликты ловим до любой мутации, чтобы statement был атомарным
    for (const item of pending) {
      lockAndCheckWrite(this.heap, this.ctx, this.relationId, item.rid);
    }
    // ... проверка уникальности нового ключа (без изменений с урока 8) ...
    for (const item of pending) {
      this.heap.markDeleted(item.rid, this.ctx.xid);
      const tuple = new Tuple(item.values, { xmin: this.ctx.xid, xmax: 0 });
      const newRid = this.heap.insertTuple(tuple, this.ctx.xid);
      this.ctx.locks.acquire(this.ctx.xid, lockKey(this.relationId, newRid));
      maintainIndex(this.index, this.indexedColumn, item.values, newRid);
    }
    return countRow(BigInt(pending.length));

Чтобы операторы знали relationId, их конструкторы получают этот параметр. Меняем сигнатуры Insert, Delete, Update: добавляем relationId: number рядом с ctx. Это механическая правка, важно лишь не забыть прокинуть его из планировщика, чем и займёмся.