Глава 112. Database Internals: A Deep Dive (short summary)

Связанная глава

PostgreSQL изнутри

Глубокое погружение в MVCC, WAL, блокировки и индексы PostgreSQL от Егора Рогова.

Читать обзор

Database Internals (Движки хранения)

Авторы: Alex Petrov
Издательство: O'Reilly Media, Inc.
Объём: 370 страниц

Разбор книги Alex Petrov: B-Trees, LSM-Trees, транзакции, репликация, консенсус и внутреннее устройство СУБД.

Оригинал

Перевод

Подробный разбор

Code of Architecture

Детальный разбор первой части от Александра и клуба Code of Architecture

Читать разбор

Часть I: Storage Engines (Движки хранения)

B-Trees и их варианты

Структуры данных

B-Tree

Базовая структура с ключами в узлах

B+ Tree

Данные только в листьях, связный список

B* Tree

Оптимизация заполнения узлов

Bw-Tree

Lock-free B-Tree для in-memory

Дисковые оптимизации

Page Organization

Структура страницы: заголовок, ячейки, указатели

Buffer Pool

Кеширование страниц в памяти

Split & Merge

Разделение и слияние узлов при overflow/underflow

Overflow Pages

Хранение больших значений отдельно

Ключевой инсайт: B-Tree оптимизированы для чтения и in-place updates, что делает их идеальными для OLTP-нагрузок. PostgreSQL и MySQL InnoDB используют B+ Tree для индексов.

Подробный разбор

Code of Architecture

Детальный разбор главы об LSM-Tree от Александра и клуба Code of Architecture

Читать разбор

LSM-Trees (Log-Structured Merge Trees)

Компоненты

MemTable

In-memory буфер записей (обычно Red-Black Tree)

SSTable

Sorted String Table — неизменяемые файлы на диске

WAL

Write-Ahead Log для durability

Compaction

Size-Tiered

Группировка по размеру, меньше write amplification

Leveled

Уровни с лимитом размера, лучше read

FIFO

Для time-series данных с TTL

Оптимизации чтения

Bloom Filter

Вероятностная проверка наличия ключа

Sparse Index

Индекс на блоки SSTable

Block Cache

Кеширование блоков данных

Ключевой инсайт: LSM-Trees оптимизированы для записи (sequential I/O), но требуют compaction для поддержания read-производительности. Используются в Cassandra, RocksDB, LevelDB, HBase.

B-Tree vs LSM-Tree: выбор структуры данных

Архитектура B-Tree

[10 | 20 | 30]

[3|5|8]

[12|15|18]

[22|25|28]

Листья содержат указатели на данные

✓ Преимущества

Быстрое чтение: O(log N)
Эффективные range-запросы
In-place updates

✗ Недостатки

Write amplification
Random I/O при записи

Где используется:

PostgreSQLMySQL InnoDBOracleSQL ServerSQLite

Transaction Processing

Управление конкурентностью

2PL (Two-Phase Locking)

Growing phase → Shrinking phase

MVCC

Multi-Version Concurrency Control, snapshot isolation

OCC

Optimistic Concurrency Control, validation при commit

SSI

Serializable Snapshot Isolation

Recovery (Восстановление)

WAL (Write-Ahead Log)

Журнал изменений до применения

ARIES

Analysis, Redo, Undo — алгоритм восстановления

Checkpointing

Периодическое сохранение состояния

Shadow Paging

Copy-on-write страницы

Часть II: Distributed Systems

Подробный разбор

Code of Architecture

Детальный разбор главы о репликации и партиционировании от Александра и клуба Code of Architecture

Читать разбор

Replication & Partitioning

Репликация

Single-Leader

Один мастер для записи, реплики для чтения

Multi-Leader

Несколько мастеров, конфликты при записи

Leaderless

Quorum-based чтение/запись (Dynamo-style)

Chain Replication

Цепочка узлов для strong consistency

Партиционирование

Range Partitioning

По диапазону ключей, риск hotspots

Hash Partitioning

Равномерное распределение, но range queries сложнее

Consistent Hashing

Минимизация перебалансировки при добавлении узлов

Compound Partitioning

Комбинация hash + range

Подробный разбор

Code of Architecture

Детальный разбор главы о протоколах консенсуса от Александра и клуба Code of Architecture

Читать разбор

Consensus Protocols

Paxos

Классический алгоритм Лампорта
Prepare → Promise → Accept
Сложен в реализации
Multi-Paxos для лидера

Raft

Understandable consensus
Leader election + Log replication
etcd, Consul, CockroachDB
Проще в реализации

Zab

Zookeeper Atomic Broadcast
Primary-backup model
FIFO ordering гарантии
Optimized for writes

Distributed Transactions

Atomic Commit Protocols

Two-Phase Commit (2PC)

Prepare → Vote → Commit/Abort. Blocking при падении координатора.

Three-Phase Commit (3PC)

Добавляет pre-commit фазу для non-blocking recovery.

Альтернативные подходы

Saga Pattern

Цепочка локальных транзакций с компенсирующими действиями.

Calvin / Deterministic DB

Детерминированный порядок транзакций, replicated state machine.

Низкоуровневые детали

Файловые форматы

Slotted Pages

Гибкое размещение записей переменной длины

Cell Layout

Key-Value-Pointer структуры в страницах

Checksums

CRC32/xxHash для обнаружения повреждений

Alignment

Выравнивание для оптимизации I/O

Disk I/O оптимизации

Sequential vs Random

Предпочтение последовательного чтения/записи

Direct I/O

Обход файлового кеша ОС

Read-Ahead

Упреждающее чтение блоков

Write Coalescing

Группировка записей для batch I/O

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

PostgreSQL

Storage: B+ Tree (Heap + Indexes)

MVCC, WAL, TOAST для больших значений

MySQL InnoDB

Storage: B+ Tree (Clustered Index)

MVCC, Double Write Buffer, Change Buffer

RocksDB

Storage: LSM-Tree

Column Families, Leveled/Universal Compaction

Cassandra

Storage: LSM-Tree

Leaderless Replication, Tunable Consistency

MongoDB

Storage: WiredTiger (B-Tree + LSM)

Document model, Sharding, Replica Sets

CockroachDB

Storage: RocksDB + Raft

Serializable Transactions, Geo-partitioning

Итоги и рекомендации

Сильные стороны

Глубокий разбор внутреннего устройства баз данных
Сравнение B-Tree vs LSM-Tree с trade-offs
Детальный анализ алгоритмов консенсуса
Примеры из реальных production систем
Объяснение физического хранения на диске

Кому подойдёт

Инженерам, работающим с базами данных
Разработчикам storage-систем
Тем, кто хочет понять trade-offs разных СУБД
Подготовка к Staff+ позициям в DB-компаниях
Исследователям в области систем хранения

Вердикт: «Database Internals» — это уникальная книга, которая заполняет пробел между высокоуровневыми книгами по системному дизайну и академическими трудами. Если DDIA объясняет что делать, то Петров объясняет как это реализовано внутри. Обязательна для тех, кто хочет понимать базы данных на глубоком уровне.

Где найти книгу

O'Reilly (оригинал)

Database Internals: A Deep Dive

Русский перевод (Питер)

Погружение в мир распределённых данных