Блоки, free list и метаданные

В предыдущем уроке мы вскрыли первые байты файла .duckdb — заголовок, magic bytes, checksum, версию формата. Сразу за тремя заголовками начинается тело файла. Оно не сплошное: файл разбит на блоки фиксированного размера. Этот урок объясняет, почему именно блоки, почему именно 256 KiB, как файл переиспользует место после удаления данных через free list, и где внутри блоков прячутся метаданные, связывающие всё в граф.

Почему файл разбит на блоки

Можно было бы хранить данные в файле сплошным потоком — таблица за таблицей, без всякой нарезки. Так не делают, и причина — изменчивость данных. Базу не пишут один раз: в неё вставляют строки, удаляют, обновляют, добавляют и дропают таблицы. Если данные лежат сплошняком, удаление таблицы в середине файла оставляет «дыру», а вставка новых данных требует либо втиснуть их в дыру нужного размера, либо сдвинуть весь хвост файла. Сдвигать гигабайты при каждой вставке — неприемлемо.

Решение — нарезать файл на блоки одинакового размера и работать в гранулярности блока. Блок становится единицей выделения и освобождения места. Удалили таблицу — её блоки помечаются свободными. Вставили данные — движок берёт свободные блоки и пишет в них. Никакого сдвига хвоста: место переиспользуется на месте. Это та же идея, что страницы (pages) в Postgres или блоки в файловых системах — фиксированный квант, которым оперирует менеджер хранилища.

Фиксированный размер блока даёт и второе преимущество — простую адресацию. Любой блок адресуется одним целым числом — его индексом. Смещение блока в файле вычисляется умножением: offset = header_size + block_id * block_size. Не нужна таблица «где какой блок лежит», арифметика тривиальна, а значит дёшев и random access к произвольному блоку.

Почему именно 256 KiB

Размер блока по умолчанию — 256 KiB, то есть 262144 байта. Это видно в выводе PRAGMA database_size из прошлого урока: поле block_size равно 262144. Размер выбран как компромисс между двумя противоположными давлениями.

Давление в сторону крупного блока — амортизация. Каждое чтение или запись блока несёт накладные расходы: системный вызов, seek диска, проверка checksum, обновление метаданных. Чем крупнее блок, тем больше полезных данных приходится на одну такую операцию, тем дешевле обходится каждый байт. Для аналитической нагрузки, где запросы сканируют большие диапазоны, крупный блок означает меньше операций ввода-вывода и более последовательное чтение с диска — а последовательное чтение в разы быстрее случайного и на HDD, и на SSD.

Давление в сторону мелкого блока — гранулярность и потери на округление. Если в базе много крошечных таблиц по сотне строк, каждая всё равно займёт минимум один блок целиком. С блоком 256 KiB сотня строк, которой хватило бы килобайта, «съедает» 256 KiB — остальное место в блоке простаивает. Чем крупнее блок, тем заметнее эти потери на маленьких таблицах. Мелкий блок их уменьшил бы, но ценой роста числа блоков и накладных расходов на каждый.

256 KiB — точка баланса для типичной аналитической базы: достаточно крупно, чтобы амортизировать I/O на больших сканах, и не настолько крупно, чтобы разнести вдребезги хранение мелких таблиц. Это давнее значение по умолчанию, проверенное практикой.

Free list: переиспользование освобождённых блоков

Когда вы делаете DROP TABLE или удаляете много строк и происходит checkpoint, блоки, которые занимала таблица, перестают быть нужны. DuckDB не вырезает их из файла и не сдвигает хвост — он добавляет их идентификаторы в free list, список свободных блоков.

Free list — это просто реестр номеров блоков, которые сейчас никем не заняты и доступны для повторного использования. При следующей записи, когда движку нужно место под новые данные, он сначала смотрит в free list: есть свободный блок — берёт его и пишет туда. Только если свободных блоков не осталось, файл расширяется — в конец дописывается новый блок, и файл на диске растёт.

Из этой механики следует поведение, которое регулярно удивляет новичков: файл базы DuckDB не уменьшается сам по себе после удаления данных. Вы дропнули большую таблицу, ожидаете, что файл похудел — а его размер на диске тот же. Это не баг. Блоки той таблицы ушли в free list и считаются свободными внутри файла, но физически файл не обрезан: место зарезервировано под будущие вставки. Со стороны ОС файл занимает столько же, сколько занимал.

Это видно через ту же pragma. После удаления таблицы и checkpoint число free_blocks растёт, а total_blocks остаётся прежним:

-- До удаления
PRAGMA database_size;
-- total_blocks=120  used_blocks=118  free_blocks=2

DROP TABLE big_table;
CHECKPOINT;

-- После удаления и checkpoint
PRAGMA database_size;
-- total_blocks=120  used_blocks=40  free_blocks=80

total_blocks не изменился — файл на диске того же размера. Но free_blocks подскочил с 2 до 80: эти 80 блоков теперь в free list и будут переиспользованы при следующих вставках, без роста файла.

Если файл нужно физически уменьшить — отдать освобождённое место операционной системе — есть отдельная операция. Полностью пересобрать файл и убрать свободные блоки можно через EXPORT DATABASE с последующим IMPORT DATABASE в новый файл, либо через ATTACH нового файла и копирование таблиц. Логический дамп и реимпорт — тема отдельного урока этого модуля. Главное сейчас: усадка файла — это явное действие, а не автоматический эффект DROP.

Метаданные: где DuckDB хранит карту самого себя

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

Метаданные — это всё, что не пользовательские строки, но без чего файл нельзя интерпретировать: каталог (список схем, таблиц, колонок, их типы, представления, индексы), указатели на то, где физически лежат данные каждой таблицы и каждого колоночного сегмента, сам free list, статистика. Database header из первого урока — это, по сути, точки входа в граф метаданных: они указывают на метаблоки, а те описывают всё остальное.

Метаданные хранятся в тех же блоках того же файла, что и данные, — отдельного файла под каталог нет. Это часть философии «одного файла»: скопировали .duckdb — скопировали и данные, и полное описание их структуры. Файл самодостаточен.

Связь между метаданными и данными — это указатели в виде идентификаторов блоков. Запись в каталоге про таблицу orders не содержит самих строк — она содержит ссылки: «колонка amount таблицы orders хранится начиная с такого-то блока». Чтение запроса идёт по цепочке: database header -> метаблоки каталога -> найти таблицу -> найти колонку -> по block id прыгнуть к блокам с данными. Весь файл — это граф, где рёбра — идентификаторы блоков, а заголовок — корень.

Заглянуть в эту структуру можно через системные функции. Распределение блоков по таблицам и колонкам показывает pragma_storage_info:

duckdb demo.duckdb
CREATE TABLE orders AS
  SELECT range AS id, range % 7 AS status FROM range(500000);
CHECKPOINT;

SELECT row_group_id, column_name, count(*) AS segments,
       sum(count) AS rows
FROM pragma_storage_info('orders')
GROUP BY row_group_id, column_name
ORDER BY row_group_id, column_name
LIMIT 6;

Вывод:

row_group_id  column_name  segments  rows
0             id           1         122880
0             status       1         122880
1             id           1         122880
1             status       1         122880
2             id           1         122880
2             status       1         122880

pragma_storage_info показывает, на какие физические сегменты разложена каждая колонка таблицы и в каких блоках они лежат. Это и есть взгляд на метаданные изнутри: движок отвечает, где именно в файле находятся данные. Структуру row group (видную здесь по row_group_id) разберём в следующем уроке — а сейчас важно, что движок умеет по запросу показать собственную карту хранения.

Попробуй сам

Понаблюдайте за блоками и free list на живой базе.

1. Создайте базу и крупную таблицу: duckdb blocks.duckdb, затем CREATE TABLE big AS SELECT range AS n, range::VARCHAR AS s FROM range(2000000); и CHECKPOINT;.
2. Посмотрите PRAGMA database_size;. Запишите total_blocks, used_blocks, free_blocks и block_size.
3. Прикиньте: used_blocks * block_size — близко ли это к ожидаемому размеру таблицы? Сравните с реальным размером файла на диске (ls -lh blocks.duckdb).
4. Создайте вторую таблицу того же объёма, сделайте CHECKPOINT, снова посмотрите pragma — total_blocks вырос, файл на диске вырос.
5. Теперь DROP TABLE big; CHECKPOINT; и снова PRAGMA database_size;. Что произошло с free_blocks? А с total_blocks и с размером файла на диске? Объясните разницу через механику free list.
6. Создайте третью таблицу примерно того же размера, что дропнутая, сделайте CHECKPOINT. Вырос ли файл на диске на этот раз — или движок переиспользовал блоки из free list?

Этот эксперимент даёт почувствовать руками: total_blocks — это размер файла, used_blocks — реально занятое, free_blocks — переиспользуемый резерв внутри файла, который DROP создаёт, но не возвращает операционной системе.