Путеводитель по базам данных

Компания Postgres Professional
Владимир Комаров
Путеводитель
по базам данных
Рекомендовано Институтом системного программирования
им. В. П. Иванникова Российской академии наук (ИСП РАН)
в качестве учебного пособия
Москва, 2024

УДК 004.65
ББК 32.972.134
К63
Комаров В. И.
К63
Путеводитель по базам данных. — М.: ДМК-Пресс, 2024. — 520 с.
ISBN 978-5-93700-287-7
Книга рассказывает об архитектурных принципах, на которых базируются все современные системы управления базами данных, а также об алгоритмах и структурах данных, которые в них используются. Особое внимание
уделено сравнению реализаций одних и тех же подходов в близких по функциональности платформах. Кроме того, предлагается оригинальная классификация СУБД, рассматриваются вопросы эксплуатации и обеспечения безопасности.
Для широкого круга ИТ-специалистов и студентов профильных вузов.
Сайт книги: postgrespro.ru/education/books/dbguide.
УДК 004.65
ББК 32.972.134
© Текст, оформление, ООО «ППГ», 2024
ISBN 978-5-93700-287-7
© Издание, ДМК-Пресс, 2024

Оглавление
От автора . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Часть I. Классификация баз данных
19
Глава 1. Модели данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Глава 2. Другие методы классификации баз данных
. . . . . . . . . . . . . .
61
Часть II. Доступ к данным
73
Глава 3. Структуры хранения данных . . . . . . . . . . . . . . . . . . . . . . .
75
Глава 4. Обработка данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Часть III. Архитектура СУБД
209
Глава 5. Гарантии корректности данных . . . . . . . . . . . . . . . . . . . . . 211
Глава 6. Устройство СУБД
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
Часть IV. Распределённые базы данных
273
Глава 7. Компромиссы распределённых баз данных . . . . . . . . . . . . . . . 275
Глава 8. Изменение данных в распределённых системах . . . . . . . . . . . . 309
Часть V. Восстановление при сбоях
359
Глава 9. Репликация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
Глава 10. Резервное копирование . . . . . . . . . . . . . . . . . . . . . . . . . 377
Часть VI. Эксплуатация баз данных
389
Глава 11. Управление базой данных . . . . . . . . . . . . . . . . . . . . . . . . 391
Глава 12. Оборудование
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Глава 13. Коммерческие вопросы эксплуатации . . . . . . . . . . . . . . . . . 419
Часть VII. Безопасность баз данных
447
Глава 14. Разграничение доступа . . . . . . . . . . . . . . . . . . . . . . . . . 449
Глава 15. Защита от внутренних угроз . . . . . . . . . . . . . . . . . . . . . . 461
Послесловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475
Предметно-именной указатель
. . . . . . . . . . . . . . . . . . . . . . . . . . 481
3

Содержание
От автора
13
Часть I. Классификация баз данных
19
Глава 1. Модели данных
21
1.1. Реляционные БД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
Исторический экскурс
. . . . . . . . . . . . . . . . . . . . . . . . . .
21
Реляционная алгебра . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
Ограничения целостности . . . . . . . . . . . . . . . . . . . . . . . .
27
Вспомогательные структуры данных . . . . . . . . . . . . . . . . . .
29
Диаграммы «сущность—связь»
. . . . . . . . . . . . . . . . . . . . .
30
Нормальные формы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
1.2. Хранилища «ключ—значение» . . . . . . . . . . . . . . . . . . . . . .
38
Java caching API
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
Документоориентированные БД . . . . . . . . . . . . . . . . . . . . .
39
Форматы хранения документов . . . . . . . . . . . . . . . . . . . . .
43
Хранилища семейств колонок . . . . . . . . . . . . . . . . . . . . . .
50
БД временны́х рядов
. . . . . . . . . . . . . . . . . . . . . . . . . . .
52
1.3. Другие модели данных
. . . . . . . . . . . . . . . . . . . . . . . . . .
53
Объектные БД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
Графовые БД . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
1.4. Сравнение моделей данных
. . . . . . . . . . . . . . . . . . . . . . .
57
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
Глава 2. Другие методы классификации баз данных
61
2.1. Аналитические и транзакционные БД
. . . . . . . . . . . . . . . . .
61
2.2. Монолитные и распределённые БД . . . . . . . . . . . . . . . . . . .
63
2.3. БД на диске и в памяти . . . . . . . . . . . . . . . . . . . . . . . . . .
66
2.4. Карта баз данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4

