#31: WAL: сердце любой базы данных

[00:21] Здорово! Меня зовут Саша Пахомов, и я инженер, который любит своё дело. Вы слушаете подкаст, в котором разработчик современной базы данных изучает, как они работают, и делится знаниями со слушателями. Сегодня мы по полочкам разберём процесс восстановления после сбоя. Благодаря ему мы можем гарантировать атомарность транзакций и их долговечность. Без преувеличения можно сказать, что это сердце почти любой базы данных. Постараюсь быть кратким и не душнить. Это выпуск про Write-Ahead Log. Поехали!

[01:02] Для начала давайте разберёмся, какую проблему мы решаем. Зачем нам вообще что-то логировать, добавлять какой-то новый уровень сложности в нашу и без того сложную систему баз данных? Проблема в том, что мы, как разработчики баз данных, используем ресурсы по максимуму: предполагается, что базой данных будут пользоваться многие приложения, что нагрузка будет высокой и всё должно работать максимально быстро. А чтобы что-то работало максимально быстро, нужно использовать максимально быструю память. На текущий момент более-менее доступная быстрая память — это оперативная память, и она используется на все сто процентов. Как вы знаете, внутри базы данных есть и буфер-пулы, и всякие кэширующие вещи — они, безусловно, есть.

[01:44] Проблема оперативной памяти в том, что она недолговечна. Что это значит? Что если произойдёт какой-то сбой… А какой сбой может случиться? Ну, в самом банальном примере — отключение питания у компьютера, на котором работает база данных. Если отрубить питание, всё, что было в оперативной памяти, пропадёт — и через минуту мы увидим, что данных нет. Так вот, база данных, если коммитит, то коммитит навсегда.

[02:25] Помимо таких жёстких сбоев, могут быть, например, логические сбои. Скажем, не отработал constraint и нужно откатить транзакцию. Или случился deadlock в блокировках. Или операционная система глюканула, произошло деление на ноль и так далее — очень много бывает ошибок, после которых нужно предпринять какие-то действия, например откатиться.

[02:43] Так что проблемы у нас на самом деле две. Первая — как откатывать транзакции назад, если что-то пошло не так. Вторая — как восстанавливаться после сбоя. И обе эти проблемы решаются с помощью write-ahead log. Но, как и всё в программировании, у этого решения есть трейд-оффы — это не серебряная пуля. В частности, оно не защищает нас от порчи диска. Если у диска сгорела или сломалась вращающаяся головка, или его просто уборщица залила водой, — никакое логирование не поможет. В этом случае состояние базы данных нужно восстанавливать из заархивированных бэкапов, которые хранятся распределённо на других машинах, чтобы восстановить базу хотя бы до какого-то состояния. Но то, что база выполняла в момент, когда диск залили водой, скорее всего, уже не восстановить. Это, впрочем, другой случай — от всех остальных сбоев мы более-менее защищаемся с помощью write-ahead log.

[03:37] Справедливости ради, прежде чем погружаться в тему глубже, давайте рассмотрим, какие у нас есть альтернативы. Мы же можем просто не использовать оперативную память — записывать каждый коммит сразу на диск. Вот прямо каждый раз: любая транзакция, прежде чем вернуть OK на пользовательский коммит, сначала записывает все данные, которые она замодифицировала, из оперативной памяти на диск. Так мы гарантируем, что данные там остаются, и только после этого возвращаем OK. Очевидный минус этого решения в том, что оно непроизводительное. Представьте: несколько тысяч, а то и сотни тысяч транзакций одновременно начинают коммитить — и это сотни тысяч записей на диск.

[04:48] Да, мы не будем флашить на диск все страницы, но где-то какая-то информация всё-таки должна оказаться. И как раз эту информацию мы складываем в write-ahead log. То есть все изменения, которые транзакция произвела над данными до своего коммита, должны быть записаны в write-ahead log, в эту структуру данных, — и только тогда мы можем сказать, что транзакция закоммитилась.

[05:09] Важно отметить: мы не записываем грязные страницы с модифицированными данными этой транзакции из оперативной памяти на диск в момент коммита — мы записываем лишь маленький кусочек в write-ahead log, а грязные страницы потом дозапишутся асинхронно. Это и есть оптимизация: мы не бампаем на диск все грязные страницы, а сохраняем только необходимую информацию в write-ahead log.

