#29: Concurrency control: 2PL, OCC, MVCC

[00:20] Здорово! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. В предыдущем выпуске мы разобрались с тем, что такое ACID. Это был теоретический выпуск, и я намеренно не погружался в детали реализации. Но мне всегда было интересно: а как базы данных гарантируют уровни изоляции? Как так получается, что транзакции действительно выполняются параллельно, но результат их выполнения полностью эквивалентен последовательному? Какие алгоритмы за это отвечают? В сегодняшнем выпуске поговорим про двухфазную блокировку, оптимистическое управление конкурентностью и мультиверсионирование. Надеюсь, вам это так же интересно, как и мне. Поехали!

[01:16] В 26-м выпуске мы разобрали защёлки, или latches по-английски. Тогда я говорил, что это аналог мьютекса или read-write-блокировки из мира языков программирования. Но когда мы говорим про блокировки в контексте баз данных, стоит отметить: это не те же самые блокировки, что в языках. Блокировки в базах данных используются, чтобы поддерживать различные уровни изоляции транзакций, и за доступ к ним отвечает отдельная подсистема — Lock Manager. Сейчас расскажу, какие виды блокировок есть в базах данных. Чтобы лучше это понять, приведу пример из Java, где есть read-write-блокировка со знакомой нам семантикой: можно взять неограниченное количество блокировок на чтение, но лишь одну — на запись.

[01:55] В контексте баз данных тоже существует два вида блокировок — это shared lock и exclusive lock. Иногда их называют блокировкой на чтение и блокировкой на запись. Работают они точно так же, как в Java: блокировку на чтение может одновременно взять неограниченное количество транзакций, а блокировка на запись эксклюзивна — и когда какая-то транзакция её взяла, ни одна другая не вправе ни читать, ни писать. Давайте разберёмся на примере двух простых транзакций.

[02:28] Допустим, у нас есть транзакция 1 и транзакция 2. Транзакция 1 просто читает значение X, а транзакция 2 сначала его читает, а потом записывает. Чтобы прочитать, нужно взять на объект X shared lock; чтобы записать — exclusive lock. Первая транзакция берёт shared-блокировку на X, ничего не ожидая, и читает значение. В этот момент вторая транзакция тоже хочет взять блокировку на чтение того же объекта — и успешно её берёт, тоже читает. Первая транзакция, прочитав, отпускает блокировку. Вторая думает: «ага, теперь мне нужно записать» — и ей нужно повысить блокировку с чтения до записи. Она её повышает и таким образом меняет значение объекта X. Если объектов много — не один X, а X, Y, Z и так далее, — то на каждый отдельный объект мы берём отдельную блокировку. Это в нашей первоначальной, наивной модели; иерархические блокировки разберём чуть позже.

[03:34] Итак, пока какая-то транзакция читает значение, остальные могут только читать; если же транзакция пишет — никто не может ни читать, ни писать. Подход довольно стандартный, простой и понятный. Но штука в том, что я сейчас описал ситуацию, когда мы захватываем блокировку прямо перед работой с объектом, а возвращаем сразу после — то есть держим её не всё время транзакции, а только пока работаем с объектом. И тут возникает проблема: мы можем, например, дважды прочитать один и тот же объект, дважды взяв на него блокировку. Всё, что мы гарантируем, беря блокировку на объект и отпуская её после работы, — это что во время удержания блокировки с объектом ничего не случилось. Но если в рамках одной транзакции мы взаимодействуем с объектом больше одного раза и берём блокировку дважды, то между этими взятиями кто-то мог значение поменять. И мы можем получить любую аномалию — грязное чтение, dirty write, lost update.

[04:40] Поэтому первая оптимизация наивной модели — нам нужен более сложный протокол, который запрещал бы дважды брать блокировку. Он говорит примерно так: если берёшь блокировки — бери их все в одной фазе, а как только начал отпускать, новых уже не бери. Это называется двухфазный протокол блокировки, или двухфазная блокировка. Не путайте с двухфазным коммитом — это другое, про него поговорим отдельно в распределённой части. А сейчас речь именно про двухфазную блокировку как протокол взятия блокировок. Заключается ванильный протокол в том, что есть две фазы. Первая — когда мы только берём, только захватываем блокировки; она называется growing phase. Если посмотреть на жизненный цикл транзакции, увидим, что сначала количество взятых блокировок растёт вверх-вверх-вверх, потому что мы их только берём.

