Контрольные точки

примечание

Эта страница переведена при помощи нейросети GigaChat.

Порядок обхода дерева

Процесс контрольных точек (Checkpointer) обходит деревья OrioleDB в порядке LNR (лево-узел-право). Обход разбит на шаги. Результат каждого шага — сообщение, определяющее следующий шаг. Возможные сообщения приведены ниже.

1. WalkDownwards — на последнем шаге найден in-memory (в оперативной памяти) downlink во внутренней странице. Следующий шаг должен посетить страницу на нижнем уровне и начать ее обработку.
2. WalkUpwards — обработка страницы завершена на последнем шаге. Следующий шаг должен продолжить обработку родительской страницы.
3. WalkContinue — продолжить работу с текущей страницей после снятия блокировки. Происходит, когда процесс контрольных точек должен ожидать завершения конкурентной операции.

На рисунке ниже приведен пример обхода B-дерева OrioleDB процессом контрольных точек.

Процесс контрольных точек приходит к корневой странице n1 с сообщением WalkDownwards (шаг 1), затем проверяет первый downlink l1. Так как l1 является in-memory downlink, процесс контрольных точек переходит к листовой странице n2 с сообщением WalkDownwards (шаг 2). После сброса n2 процесс контрольных точек возвращается к n1 с сообщением WalkUpwards (шаг 3) и продолжает итерацию по downlink'ам страницы n1. Аналогично происходит спуск к странице n3 и возврат через downlink l2 (шаги 4 и 5). Downlink l3 оказывается downlink'ом с выполняющимся в данный момент вводом-выводом (IO in-progress), и процессу контрольных точек необходимо снять блокировку страницы n1, дождаться завершения ввода-вывода и продолжить с сообщением WalkContinue (шаг 6). После повторной блокировки n1 процесс контрольных точек обнаруживает l3 как downlink для дискового хранения и копирует его «как есть». Наконец, процесс контрольных точек спускается к странице n4 и возвращается через downlink l4 (шаги 7 и 8). Затем обработка n1 завершена, процесс контрольных точек заканчивает обход сообщением WalkUpwards.

Состояние контрольной точки

Пока процесс контрольных точек записывает дочерние страницы нелистовой страницы, могут происходить конкурентные разделения и слияния. Поэтому состояние контрольной точки содержит изображения нелистовых страниц под контрольной точкой в том виде, в каком они реконструируются по мере посещения downlink'ов процессом контрольных точек. Если конкурентных изменений нелистовой страницы не происходит, реконструированное состояние в итоге совпадает с состоянием страницы. В противном случае реконструированное состояние страницы может не совпадать ни с каким состоянием страницы в какой-либо момент времени, но всегда соответствует истории обхода дерева процессом контрольных точек.

Обратите внимание, что реконструированное состояние не содержит in-memory downlink'ов. In-memory downlink'ы заменяются downlink'ами для дискового хранения по мере записи страниц дочерних элементов.

На рисунке ниже приведен пример состояния контрольной точки.

Корневая страница n1, внутренняя страница n3 и листовая страница n8 в настоящее время находятся под контрольной точкой. Downlink l2 записан в реконструированное состояние. Downlink l3 является next downlink (следующим downlink) в реконструированном состоянии. Его ключ известен, но сам downlink неизвестен, поскольку соответствующие дочерние элементы еще не были записаны. Аналогично, downlink l6 записан, downlink l7 является next downlink, а downlink l8 еще не обработан.

Предположим, что произошло следующее событие:

1. Страница n7 была записана процессом контрольных точек.
2. Страница n8 была разделена на n8 и n9.
3. Страницы n6 и n7 были слиты. Результат отмечен как n67.
4. Процесс контрольных точек записал страницу n8 и начал обработку страницы n9.

Результирующее состояние приведено на рисунке ниже. Обратите внимание, что реконструированное изображение страницы содержит downlink l6 и l7 (поскольку они были посещены до слияния), но содержит l8 и next downlink, соответствующий l9 (поскольку эти downlink были посещены после разделения).

Автономные нелистовые страницы

Если нелистовая страница под контрольной точкой изменяется конкурентно, она становится «автономной» нелистовой страницей. Автономные страницы работают по следующим правилам.