[05:35] С записью грязных страниц на диск связан ещё один момент — политика буферизации. Немного её объясню, потому что в контексте восстановления и логирования она имеет значение. Мы можем использовать политику steal/no-steal и force/no-force. steal означает, что мы можем записывать на диск грязные страницы, модифицированные ещё не закоммиченными транзакциями. Представьте: какая-то транзакция работает в буфер-пуле, меняет что-то — значение a на b, b на c; а другая транзакция рядом в этой же странице тоже что-то меняет и делает commit. Та, которая закоммитилась, обязана записать эту страницу на диск. И если у нас политика steal, мы можем записать эту страницу на диск как есть — то есть фактически записать на диск незакоммиченные данные. Если же мы используем no-steal, то есть противоположную политику, — мы не можем записывать незакоммиченные данные на диск.

[06:47] А со второй стороны у нас есть force/no-force. Здесь либо мы перед коммитом ждём, пока грязные страницы запишутся на диск, либо не ждём записи этих страниц, а используем лог. Получается, с логом мы уже знакомы — это политика steal + no-force: мы разрешаем писать незакоммиченные значения на диск, но не ожидаем записи страниц на коммите.

[07:11] А вторая политика — no-steal + force: мы не записываем незакоммиченные значения на диск, но при коммите ожидаем записи всех изменённых значений. Этот подход называется shadow paging — можно представить его как copy-on-write. Вот когда мы рассматривали B-деревья, при каждой модификации часть дерева просто копируется и страницы модифицируются — такое как бы раздвоение: есть мастер и реплика. И когда мы делаем коммит, указатель на руте переключается на ту ветку, которая изменена. То есть коммит триггерит это переключение, а раз триггерит — значит, мы должны записать новую структуру данных на диск, то есть делаем force. Проблема shadow paging в том, что это много random writes: мы пишем в разные участки диска, и это неэффективно, если мы хотим максимизировать runtime базы данных.

[08:03] А вот если нам нужно быстро восстанавливаться после краха, то политика no-steal + force подходит лучше всего, потому что восстановления как такового у нас нет: каждый коммит записывает актуальное состояние базы данных, и мы просто поднимаемся из того состояния, которое есть, — если грубо. Но я не хочу на этом сильно останавливаться, потому что абсолютное большинство баз данных использует другую политику — steal + no-force, — которая и является подходом write-ahead logging. Сейчас про него подробно и поговорим.

[08:38] Чтобы было понятнее, давайте представим себе такую плашечку в памяти. Она конечная: у неё есть какая-то начальная точка — пока не знаем какая — и конечный указатель на последнее значение. И какой-то процесс (или несколько процессов) туда постоянно записывает. То есть это append-only структура данных, лог: мы дописываем только в конец. Ещё эта структура иммутабельная — мы не можем её менять. Поэтому читающие процессы, которые по какой-то причине (например, для восстановления) читают эту структуру, могут быть уверены, что никто не поменяет значение у них под ногами, — ведь структура иммутабельная.

[09:19] Что же мы дописываем в конец? Так называемые записи логирования, или записи журналирования, на английском — log records. Это записи, которые, по сути, хранят журнал того, что происходит с базой данных в каждый момент времени. Самая примитивная запись может выглядеть так: ID транзакции (какая транзакция выполняет действие), идентификатор объекта, над которым происходит действие (указатель, страница — не так важно), и состояние объекта до и после. То есть log record хранит идентификацию, по которой мы можем понять, кто с чем работает и что произошло, — какие данные были изменены. Это полезно, если мы захотим потом откатываться назад: у нас есть before value — значение, которое было до, — и мы просто его накатим. Очень удобно. Также бывают более служебные записи, которые говорят, что транзакция началась, что транзакция закончилась (commit), что вызван abort, и так далее. Все эти действия одно за другим записываются в лог.

