Обзор архитектуры OrioleDB

примечание

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

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

Индексы

Данные в OrioleDB хранятся в таблицах с индексной организацией. Рассмотрим пример таблицы vegetables, которая имеет первичный индекс по id и вторичный индекс по count.

| Id  | Name     | Count |
| --- | -------- | ----- |
| 1   | Tomato   | 10    |
| 2   | Cucumber | 3     |
| 3   | Cabbage  | 7     |
| 4   | Melon    | 6     |

Ниже приведена структура данных, лежащая в основе таблицы vegetables. Как первичные, так и вторичные индексы представляют собой варианты B+-дерева. Кортежи листовых страниц выделены синим цветом, нелистовые кортежи — зеленым, ключи верхней границы — желтым. Нелистовые кортежи и ключи верхней границы первичного индекса состоят из столбцов первичного ключа; кортежи листовых страниц сами являются строками таблицы. Нелистовые и листовые кортежи, а также ключи верхней границы вторичного индекса состоят из столбцов вторичного индекса и столбцов первичного индекса.

Первичный индекс и вторичный индекс не связаны напрямую; они соединены только логическими значениями, сохраняемыми в строках таблицы. При отсутствии явного первичного индекса, OrioleDB автоматически создает первичный индекс по виртуальному столбцу ctid.

Двойные указатели

Для избежания необходимости маппинга буферов и связанных с этим узких мест OrioleDB использует схему так называемых dual pointers (двойных указателей). Суть схемы dual pointers заключается в том, что вниз указатели (downlinks) в нелистовых in-memory страницах могут указывать как на in-memory, так и на страницы дискового хранилища. Следовательно, навигация по in-memory страницам осуществляется с помощью прямых ссылок без обращения к таблице буферов. В случае необходимости перехода по вниз указателю, указывающему на страницу хранения, последняя загружается в оперативную память, а соответствующий вниз указатель заменяется на in-memory указатель.

На диаграмме ниже показана упрощенная структура B-дерева OrioleDB. Данная диаграмма не содержит деталей содержимого страниц: страницы оперативной памяти пронумерованы так же, как их прототипы на диске. Стрелки обозначают вниз указатели.

Страница оперативной памяти может ссылаться как на страницы оперативной памяти, так и на страницы хранения. Однако страницы хранения могут ссылаться только на страницы хранения. Поэтому, помимо страниц оперативной памяти и страниц хранения, страницы 1, 2 и 3 имеют одинаковые номера со страницами хранения 1, 2 и 3, но их содержимое отличается в вышеописанном аспекте.

Для реализации данной схемы необходимо отказаться от rightlinks (правых указателей). Переключение вниз указателей и правых указателей между in-memory и указателями хранения оказалось бы слишком сложным (и медленным).

С технической точки зрения, B-деревья OrioleDB по-прежнему содержат rightlinks, однако они используются только временно при разделении страниц. Rightlink существует исключительно между созданием новой страницы и вставкой вниз указателя в родительскую страницу. Следовательно, если завершенное разделение происходит одновременно с поиском страницы дерева, необходимо повторить поиск начиная с родительской страницы (смотрите функцию find_page()). Переход по страницам дерева вправо и влево также становится более сложным. Вместо использования rightlinks (и leftlinks) необходимо находить соседние страницы через родительскую (смотрите find_right_page() и find_left_page()). Тем не менее, данная сложность полностью оправдана лучшей вертикальной масштабируемостью.

Дополнительную информацию смотрите в разделе «Алгоритмы параллелизма в B-дереве OrioleDB».

Структура страницы

В OrioleDB реализована новая структура страницы, оптимизированная для современных многопроцессорных систем.

В заголовке страницы содержится атомарная переменная state. Данная атомарная переменная обеспечивает следующий функционал:

1. Исключительная блокировка страницы. Одновременно может существовать только один владелец исключительной блокировки страницы. Исключительная блокировка сама по себе не предоставляет права на изменение содержимого страницы или запрет чтения страницы другими процессами.
2. Владелец исключительной блокировки может повысить уровень блокировки для блокировки читателей страницы. После блокировки читателей владелец блокировки может начать изменение содержимого страницы.
3. Отслеживание количества изменений содержимого страницы. Благодаря этому возможно копирование части страницы (или выполнение вычислений) с последующей проверкой, что страница не была изменена concurrently (и повтор попытки в случае изменения).

Дополнительную информацию смотрите в файле src/btree/page_state.c.

