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

Кому это. В прошлом уроке у движка появились транзакции и версии кортежа. Удаление стало журналируемой пометкой Xmax, видимость считает txn.IsVisible по снимку, COMMIT форсит журнал, ROLLBACK откатывает по undo-log. Хэндлы db.Begin() уже открываются по несколько, но ничто не мешает двум из них переписать одну строку: последний писатель молча затрёт первого.

Зачем. Сегодня даём транзакциям честно конкурировать. Несколько хэндлов чередуют операторы, и мы проверим, что каждый видит свой snapshot isolation, а запись защитит пакет lock: эксклюзивный лок строки по строгому двухфазному протоколу, граф ожидания и детект дедлоков. Со стороны Go урок про карты-множества, обобщённую функцию и одно честное решение порта, которое многих удивит: на занятом локе горутина не засыпает. Почему, станет ясно, если заглянуть в урок 11, где движок встанет под sync.RWMutex.

Важно про объём. Фундамент готов с прошлого урока: версии, видимость, снимок, менеджер транзакций. Сегодня мы снимаем ограничение и достраиваем сбоку: новый пакет lock на 80 строк, ReadXmax в куче, две функции в операторах и отпускание локов в commit и abort. Тесты урока чередуют операторы нескольких транзакций в одной горутине: этого хватает, чтобы воспроизвести стабильный снимок, конфликт записи и дедлок. Настоящие горутины на соединение и sync.RWMutex вокруг движка придут в уроке 11.

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

wire/              протокол и TCP-сервер                   урок 11
engine/            каталог, binder, планировщик, Volcano   урок 6, +локи в DML сегодня
sql/               лексер, парсер, AST                     урок 5
vacuum/            сборка мёртвых версий                   урок 10
lock/              блокировки, граф ожидания               урок 9  ← мы здесь
txn/               xid, снимки, undo-log                   урок 8
dberr/             ошибки движка с кодом                   урок 6
wal/, recovery/    журнал и redo-проход                    урок 7
btree/             B+Tree индекс                           урок 4
heap/, tuple/      куча и кортеж                           урок 3
bufferpool/        кэш страниц, вытеснение clock           урок 2
page/, disk/       страница и файл                         урок 1

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

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

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

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

Вторая это запись. Тут одного MVCC мало: если две транзакции меняют одну строку, кто-то должен проиграть, иначе одно изменение потеряется. Решение в два слоя. Эксклюзивный лок строки сериализует писателей. А write-write конфликт, когда строку уже изменила транзакция, зафиксировавшаяся после моего снимка, ловится проверкой Xmax.

И есть третья сторона, которой у TS-движка не было вовсе: физическая. Логические транзакции живут над структурами в памяти: картами менеджера транзакций, кадрами пула, буфером журнала. Когда в уроке 11 к движку придут горутины, эти структуры начнут трогать одновременно. Логическую изоляцию дают снимки и локи строк, физическую целостность даст sync.RWMutex. Это разные уровни: логический заводим сегодня, физический в финале.

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

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

// capture берёт снимок: активны все открытые кроме самой себя, Xmax это self.
func (m *Manager) capture(self uint32) Snapshot {
	snap := Snapshot{Xmin: self, Xmax: self, Active: make(map[uint32]bool, len(m.active))}
	for xid := range m.active {
		if xid != self {
			snap.Active[xid] = true
			snap.Xmin = min(snap.Xmin, xid)
		}
	}
	return snap
}

Он всегда собирал Active из всех открытых транзакций. Тесты прошлого урока держали по одной транзакции за раз, поэтому множество оставалось пустым. Стоит открыть две одновременно, и снимок второй честно запишет первую в Active. А CommittedAsOf это уже учитывает: !snap.Active[x] в его условии и есть изоляция. Даже если x уже зафиксировалась, но на момент моего снимка была активной, её изменения в мой снимок не пролезут. Чтение готово, осталось защитить запись.

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

Теперь сторона записи. Заведи пакет lock и файл lock/lock.go. Он на удивление компактный.

// Package lock это менеджер блокировок (урок 9): строгий 2PL. Транзакция берёт эксклюзивный
// лок строки при записи и держит до commit/abort. На конфликте строится граф ожидания:
// цикл это дедлок (запросивший жертва), иначе would-block.
//
// Как в эталоне, лок не блокирует горутину: конфликт без цикла валит только statement
// (dberr.LockWait), транзакция жива и её ребро ожидания остаётся в графе, поэтому взаимное
// ожидание при чередовании операторов ловится поиском цикла. Менеджер зовётся только под
// эксклюзивным локом движка, своей синхронизации ему не нужно.
package lock

import "ourdb/dberr"

// Manager держит владельцев ресурсов и граф ожидания.
type Manager struct {
	owners   map[string]uint32
	held     map[uint32]map[string]bool
	waitsFor map[uint32]map[uint32]bool
}

// New создаёт пустой менеджер.
func New() *Manager {
	return &Manager{owners: map[string]uint32{}, held: map[uint32]map[string]bool{}, waitsFor: map[uint32]map[uint32]bool{}}
}