[10:23] Что важно понимать про лог, что играет ключевое значение? Во-первых, он должен располагаться на диске. Но мы не можем каждый раз писать на диск — у нас должен быть буфер. Потому что если записывать на диск каждое действие, это почти ничем не будет отличаться от записи грязных страниц на каждый commit. Поэтому у write-ahead log есть небольшой буфер — так называемый хвост, или tail. Сначала мы очень-очень быстро буферизируем все эти записи в оперативной памяти, а записываем этот хвостик на диск либо когда он вырастет до достаточного размера, либо когда одна из транзакций, записанных внутри этого буфера, закоммитится.

[11:06] Так вот, ключевое, что нужно понимать: перед коммитом транзакции мы обязаны зафлашить буфер в write-ahead log — без этого коммит не будет считаться успешным. Это первое строгое требование. Второе строгое требование (хотя по логике оно как раз первое): любое действие, любая модификация страниц должны сначала записываться в лог, и только потом происходит непосредственная модификация страниц в буфере. Так мы страхуемся: если мы начали что-то делать в буфере и отключили свет, то, восстановившись, мы ниоткуда не возьмём эту информацию. А вот если мы сначала запишем лог, и он потом попадёт на диск, — мы будем знать, что происходило с буфером. То есть сначала декларируем свои намерения о действии, записывая лог, а потом совершаем само действие.

[11:58] Давайте ещё раз повторю эти две вещи, потому что если их понять, то можно понять, к чему вообще write-ahead log. Первое: на каждый коммит транзакции мы записываем на диск состояние лога и всё, что относится к этой транзакции, и только потом говорим, что коммит совершён, — так гарантируется долговечность. Второе: чтобы гарантировать корректность работы алгоритма и корректность восстановления, все модификации данных сначала записываем в лог, а только потом производим реальные модификации над страницами. Такие вот два простых правила.

[12:32] В write-ahead logging есть и узкие места, некоторые ограничения. Например, требование на каждый коммит записывать tail на диск может быть неэффективным: у нас могут быть тысячи, сотни тысяч транзакций, которые начинают коммитить, и каждый раз мы будем триггерить флаш на диск, то есть делать fsync, — а это небыстрая операция. Поэтому некоторые реализации группируют коммиты — так называемый grouped commit. Допустим, есть буфер в памяти, и в него пишут две транзакции. Первая хочет закоммититься, но система понимает, что вторая тоже пишет в этот буфер, — поэтому первая транзакция подождёт вторую, и они закоммитятся одновременно: произойдёт один fsync на диск, а закоммитятся две транзакции или больше. Это оптимизация, но она может быть неудобна, если у нас есть одна долгая-долгая транзакция, которая тормозит за собой остальные, — поэтому подходить к этому нужно аккуратно.

[13:28] Что касается логирования действий: как я уже говорил, запись может состоять из значения до, значения после и какой-то другой метаинформации. Так вот, значения до и после можно выразить, грубо говоря, в двух вариантах. Первый — физический: мы говорим, что в колонке a было значение 1, стало значение 2. Мы знаем конкретное физическое значение: было 1, стало 2. Второй вариант — залогировать целый запрос, который это делал: например, UPDATE ... SET a = 2 WHERE a = 1. То есть мы логируем сам SQL-запрос или какое-то его внутреннее представление — не так важно, — но делаем это на логическом уровне. Это называется логическим логированием.

[14:12] Чем одно хорошо, другое плохо? Физическое логирование позволяет легко сделать откат, потому что у нас тут же есть before value: при восстановлении мы быстро-быстро с этим before value откатываемся. Это даже проще с точки зрения реализации. А при логическом нам нужно применять запрос ко всей базе данных, и при восстановлении это может быть долго. Поэтому базы данных на самом деле совмещают эти два подхода. Если мы апдейтим, скажем, миллион записей одним запросом, то, конечно, проще залогировать один запрос, чем миллион состояний всех записей, — иначе это неэффективно с точки зрения использования лога. Так что зависит от того, какую схему база данных будет использовать.

[14:56] Помимо оптимизации занимаемого в логе места с помощью логического логирования, есть ещё одна вещь — даже не оптимизация, а необходимость. Это checkpoints. Это тоже специальные записи, как begin transaction или commit transaction: специальная запись checkpoint, которая говорит, что всё, что было до неё, уже стопроцентно записано на диск, все страницы модифицированы, — и нам нет смысла больше хранить эту часть лога и читать её при восстановлении, потому что всё уже и так на диске. Поэтому раз в какое-то время база данных делает checkpoint — это специальный асинхронный процесс, — и записывает состояние всех грязных страниц на диск. Таким образом с одного конца лог постоянно растёт, а с другого конца с помощью checkpoint’ов отрубается. Интересный процесс.

