MVCC, B-дерево и параллелизм

MVCC может быть реализован различными способами. Единственное требование состоит в том, чтобы каким-то образом были доступны более старые версии строк.

Например, SQL Server хранит их во временной базе данных, которая сбрасывается при перезапуске сервера.

Postgres хранит версии строк как скрытые строки непосредственно в b-дереве. Он добавляет в дерево скрытый ключевой столбец. При чтении из дерева выставляется только та версия, которая логически должна быть видна.

Voron от RavenDB управляет страницами b-tree как неизменяемыми данными. Пишет создать совершенно новые деревья. Таким образом, MVCC реализуется как чтение из правильного неизменного дерева.

Базы данных редко блокируют физические структуры на длительное время. Не рекомендуется разрешать клиенту базы данных останавливать выполнение внутренних структур базы данных. Внутренние конструкции обычно запираются очень ненадолго. Логические блокировки строк обрабатываются отдельно.

Если бы мне пришлось догадываться, concurrency control on search structures относится к физической безопасности потоков. Обычно это не связано с MVCC, потому что нет необходимости управлять несколькими версиями. Обычных блокировок в памяти достаточно для кратковременного доступа.

MVCC означает, что вам не нужно использовать блокировки.

Представьте, что каждая транзакция получает числовую метку времени, которая увеличивается для каждой транзакции. В этом примере у нас есть транзакции 1 и 2.

Транзакция 1 читает A и записывает значение (A + 1). Изоляция снимка создает временную версию (A), которой владеет транзакция 1. Временная метка чтения A устанавливается на транзакцию 1.

Если транзакция 2 появится в то же время и прочитает A, она также прочитает зафиксированную A — она не увидит A + 1, потому что она не была зафиксирована. Транзакция 2 может видеть версии A, которые == lastCommittedA и ‹= транзакция 2.

Когда транзакция 2 читает A, она также проверит временную метку чтения A и увидит, что транзакция 1 существует, и проверит временную метку транзакции 1 ‹ временную метку транзакции 2. Поскольку 1 ‹ 2, транзакция 2 будет прервана, поскольку она уже зависит от старого значения A.

(Я реализовал MVCC на Java. См. транзакция, бегун и mvcc Я реализовал btree на Python.)