Управление свободным пространством

примечание

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

OrioleDB управляет свободным пространством для обычных и сжатых деревьев с использованием комбинации файлов метаданных, контрольных точек и системных деревьев для эффективного выделения и отслеживания свободных блоков и интервалов (extent).

Обычные деревья

Каждое дерево OrioleDB имеет связанный файл данных. Длина этого файла данных хранится в BTreeMetaPage.datafileLength. Она не обязательно строго совпадает с фактической длиной файла. Файл данных может быть короче значения BTreeMetaPage.datafileLength: это означает, что некоторым страницам виртуально выделены смещения, но они еще не были записаны. Также файл данных может быть длиннее значения BTreeMetaPage.datafileLength: некоторые страницы были записаны в предыдущем сеансе работы базы данных, завершившемся аварийным остановом, однако в настоящее время эти места должны считаться свободным пространством.

Каждой контрольной точке дерева соответствуют два файла для управления свободным пространством.

• файл *.tmp содержит номера блоков, которые были освобождены с момента завершения предыдущей контрольной точки до момента завершения текущей. Этот файл является опциональным и может отсутствовать, если в указанный период не было освобождено ни одного блока;

• файл *.map, который содержит:

  • ссылку на корень дерева;
  • длину файла данных на момент завершения контрольной точки;
  • массив номеров свободных блоков в данной контрольной точке.

Таким образом, корень и все блоки, прямо или косвенно на которые ссылается корень, считаются занятыми в данной контрольной точке. Все остальные блоки в пределах длины файла данных считаются свободными и должны быть занесены в массив свободных блоков.

Когда OrioleDB требуется блок для записи страницы, он выделяется в следующем порядке:

• из массива номеров свободных блоков в файле *.map контрольной точки, в которой был запущен экземпляр базы данных;
• из файлов *.tmp последующих завершенных контрольных точек, если таковые имеются;
• за счет увеличения длины файла данных (атомарное.increment значения BTreeMetaPage.datafileLength).

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

Если для записываемой страницы уже существует связанный блок в файле данных, этот номер блока записывается в файлы *.tmp и *.map следующей контрольной точки. На рисунке предыдущий номер блока записывается в файлы *.tmp и *.map контрольной точки 2.

Новый номер блока для данной страницы приобретается в соответствии с описанными выше правилами. На рисунке он берется из файла *.tmp контрольной точки 1.

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

На приведенном рисунке контрольная точка 1 завершена, а контрольная точка 2 находится в процессе выполнения. Процесс контрольных точек (Checkpointer) обрабатывает деревья в определенном детерминированном порядке.

Для деревьев, уже пройденных процессом контрольных точек, контрольная точка в процессе выполнения считается завершенной. На рисунке дерево 1 уже пройдено процессом контрольных точек. Следовательно, контрольная точка 2 считается завершенной, а контрольная точка 3 — будущей.

Для деревьев, которые процесс контрольных точек еще не достиг, контрольная точка в процессе выполнения аналогична еще не начавшейся. На рисунке дерево 3 еще не достигнуто процессом контрольных точек. Следовательно, контрольная точка 1 считается завершенной, а контрольная точка 2 — будущей.

Дерево, находящееся в обработке у процесса контрольных точек, представляет наиболее сложный случай. Процесс контрольных точек уже записал некоторые части дерева. При необходимости записи этой части дерева выполнить запись на месте невозможно, поскольку это нарушит принцип copy-on-write. Вместо этого страницы записываются в новое место. Это место соответствует контрольной точке, следующей за находящейся в процессе выполнения. Таким образом, когда процесс контрольных точек обходит дерево слева направо, конкретная логика зависит от того, прошел ли процесс контрольных точек конкретную страницу.

• Когда страница, требующая записи, уже пройдена процессом контрольных точек и имеет связанный блок в файле данных, этот блок записывается в файлы *.tmp и *.map контрольной точки, следующей за находящейся в процессе выполнения. На рисунке предыдущий номер блока страницы 5 дерева 2 записывается в файлы *.tmp и *.map контрольной точки 3.

• Когда страница, требующая записи, уже пройдена процессом контрольных точек, новый номер блока приобретается в соответствии с описанными выше правилами. Файл *.tmp контрольной точки в процессе выполнения по-прежнему не может являться источником новых блоков, так как он не завершен для данного дерева. Однако при получении нового номера блока необходимо также записать его в файл *.map контрольной точки в процессе выполнения, поскольку этот блок принадлежит следующей контрольной точке и является свободным для контрольной точки в процессе выполнения. На рисунке новый номер блока для страницы 5 дерева 2 берется из файла *.tmp контрольной точки 1 и также записывается в файл *.map контрольной точки 2.