[05:41] Взяв все нужные блокировки, мы производим работу — хотя и в процессе взятия мы тоже работаем: берём их не за один присест, а по мере надобности. Сначала берём объект X, поработали, не отпускаем; потом берём Y, поработали, не отпускаем; а в конце уже отпускаем X, отпускаем Y. График сначала растёт вверх, потом плавно идёт вниз — это shrinking phase. Смысл в том, что если мы дважды работаем с объектом в рамках одной транзакции, блокировка на него будет взята один раз, и между взятиями никто не подлезет и ничего не поменяет. Это решает проблему. Но у протокола есть и свои минусы, он не идеален: мы отпускаем блокировки не все разом в конце, а по очереди — например, в середине транзакции. То есть как только перестали работать с каким-то объектом, понимаем, что блокировка больше не нужна, и отпускаем её. Но коммит ещё не делаем.

[06:45] И вот в чём загвоздка: мы могли в объект что-то записать, отпустить блокировку, а потом в конце, перед коммитом, закрешиться или решить сделать аборт. Так вот, то значение, которое мы записали и на которое отпустили блокировку в середине транзакции, могло быть уже прочитано другой транзакцией — а она ничего о нашем аборте не знает. Получается, нам нужно делать каскадный аборт: откатить не только нашу транзакцию, но и ту, которая завязалась на наше значение. Это проблема каскадного аборта, и решается она через strong strict two-phase locking — строгую двухфазную блокировку. В чём тут строгость? В том, что мы отпускаем блокировки только во время коммита. Когда понимаем, что коммитимся, — отпускаем одновременно все блокировки. Growing phase остаётся такой же плавной, а release phase происходит в самом конце, разом.

[07:43] Тогда получается, что если в конце мы принимаем решение сделать rollback, то перед сбросом блокировок переписываем наши значения назад, и когда отпускаем блокировку, те транзакции, что ждали доступа к X, только сейчас получают блокировку на чтение, берут её и читают предыдущее состояние — то, что было до нашего rollback. Таким образом каскадного аборта нет, каскадирование не происходит. Этот протокол называется strong strict two-phase locking. Возможно, для подкаста звучит немного сложновато, но, думаю, основную идею вы поняли. Если хотите разобраться поглубже — поищите материалы, напишите мне, я скину, или просто загуглите. Сам протокол не такой сложный, но вокруг него есть всякие пляски с бубнами, чтобы он работал, потому что в продакшене при работе с блокировками у нас, скорее всего, будут дедлоки. Не скорее всего, а стопроцентно будут, если система более-менее нагружена.

[08:43] Сам протокол никак не говорит, как работать с дедлоками, — это уже детали реализации. Но определить дедлок довольно просто, если есть специальный Lock Manager, а он у нас есть. Когда к менеджеру приходит запрос на блокировку от транзакции, он принимает решение — заставить её подождать или нет; он знает, какая транзакция какой объект и какую блокировку запрашивает. На основе этого он строит так называемый waits-for-graph. Условно: транзакция 1 ждёт взятия блокировки на запись объекта такого-то. Если объект, который нужен первой транзакции, уже занят и блокировка взята второй транзакцией, выстраивается направленная зависимость: первая транзакция ждёт вторую. Это и есть waits-for-graph. И если мы плюс-минус шарим за графы, то отсутствие цикла в этом графе говорит, что дедлоков нет, а наличие цикла — что дедлоки есть.

[09:50] Разрулить их тоже довольно просто. Имея граф, мы определяем циклы. Пусть в простом случае цикл состоит из двух нод, хотя вообще он может состоять и из десяти, и из двадцати транзакций, опосредованно связанных. Чтобы убрать цикл, нужно разорвать одну из связей. Для этого мы выбираем транзакцию, которой говорим: «ты теперь victim, жертва, и мы тебя откатываем». Тем самым мы прекращаем выполнение этой транзакции, граф разрывается, а транзакция начинает работать заново и берёт новые блокировки — и цикл разруливается. Rollback можно сделать полностью или частично, например до ближайшего сейвпоинта, — это зависит от реализации. Помимо того, что дедлоки можно разруливать по факту, их можно и превентивно ограничивать: догадаться, что сейчас будет дедлок, и откатиться прямо в момент взятия блокировки — не начинать висеть на ожидании и зацикливать waits-for-graph, а увидеть, что нужная блокировка уже кем-то держится, и лучше сразу откатиться. Тоже рабочий способ, но deadlock detection через waits-for-graph — более распространённая тема.