1. Если страница отмечена как «автономная», все ее родительские элементы до корня также отмечаются как «автономные».
2. Если у страницы имеется связанное место для дискового хранения, эта ассоциация очищается. Соответствующее место отмечается как свободное пространство в текущей контрольной точке.
3. Автономная страница будет обрабатываться до тех пор, пока не будет достигнут ее hikey, независимо от количества посещенных страниц для достижения этой цели (из-за конкурентных вставок это может быть множество страниц).
4. Даже если исходная страница, соответствующая автономной странице, была разделена. Отслеживается страница, содержащая исходный hikey. Слияние, которое удалило бы этот hikey, предотвращается.
5. Если автономная страница заполнена, но соответствующий hikey еще не достигнут, текущее содержимое сбрасывается на диск (и родитель получает соответствующий downlink с WalkUpwards), но обработка автономной страницы продолжается до достижения hikey.
6. При сбросе автономной страницы соответствующее место для дискового хранения отмечается как свободное для будущей контрольной точки.

Сообщения процесса контрольных точек

Рассмотрим более подробно сообщения процесса контрольных точек, перечисленные выше.

WalkDownwards

Данное сообщение имеет следующие параметры.

• Номер и счетчик изменений in-memory (в оперативной памяти) страницы, которую необходимо посетить.
• Минимальный ключ (lokey). Lokey берется из downlink родительской страницы либо является lokey родительской страницы, если downlink является первым на странице.

Процессу контрольных точек необходимо обработать указанную страницу. После обработки страницы должно быть возвращено сообщение WalkUpwards. Если указанная страница является нелистовой, во время ее обработки будет выдано больше сообщений, но в конце должно быть сообщение WalkUpwards для указанной страницы.

Может произойти сбой из-за конкурентных операций: in-memory страница может иметь другой счетчик изменений. В этом случае соответствующее WalkUpwards должно вернуть недействительный downlink. Также в случае сбоя сообщение WalkUpwards должно следовать сразу после WalkDownwards: после начала обработки нелистовой страницы она должна быть завершена.

WalkUpwards

Данное сообщение имеет следующие параметры.

• Downlink для дискового хранения. Этот downlink может быть недействительным, как описано выше.
• Следующий ключ. Фактически это hikey записанной страницы. Он может не совпадать с последующим downlink'ом родительской страницы из-за конкурентных разделений и слияний. При несовпадении родительская страница должна быть отмечена как «автономная».
• Флаг, указывающий, что родительская страница должна быть отмечена как «dirty» (измененная). Этот флаг устанавливается, когда страница была записана в новое место после предыдущей контрольной точки. Этот флаг не устанавливается, если страница и ее дочерние элементы не будут изменены. Родительская страница должна быть отмечена как «dirty» для записи и отражения нового downlink для дискового хранения.
• Флаг указывает на необходимость сохранения существующего next downlink на родительской странице. Это происходит для автономной страницы, когда текущее реконструированное изображение завершено: страница записана и необходимо вставить новый downlink в родительскую страницу, но все еще требуется посетить тот же next downlink.

Данное сообщение указывает, что дочерняя страница обработана, и родительская страница должна добавить downlink. Если родительской страницы нет, обработана корневая страница, и в настоящее время имеется указатель на новое место для дискового хранения корневой страницы.

WalkContinue

Данное сообщение не имеет параметров. Оно указывает лишь на то, что процессу контрольных точек необходимо продолжить обработку той же страницы с тем же next downlink. Происходит, когда процессу контрольных точек необходимо дождаться завершения конкурентной операции, например, при обнаружении downlink с выполняющимся в данный момент вводом-выводом и необходимости снять блокировку журнала и дождаться завершения ввода-вывода.

Последовательные буферы

Что такое последовательные буферы?

Последовательные буферы (seq bufs) — это легкие абстракции потокового ввода-вывода, привязанные к файлам, используемые процессом контрольных точек и обычными бэкендами, которые записывают страницы B-дерева. Вместо хранения всех метаданных контрольной точки в общей памяти, seq bufs потоково передают данные в файлов для дискового хранения и из них, используя две in-memory (в оперативной памяти) страницы OrioleDB в качестве двойного буфера. Пока одна страница заполняется (или опустошается) вызывающей стороной, другая может сбрасываться на диск или предварительно загружаться в фоновом режиме, обеспечивая последовательную пропускную способность без занятия больших объемов общей памяти.

Каждый seq buf идентифицируется тегом SeqBufTag — кортежем (datoid, relnode, checkpointNumber, type). Поле type различает два вида файлов:

• 'm' (map file) — карта контрольной точки, которая фиксирует места страниц для дискового хранения;
• 't' (temporary file) — временный файл отслеживания, используемый во время обхода контрольной точки.