[15:41] Но когда мы говорим про checkpoints, тут есть важный момент: есть два способа их делать, которые всплывают в дискуссиях. Первый — блокирующий checkpoint: чтобы его сделать, нужно остановить все запросы, заморозить все бегущие транзакции, арестовать все блокировки на запись и сделать этот дамп. Это как stop the world из мира Java и garbage collector’ов — что очевидно неэффективно. Что же использует большинство современных баз данных — так это fuzzy checkpoint. По сути, это двухфазный checkpoint, у которого есть первая фаза — begin checkpoint — и вторая фаза — end checkpoint, а всё, что происходит между этими двумя записями, — это как раз асинхронная запись страниц. В детали, как устроен fuzzy checkpoint, я вдаваться не буду — думаю, если интересно, посмотрите. Но его прикол в том, что он позволяет не блокировать бегущие транзакции: это действительно асинхронный процесс, который почти никак не влияет на производительность базы данных.

[16:45] Итак, мы подошли к интересному моменту обсуждения write-ahead logging. Мы уже понимаем, как формируется write-ahead log, какие записи туда пишутся транзакциями и так далее. Но мы ещё не обговорили основное — то, ради чего мы всё это делаем. По сути, если предположить, что электричество никогда не отключается и никаких непредвиденных ошибок не случается, — можно вообще выкинуть лог из системы, и с точки зрения внешнего наблюдателя она будет работать точно так же, даже быстрее, потому что мы не будем делать лишние записи на диск. Но электричество, естественно, отключается, и shit happens, поэтому обязательно нужно рассмотреть процесс восстановления из лога: то, ради чего эта информация служит, и как она потом используется.

[17:27] Когда мы говорим про восстановление из лога, как правило, это целое семейство алгоритмов под названием ARIES. Расшифровывается это как Algorithms for Recovery and Isolation Exploiting Semantics. Не спрашивайте, почему такое сложное название, но если перевести своими словами — это алгоритмы восстановления и изоляции на основе семантики. Короче говоря, это то, как из лога восстанавливается большинство современных баз данных.

[17:51] Прежде чем объяснить сам алгоритм и посмотреть на его фазы восстановления, нужно ввести ещё несколько дополнительных понятий. Я не буду глубоко в них копать, потому что для подкаста это немного сложновато, но эти слова фигурируют в объяснении того, как работает ARIES, и их нужно сначала пояснить. Буквально пара-тройка минут, думаю, — и всё будет плюс-минус понятно.

[18:21] Первое: чтобы использовать ARIES, нам нужно расширить наше прежнее понимание log record. То, что мы пишем в лог, — эту запись со значениями до-после и всякими айдишниками — нужно расширить, потому что без дополнительной информации ARIES реализовать не получится. Расширяем мы её с помощью специальных айдишников, которые называются LSN — Log Sequence Number. Это группа монотонно возрастающих циферок-идентификаторов, которые потом помогают при восстановлении. Самый основной — это просто LSN: монотонно возрастающий идентификатор записи лога. Первая запись лога получит LSN 1, вторая — 2, потом 3, 4 и так далее; они просто монотонно растут и позволяют идентифицировать log records между собой — по сути, это их айдишник.

[19:05] Помимо просто LSN, есть prev-LSN — предыдущий LSN, айдишник предыдущей записи. Благодаря ему по логу можно навигироваться не только от начала, но и от конца цепочки. По сути, чтобы для одной транзакции восстановить цепочку обратных действий, мы берём самую последнюю запись этой транзакции и по prev-LSN прыгаем на предыдущие записи по их айдишникам. Такие вот цепочки до и после, и навигироваться по ним туда-обратно очень легко с помощью пары prev-LSN и LSN. Ещё у каждой страницы есть свой LSN. В общем, всех этих номеров там штук пять-шесть, и служат они для того, чтобы алгоритм корректно работал. Например, мы не всегда можем записать страницу на диск: если prev-LSN, который лежит в странице, больше, чем last flushed LSN, — то есть лог ещё не зафлашился, а мы хотим зафлашить грязные страницы, — так не получится. Благодаря этим номерам система может отследить, что всё, что флашится в лог, флашится раньше того, что флашится в буфер-пул. Так мы соблюдаем очередность — а это нужно для корректности.