[11:16] Когда мы говорим про блокировки в мире баз данных, появляется понятие гранулярности блокировок. В программировании блокировки в целом не гранулярны: есть просто объект блокировки, отвечающий за какую-то область памяти, доступ к которой мы решили осуществлять через эту блокировку, — так мы и определяем её скоуп. А в базе данных скоуп блокировки определяет сама база, и выбор у неё не так велик: можно заблокировать всю базу данных (в экстремальном случае), всю таблицу, одну запись в таблице или один атрибут внутри записи — то есть одну колонку одной строки. И тут возникает trade-off. Ради эффективности и меньшего контеншена нам хотелось бы брать блокировки настолько мелкие и гранулярные, насколько возможно, — то есть блокировать отдельные строки, а не таблицу целиком. Например, если одна транзакция работает с записью Саши Пахомова в какой-нибудь CRM, а другая — с записью Васи Петрова, зачем им блокировать друг друга? На каждый тюпл вешается своя блокировка, и они никого не блокируют.

[12:50] Однако если мы делаем full scan таблицы или считаем важную статистику, которая должна быть исполнена транзакционно, — то есть нам нужна большая часть таблицы, — блокировать каждый тюпл невыгодно: представьте, сколько записей в базе, столько же блокировок мы создадим. Проще взять одну блокировку на уровень выше по иерархии — на таблицу целиком. Так что гранулярность блокировки — это всегда trade-off, и он не всегда однозначен. Поэтому инженеры баз данных придумали такое понятие, как intention locks. Это не блокировка — несмотря на слово «lock», это условно маркер, метаданные, которые так или иначе используются базой при взятии блокировок. Представьте: есть таблица — квадратик вверху, от него идёт множество стрелочек к тюплам, то есть к строкам-записям. И вот приходит транзакция и говорит: «мне нужно взять блокировку на чтение одного из тюплов». Например, SELECT ... FROM users WHERE id = 1.

[14:00] Она собирается взять на тюпл с id 1 shared-блокировку. И прежде чем повесить на него настоящий shared lock, она на родителя — на шаг вверх по иерархии (для тюпла это таблица, для таблицы это база данных) — вешает intention shared lock. Он говорит: «слушай, верхний узел, ты таблица, где-то внутри тебя, у одного из твоих children, висит shared lock». Также есть intention exclusive lock и intention shared exclusive lock — всего три варианта: IS говорит, что где-то внизу есть shared-блокировка, IX — что где-то есть exclusive, а SIX — что есть и shared, и exclusive. Как это помогает? Когда транзакция хочет взять exclusive-блокировку на всю таблицу целиком, нужно, чтобы ни один тюпл внутри не был заблокирован. Но если тюпл заблокирован, на таблице висит intention shared lock — и транзакции не нужно проходить по всем тюплам и проверять их: она уже на уровне таблицы понимает, что внутри что-то заблокировано, а значит, exclusive-блокировку на всю таблицу взять нельзя. Такой хинт на верхнем уровне сильно всё оптимизирует. В программировании подобной концепции я не встречал, а в базах данных она есть — довольно интересная штука.

[15:55] Давайте подытожим про двухфазную блокировку. Это самый распространённый протокол работы с блокировками и вообще с управлением конкурентностью, многопоточностью в базах данных: почти любая база так или иначе поддерживает two-phase locking. Но это не единственный способ гарантировать те или иные уровни изоляции. Есть и другой подход к контролю конкурентности во время выполнения транзакций — и он совсем не использует блокировок, а использует таймстемпы. Когда я говорю «таймстемп», это может быть логический таймстемп, системные часы или какой-то логический счётчик. Сам таймстемп — это абстракция, о которой мы пока не задумываемся: все проблемы со временем оставим на потом и будем верить, что какая-то система поставляет нам правильный таймстемп. Приложение у нас пока не распределённое, так что сильных проблем с этим не будет.