Содержание
Часть II. Доступ к данным
73
Глава 3. Структуры хранения данных
75
3.1. Общая информация о дисковых структурах . . . . . . . . . . . . . .
75
Изменяемые и неизменяемые структуры . . . . . . . . . . . . . . . .
75
Эффективность операций
. . . . . . . . . . . . . . . . . . . . . . . .
77
3.2. Изменяемые структуры . . . . . . . . . . . . . . . . . . . . . . . . . .
79
Неупорядоченная таблица . . . . . . . . . . . . . . . . . . . . . . . .
79
Сжатие данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
B-дерево
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
Другие страничные структуры . . . . . . . . . . . . . . . . . . . . . .
90
Буферный кеш . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
3.3. Неизменяемые структуры
. . . . . . . . . . . . . . . . . . . . . . . .
96
LSM-дерево . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
Фильтр Блума
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
Механизмы хранения на основе LSM-деревьев
. . . . . . . . . . . . 102
Прочие неизменяемые структуры . . . . . . . . . . . . . . . . . . . . 103
3.4. Колоночное хранение . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Концепция и история . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Оптимизация доступа . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
Обновление данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.5. Локализация данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Секционирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
Шардирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.6. СУБД в памяти . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
IMDG и IMDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
Обеспечение надёжного хранения
. . . . . . . . . . . . . . . . . . . 134
Примеры СУБД в памяти . . . . . . . . . . . . . . . . . . . . . . . . . 136
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
Глава 4. Обработка данных
149
4.1. Поиск данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Поиск данных в структурах на основе LSM-дерева
. . . . . . . . . . 149
Поиск в неупорядоченной таблице
. . . . . . . . . . . . . . . . . . . 150
Индексирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153
Поиск в B-дереве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
5

Содержание
Самый быстрый способ поиска
. . . . . . . . . . . . . . . . . . . . . 161
4.2. Операции реляционной алгебры
. . . . . . . . . . . . . . . . . . . . 162
Соединение вложенными циклами (nested loops) . . . . . . . . . . . 164
Соединение слиянием (merge join) . . . . . . . . . . . . . . . . . . . 165
Соединение хешированием (hash join) . . . . . . . . . . . . . . . . . 166
Самый быстрый способ соединения . . . . . . . . . . . . . . . . . . . 168
4.3. Оптимизация запросов . . . . . . . . . . . . . . . . . . . . . . . . . . 170
План выполнения запроса
. . . . . . . . . . . . . . . . . . . . . . . . 171
Эвристическая оптимизация . . . . . . . . . . . . . . . . . . . . . . . 174
Оптимизация, основанная на стоимости . . . . . . . . . . . . . . . . 175
Кеширование запросов и планов
. . . . . . . . . . . . . . . . . . . . 184
Оптимизация параметризованных запросов . . . . . . . . . . . . . . 186
Ручное управление планами . . . . . . . . . . . . . . . . . . . . . . . 190
4.4. Реализация бизнес-логики . . . . . . . . . . . . . . . . . . . . . . . . 192
Клиентские модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
ORM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
Хранимый код . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
Часть III. Архитектура СУБД
209
Глава 5. Гарантии корректности данных
211
5.1. Транзакции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
Атомарность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
Согласованность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
Изоляция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
Долговечность (надёжность) . . . . . . . . . . . . . . . . . . . . . . . 220
5.2. Журналирование
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Назначение журнала
. . . . . . . . . . . . . . . . . . . . . . . . . . . 221
Работа с журналом
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Устройство журнала . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
Структуры без журналирования . . . . . . . . . . . . . . . . . . . . . 228
Общий алгоритм выполнения транзакции . . . . . . . . . . . . . . . 231
5.3. Блокировки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232
Классификация блокировок . . . . . . . . . . . . . . . . . . . . . . . 232
6

