CS Notes

pages-and-tuples

7 min read

Страницы и кортежи — физическое хранение данных

Предпосылки: ACID, таблицы и типы данных.

← ACID в PostgreSQL | TOAST →

Цена гарантий упирается в диск: случайный I/O дорогой, а данные нужно уметь обновлять без переписывания гигантских файлов.

Фундаментальное ограничение: диск медленный

Дизайн хранилища упирается в физику диска: доступ к данным на диске на порядки медленнее доступа к памяти, а «случайный» I/O обычно заметно дороже «последовательного».

HDD (жёсткий диск, подробнее): вращающиеся пластины и механическая головка. Для случайного чтения/записи устройству нужно «дойти» до нужного места, поэтому задержка одной операции измеряется миллисекундами.

На HDD случайный доступ обычно упирается в задержку одной операции, а не в объём данных. Для диска 7200 RPM порядок величин такой:

seek (перемещение головки):              ~5–10 мс
rotational latency (ожидание сектора):   ~4 мс (≈ половина оборота при 7200 RPM)
transfer (прочитать 8 КБ):               доли мс
 
Итого: порядка ~10 мс на операцию → около 100 IOPS
100 IOPS × 8 КБ ≈ 800 КБ/с

IOPS (Input/Output Operations Per Second) — сколько операций чтения/записи устройство может выполнить за секунду. Если одна операция занимает около 10 мс, верхняя оценка получается около 100 операций в секунду.

При последовательном чтении/записи позиционирование делается редко, дальше данные идут потоком. Поэтому последовательное чтение даёт на порядки больше пропускной способности, чем чтение тех же 8 КБ «вразнобой».

Для ориентира: последовательное чтение на HDD обычно измеряется десятками/сотнями МБ/с, а случайное чтение страниц по 8 КБ при ~100 IOPS — это около 0.8 МБ/с. Отсюда и берётся разница порядка 100× и больше между последовательным и случайным доступом на HDD.

Эта же оценка помогает понять типичный симптом: «запрос внезапно стал секундным». Прочитать 1000 страниц (≈ 8 МБ) случайно на HDD — это примерно 1000 × 10 мс ≈ 10 секунд только на ожидание I/O.

SSD: убирает механические задержки и делает случайный доступ намного дешевле. Но разница между «в памяти» и «с диска» всё равно огромна, поэтому кеширование страниц остаётся критичным.

Именно поэтому PostgreSQL много внимания уделяет двум вещам: читать меньше страниц (например, через индексы) и удерживать горячие страницы в памяти (см. буферный кеш).

Наивный подход и его проблемы

Представим простейшее хранилище: пишем строки подряд в файл, храним индекс «строка N начинается с байта M».

Файл:
[Alice,100][Bob,200][Charlie,150]...
     ↑          ↑
   байт 0    байт 11

Проблема 1: Удаление. Удалили Bob. Осталась «дыра» в 9 байт. Новая строка [Dave,50] туда поместится, а [Elizabeth,300] — нет. Свободное место разбросано мелкими кусками. Это фрагментация.

Проблема 2: Обновление. Alice сменила имя на Alexandra. Новая версия длиннее — куда её положить? Либо двигать все последующие строки (дорого), либо класть в конец и менять индекс (ломает последовательное чтение).

Проблема 3: Сбой при записи. Начали писать новую строку, записали половину, питание отключилось. Файл повреждён, часть данных — мусор.

Решение: страничная организация

PostgreSQL делит файлы на страницы фиксированного размера — 8 КБ.

Почему «страница» (page)? Термин из операционных систем: ОС управляет памятью страницами фиксированного размера. PostgreSQL использует ту же идею для диска. Иногда говорят «блок» (block) — это синоним в контексте PostgreSQL.

Что это даёт:

Фрагментация локализована. Дыры внутри одной страницы — проблема этой страницы. Соседние страницы не затронуты. Управлять свободным местом проще: «на странице 5 есть 2 КБ свободно» вместо «байты 1024-1030, 2048-2100, 5000-5010 свободны».

Единица I/O стандартизирована. Читаем и пишем всегда по 8 КБ. Хорошо ложится на сектора диска (обычно 512 байт или 4 КБ) и страницы ОС.

Чего страничная организация не даёт:

Атомарность записи. Запись страницы на диск не гарантированно атомарна: сбой может оставить страницу в «разорванном» состоянии (torn page), когда часть 8 КБ — новая, а часть — старая. Страничная организация эту проблему не решает — она лишь стандартизирует единицу, с которой работает защита.