[17:01] Итак, как работает базовый алгоритм timestamp ordering? Блокировок он не использует вообще. При каждом чтении объекта X мы записываем рядом с ним значение таймстемпа, с которым прочитали. У каждой транзакции есть свой таймстемп на момент старта: читая X, мы пишем в таблицу рядом с X, что последний read-таймстемп — 3; записывая X, пишем рядом, что последний write-таймстемп — 4, и так далее. Рядом с объектами появляется метаинформация с таймстемпами. Как это разруливает конфликты? Если какая-то транзакция записала для X write-таймстемп 4 (то есть записала «в будущем», позже нашего), а мы транзакция с таймстемпом 3 и пытаемся X прочитать, — мы немедленно откатываемся и начинаем заново. То есть если кто-то из будущего записал write-таймстемп больше нашего, читать это значение нельзя, и мы откатываемся.

[18:14] Давайте ещё раз, по шагам, про базовое чтение. Прежде чем читать X, мы смотрим его write-таймстемп. Если его записали после нас — write-таймстемп X больше нашего, — значит, мы читаем «значение из будущего», делаем аборт, перезаписываем наш таймстемп более новым и пробуем заново. Если же write-таймстемп с тех пор не поменялся и наш таймстемп больше либо равен write-таймстемпу X, мы спокойно читаем X и одновременно пишем в его read-таймстемп наш таймстемп — помечаем, что последнее чтение произошло тогда-то. И делаем копию X где-то внутри нашей транзакции, чтобы работал repeatable read: при повторном чтении мы пойдём не в таблицу, а к своему локальному X. Базовая запись даже чуть проще: если наш таймстемп меньше read-таймстемпа или write-таймстемпа объекта, нужно рестартовать. На write мы смотрим не только на write-таймстемп, но и на read: если кто-то уже прочитал «из будущего», перезаписать значение нельзя. А во время записи мы обновляем write-таймстемп.

[19:57] Фух. Думаю, для подкаста было не слишком сложно, но этот алгоритм важно понять, потому что он — основа для реальных алгоритмов. Я сейчас описал то, чего не делает ни одна база данных: это теоретический алгоритм, в реальной жизни его никто не использует. А не используют потому, что представьте — при каждом чтении и каждой записи X мы идём в базу, в таблицу, и обновляем write- и read-таймстемпы. Это какое-то централизованное хранилище, в которое мы пишем даже во время чтения: если 10 транзакций начнут читать X, они 10 раз запишут туда новые значения — представляете, какой контеншен на записи. Это просто неэффективно; когда мы читаем, мы вообще не хотим ничего писать, даже быстро проинкрементить одно число. Но сама идея крутая, и поверх неё реализованы другие алгоритмы. Важно, что это управление конкурентностью без блокировок: нет ни дедлоков, ни Lock Manager, ни waits-for-graph — куча сущностей из мира блокировок просто уходит. Реальных алгоритмов, которые переиспользуют эти техники, два: Optimistic Concurrency Control и Multiversion Concurrency Control.

[21:20] Давайте сначала посмотрим, как работает Optimistic Concurrency Control. Откуда название? Вот мы и дошли до момента, когда пора объяснить, чем optimistic concurrency control отличается от pessimistic. А отличается тем, что pessimistic concurrency control — это как раз двухфазная блокировка, самый банальный пример пессимистичного управления конкурентностью. В чём пессимистичность? В том, что мы считаем, будто конфликтов будет много, будто с этим значением работает много транзакций, и потому сразу, наперёд, его блокируем: «всё, никто с ним не работает, работать буду я». А optimistic говорит: «да наверное, не так уж много транзакций, и скорее всего конкретно с записью Саши Пахомова сейчас никто не работает — поэтому я не буду брать блокировку, а в конце, при коммите, проверю».

[22:24] Как эта проверка работает и как вообще можно не брать блокировку, а что-то валидировать в конце? Каждая транзакция обладает своим так называемым private workspace — это область памяти, принадлежащая только этой транзакции. Туда попадает любой объект, который мы читаем или модифицируем во время работы: по сути, мы делаем локальную копию всех данных, с которыми работаем. Если мы 10 раз читаем X, то первое чтение положит X в private workspace, а дальше мы уже спокойно читаем его оттуда. Во-первых, это лучше по перформансу — мы не ходим в централизованное хранилище; во-вторых, мы сразу избавляемся от таких вещей, как dirty read, — сделать грязное чтение не можем, потому что реально читаем из таблицы один раз, а потом читаем своё. То же с записью: мы не пишем сразу в базу, а модифицируем в private workspace.