[20:15] Также, помимо commit, begin и abort для транзакций, есть маркер об окончании обработки транзакции — он называется TXN END. По сути, мы говорим, что всё: транзакция либо полностью закоммитилась и мы её обработали (она на диске), либо полностью откатилась и abort совершился успешно. Это тоже специальная служебная запись в контексте ARIES.

[20:38] Помимо обычных log records (обновила такую-то страницу, begin transaction, end transaction, удалила такую-то запись и так далее), мы ещё ведём журнал так называемых compensation log records. Это тот же журнал — не отдельный, — но в нём есть специальное подмножество записей, которые говорят, что мы делаем с данными не то, что делает с ними транзакция (то есть не обновляем), а откатываем их как система. Смотрите: в ходе обычной работы транзакция обновляет данные и записывает это в лог — update1, update2, update3. После этого мы принимаем решение сделать abort — например, даже с клиентской точки зрения что-то пошло не так, и транзакцию нужно отменить. Эти записи нам надо как-то откатить обратно, ведь мы их уже записали в лог. Поэтому мы создаём так называемые CLR — compensation log records, — которые говорят: откатываю значение с 3 к 2, откатываю с 2 к 1, откатываю к 0. То есть откат происходит в обратном порядке, и записывается он тоже в журнал. Зачем они нужны и почему мы не можем просто откатывать обратно — узнаем чуть позже.

[21:42] И последние два понятия в контексте ARIES, которые нужны, чтобы рассмотреть работу алгоритма, — это active transaction table (таблица активных транзакций) и dirty page table (таблица грязных страниц). Это просто таблицы, которые система заводит, чтобы во время чтения из лога (то есть во время восстановления) складывать в одну из них транзакции, которые мы сейчас читаем. По сути, это хэш-таблица, в которую мы, проходя по логу, помечаем: вот эта транзакция активна, вот эта активна, а вот эта заабортилась, а вот эта закоммитилась — поэтому убираем её из active transaction table. То есть это просто хранилища знаний, которые используются в процессе анализа лога при восстановлении. Точно так же и для грязных страниц: вот эта страница была грязная, вот эта была грязная, а вот эту потом зафлашили. Все эти записи хранятся в логе, и в процессе восстановления — при вычитывании того кусочка лога, который нам нужно восстановить, — мы складываем их в эти утилитарные таблицы.

[22:39] Всё. Теперь мы знаем все слова, все базворды, которые нужны, чтобы посмотреть, как работает ARIES. Давайте наконец это сделаем.

[22:52] Задача алгоритмов recovery — сделать так, чтобы база данных пришла в точно такое же состояние, в каком была в момент до краха. Крахом мы будем называть любое событие, например выключение света. Задача в том, чтобы, когда свет включили и мы запустили базу данных, через какое-то время — пять, десять, двадцать минут, час, сутки, в контексте алгоритмов не так важно — получить базу данных в точно таком же состоянии, в каком она была до краха, и это состояние должно быть корректным.

[23:24] Чтобы это сделать… вот, допустим, мы запустили базу данных, она поднялась и понимает, что ей нужно восстанавливаться из лога. Этот процесс делится на три фазы. Первая — analysis (анализ), вторая — redo, третья — undo. Redo означает, что мы накатываем изменения, которые есть в логе, а undo — откатываем.

[23:44] В первой фазе, фазе анализа, мы исследуем наш write-ahead log, начиная с последней точки checkpoint — того самого checkpoint, который мы рассматривали в начале. begin checkpoint, фаза checkpoint — это как раз та точка, с которой мы начинаем вычитывать при восстановлении. Мы просто берём блок с конца, находим первый begin checkpoint и говорим: всё, отсюда начинаем читать. Это ещё называется master record. Во время анализа мы вычитываем в хронологическом порядке, с увеличением LSN, всё, что происходило с базой данных с этого begin checkpoint и до краха. И в момент вычитывания как раз наполняем информацией наши active transaction table и dirty page table. То есть просто вычитываем, но пока ничего не делаем с данными — это просто анализ.

