Карта свободного пространства , она же free space map или FSM — это структура в PostgreSQL, предназначенная для быстрого поиска страницы c заданным количеством свободного места. Без FSM при записи новых данных СУБД приходилось бы сканировать всю кучу, либо записывать данные в ее конец.

Подобно карте видимости , карта свободного пространства хранится в отдельном форке. Если таблица имеет relfilenode равный 16393, то FSM будет лежать рядом, в файле с именем 16393_fsm. FSM строится для кучи, а также для всех индексов, кроме hash-индекса. У каждой таблицы и каждого индекса свой отдельный FSM.

Как и куча, FSM хранится на диске в страницах размером BLCKSZ. Работа с FSM осуществляется через разделяемые буферы . Для понимания устройства FSM сначала рассмотрим, что хранится в одной его странице. Затем постараемся понять, как страницы связаны между собой.

Одна страница FSM представляет собой массив байт. Логически эти байты образуют бинарное дерево, как показано ниже:

Здесь в узлах дерева показаны номера байт в массиве. Нулевой байт всегда является корнем, первый и второй байт — его дочерними узлами, и так далее. Часть листовых узлов может отсутствовать, если они не поместились в страницу. Для простоты показано дерево из шести узлов. На самом деле, в странице их помещается намного больше. Дерево не перестраивается динамически. Его высота фиксирована и положение всех узлов в массиве известно заранее. Листовые узлы также называются «слотами», поскольку именно в них содержится полезная нагрузка.

Итак, в каждом слоте содержится один байт. Этот байт соответствует некоторой странице хипа или индекса. Его значение вычисляется как доступное свободное пространство в странице поделенное на BLCKSZ/256 с округлением в меньшую сторону. Для свободной страницы байт будет содержать 255. Для полностью заполненной или почти заполненной страницы значение байта равно 0.

Родительский узел содержит максимальное значение своих дочерних узлов. Соответственно, корень хранит максимальное значение для всего дерева. Структура позволяет быстро найти страницу, способную вместить в себя заданное количество байт. Если такой страницы нет, мы сразу видим это по значению в корне.

Помимо дерева в странице FSM хранится индекс слота fp_next_slot . Поиск страницы начинается с этого слота, а не с корня дерева. Номер найденного слота запоминается в fp_next_slot . Так сделано для того, чтобы при конкурентной записи несколькими бэкендами были найдены разные страницы, и бэкенды не дрались за локи . Также это обеспечивает последовательное чтение страниц с диска, если их еще нет в разделяемых буферах. Последовательное чтение эффективнее случайного, а также позволет ОС использовать prefetching.

Детали реализации этого уровня находятся в fsmpage.c и fsm_internals.h . Работу с fp_next_slot вы найдете в fsm_search_avail() . А так выглядят макросы для навигации по дереву:

В целом, речь идет про 375 строк кода на C с подробными комментариями.

Итак, мы разобрались, что хранится в одной странице FSM. Осталось понять, как страницы связаны между собой. Страницы тоже объединены в дерево, только не бинарное. При стандартном размере страницы 8 Кб каждая страница FSM будет иметь ~4000 дочерних страниц, по числу слотов в странице. «Страничное дерево» имеет фиксированную высоту. Дело в том, что мы заранее знаем максимальное число страниц в одной таблице PostgreSQL. Ограничение составляет 2 ³² -1 страниц. При стандартном BLCKSZ «страничному дереву» достаточно иметь три уровня.

Корневой узел «страничного дерева» хранится в нулевой странице. В каждой странице хранится «байтовое дерево», как было описано ранее. У «байтового дерева» есть листья. В листьях хранится то же значение, что и в корнях «байтовый деревьев», хранящихся в дочерних узлах «страничного дерева».

Другими словами, внутри большого «страничного дерева» хранятся маленькие «байтовые деревья», и вместе они образуют одно большое логическое дерево. Тут главное не запутаться о каких корнях и о каких листьях речь. А еще нужно правильно брать локи. Детали находятся во freespace.c и freespace.h . Здесь мы погружаться в них не будем.

Интересно, что напрямую FSM не журналируется . Допустим, в нем окажутся неверные значения. Что произойдет в худшем случае? Возможно, какая-то страница окажется мало заполнена. А возможно, мы найдем страницу для некоторых данных, но окажется, что по факту свободного места недостаточно. Ну и ничего страшного. Поправим FSM и попробуем снова.

Иначе говоря, весь код написан в предположении, что данные карты свободного пространства могут оказаться неверны. Вот пример, как это выглядит. Кроме того, FSM приводится в актуальное состояние во время VACUUM, по мере обращения к соответствующим страницам. Вот так глубоко внутри строгой ACID MVCC СУБД находят применение eventual consistent структуры данных.

Больше информации о FSM вы найдете в соответствующем файле README . Также вас может заинтересовать расширение pg_freespacemap .

Дополнение: Внутренности PostgreSQL: кэш системного каталога