• Когда страница, требующая записи, еще не пройдена процессом контрольных точек, работа происходит аналогично деревьям, которые процесс контрольных точек еще не достиг. Те же правила применяются к процессу контрольных точек при самостоятельной записи страниц. Если существует связанный блок в файле данных, этот номер блока записывается в файлы *.tmp и *.map контрольной точки в процессе выполнения. На рисунке предыдущий номер блока страницы 6 дерева 2 записывается в файлы *.tmp и *.map контрольной точки 2. Новый номер блока страницы приобретается в соответствии с описанными выше правилами. На рисунке новый номер блока для страницы 6 дерева 2 берется из файла *.tmp контрольной точки 1.

По завершении создания контрольной точки для конкретного дерева процессу контрольных точек необходимо завершить формирование файла *.map. В частности, все доступные свободные блоки из файлов *.map и *.tmp (в соответствии с правилами) добавляются в файл *.map, а текущее значение BTreeMetaPage.datafileLength записывается в качестве длины файла.

Сжатые деревья

В OrioleDB реализовано сжатие на уровне страниц. Страницы имеют фиксированный размер in-memory, но переменный размер в файле данных. Следовательно, описанное выше управление свободным пространством требует некоторых доработок.

Во-первых, файлы *.tmp и *.map содержат не номера свободных блоков, а свободные интервалы (extent). Интервал (extent) включает смещение и длину.

Поскольку работа ведется с интервалами (extent), файлы *.tmp и *.map можно читать последовательно, так как могут встретиться интервалы, не соответствующие требуемой длине. Для работы со свободными интервалами используются системные деревья SYS_TREES_EXTENTS_OFF_LEN и SYS_TREES_EXTENTS_LEN_OFF. Дерево SYS_TREES_EXTENTS_LEN_OFF упорядочено по длине интервала (extent) и используется для поиска интервала, наилучшим образом подходящего под потребности. Дерево SYS_TREES_EXTENTS_OFF_LEN упорядочено по смещению интервала (extent) и используется для объединения смежных интервалов.

Деревья SYS_TREES_EXTENTS_OFF_LEN и SYS_TREES_EXTENTS_LEN_OFF являются временными. Их содержимое не сохраняется после перезапуска сервера: загрузка всегда начинается с пустых деревьев. После загрузки любого дерева содержимое его файла *.map также загружается в SYS_TREES_EXTENTS_OFF_LEN и SYS_TREES_EXTENTS_LEN_OFF. По завершении контрольной точки дерева содержимое файла *.tmp предыдущей контрольной точки считывается в эти деревья. По завершении контрольной точки интервалы (extent) из этих деревьев добавляются в файл *.map.

Несколько процессов могут одновременно искать свободный интервал (extent), в то время как один процесс вставляет новый свободный интервал. Корректная обработка проблемы конкурентного доступа представляет сложную задачу. Алгоритмы рассмотрены ниже.

Ниже приведен алгоритм получения свободного интервала (extent) для записи страницы.

1. Найти кратчайший подходящий интервал (extent) в дереве SYS_TREES_EXTENTS_LEN_OFF и удалить его. При отсутствии подходящего интервала увеличить BTreeMetaPage.datafileLength на требуемую длину и вернуть соответствующий интервал (extent).
2. Если осталась неиспользованная часть выбранного интервала (extent), вставить ее в дерево SYS_TREES_EXTENTS_OFF_LEN.
3. Удалить выбранный интервал (extent) из дерева SYS_TREES_EXTENTS_OFF_LEN.
4. Если осталась неиспользованная часть выбранного интервала (extent), вставить ее в дерево SYS_TREES_EXTENTS_LEN_OFF.

Следует отметить, что если параллельному процессу требуется объединить оставшуюся часть, он всегда находит некоторый интервал (extent) для объединения. В SYS_TREES_EXTENTS_OFF_LEN сначала выполняется вставка (шаг 2) и только затем удаление (шаг 3). Таким образом, не возникает промежуточного состояния без интервала для объединения.

Ниже приведен алгоритм вставки нового свободного интервала (extent).

1. В дереве SYS_TREES_EXTENTS_OFF_LEN найти левых и правых соседей нового интервала (extent). Проверить, являются ли они смежными с новым интервалом; в случае ссмежности требуется выполнить их объединение.
2. Если требуется объединить левого соседа, удалить его из дерева SYS_TREES_EXTENTS_LEN_OFF. При ошибке повторить попытку с шага 1.
3. Если требуется объединить правого соседа, удалить его из дерева SYS_TREES_EXTENTS_LEN_OFF. При ошибке повторно вставить левого соседа (если он был удален) и повторить попытку с шага 1.
4. На данном этапе параллельный процесс не может использовать ни левого, ни правого соседа, поскольку они были удалены из дерева SYS_TREES_EXTENTS_LEN_OFF.
5. Удалить соседние интервалы (extent), подлежащие объединению, из дерева SYS_TREES_EXTENTS_OFF_LEN.
6. Вставить новый интервал (extent) (с объединенными соседями) в дерево SYS_TREES_EXTENTS_OFF_LEN, затем в дерево SYS_TREES_EXTENTS_LEN_OFF.