Кортежи на странице разделены на блоки (chunks). Также существует область ключей верхней границы (high keys), где каждому блоку сопоставлен свой ключ верхней границы. Ключ верхней границы последнего блока одновременно является ключом верхней границы страницы. Благодаря этому, при необходимости получения конкретного кортежа на странице, не требуется копировать всю страницу. Достаточно скопировать область ключей верхней границы, найти соответствующий блок страницы и скопировать его. Структура PartialPageState предназначена для отслеживания частично прочитанных страниц.

В будущем планируется отказаться от копирования в большинстве сценариев доступа к страницам и реализовать векторизацию для ускорения поиска внутри страницы.

Контрольные точки с копированием при записи

В OrioleDB используются контрольные точки с копированием при записи (copy-on-write) и WAL на уровне строк. Пример ниже иллюстрирует общую схему контрольных точек с копированием при записи.

Предположим, что страница с номером 7 была изменена. Она помечена как 7*.

Контрольная точка записала 7* в область хранения. Запись выполнена в свободное пространство в соответствии с принципом копирования при записи. При обработке нелистовой страницы контрольная точка заменяет in-memory вниз указатели на указатели хранения. Поэтому страница 3 также считается измененной, поскольку необходимо сослаться на новую 7* со страницы хранения. Таким образом, страница 3* также записывается в свободное пространство хранения. Аналогично записывается 1*.

После завершения контрольной точки старые изображения страниц хранения 1, 3 и 7 помечаются как свободное пространство.

Следовательно, в любой момент времени в хранилище существует непротиворечивое изображение дерева.

В OrioleDB поддерживается нечеткое checkpointing (fuzzy checkpointing). То есть допускается изменение дерева одновременно с процессом checkpointing. Это необходимо, поскольку слишком быстрые или частые контрольные точки могут вызвать write flood (лавину записей).

Рассмотрим следующий пример. Дерево содержит страницы 1 – 7. Страницы 1 – 6 присутствуют как в оперативной памяти, так и в хранилище (контрольная точка 1), тогда как страница 7 присутствует только в хранилище. Страница 4 была изменена (4*).

Процесс checkpointing инициирован для обхода дерева слева направо и прошел поддерево страниц 2, 4 и 5. Изображения страниц 4* и 2* были записаны в контрольную точку 2.

Одновременно страница 5 была изменена (5*). Фоновый процесс записи (background writer) записал изображение страницы 5*. Страница 5 принадлежит части дерева, которая уже обработана контрольной точкой. Именно поэтому запись в контрольную точку 2 невозможна, поскольку это может повлиять на ее непротиворечивость.

Страница с номером 7 также была изменена одновременно, но не была записана фоновым процессом.

Затем контрольная точка завершила запись изображений страниц 7*, 3* и 1* в контрольную точку 2.

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

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

Дополнительную информацию смотрите в разделе «Контрольные точки».

Журнал отката (Undo log)

Транзакции и MVCC в OrioleDB реализованы с использованием журнала отката (UNDO log). Записи отката на уровне строк формируют цепочки версий строк. В частности, заголовки кортежей соединены в списки, где голова расположена на странице данных, а остальные элементы находятся в журнале отката. Смотрите диаграмму ниже.

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

Помимо присутствия в цепочках версий строк, записи отката также присутствуют в цепочках транзакций. При откате транзакции соответствующая цепочка обходится для повторного воспроизведения всех записей отката.

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

Иногда требуется воспроизвести только часть цепочки транзакции. Например, реализация ROLLBACK TO SAVEPOINT в OrioleDB воспроизводит цепочку журнала отката транзакции до указанной точки. Аналогичным образом работает откат спекулятивных вставок при выполнении INSERT ... ON CONFLICT .... Однако, после воспроизведения части цепочки отката транзакции, она может потребоваться при восстановлении, поскольку соответствующие данные могли быть (частично) сохранены контрольной точкой до воспроизведения. Для отслеживания таких случаев добавляются специальные записи отката типа branch (ветвь), которые предоставляют возможность восстановления для обхода уже воспроизведенных ветвей.

Некоторые записи отката также требуют выполнения действий при фиксации. Например, реализация TRUNCATE создает запись отката, которая удаляет старые relfilenodes при фиксации транзакции и удаляет новые relfilenodes при откате транзакции. Отдельный список записей отката, требующих действий при фиксации, отслеживается отдельно.

В OrioleDB также поддерживаются записи отката на уровне блоков. Записи отката на уровне блоков представляют собой изменения, примененные ко всей странице.

