Log Sequence Number

Log Sequence Number (LSN, номер последовательности журнала) — это монотонно возрастающий уникальный идентификатор, присваиваемый каждой записи в журнале транзакций (transaction log) системы управления базами данных (СУБД). LSN используется для обеспечения атомарности, согласованности, изоляции и долговечности (ACID) транзакций, а также для восстановления базы данных после сбоев.

Назначение

Основная функция LSN — упорядочивание операций записи в журнал транзакций. Каждая операция модификации данных (вставка, обновление, удаление) фиксируется в журнале с присвоением LSN. Это позволяет СУБД точно определить хронологию изменений, что критически важно для:

• Отката транзакций (rollback): при необходимости отменить изменения, СУБД использует LSN для поиска и отмены всех записей, относящихся к конкретной транзакции.
• Восстановления после сбоя (crash recovery): при запуске после аварийного завершения, СУБД анализирует журнал от последней контрольной точки (checkpoint) до конца, используя LSN для определения, какие изменения были зафиксированы, а какие нет.
• Репликации и резервного копирования: LSN служит маркером для синхронизации данных между серверами (например, в PostgreSQL — через WAL (Write-Ahead Log) и LSN).
• Управления контрольными точками (checkpoints): СУБД периодически создаёт контрольные точки, фиксируя LSN, до которого все изменения гарантированно записаны на диск. Это ускоряет восстановление.

Структура и формат

Формат LSN зависит от конкретной СУБД, но общий принцип — это 64-битное или 128-битное целое число, которое монотонно возрастает. В большинстве реляционных СУБД (например, PostgreSQL, SQL Server, Oracle) LSN представлен в виде пары чисел:

• Номер журнала (log file number): указывает на физический файл журнала, в котором находится запись.
• Смещение (offset): позиция записи внутри файла.

Пример в PostgreSQL: 0/16B3748 — где первая часть (0) — номер файла WAL, вторая (16B3748) — смещение в байтах.

В Microsoft SQL Server LSN также имеет три компонента: (VLF Sequence Number, Log Block Number, Slot Number), где VLF (Virtual Log File) — виртуальный файл журнала.

Принцип работы

1. Генерация LSN: При каждом изменении данных СУБД создаёт новую запись в журнале и присваивает ей следующий по порядку LSN. LSN строго возрастает в пределах одной базы данных.
2. Запись в журнал: Запись содержит LSN, идентификатор транзакции, тип операции (INSERT, UPDATE, DELETE), а также данные до и после изменения (для возможности отката).
3. Фиксация транзакции: При COMMIT транзакции СУБД записывает в журнал запись с LSN, подтверждающую фиксацию. Только после этого изменения считаются долговечными.
4. Использование при восстановлении:

• REDO: СУБД применяет все записи с LSN, большим, чем LSN последней контрольной точки, для восстановления данных до последнего зафиксированного состояния.
• UNDO: СУБД отменяет изменения транзакций, которые не были зафиксированы (их LSN не имеют соответствующей записи COMMIT).

Примеры в различных СУБД

PostgreSQL

В PostgreSQL LSN называется WAL position и используется в механизме Write-Ahead Log (WAL). LSN представлен в формате X/Y, где X — 32-битный номер файла WAL, Y — 32-битное смещение. LSN можно получить с помощью функций pg_current_wal_lsn() или pg_last_wal_replay_lsn(). LSN используется для:

• Определения точки восстановления (recovery target).
• Настройки репликации (например, в pg_stat_replication).
• Управления архивацией WAL.

Microsoft SQL Server

В SQL Server LSN называется Log Sequence Number и имеет формат (VLF Sequence Number, Log Block Number, Slot Number). LSN используется для:

• Восстановления базы данных (RESTORE ... WITH STOPAT, STOPBEFOREMARK).
• Определения точек восстановления (log backup chain).
• Анализа активности с помощью функции fn_dblog().

Oracle Database

В Oracle LSN называется System Change Number (SCN). SCN — это 64-битное число, которое генерируется глобально в кластере. SCN используется для:

• Управления многоверсионностью (MVCC).
• Восстановления после сбоя (instance recovery).
• Репликации (Data Guard, GoldenGate).

Связь с контрольными точками

Контрольная точка (checkpoint) — это событие, при котором СУБД записывает все изменённые страницы данных из буферного кэша на диск и фиксирует в журнале LSN, до которого все изменения гарантированно сохранены. При восстановлении СУБД начинает анализ журнала с LSN последней контрольной точки, что сокращает время восстановления.

Ограничения и особенности

• Монотонность: LSN должен строго возрастать, чтобы обеспечить однозначную хронологию. Нарушение монотонности (например, при повреждении журнала) может привести к невозможности восстановления.
• Размер: В большинстве СУБД LSN — 64-битное число, что теоретически позволяет обработать до 2^64 записей. Однако на практике лимит может быть ниже из-за ограничений файловой системы.
• Управление журналом: Журналы транзакций имеют ограниченный размер и циклически перезаписываются. LSN позволяет определить, какие записи ещё нужны для восстановления, а какие можно удалить (например, после резервного копирования).

Критика и альтернативы

• Сложность реализации: Поддержка LSN требует точной синхронизации между буферным кэшем, журналом и диском.
• Производительность: Генерация и запись LSN могут создавать накладные расходы, особенно при высоких нагрузках.
• Альтернативы: В некоторых NoSQL-системах (например, Cassandra) используются другие механизмы упорядочивания (например, временные метки), но они менее надёжны для восстановления.

Источники

• PostgreSQL Documentation: Write-Ahead Log (WAL) and LSN.
• Microsoft SQL Server Documentation: Log Sequence Number (LSN) and Transaction Log Architecture.
• Oracle Database Concepts: System Change Number (SCN).
• Elmasri, R., Navathe, S. B. «Fundamentals of Database Systems» (7th ed.), Chapter 17: Recovery.
• Gray, J., Reuter, A. «Transaction Processing: Concepts and Techniques».