// Acquire берёт эксклюзивный лок. Повторный захват владельцем это no-op.
func (m *Manager) Acquire(xid uint32, resource string) error {
	owner, taken := m.owners[resource]
	if !taken || owner == xid {
		m.owners[resource] = xid
		addTo(m.held, xid, resource)
		return nil
	}
	addTo(m.waitsFor, xid, owner)
	if m.hasCycle(xid) {
		delete(m.waitsFor[xid], owner)
		return dberr.New(dberr.Deadlock, "deadlock: транзакция %d откатывается (ждала %d)", xid, owner)
	}
	return dberr.New(dberr.LockWait, "ресурс %s занят транзакцией %d", resource, owner)
}

// Release освобождает все локи и рёбра ожидания транзакции (на commit/abort).
func (m *Manager) Release(xid uint32) {
	for resource := range m.held[xid] {
		if m.owners[resource] == xid {
			delete(m.owners, resource)
		}
	}
	delete(m.held, xid)
	delete(m.waitsFor, xid)
	for _, targets := range m.waitsFor {
		delete(targets, xid)
	}
}

// hasCycle ищет в глубину путь из start обратно в start.
func (m *Manager) hasCycle(start uint32) bool {
	visited := map[uint32]bool{}
	stack := []uint32{start}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		for next := range m.waitsFor[node] {
			if next == start {
				return true
			}
			if !visited[next] {
				visited[next] = true
				stack = append(stack, next)
			}
		}
	}
	return false
}

func addTo[K comparable, V comparable](m map[K]map[V]bool, k K, v V) {
	if m[k] == nil {
		m[k] = map[V]bool{}
	}
	m[k][v] = true
}

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

Acquire это вся логика. Свободный ресурс или свой же повторный захват это успех. Чужой ресурс это конфликт: добавляем ребро ожидания и ищем цикл. Цикл значит дедлок, запросившая транзакция становится жертвой: ребро убираем, чтобы граф не врал после её отката, и отдаём dberr.Deadlock (40P01). Конфликт без цикла это dberr.LockWait (55P03): ресурс занят, взаимного ожидания нет.

Посмотри на Go-сторону. Множества тут это map[T]bool: Go не завёл отдельного типа множества, и карта с булевым значением его заменяет. Чтение отсутствующего ключа даёт false, поэтому visited[next] не требует проверки наличия. delete(m.waitsFor[xid], owner) безопасен, даже если внутренней карты нет: delete из nil-карты в Go ничего не делает. А вот запись в nil-карту паникует, поэтому вставка идёт через addTo, который лениво заводит внутреннюю карту. Это обобщённая функция: [K comparable, V comparable] говорит, что ключи обеих карт должны поддерживать ==. Одна функция обслуживает и held (uint32 -> string), и waitsFor (uint32 -> uint32). Поиск в глубину идёт явным стеком на срезе, без рекурсии: stack[:len(stack)-1] это pop.

Коды конкуренции

Менеджер блокировок возвращает две ошибки, а оператор записи третью. Коды для них лежат в dberr/dberr.go рядом с Engine и Uniqueness из урока 6 (на этапах пакет дан готовым), но до сегодняшнего дня их никто не возвращал:

const (
	Engine        Code = "42000" // анализ, план, исполнение
	Uniqueness    Code = "23505" // дубликат PRIMARY KEY
	Serialization Code = "40001" // write-write конфликт под snapshot isolation
	Deadlock      Code = "40P01" // цикл в графе ожидания, запросивший это жертва
	LockWait      Code = "55P03" // лок занят без цикла: падает statement, транзакция жива
)

У TS-трека это три подкласса EngineError, и тест проверяет класс через instanceof. Здесь тест спрашивает dberr.CodeOf(err) == dberr.Deadlock. Коды взяты из SQLSTATE Postgres: в уроке 11 сессия протокола отдаст их клиенту как есть, и клиент, знакомый с Postgres, поймёт их без словаря.

Почему горутина не засыпает на локе

Тут остановимся. TS-движок однопоточный, блокировать там некого, поэтому LockWaitError просто валит текущий оператор. Логично ожидать, что Go-порт, где горутины есть, сделает по-взрослому: занятый лок усыпит горутину до COMMIT владельца, как это делает Postgres. Эталон этого сознательно не делает: Acquire возвращает 55P03 сразу, ровно как TS. Причины две, и вторая важнее.

Первая: тесты. Урок 9 TS-трека проверяет поведение чередованием операторов в одном потоке: A берёт строку, B получает “занято”, A фиксирует, B откатывается. С засыпающим локом этот тест повис бы навсегда: B ждёт A, а A не может сделать следующий шаг, потому что тест крутится в той же горутине и сам ждёт B. Порт держит те же тесты, что и TS, поэтому и поведение то же.

Вторая: мьютекс движка. Смотри комментарий пакета: менеджер зовётся только под эксклюзивным локом движка. Сегодня движок однопоточный, но в уроке 11 он встанет под sync.RWMutex, и любая мутация пойдёт под db.mu.Lock(). Представь: UPDATE берёт db.mu.Lock(), доходит до Acquire, а тот находит строку занятой. Если бы Acquire усыпил горутину, она спала бы, держа db.mu. Владелец строки, чтобы сделать COMMIT и отпустить её, сам должен взять db.mu.Lock(), а мьютекс занят спящим. Получился бы дедлок, который граф ожидания не видит: он не на строках, а на мьютексе Go. Весь движок встал бы.