Содержание
Управление блокировками . . . . . . . . . . . . . . . . . . . . . . . . 239
Конкурентные транзакции без блокировок
. . . . . . . . . . . . . . 243
5.4. Версионирование данных
. . . . . . . . . . . . . . . . . . . . . . . . 244
Обработка данных без версионирования . . . . . . . . . . . . . . . . 244
Версионирование в страничных хранилищах . . . . . . . . . . . . . 245
Версионирование в хранилищах на основе LSM-деревьев . . . . . . 250
Версионирование в СУБД в памяти . . . . . . . . . . . . . . . . . . . 252
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
Глава 6. Устройство СУБД
257
6.1. Экземпляр
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
Структура экземпляра
. . . . . . . . . . . . . . . . . . . . . . . . . . 257
Общая память экземпляра . . . . . . . . . . . . . . . . . . . . . . . . 258
Пользовательские процессы . . . . . . . . . . . . . . . . . . . . . . . 263
Служебные процессы . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
6.2. База данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
Связь базы данных и экземпляра
. . . . . . . . . . . . . . . . . . . . 267
Состав базы данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Часть IV. Распределённые базы данных
273
Глава 7. Компромиссы распределённых баз данных
275
7.1. CAP-теорема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
Формулировка CAP-теоремы . . . . . . . . . . . . . . . . . . . . . . . 276
Критика CAP-теоремы
. . . . . . . . . . . . . . . . . . . . . . . . . . 278
Системы CP и AP и классификация PACELC
. . . . . . . . . . . . . . 279
7.2. Исторический экскурс: CA-системы . . . . . . . . . . . . . . . . . . . 282
Oracle RAC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
IBM PureData System for Transactions
. . . . . . . . . . . . . . . . . . 285
HPE NonStop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
SAP HANA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
7.3. Согласованность в распределённых системах . . . . . . . . . . . . . 291
Линеаризация изменений
. . . . . . . . . . . . . . . . . . . . . . . . 291
Причинная согласованность . . . . . . . . . . . . . . . . . . . . . . . 296
7

Содержание
7.4. Топология кластера . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Статическая топология . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Протоколы сплетен . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
Глава 8. Изменение данных в распределённых системах
309
8.1. Основные понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309
8.2. Отказоустойчивый кластер с репликацией . . . . . . . . . . . . . . . 311
8.3. Распределённый консенсус . . . . . . . . . . . . . . . . . . . . . . . . 314
Paxos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
Multi-paxos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
Raft
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
Zookeeper Atomic Broadcast . . . . . . . . . . . . . . . . . . . . . . . . 323
Другие алгоритмы распределённого консенсуса . . . . . . . . . . . . 324
8.4. Распределённые транзакции . . . . . . . . . . . . . . . . . . . . . . . 326
Протокол двухфазной фиксации . . . . . . . . . . . . . . . . . . . . . 326
Детерминированные транзакции (Calvin transactions) . . . . . . . . 328
Сага . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.5. Компенсация несогласованности . . . . . . . . . . . . . . . . . . . . 336
Нестрогий кворум и направленная передача
. . . . . . . . . . . . . 336
Восстановление данных и дерево Меркла
. . . . . . . . . . . . . . . 337
Версионирование объектов
. . . . . . . . . . . . . . . . . . . . . . . 338
8.6. Безопасные типы данных . . . . . . . . . . . . . . . . . . . . . . . . . 342
Счётчик (counter) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
Множество (set) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344
8.7. Архитектура распределённых платформ . . . . . . . . . . . . . . . . 345
Приложение как координатор транзакции . . . . . . . . . . . . . . . 345
Буквальная реализация спецификации X/Open . . . . . . . . . . . . 346
Выделенный координатор транзакций . . . . . . . . . . . . . . . . . 346
«Настоящее горизонтальное масштабирование»
. . . . . . . . . . . 348
Google Spanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
CockroachDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
FoundationDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
Независимые узлы — участники саги . . . . . . . . . . . . . . . . . . 354
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
8