In-memory (в оперативной памяти) состояние, которое должно быть общим между процессом контрольных точек и бэкендами-записывателями, находится в SeqBufDescShared, который встроен непосредственно в мета-страницу B-дерева (BTreeMetaPage). Состояние для каждого бэкенда, такое как открытый файловый дескриптор, находится в SeqBufDescPrivate, которое хранится в дескрипторе дерева (BTreeDescr) и является приватным для каждого бэкенда.

Почему используются последовательные буферы?

Каждое B-дерево, доступное для контрольных точек, сохраняет три группы seq bufs:

1. freeBuf — при входе в новую контрольную точку процесс контрольных точек открывает этот буфер для чтения списка свободных extents диска, записанных предыдущей контрольной точкой. По мере записи страниц текущей контрольной точки эти extents могут быть повторно использованы, избегая ненужного роста файла. Существует ровно один freeBuf на дерево (без двойного массива), так как он заменяется атомарно в начале каждой контрольной точки: новый файл устанавливается на место до удаления старого.
2. nextChkp[2] — процесс контрольных точек открывает один из этих двух слотов для записи файла карты контрольной точки для текущей контрольной точки. Каждый раз, когда страница B-дерева сбрасывается на диск, ее место добавляется в карту. Следующая контрольная точка будет читать эту карту через freeBuf, чтобы знать, где находится каждая страница, без необходимости повторно обходить все дерево.
3. tmpBuf[2] — процесс контрольных точек открывает один из этих двух слотов для записи временного файла, который отслеживает каждую страницу, записанную во время обхода контрольной точки. После завершения обхода этот файл сортируется, удаляются дубликаты, и он запускает проход пробивки дыр (hole-punching), который освобождает неиспользованное пространство внутри файла данных. Файл удаляется после завершения контрольной точки.

Почему существует два слота (массивы [2])?

Контрольные точки OrioleDB выполняются конкурентно с обычными операциями DML. Для избежания сериализации контрольной точки N по отношению к инициализации контрольной точки N+1 каждый из массивов (nextChkp, tmpBuf, datafileLength, partsInfo) индексируется по checkpointNumber % 2.

В любой момент ровно один слот является «активным» — слот, в который в данный момент записывает выполняющаяся контрольная точка, — в то время как другой слот либо все еще содержит данные из предыдущей контрольной точки (необходимые для восстановления до проверки новой контрольной точки), либо простаивает.

Checkpoint N   → uses slot  N % 2
Checkpoint N+1 → uses slot (N+1) % 2   (the other slot)

Такая схема «пинг-понг» означает, что контрольная точка N+1 может начать распределение страниц и инициализацию файлов seq buf, пока контрольная точка N все еще завершается, без каких-либо коллизий общего состояния.

Два dirty-флага на мета-странице (dirtyFlag1, dirtyFlag2) поддерживают ту же схему. dirtyFlag1 очищается в начале контрольной точки. dirtyFlag2 предоставляет дополнительную генерацию, чтобы изменение, конкурентное с очисткой dirtyFlag1, никогда не было тихо потеряно. Если оба флага имеют значение false, когда процесс контрольных точек собирается начать обработку дерева, дерево не изменилось с последней контрольной точки; только что инициализированные файлы seq buf закрываются и удаляются немедленно без записи каких-либо данных.

Когда последовательные буферы удаляются?

In-memory (в оперативной памяти) страницы seq buf возвращаются в пул страниц сразу после завершения буфера. Это происходит в одной из следующих ситуаций:

• Контрольная точка успешно завершена — страницы tmpBuf освобождаются после постобработки; страницы nextChkp освобождаются после записи заголовка файла карты и переименования файла.
• Дескриптор дерева вытеснен — когда дескриптор дерева извлекается из кэша дескрипторов, btree_finalize_private_seq_bufs() сбрасывает и освобождает все in-memory страницы, принадлежащие активным seq bufs этого дескриптора.
• Дерево удалено — checkpointable_tree_free() закрывает все файловые дескрипторы seq buf, освобождая ресурсы ОС.

Файлы seq buf для дискового хранения имеют более длительный срок жизни, чем in-memory страницы:

• Временный файл ('t') удаляется после завершения постобработки контрольной точки, которая его создала.
• Файл карты ('m') из контрольной точки N сохраняется до завершения контрольной точки N+1 и установки ее собственного файла карты. Это обеспечивает возможность восстановления на определенный момент времени (point-in-time recovery), которая всегда может найти последнюю чистую контрольную точку.
• Файл свободных extents заменяется атомарно: новый файл записывается и переименовывается на место перед удалением старого.
• Если дерево не изменялось между двумя контрольными точками (оба dirty-флага имеют значение false), файлы seq buf, инициализированные для этой контрольной точки, закрываются немедленно и удаляются без записи каких-либо данных.