Распределенные данные. Алгоритмы работы современных систем хранения информации

Предисловие к русскому изданию....5

Предисловие....6

Кому предназначена эта книга....7

Зачем мне читать эту книгу?....9

Рассматриваемые темы....10

Структура книги....11

Условные обозначения....13

Благодарности....14

От издательства....15

ЧАСТЬ I. Подсистема хранения данных....16

Сравнение баз данных....18

Понимание преимуществ и недостатков....23

Глава 1. Введение и обзор....26

Архитектура СУБД....28

Резидентные и дисковые СУБД....32

Колоночные и строчные СУБД....36

Файлы данных и индексные файлы....44

Буферизация, неизменяемость и упорядочение....52

Итоги....55

Дополнительная литература....55

Глава 2. Введение в B-деревья....57

Двоичные деревья поиска....58

Дисковые структуры....64

Вездесущие B-деревья....70

Итоги....86

Дополнительная литература....87

Глава 3. Форматы файлов....88

Актуальность....89

Двоичное кодирование....91

Основные принципы....97

Структура страницы....100

Слоттированные страницы....101

Структура ячеек....104

Объединение ячеек в слоттированные страницы....108

Управление данными переменного размера....109

Управление версиями....112

Вычисление контрольной суммы....113

Итоги....115

Дополнительная литература....115

Глава 4. Реализация B-деревьев....117

Заголовок страницы....117

Двоичный поиск....126

Распространение операций разделения и слияния....128

Перебалансировка....131

Добавление только справа....133

Сжатие....136

Очистка и обслуживание....138

Итоги....142

Дополнительная литература....144

Глава 5. Обработка транзакций и восстановление....145

Организация буферизации данных....146

Восстановление....155

Управление параллелизмом....161

Итоги....179

Дополнительная литература....179

Глава 6. Варианты B-деревьев....181

Копирование при записи....182

Абстракции для управления обновлениями....185

Ленивые B-деревья....186

FD-деревья....190

Bw-деревья....196

Кэш-независимые B-деревья....203

Итоги....207

Дополнительная литература....208

Глава 7. Журналированное хранилище....211

LSM-деревья....213

Чтение, запись и увеличение пространства....237

Подробнее о реализации....240

Неупорядоченное LSM-хранилище....253

Параллелизм в LSM-деревьях....258

Многоуровневое совмещение журналов....261

LLAMA и тщательное многоуровневое совмещение....266

Итоги....270

Дополнительная литература....271

Часть I. Заключение....273

ЧАСТЬ II. Распределенные системы....275

Основные определения....276

Глава 8. Введение и обзор....279

Конкурентное выполнение....279

Общее состояние в распределенной системе....282

Абстракции распределенных систем....299

Задача двух генералов....309

Невозможность Фишера–Линча–Патерсона....311

Синхронность системы....313

Модели отказов....315

Итоги....320

Дополнительная литература....321

Глава 9. Обнаружение отказов....322

Контрольные пакеты и эхо-запросы....325

Детектор отказа с накопленным уровнем подозрительности....329

Сплетни и обнаружение отказов....331

Обратный взгляд на проблему обнаружения отказов....333

Итоги....335

Дополнительная литература....335

Глава 10. Выбор лидера....337

Алгоритм забияки....340

Аварийное переключение к следующему в очереди....342

Оптимизация с кандидатами и обычными узлами....343

Алгоритм с приглашениями....345

Кольцевой алгоритм....347

Итоги....349

Дополнительная литература....351

Глава 11. Репликация и согласованность....352

Обеспечение доступности....353

Печально известная теорема CAP....354

Общая память....360

Упорядочение....362

Модели согласованности....365

Модели сеансов....386

Согласованность в конечном счете....389

Настраиваемая согласованность....390

Реплики-свидетели....393

Строгая согласованность в конечном счете и структуры CRDT....396

Итоги....401

Дополнительная литература....403

Глава 12. Антиэнтропия и распространение....405

Исправление при чтении....407

Чтение с запросом хэш-суммы....410

Передача подсказки....411

Деревья Меркла....412

Битовая карта векторов версий....414

Распространение сплетен....416

Итоги....425

Дополнительная литература....427

Глава 13. Распределенные транзакции....429

Обеспечение атомарности операций....431

Двухфазная фиксация....433

Трехфазная фиксация....440

Распределенные транзакции с использованием протокола Calvin....443

Распределенные транзакции с использованием протокола Spanner....447

Секционирование базы данных....451

Распределенные транзакции с использованием библиотеки Percolator....454

Исключение координации....459

Итоги....464

Дополнительная литература....465

Глава 14. Консенсус....467

Рассылка....469

Атомарная рассылка....471

Паксос....478

Raft....505

Византийский консенсус....514

Итоги....521

Дополнительная литература....523

Часть II. Заключение....526

Дополнительная литература....527

Об авторе....531

Об обложке....532

Приложение А. Библиография....533

Когда дело доходит до выбора, использования и обслуживания базы данных, важно понимать ее внутреннее устройство. Как разобраться в огромном море доступных сегодня распределенных баз данных и инструментов? На что они способны? Чем различаются?

Алекс Петров знакомит нас с концепциями, лежащими в основе внутренних механизмов современных баз данных и хранилищ. Для этого ему пришлось обобщить и систематизировать разрозненную информацию из многочисленных книг, статей, постов и даже из нескольких баз данных с открытым исходным кодом.

Вы узнаете о принципах и концепциях, используемых во всех типах СУБД, с акцентом на подсистеме хранения данных и компонентах, отвечающих за распределение. Эти алгоритмы используются в базах данных, очередях сообщений, планировщиках и в другом важном инфраструктурном программном обеспечении. Вы разберетесь, как работают современные системы хранения информации, и это поможет взвешенно выбирать необходимое программное обеспечение и выявлять потенциальные проблемы.