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

Предисловие к русскому изданию....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