[23:14] У этого протокола три фазы: фаза чтения, фаза валидации и фаза записи. Перед коммитом мы сначала выполняем валидацию, потом запись, а во время работы транзакции идёт фаза чтения. На пальцах: транзакция стартовала, начитала значения в private workspace, работает с ними — апдейтит, делит — это фаза чтения. Потом, перед коммитом, наступает фаза валидации — самая сложная. Мы берём наш write-set (всё, что меняли и писали, — мы же это у себя в private workspace запомнили) и проверяем, не было ли транзакций с таким же write-set или пересекающимся, которые что-то поменяли во время нашей работы. Поскольку, работая, мы сохраняем таймстемпы, мы можем понять: если наш таймстемп в write-set больше всех остальных, значит, мы логически выполнились последними и имеем право записать. А если логически выполнились до какой-то транзакции — на валидации принимаем решение откатиться и выполнить всё заново. Это и есть optimistic concurrency control. Во время записи мы просто берём более-менее глобальную блокировку, записываем и обновляем все таймстемпы — write-таймстемпы и так далее.

[24:45] Такой подход отлично годится для транзакций, которые, например, всегда read-only: мы постоянно читаем, записей нет — значит, и конфликтов нет. Или когда чтения-записи активные, но разные транзакции работают с разными областями базы или таблицы. Банально: интернет-магазин, я меняю свой профиль, и ещё сто тысяч юзеров по миру одновременно меняют свои — у каждого свой id, каждый меняет только свою строку. При таком подходе блокировки не нужны: формально мы выполняемся параллельно, но по факту каждый на своём сабсете, и optimistic concurrency control работает идеально — будто мы всё фигачим параллельно и говорим, что конфликтов не будет, и их действительно нет. Но есть и минусы. Например, большой overhead на локальное копирование данных: private workspace бесплатно не появляется, его нужно создать, мейнтенить, и он может быть довольно большим — при огромном числе транзакций всё это может раздуться и ударить по памяти и перформансу. Также валидация и запись — узкие места, bottlenecks: мы должны провалидировать или записать объекты в центральную базу, а не в локальный workspace, и там уже нужны блокировки, потому что при проверке тоже может быть контеншен.

[26:19] И ещё сравнение с двухфазной блокировкой: она зафейлится быстрее. Представьте длинную транзакцию, которая выполняется, скажем, час. Взять блокировку где-то на середине пути, понять, что не можешь, даже оказаться жертвой дедлока, откатиться и начать заново — всё равно лучше, чем час выполняться под optimistic concurrency control и в самом конце, на валидации, услышать: «сорян, чувак, ты записал что-то, что записать нельзя», — и быть откаченным. И так снова на час, а на следующий час опять откат. То есть long-running transactions под OCC начинают страдать, и тут двухфазная блокировка пусть и не так эффективна, но хотя бы работает.

[27:15] Итак, с optimistic concurrency control разобрались. Но всё это время мы предполагали, что работаем с одним значением — X, Y, одной строкой. А если мы работаем с диапазонами, никакой гарантии, что диапазон каждый раз отработает одинаково, нет. Я про фантомные записи. Если хотите освежить представление про phantom read, послушайте предыдущий выпуск, а сейчас просто пример. Мы считаем статистику — например, всех юзеров старше 18: по условию age > 18 делаем count и получаем 100 человек. Потом в той же транзакции пересчитываем count и получаем 101. Даже если использовать two-phase locking в том понимании, как я описал, возможна проблема фантомной записи: мы блокировали все записи, где age > 18, — эти 100 записей, взяв на каждую shared lock (не на всю таблицу, а на каждую сущность). Потом добавилась новая сущность, на которую у нас блокировки нет и быть не может. И когда мы заново сделали count, мы её увидели, и она законтрибьютила в результат — 101. Таким образом, даже используя блокировки, мы получили фантомную запись — гарантии serializable нет.

