Записки программиста

В контексте СУБД можно столкнуться с понятием двойных указателей, которые не имеют ничего общего с int**. Устоявшейся терминологии здесь нет, поэтому кто-то может называть тот же подход «холодными» и «горячими» указателями, или как-то иначе. Идея простая, но как будто бы она не часто описывается в литературе и других источниках. Двойным указателям можно найти применение в разработке не только СУБД, но и всяких бэкендов в целом.

Вспомним, как работают обычные указатели:

Перед нами две страницы фиксированного размера. Внутри левой страницы содержится указатель / ссылка на данные из правой страницы. Указатель хранит адрес данных в памяти. Предельно простая ситуация.

Если мы пишем in-memory СУБД, то она вполне может обойтись только прямыми ссылками, при условии, что данные не перемещаются и т.п. Проблема возникает, когда не весь объем данных помещается в памяти. В этом случае в произвольный момент времени мы не можем знать, находится ли заданная страница в памяти, или она выгружена на жесткий диск. Если страница и находится в памяти, то не ясно, по какому адресу ее искать.

Поэтому применяют схему наподобие следующей:

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

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

Что их действительно устраняет — это те самые двойные указатели:

Признак того, находится ли сейчас страница в памяти или на диске, хранится в самом указателе. Достичь этого можно несколькими способами. Например, можно потребовать, чтобы данные, на которые существуют ссылки из других страниц, всегда хранились по четным адресам. Тогда в нашем распоряжении оказывается младший бит указателя. Если он равен нулю, то это прямой указатель на память. Иначе это виртуальный указатель. Двойные указатели используется в OrioleDB. Термин взят именно из этой системы.

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

Первый недостаток — не ясно, как в общем случае выгружать из памяти данные, на которые есть прямые указатели. Одно из возможных решений состоит в том, чтобы использовать прямые указатели только для данных, обращение к которым происходит особенно часто, а потому их нет смысла выгружать. Примером таких данных может служить системный каталог СУБД. Также мы можем не выгружать первые N уровней B+tree индексов. Если же пользователь говорит DROP INDEX, то индекс уничтожается целиком. Все прямые ссылки внутри индекса перестают существовать одновременно.

Второй недостаток — запись страниц на жесткий диск становится более дорогой. Представьте, что мы хотим выгрузить Page 1. При этом она содержит прямые указатели и модифицировалась после загрузки с диска. Тогда перед записью страницы все прямые адреса нужно отобразить обратно в виртуальные. Если такое решение не устраивает, то можно, к примеру, не заменять виртуальные адреса прямыми, а хранить и те и другие. Вот только расплачиваться за это придется использованием лишней памяти.

Заметьте, что частным случаем «выгрузки» страницы является ведение WAL. С двойными указателями не получится писать в журнал просто копии страниц и их diff’ы. Нужно либо работать с модифицированной копией страницы, либо хранить виртуальные и прямые адреса одновременно, либо писать логический WAL, либо придумывать что-то еще. Если двойные указатели применяются только для нелогируемых или неизменяемых страниц, то проблема теряет актуальность.

Несмотря на перечисленные трудности, преимущества двойных указателей могут превосходить недостатки. В связи с чем они находят практическое применение в современных СУБД.

Дополнение: @cheese_hs и @sergey_rashitov отмечают в комментариях, что двойные указатели являются частным случаем помеченных указателей.

Метки: Алгоритмы, СУБД.