[24:29] После того как мы дошли до точки краха, начинаем фазу redo — восстанавливаем состояние грязных страниц в памяти на момент краха. По сути, мы берём все транзакции, которые оказались в active transaction table, смотрим, какие записи они обновляли, и просто начинаем обновлять записи — проигрывать заново всё это дело, как плеер. Есть некоторые оптимизации: например, можно не проигрывать транзакции, которые к этому моменту уже откатились и про которые мы точно знаем, что у них был abort, — их можно просто пропустить. А вот те, про которые мы не знаем, были они закоммичены или нет, мы просто проигрываем. Это фаза redo: мы проиграли и восстановили наш buffer pool в памяти на момент сбоя.

[25:13] Третья фаза — undo. Это фаза, в которой мы приводим базу данных в согласованное состояние. Что это значит? Сейчас в buffer pool в памяти находится набор страниц, модифицированных незакоммиченными транзакциями, — ведь некоторые транзакции во время сбоя не успели закоммититься. И то, что они не успели закоммитить, нам нужно откатить назад — то есть отыграть чуть-чуть назад наш лог для этих конкретных транзакций. Для этого как раз подходят наши записи предыдущих значений для каждой строчки в каждой таблице. Мы просто для тех транзакций, которые не успели закоммититься, отыгрываем назад и внутри buffer pool приводим состояние этих dirty pages к моменту begin этих транзакций.

[25:58] Таким образом, все транзакции, которые закоммитились, мы проиграли и записали на диск; те, которые не успели закоммититься, заабортили — всё, что они сделали, откатили назад одно за другим. И получили согласованное состояние базы данных. Для каждой обработанной транзакции сделали запись TXN END. Хорошо бы тут сделать новый checkpoint, чтобы в следующий раз опять всё это не проигрывать, — но я не уверен, что на этом этапе checkpoint делается.

[26:25] Тут важно отметить: во время undo-фазы, вместе с тем как мы применяем какое-то значение к странице в памяти, мы записываем так называемый compensation log record, который рассматривали раньше. Это нужно на случай, если сбой случится во время восстановления после сбоя, — чтобы мы не начали модифицировать данные ещё раз, по второму, третьему, четвёртому кругу. Ведь сбои могут быть постоянными — и это на самом деле частый кейс, когда какая-то неисправность диска приводит к тому, что сбой происходит каждый раз: только запустили базу данных — опять сбой. Так вот, чтобы не делать лишнюю работу и чтобы алгоритм работал корректно, во время отката мы фиксируем: откатываем вот это значение, потом вот это значение, — то есть тоже логируем процесс восстановления. Довольно интересный и забавный факт.

[27:13] Итак, давайте проговорим основные идеи сегодняшнего выпуска — их на самом деле немного. Я старался не вдаваться в детали: если в них уходить, это был бы опять выпуск на полтора-два часа, и вряд ли кому-то было бы интересно. А если было бы — пишите в комментариях к этому выпуску в телеграм-канале подкаста «Тысяча фичей». Подведём итог того, что мы рассмотрели.

[27:38] Мы поняли, что для восстановления после сбоя и для обеспечения durability из ACID большинство современных баз данных используют write-ahead log, у которого политика работы с буфер-пулами подразумевается steal + no-force. Большинство алгоритмов используют fuzzy checkpoint — двухфазные checkpoint’ы. В процессе восстановления используются фазы analysis, redo и undo. Мы записываем compensation log records, когда делаем undo, чтобы всё работало нормально, если произойдёт сбой. Также используются специальные идентификаторы — Log Sequence Numbers, LSN, — чтобы идентифицировать записи в логе и чтобы алгоритм работал корректно.

[28:19] Теперь вы знаете, как устроено журналирование в базах данных. Я уверен, что это знание вам пригодится. Не забывайте делиться подкастом с друзьями и коллегами — давайте прокачивать себя и людей вокруг. Ну а на этом всё. Услышимся!