Алгоритмы параллелизма в B-дереве OrioleDB
Эта страница переведена при помощи нейросети GigaChat.
Счетчик изменений страницы
В B-дереве OrioleDB блокировка страниц не применяется, за исключением случаев необходимости их модификации. По этой причине после обхода по нисходящей ссылке (downlink) необходимо проверять попадание на целевую страницу (так как страница могла быть одновременно вытеснена, объединена и т. д.). Для решения этой задачи каждая in-memory (в оперативной памяти) страница в OrioleDB имеет поле OrioleDBPageHeader.pageChangeCount, которое увеличивается при каждом изменении идентичности in-memory страницы. Идентичность in-memory страницы означает конкретное дерево, уровень и lokey (нижнюю границу диапазона ключей страницы). Несмотря на то, что lokey страницы не хранится непосредственно на странице, он определяется структурно. Таким образом, левая страница при разделении и левая страница при объединении сохраняют свою идентичность. Благодаря механизму счетчика изменений процесс, обходящий нисходящую ссылку, может обнаружить одновременное изменение идентичности страницы.
Правые ссылки
В OrioleDB in-memory нисходящие ссылки могут заменяться на дисковые нисходящие ссылки и наоборот при вытеснении и загрузке страниц соответственно. По этой причине страницы OrioleDB обычно не содержат правых или левых ссылок. Правые ссылки (rightlink) временно существуют в процессе разделения для предотвращения блокировки навигации по дереву. Рассмотреть процесс разделения страницы на рисунках ниже.
Шаг 1 изображает начальное состояние части дерева, состоящего из родительской страницы 1 и дочерней страницы 2.
Шаг 2 изображает разделение страницы 2 с созданием новой страницы 3. На этом этапе страница 2 имеет правую ссылку на страницу 3. Если на этом этапе параллельный процесс ищет ключ, расположенный на странице 3, он проверяет hikey страницы 2 и переходит на страницу 3 по правой ссылке. Ключи, расположенные на странице 2, могут быть найдены обычным образом.
Шаг 3 изображает вставку новой нисходящей ссылки на страницу 1. Правая ссылка между страницами 2 и 3 все еще сохраняется. На этом этапе параллельный процесс может найти страницу 3 по нисходящей ссылке. Если параллельный процесс попал на страницу 2 до вставки нисходящей ссылки, он по-прежнему может использовать правую ссылку.
Шаг 4 изображает удаление правой ссылки со страницы 2 на страницу 3. Если параллельный процесс, который попал на страницу 2 до вставки нисходящей ссылки, ищет ключ, расположенный на странице 3, то ему необходимо проверить правую ссылку и перезапустить поиск со страницы 1.
Вытеснение страницы
Вытеснение страницы запрещено для страницы с правой ссылкой или без нисходящей ссылки от родительской страницы. Как правило, запрещены обе стороны правой ссылки (источник и целевая). Таким образом, процесс вытеснения страницы не взаимодействует с правыми ссылками. Правые ссылки могут соединять только in-memory страницы. Рассмотреть процесс вытеснения страницы на рисунках ниже.
Шаг 1 изображает начальное состояние части дерева, состоящего из родительской страницы 1 и дочерней страницы 2. Страница 2 заблокирована и подлежит вытеснению. На этом этапе процесс вытеснения должен найти и заблокировать родительскую страницу 1, используя hikey страницы 2 для ее поиска.
Шаг 2 изображает заблокированные страницы 1 и 2. На этом этапе процесс вытеснения заменяет in-memory нисходящую ссылку на IO-ссылку и увеличивает счетчик изменений страницы. IO-ссылка предотвращает ее использование параллельным процессом, заставляя его ждать завершения операции ввода-вывода. Увеличенный счетчик изменений предотвращает использование страницы 2 всеми параллельными процессами, которым удалось воспользоваться in-memory нисходящей ссылкой.
Шаг 3 изображает страницу 1, отключенную от дочерней страницы с IO-ссылкой.
Наконец, процесс вытеснения записывает дисковую нисходящую ссылку на страницу 1 (шаг 4).
Загрузка страницы
Когда бэкенд PostgreSQL нуждается в странице, на которую ссылается дисковая нисходящая ссылка на нелистовой странице OrioleDB, необходимо загрузить эту страницу.
Шаг 1 изображает начальное состояние нелистовой страницы 1 до загрузки дочерней страницы. Страница 1 заблокирована и имеет дисковую нисходящую ссылку. На этом этапе процесс должен заменить нисходящую ссылку на ссылку с IO в процессе, разблокировать страницу 1 и начать операцию ввода-вывода.
Шаг 2 изображает состояние страницы 1 во время выполнения операции ввода-вывода. Все параллельные процессы, работающие с данной нисходящей ссылкой, должны ждать завершения операции ввода-вывода. По завершении операции ввода-вывода процесс должен повторно заблокировать страницу 1.
Шаг 3 изображает состояние при повторной блокировке страницы 1. На этом этапе процесс должен добавить дочернюю страницу 2 и настроить нисходящую ссылку на странице 1 на указание на страницу 2.
Шаг 4 представляет конечное состояние. Страница 2 загружена, а страница 1 содержит in-memory нисходящую ссылку на страницу 2.
Объединение страниц
Когда у OrioleDB имеется кандидат на вытеснение страницы и эта страница является слишком разреженной (менее 30 % пространства занято), рассматривается объединение страниц. Объединение страниц также освобождает in-memory страницу, но не требует операции ввода-вывода даже для грязной страницы.
Шаг 1 изображает начальное состояние части дерева, состоящего из родительской страницы 1, дочерней страницы 3, подлежащей объединению (заблокирована), левого соседа 2 и правого соседа 4. На этом этапе необходимо заблокировать родительскую страницу 1. Сначала снимается блокировка дочерней страницы 3.
Шаг 2 изображает состояние, при котором родительская страница 1 заблокирована, а дочерняя — нет. На этом этапе необходимо повторно заблокировать дочернюю страницу 3, подлежащую объединению. Если эта страница исчезла (в результате параллельного вытеснения или другого объединения), отменить объединение. Также проверяется, что родительская страница не находится под контрольной точкой, в противном случае отменить операцию.
Шаг 3 изображает заблокированные родительскую страницу 1 и дочернюю страницу 3. Здесь необходимо выбрать способ объединения. Проверяется, что дочерняя страница 3 не находится под контрольной точкой и не имеет правой ссылки. В противном случае отменить операцию.
Шаг 4 изображает два возможных способа объединения: с правым соседом 4 (верхний рисунок) или с левым соседом 2 (верхний рисунок). Следует отметить, что левая страница всегда сохраняет свою идентичность независимо от выбранного направления. Таким образом, если объединение выполняется влево, страница 3 будет удалена. Невозможно выполнить объединение с соседом, находящимся под контрольной точкой или имеющим правую ссылку.
Шаг 5 изображает результат объединения. В данном примере объединение выполнено вправо. Все кортежи на странице 4 объединены со страницей 3. Результирующая страница обозначена как страница 34. Страница 34 также содержит hikey страницы 4. Кроме того, удаляется страница 4 и соответствующая нисходящая ссылка на странице 1.