Чтобы ждать честно, спящий обязан отпустить мьютекс движка на время сна и взять его обратно при пробуждении. В стандартной библиотеке ровно для этого есть sync.Cond: cond.Wait() атомарно отпускает связанный мьютекс, спит до Broadcast и снова его берёт. А проснувшись, оператор обязан перепроверить и лок, и Xmax: пока он спал, мир изменился. Это хорошее упражнение со звёздочкой, оно в конце урока. Базовая линия держит паритет с TS: 55P03 это “сейчас не вышло, попробуй позже или откатись”, а 40P01 это “так не выйдет никогда, откатываю тебя”.

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

Контекст транзакции получает менеджер блокировок. В engine/operators.go:

type TxnContext struct {
	Xid      uint32
	Snapshot txn.Snapshot
	Status   *txn.CommitStatus
	Locks    *lock.Manager
}

func lockKey(relationID uint32, rid heap.Rid) string {
	return fmt.Sprintf("%d:%d:%d", relationID, rid.PageID, rid.Slot)
}

// lockAndCheckWrite берёт эксклюзивный лок строки и ловит write-write конфликт: xmax уже
// выставлен другой транзакцией, это first-updater-wins.
func lockAndCheckWrite(h *heap.File, ctx TxnContext, relationID uint32, rid heap.Rid) error {
	if err := ctx.Locks.Acquire(ctx.Xid, lockKey(relationID, rid)); err != nil {
		return err
	}
	xmax, err := h.ReadXmax(rid)
	if err != nil {
		return err
	}
	if xmax != 0 && xmax != ctx.Xid {
		return dberr.New(dberr.Serialization, "строка %s изменена другой транзакцией", lockKey(relationID, rid))
	}
	return nil
}

Лок берётся на конкретную строку. RID это страница плюс слот, но один и тот же RID в разных таблицах это разные строки, поэтому в ключ входит ещё relationID. Ключ строковый ради простоты и паритета с TS; структура struct{ rel, page uint32; slot uint16 } тоже подошла бы ключом карты (она comparable) и не выделяла бы память на Sprintf, это приятная оптимизация на потом.

Порядок важен: сначала Acquire. Если лок занят, падаем сразу, не дойдя до Xmax. Если взят, читаем Xmax из кучи. 0 значит строку никто не удалял. ctx.Xid значит удалил я сам в этой же транзакции. А чужой Xmax означает, что строку изменила транзакция, которой нет в моём снимке: потерянное обновление, и мы отдаём 40001.

Почему проверка корректна именно так? Удаление и обновление работают только над видимыми строками, скан их уже отфильтровал. Видимая строка ещё не удалена видимым мне образом. Если пометку поставила ещё открытая транзакция, она держит лок строки, и мы упали бы на Acquire раньше. Откатившаяся вернула бы Xmax в 0. Значит, до проверки доходит только пометка транзакции, которая зафиксировалась после моего снимка и отпустила лок. Это ровно first-updater-wins.

Дальше расставляем вызовы по операторам из engine/dml.go. Вставка берёт лок на новую строку сразу после записи в кучу: новый RID никто не держит, но лок не даст его тронуть до нашего COMMIT.

func (t target) insertVersion(ctx TxnContext, values []tuple.Value) error {
	rid, err := t.heap.Insert(tuple.Tuple{Values: values}, ctx.Xid)
	if err != nil {
		return err
	}
	if err := ctx.Locks.Acquire(ctx.Xid, lockKey(t.relationID, rid)); err != nil {
		return err
	}
	return t.maintainIndex(values, rid)
}

func newDelete(child Operator, t target, ctx TxnContext) Operator {
	return &dml{child: child, run: func() (int, error) {
		rows, err := drain(child)
		if err != nil {
			return 0, err
		}
		// конфликты до любой мутации, чтобы statement был атомарным
		for _, r := range rows {
			if err := lockAndCheckWrite(t.heap, ctx, t.relationID, *r.Rid); err != nil {
				return 0, err
			}
		}
		for _, r := range rows {
			if err := t.heap.MarkDeleted(*r.Rid, ctx.Xid); err != nil {
				return 0, err
			}
		}
		return len(rows), nil
	}}
}

Удаление проходит строки дважды: сначала ловит все конфликты, потом мутирует. Так оператор атомарен: либо помечаются все строки, либо ни одна. Взятые до ошибки локи остаются у транзакции: по строгому 2PL их отпустит только конец транзакции. UPDATE устроен так же: вычисляет новые значения, ловит конфликты, проверяет уникальность новых ключей (checkNewKeys) и только потом для каждой строки делает MarkDeleted плюс insertVersion.

target это маленькая структура-значение с кучей, relationID, индексом и колонкой: планировщик собирает её из каталога и передаёт операторам. Сканы (SeqScan, IndexScan) локов не берут: чтение идёт по снимку.