[28:46] Базы данных решают эту проблему по-разному, но подходов ряд. Первый: при каждом подсчёте статистики читать данные заново. Есть датасет из 100 юзеров в начале, мы его где-то сохранили, потом читаем заново, видим 101, сравниваем датасеты и говорим: в результатах чтений есть фантомная запись — делаем fail и начинаем транзакцию заново. Второй: лочить предикаты. Теория, которая на практике скорее не используется: на предикат age > 18 вешаем логическую блокировку, и каждая вставка или удаление, попадающая под этот предикат, сначала ждёт нашего выполнения, а потом исполняется. То есть блокировка уже не на атрибуты тюплов, а на предикат. Штука довольно наукоёмкая, и систем, которые её реализуют, вроде бы мало. А вот что реализуют — это index locking: блокируем не саму таблицу, а индекс, если он есть. Если есть индекс по условию age > 18, мы по нему заблокируемся, и когда будем вставлять значение, оно попадёт в тот лист или поддерево индекса, которое заблокировано, — и проблемы фантомных записей не будет. Ещё можно брать блокировки на диапазоны ключей и делать оптимизации на уровне иерархии. В общем, проблема решаема; я рассказал про неё, чтобы вы понимали — там не всё так просто, и подобных проблем куча.

[30:31] Говоря про уровни изоляции, о которых я рассказывал в предыдущем выпуске: я тогда разобрал базовые уровни, но есть и другие. Давайте посмотрим, какие уровни изоляции самые популярные базы используют по дефолту и какие максимальные предоставляют. В реальности serializable — самый строгий уровень — нужен не всегда, и базы позволяют себе опустить его на один или даже на два уровня, просто потому что поддерживать serializable по перформансу очень тяжело. А более низкий уровень изоляции точно так же решает большинство проблем пользователей — даёт гарантии, скажем, read committed, которого достаточно большинству приложений. Оказывается, большинству serializable не нужен: если вы не переводите деньги со счёта на счёт, где всё должно быть чётко, возможно, вам хватит и меньшего. Например, Postgres по дефолту даёт read committed, но при желании можно поднять до serializable — понимая, что, повышая уровень изоляции и делая его строже, мы ухудшаем перформанс: заставляем базу использовать более строгие, более пессимистичные алгоритмы и больше проверок, а конкурентность и параллельность падают.

[31:57] Oracle по дефолту тоже поставляет read committed, как и Postgres. Но, кстати, у Oracle даже serializable нет: самый высокий, самый строгий уровень изоляции в Oracle — это snapshot isolation. Про snapshot isolation я в предыдущем выпуске осознанно не рассказывал, чтобы не перегружать. Это уровень на один ниже serializable, и вот это «на один» — аномалия write skew. Это та самая аномалия, когда две транзакции обе выполняют все предикаты и констрейнты, консистентность соблюдается, но результат коммита этих двух транзакций нарушает какой-то общий инвариант. Write skew допускается в snapshot isolation, а в serializable её уже нет — это единственное отличие между ними, если смотреть сверху. Так что Oracle serializable не поставляет — и ничего, зарабатывает много денег, так что, может, он и не так уж нужен. А вот база данных Google Spanner поставляет по дефолту (и одновременно как самый строгий) уровень strong serializable.

[33:05] Помимо просто serializable, есть ещё strong serializable. «Strong» здесь про то, что не просто результат выполнения транзакций будет таким, будто они выполнялись одна за другой (это говорит уровень serializable), но ещё и то, что они выполнятся в том же порядке, в котором начались. Вводится дополнительное условие: если транзакция 1 началась после транзакции 2, то гарантированно результат будет такой, будто транзакция 1 действительно выполнялась после транзакции 2. Потому что в serializable они могут поменяться местами — он не гарантирует итоговый порядок. А Spanner гарантирует, что результат будет как при выполнении в порядке старта. Это строже, и, думаю, в будущих выпусках мы разберёмся, как они этого достигают. А пока этой информации нам достаточно.

[33:58] Небольшой промежуточный итог, чтобы понять, что мы уже обсудили. Мы разобрали двухфазную блокировку и optimistic concurrency control, немного разобрали уровни изоляции транзакций, узнали про новый уровень — snapshot isolation. И идея на текущий момент такая: все эти плюсы и минусы, pros and cons, — это всегда trade-off. В базах данных слово заезженное, но это действительно так: всё есть trade-off. Если у нас высокий контеншен и одни и те же записи очень часто меняются — и на запись, и на чтение, — то, наверное, проще взять блокировку, сделать работу и отпустить её. А когда транзакции межсобойно разрежены и общие данные не мутируют и не читаются, идеально подходит optimistic concurrency control. Поэтому всегда нужно понимать, какой у вас кейс, какая нагрузка, как вы используете базу, — и тюнить её под себя, используя подходящие именно вам алгоритмы. Думаю, для этого этот подкаст в целом и существует.