PostgreSQL избегает необратимых повреждений за счёт WAL. Правило простое: прежде чем изменённая страница попадёт на диск, на диск должны попасть соответствующие записи WAL (WAL before data). А чтобы torn page можно было восстановить даже после контрольной точки, PostgreSQL при первом изменении страницы после неё пишет в WAL полный образ страницы (Full Page Writes). Контрольная точка (checkpoint) и Full Page Writes подробнее описаны в WAL и буферном кеше.

Структура страницы: slotted page

Внутри страницы та же проблема: строки разной длины. Решение — slotted page (страница со слотами).

┌─────────────────────────────────────┐  ← начало страницы (байт 0)
│ Page Header (24 байта)              │
│ - pd_lsn (позиция в WAL)            │
│ - pd_lower (конец line pointers)    │
│ - pd_upper (начало данных)          │
├─────────────────────────────────────┤
│ Line Pointer 1 (4 байта) → ─────────────────┐
│ Line Pointer 2 (4 байта) → ───────────────┐ │
│ Line Pointer 3 (4 байта) → ─────────────┐ │ │
│ ...                                     │ │ │
│ ↓ растут вниз                           │ │ │
├─────────────────────────────────────┤   │ │ │
│                                     │   │ │ │
│         Free Space                  │   │ │ │
│                                     │   │ │ │
├─────────────────────────────────────┤   │ │ │
│                    ↑ растут вверх   │   │ │ │
│ Tuple 3   ←─────────────────────────────┘ │ │
├─────────────────────────────────────┤     │ │
│ Tuple 2   ←───────────────────────────────┘ │
├─────────────────────────────────────┤       │
│ Tuple 1   ←─────────────────────────────────┘
└─────────────────────────────────────┘  ← конец страницы (байт 8191)

Line pointers растут от начала вниз. Tuples (данные строк) растут от конца вверх. Между ними — свободное пространство.

Зачем нужен line pointer — уровень косвенности

Line pointer — это не просто «указатель на данные». Это уровень косвенности (indirection), который решает критическую проблему.

Без line pointer: Индекс хранит «строка лежит на странице 5, начиная с байта 1000». При дефрагментации страницы (перемещении данных внутри неё) — индекс ломается. Нужно обновить все индексы, которые ссылаются на эту строку. Дорого.

С line pointer: Индекс хранит «строка на странице 5, позиция 3» (третий line pointer). При дефрагментации tuple может переехать с байта 1000 на байт 800 — обновляется только line pointer. Индексы не трогаем.

Line pointer занимает 4 байта и хранит: смещение tuple от начала страницы (15 бит), длину tuple (15 бит), флаги (2 бита).

ctid — адрес версии строки

ctid (tuple identifier) — физический адрес версии строки. Формат: (номер_страницы, номер_позиции).

Пример: (0, 1) означает «страница 0, line pointer 1».

Почему «позиция», а не «смещение в байтах»: Именно из-за line pointer. Позиция — это номер слота, стабильный при перемещении данных внутри страницы.

Важно: ctid — это адрес конкретной версии строки, не самой строки. При UPDATE создаётся новая версия с новым ctid. Индексы хранят ctid и обычно должны обновляться.

Heap — неупорядоченное хранилище

Heap (куча) в контексте PostgreSQL — таблица, где строки лежат без сортировки. Вставляем туда, где есть место.

Почему «куча»? Потому что данные «свалены» без порядка, как вещи в куче. Это НЕ heap как структура данных (двоичная куча для приоритетной очереди) и НЕ heap как область памяти в языках программирования.

Что это значит практически: Чтобы найти строку по значению (например, WHERE name = 'Alice'), нужно просмотреть все страницы — sequential scan. Без индекса поиск O(n), где n — количество страниц.

Tuple — физическая строка с метаданными

Tuple (кортеж) в реляционной теории — упорядоченный набор значений атрибутов.

Tuple в PostgreSQL — физическая структура на диске, содержащая:

  • Заголовок (23 байта): xmin, xmax (идентификаторы транзакций, подробнее в MVCC), ctid, флаги, информация о NULL
  • Данные полей

Путаница терминов:

  • В теории: tuple = row = кортеж = строка (логическая единица)
  • В PostgreSQL: tuple = конкретная версия строки с физическим заголовком

При UPDATE PostgreSQL создаёт новый tuple. Старый и новый tuple — это одна логическая строка, но две физические версии.

Страницы стандартизируют I/O, но не гарантируют, что COMMIT переживёт сбой. Для этого нужен журнал упреждающей записи — WAL. А когда данные не помещаются в одну страницу, PostgreSQL использует TOAST.

Sources

← ACID в PostgreSQL | TOAST →

Graph View

Backlinks