Движки хранения: страницы, WAL, B+tree и LSM

Клуб сохраняет миллион измерений температуры с датчиков. Приём работает быстро, но через час фоновые операции начинают создавать очередь. Простая оценка «каждый пакет всего 100 байт» не объясняет диск: кроме новых значений он читает, переписывает, индексирует и сохраняет журнал. Сначала нужно проследить физический путь.

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

Страница и buffer pool

Страница — единица обмена с хранилищем. Buffer pool держит часть страниц в памяти. Запрос по индексу сначала проходит его структуру, затем при необходимости читает страницу строки. Cache hit уменьшает физическое чтение, но логическая работа и конкуренция остаются. Dirty page означает, что память отличается от сохранённой страницы; запись позже должна согласоваться с журналом.

Инвариант поиска прост: найденные строки соответствуют предикату и выбранной видимости. Быстрый индекс не имеет права пропустить строку, которая обязана быть видимой. Планировщик сравнивает предполагаемую стоимость; статистика и распределение могут изменить его выбор. EXPLAIN ANALYZE выполняет запрос, поэтому изменяющие команды нельзя проверять так на рабочих данных без понимания эффекта.

B+tree: где стоят ключи

Внутренний узел содержит границы и ссылки, лист — упорядоченные ключи. Поиск выбирает нужную ветку; диапазон продолжает читать соседние листья. Split распределяет переполненный узел и обновляет родителя. Одновременная работа требует согласованного протокола доступа к структуре; row lock транзакции и краткая защита страницы решают разные задачи.

Индекс (tenant_id, created_at, id) подходит списку одного tenant в порядке времени с однозначным продолжением по ID. Для поиска только по времени его стоимость уже другая. Covering index может держать поля результата рядом с ключом, но увеличивает размер и стоимость обновлений. Index-only scan дополнительно зависит от правил видимости движка. Нельзя обещать «таблица никогда не читается» только по наличию включённых полей.

LSM: запись откладывает часть работы

Учебный LSM сохраняет команду в WAL, обновляет memtable, затем flush создаёт неизменяемую SSTable. Если ключ встречается в нескольких файлах, чтение выбирает актуальную версию. Compaction объединяет файлы, оставляя нужные версии. Sorted layout помогает диапазонам, но range scan может сливать несколько потоков, а point lookup проверять несколько файлов.

Bloom filter отвечает «точно отсутствует» или «возможно есть» в рамках корректно построенной структуры. False positive создаёт лишний поиск, false negative нарушил бы правильность. Filter не содержит авторитетного значения. Долгий compaction занимает I/O и CPU; если flush создаёт данные быстрее, чем фон обслуживает их, появляются больше файлов и read amplification. Write stall — способ ограничить дальнейший долг.

При логическом входе 20 MB/с и условной write amplification 8 только учитываемая физическая запись составляет около 160 MB/с. Если WAL измерен отдельно, его нужно прибавить отдельно; если уже входит в числитель, второй раз считать нельзя. Средняя скорость диска не объясняет p99 при compaction и конкуренции.

WAL: ответ до страницы

Порядок write-ahead требует сохранить достаточный журнал до соответствующего изменения страницы на носителе. Commit record и нужный flush задают, когда можно подтверждать durable транзакцию в выбранной конфигурации. Страницы могут обновляться позже. Recovery использует журнал и checkpoint, чтобы восстановить допустимое состояние. Это не полная спецификация ARIES и не описание любого движка: роли redo/undo зависят от его протокола.

Checkpoint не является backup: испорченный носитель может уничтожить и страницы, и журнал. Crash процесса не доказывает сохранность после потери питания. Конкретные гарантии и настройки изучают по PostgreSQL WAL.

Трасса удаления, которое вернулось

Файл F1 содержит sensor-7=v1. F2 позже содержит tombstone для sensor-7. Чтение проверяет новые версии и возвращает отсутствие. Compaction только F2 удаляет tombstone «ведь значения нет». F1 остаётся. Следующее чтение снова находит v1. Удаление ожило без новой записи.

Tombstone можно убрать только при достаточном знании старых файлов, snapshot/readers и других копий, относящихся к протоколу. В нашем маленьком примере merge F1+F2 может удалить обе записи, если прежние snapshots не нужны. В распределённой системе локальное отсутствие старого файла не доказывает отсутствие отставшей реплики. RocksDB Overview даёт первичный вход в организацию LSM; настройки compaction изучают отдельно.

Самостоятельная практика

Напишите на листе два отсортированных файла: F1 содержит (a,1),(b,1),(d,1); F2 содержит (a,2),(b,deleted),(c,1). Сначала выполните чтения a,b,c,d. Затем слейте файлы и посчитайте: шесть входных records, три живых выходных. Теперь удалите tombstone b до объединения со старым F1 и покажите ошибку. Назначайте версии явно, не выбирайте по случайному порядку файлов.

Подсказка: неизвестное значение и tombstone имеют разный смысл. Разбор: до и после безопасного merge результат a=2,b=absent,c=1,d=1; удаление tombstone только из F2 возвращает b=1. Шесть прочитанных и три записанных records — счётчики этой модели; они не являются измерением дисковых байтов настоящей БД.

Дополнительный опыт в отдельной учебной PostgreSQL-базе: создайте 100 тысяч строк через generate_series, выполните ANALYZE, снимите EXPLAIN (ANALYZE, BUFFERS) одного селективного SELECT, добавьте подходящий индекс и повторите запрос. Сверьте результат и число блоков. Маленькая таблица или прогретая память могут не дать заметного speedup; этого не нужно скрывать.

Пересмотрите движок и индекс, когда меняются доля range/point reads, размер working set, rate обновлений, допустимый write stall или объём snapshot history. Сначала исправьте запрос и измерьте текущую систему. Выбор «LSM для любых записей» не является проектом.

Первичные источники

CMU 15-445, хранение, индексы, logging/recovery, PostgreSQL WAL, RocksDB Overview. Данные, файлы и расчёты главы — оригинальные учебные модели.