[35:05] Итак, остался самый мощный и самый популярный алгоритм, который есть в большинстве баз данных и который глобально поменял то, как базы данных вообще работают, — это MVCC, Multi-Version Concurrency Control. Придуман он был ещё в 98-м году. Как и всё, что мы сейчас обсуждаем и используем в современных базах, идеи и базовые алгоритмы заложены где-то в 70–80-х: глобально архитектура дисков и компьютеров с тех пор не поменялась, мы просто растём, увеличиваем скорости, но алгоритмы и идеи в них те же. И MVCC — один из них. Коротко протокол можно описать так: база данных — уже не транзакция, а сама база — поддерживает множество физических версий одного и того же логического объекта. Если попроще: у каждой записи есть версия, и когда транзакция что-то записывает, создаётся новая версия объекта — текущая не перезаписывается in place. Была версия 1 со значением 1 — стала версия 2 со значением 10. А когда кто-то читает, он читает самую последнюю версию, если он её видит.

[36:23] Преимущество протокола в том, что writer’ы — транзакции, которые пишут, — не блокируют читающие транзакции, потому что читающие читают свою версию, а пишущие добавляют новую запись, не перезаписывая существующую. И readers, соответственно, не блокируют writer’ов — нет таких физических блокировок, как в two-phase locking. Мы очень легко достигаем snapshot isolation: нет проблемы repeatable read, потому что читаем одну и ту же версию; dirty write тоже не может быть, потому что читаем версию, доступную на момент старта транзакции. То есть by default протокол устроен так, что таких аномалий нет. Но зато остаётся аномалия write skew, которую без блокировки и глобальной проверки решить невозможно. Поэтому MVCC поставляет snapshot isolation, и всех это устраивает. Сама реализация довольно сложная, так что снаружи, верхнеуровнево, посмотрим на основные строительные блоки. Но именно multiversion concurrency control сейчас использует большинство баз данных, и это считается state-of-the-art. Внутри, конечно, используются и идея timestamp ordering, и optimistic concurrency control, и two-phase locking — все эти вещи так или иначе там есть.

[37:42] Глобально design decisions, которые нужно принять при имплементации MVCC, — их несколько. Одно из них — как всё это хранить, потому что версии объектов можно хранить по-разному. Например, можно сделать версионированный storage на уровне структуры данных. Понятно, что B-tree должно быть адаптировано под высокую запись, потому что писать в него мы будем много. И не обязательно иметь операции удаления или изменения — достаточно очень быстро поддерживать апдейт. Какой у нас может быть storage? Append-only: в одной таблице все записи, мы в неё просто пишем. Поменяли X на Y — пишем новую версию, а старые остаются. Когда кто-то читает данные через индекс, тоже два варианта: индекс указывает либо на новейшую версию, либо на старейшую. То есть цепочка версий выстраивается от старого к новому или наоборот — и это тоже trade-off. Если от старого к новому, мы указываем на старую версию, а новые добавляем очень быстро, не обновляя указатель в индексе, — но при чтении приходится разворачивать цепочку до самой свежей версии: запись ускоряется, чтение замедляется. Либо наоборот — указываем на самую новую и сразу её отдаём при чтении, но при записи нужно идти и обновлять указатель в индексе, а это не просто: надо взять блокировку, чтобы никто параллельно не обновил. Тогда чтение быстрое, запись медленная.

[39:48] Помимо версионированного стораджа, можно использовать так называемый time-travel storage — отдельное хранилище рядом с основным, не там, где таблицы, а сбоку. Есть обычный сторадж (B-tree), а есть указатель на time-travel: хочешь поработать со старыми версиями — иди туда. Основная таблица ссылается на time-travel, в основной всегда самая новая версия, а более старые хранятся в time-travel-таблице. Тоже рабочий вариант. И в последнее время часто используют delta storage: храним не версии объектов, как в time-travel, а дельты — приращения объектов. Дельты можно определить по-разному: это может быть значение, над которым нужно выполнить операцию (сложение и т.п.), чтобы получить следующее, либо готовые значения. Например, если строка — это целый tuple, мы храним не новое значение V2 целиком, а только тот кусочек, который изменился. То есть храним дельты, а не сами строки.