На диаграмме ниже приведен пример записи отката уровня блока типа compact. Здесь страницы данных содержат кортежи t1, t2 и t5. Однако изображение страницы в журнале отката содержит кортежи t1, t2, t3 и t4. Это означает, что при удалении кортежей t3 и t4 не хватило места для нового кортежа t5. Для этого сначала выполнялась compaction (уплотнение). Следовательно, создавалась запись отката уровня страницы, и кортежи t3 и t4 удалялись для размещения t5.

В OrioleDB существует три типа записей отката на уровне блоков:

1. Compact undo record (запись отката уплотнения) – одна страница данных ссылается на одно изображение страницы отката.
2. Split undo record (запись отката разделения) – две страницы данных ссылаются на одно изображение страницы отката.
3. Merge undo record (запись отката слияния) – одна страница данных ссылается на два изображения страниц отката.

Для доступа к журналу отката в OrioleDB используются как кольцевые буферы, так и блочные буферы. Дополнительную информацию смотрите в разделе «Хранение журнала отката (undo)».

WAL на уровне строк

В OrioleDB реализован WAL (журнал предзаписи) на уровне строк, используемый как для восстановления, так и для репликации. WAL на уровне строк требует непротиворечивых структурно контрольных точек, описанных выше. Записи WAL на уровне строк включают начало транзакции, вставку строки, обновление строки, удаление строки, фиксацию/откат транзакции и так далее Полный список записей WAL OrioleDB приведен в заголовочном файле include/recovery/wal.h.

Таблица OrioleDB содержит следующие B-деревья для своих данных:

1. TOAST-дерево.
2. Дерево первичного ключа.
3. Деревья вторичных ключей.

TOAST-деревья и деревья первичного ключа подлежат WAL-логированию, тогда как деревья вторичных ключей — нет. Вторичные ключи восстанавливаются на основе изменений в TOAST и первичном ключе.

Поскольку в OrioleDB реализован fuzzy checkpointing, здесь требуется свойство идемпотентности. При контрольной точке обрабатываются TOAST и первичный ключ до вторичных ключей. Следовательно, в контрольной точке вторичные ключи могут иметь более новое состояние, чем TOAST и первичные ключи. Идемпотентность гарантирует, что если некоторые изменения применяются ко вторичным ключам дважды или более раз, это не влияет на конечное состояние.

В OrioleDB реализовано параллельное применение записей WAL. Запускается количество рабочих процессов, равное значению параметра orioledb.recovery_pool_size. Каждый рабочий процесс отвечает за свой набор значений первичного ключа (согласно хеш-значению). Процесс запуска распределяет записи WAL на уровне строк по очередям, подключенным к рабочим процессам.

Обработка очередей может происходить с разной скоростью. Для избежания аномалий MVCC транзакция считается зафиксированной и видимой для читателей только после того, как все рабочие процессы завершили все работы, связанные с данной транзакцией.

Дополнительную информацию смотрите в разделе «Восстановление и репликация».

Системный каталог

В OrioleDB процессы checkpointing, записи/вытеснения страниц и восстановления оперируют деревьями на логическом уровне. Для этого требуется возможность сравнения ключей кортежей, вычисления длин кортежей и так далее. Исполняющий вышеуказанные процедуры процесс нуждается в доступе к некоторой метаинформации. Однако выполнение этих процедур необходимо без полностью инициализированного подключения к базе данных PostgreSQL.

Для решения данной проблемы в OrioleDB реализованы «системные деревья» — аналог системного каталога в OrioleDB, содержащий минимальную информацию, необходимую для выполнения процедур. Системные деревья содержат информацию о таблицах, связанных деревьях, типах данных и так далее Для дополнительной информации смотрите файл src/catalog/sys_trees.c.

Сжатие данных

В OrioleDB поддерживается сжатие данных на уровне блоков. В сжатых деревьях страницы хранения сжимаются алгоритмом zstd. Таким образом, страницы хранения имеют переменную длину. Из-за этого необходимо поддерживать более сложные механизмы управления свободным пространством в сжатых деревьях.

Управление свободным пространством в OrioleDB реализовано с использованием двух системных деревьев: SYS_TREES_EXTENTS_OFF_LEN, SYS_TREES_EXTENTS_LEN_OFF. Оба этих дерева содержат информацию об областях свободного пространства (extents). Первое поддерживает области, отсортированные по смещению, тогда как второе сортирует области по длине, затем по смещению. Второе дерево позволяет искать наиболее подходящую свободную область для нового блока хранения. Первое дерево используется для поиска смежных областей и инициации их объединения.