Содержание
Часть V. Восстановление при сбоях
359
Глава 9. Репликация
361
9.1. Блочная репликация
. . . . . . . . . . . . . . . . . . . . . . . . . . . 361
9.2. Физическая репликация
. . . . . . . . . . . . . . . . . . . . . . . . . 364
9.3. Логическая репликация . . . . . . . . . . . . . . . . . . . . . . . . . . 367
Репликация триггерами
. . . . . . . . . . . . . . . . . . . . . . . . . 370
Репликация с помощью журналов СУБД . . . . . . . . . . . . . . . . 371
Репликация с помощью CDC . . . . . . . . . . . . . . . . . . . . . . . 371
Прикладная репликация . . . . . . . . . . . . . . . . . . . . . . . . . 372
9.4. Так что же лучше? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
Глава 10. Резервное копирование
377
10.1. Выгрузка данных
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
10.2. Холодное сохранение файлов БД . . . . . . . . . . . . . . . . . . . . . 379
10.3. Горячее сохранение файлов БД
. . . . . . . . . . . . . . . . . . . . . 380
10.4. Восстановление на точку . . . . . . . . . . . . . . . . . . . . . . . . . 383
10.5. Инкрементальное резервное копирование . . . . . . . . . . . . . . . 384
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
Часть VI. Эксплуатация баз данных
389
Глава 11. Управление базой данных
391
11.1. Механизмы управления . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Мониторинг и журналирование . . . . . . . . . . . . . . . . . . . . . 391
Несколько слов о мониторинге
. . . . . . . . . . . . . . . . . . . . . 393
11.2. Мониторинг баз данных
. . . . . . . . . . . . . . . . . . . . . . . . . 395
Мониторинг доступности экземпляра
. . . . . . . . . . . . . . . . . 395
Мониторинг сервера
. . . . . . . . . . . . . . . . . . . . . . . . . . . 395
Мониторинг состояния экземпляра . . . . . . . . . . . . . . . . . . . 397
11.3. Настройка производительности . . . . . . . . . . . . . . . . . . . . . 398
Использование динамических представлений . . . . . . . . . . . . . 398
Другие методы настройки производительности . . . . . . . . . . . . 399
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
9

Содержание
Глава 12. Оборудование
403
12.1. Серверы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Мейнфреймы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
Мини-ЭВМ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
Открытые системы
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
Семейство x86 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
Что дальше?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
12.2. Системы хранения данных . . . . . . . . . . . . . . . . . . . . . . . . 411
Дисковый массив или локальные диски? . . . . . . . . . . . . . . . . 411
Протоколы сетевого доступа к дискам
. . . . . . . . . . . . . . . . . 413
Hi-end или mid-range? . . . . . . . . . . . . . . . . . . . . . . . . . . . 414
Отказоустойчивость дисковых массивов . . . . . . . . . . . . . . . . 415
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
Глава 13. Коммерческие вопросы эксплуатации
419
13.1. Надёжность и производительность . . . . . . . . . . . . . . . . . . . 419
Тестирование производительности баз данных . . . . . . . . . . . . 419
Влияние оборудования на производительность БД . . . . . . . . . . 422
Обеспечение надёжности баз данных . . . . . . . . . . . . . . . . . . 424
13.2. Классификация информационных систем . . . . . . . . . . . . . . . 428
13.3. Базы данных в облаке . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
Монолитные транзакционные платформы . . . . . . . . . . . . . . . 435
Распределённые платформы . . . . . . . . . . . . . . . . . . . . . . . 437
13.4. Процедура выбора платформы . . . . . . . . . . . . . . . . . . . . . . 439
Формирование списка
. . . . . . . . . . . . . . . . . . . . . . . . . . 439
Оценка стоимости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
Оценка возможностей
. . . . . . . . . . . . . . . . . . . . . . . . . . 442
Результат . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
Часть VII. Безопасность баз данных
447
Глава 14. Разграничение доступа
449
14.1. Ролевая модель доступа . . . . . . . . . . . . . . . . . . . . . . . . . . 449
Субъекты и объекты
. . . . . . . . . . . . . . . . . . . . . . . . . . . 449
Полномочия
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
10