[41:12] Помимо выбора основного стораджа — delta, time-travel или просто append-only-таблица — надо понять, что делать с мусором, потому что в MVCC его неизбежно будет много. Каждое старое значение: представьте, за день мы обновляем миллион записей — будет миллион новых и миллион старых. На следующий день ещё миллион. И так накапливаем, хотя up-to-date-состояние таблицы — вот эти актуальные записи, а зачем хранить предыдущие 10 миллионов, не до конца понятно, и time-travel не всем нужен. Я, честно говоря, ни разу его не использовал. Мультиверсионность нужна только в момент, когда какая-то из транзакций работает со старыми версиями. Как только ни одна транзакция значение уже не видит и с ним не работает, хорошо бы выполнить сборку мусора. И тут опять выбор, как её делать. Можно в демоне, в фоновом потоке, который просто считывает все тюплы и смотрит: ты старая, на тебя какая-то транзакция ссылается или нет? Каждый раз делать проверки, старые подчищать — такой вот вакуум. Или на уровне транзакции: при коммите или роллбэке транзакция сохраняет свой update-set, и мы понимаем — вот эти конкретные тюплы обновлены, значит, появились новые версии, а старые нужно подчистить. Это умнее, потому что мы не делаем каждый раз full scan; если таблица очень большая, вакуум будет долгим.

[42:55] Помимо background-вакууминга, можно чистить во время чтения. Когда какой-нибудь worker thread делает обход дерева и начинает высчитывать дельту, вычислять последнее значение, он посреди этого думает: «так, я уже высчитал сто значений, актуальная — последняя, на неё ссылается одна последняя транзакция, а другие значения никому не видны — я их сейчас прямо на месте, во время чтения, схлопну». Это так называемый cooperative cleaning. Trade-off понятен: в фоне мы ничего не делаем, но во время чтения платим эту монету за подчистку старых версий. Ещё в MVCC есть довольно большая проблема со вторичными индексами. Есть первичный индекс — он один и через primary key ссылается на актуальную запись, — а есть secondary index, который может ссылаться на запись через primary index или напрямую. И если этих secondary-индексов, скажем, 100 или 200, то при апдейте конкретной записи нам нужно пойти во все 200 и обновить у них новую версию. Добавление версии словно добавляет ещё одно измерение в данные, и все структуры, которые на данные ссылаются, теперь должны ссылаться с учётом версий.

[44:20] Поэтому, когда secondary-индексов много, проблема в том, что их нужно обновлять. Как правило, они ссылаются через primary: мы обновляем новую версию, идём в один primary-индекс, обновляем его, и всё окей — а secondary через primary легко находит нужное. То есть ссылаться напрямую при MVCC не так уж выгодно. И сами структуры данных в MVCC, эти индексы, возвращают, как правило, не одну entry, а много: версия вшита везде, она проникает на все уровни абстракции. Поэтому когда мы просим у индекса запись Саши Пахомова, он вернёт не одну последнюю запись, а список версий, — а я, транзакция-читатель, возьму нужную мне версию, соответствующую моему таймстемпу. Меняется и процесс удаления: при MVCC удаление происходит либо через delete-флаг — создаём новую версию объекта с флагом «удалён», — либо через tombstone: создаём не новую версию объекта, а специальный tombstone-tuple, маркер того, что значение удалено. Старые версии продолжают жить для транзакций, которые их используют и не знают, что мы удалили значение; но будущие транзакции с новым таймстемпом прочитают этот tombstone-маркер и поймут — значения нет, оно удалено. А потом, во время вакуума, оно удалится окончательно, когда его уже никто не читает.

[46:04] Кажется, это всё, что я хотел рассказать. Если вы дослушали до этого момента — вам огромный респект: значит, я не зря всё это делаю, спасибо. Сегодня вы узнали, что большинство современных баз данных поддерживают двухфазную блокировку и мультиверсионность данных. А в следующем выпуске мы повысим градус гиковости и разберёмся, как работают Log-Structured Merge Trees, или просто LSM-деревья, — сейчас это основной конкурент B+‑деревьев. Обещаю подготовиться и разложить всё по полочкам. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!