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

Description

Когда дело доходит до выбора, использования и обслуживания базы данных, важно понимать ее внутреннее устройство. Как разобраться в огромном море доступных сегодня распределенных баз данных и инструментов? На что они способны? Чем различаются? Алекс Петров знакомит нас с концепциями, лежащими в основе внутренних механизмов современных баз данных и хранилищ. Для этого ему пришлось обобщить и систематизировать разрозненную информацию из многочисленных книг, статей, постов и даже из нескольких баз данных с открытым исходным кодом. Вы узнаете об принципах и концепциях, используемых во всех типах СУБД, с акцентом на подсистеме хранения данных и компонентах, отвечающих за распределение. Эти алгоритмы используются в базах данных, очередях сообщений, планировщиках и в другом важном инфраструктурном программном обеспечении. Вы разберетесь, как работают современные системы хранения информации, и это поможет взвешенно выбирать необходимое программное обеспечение и выявлять потенциальные проблемы. Предисловие Для кого предназначена эта книга Зачем мне читать эту книгу? Рассматриваемые темы Структура книги Условные обозначения Благодарности От издательства ЧАСТЬ I. Подсистема хранения данных Сравнение баз данных Понимание преимуществ и недостатков Глава 1. Введение и обзор Архитектура СУБД Резидентные и дисковые СУБД Колоночные и строчные СУБД Файлы данных и индексные файлы Буферизация, неизменяемость и упорядочение Итоги Дополнительная литература Глава 2. Введение в B-деревья Двоичные деревья поиска Дисковые структуры Вездесущие B-деревья Итоги Дополнительная литература Глава 3 Глава 3. Форматы файлов Актуальность Двоичное кодирование Основные принципы Структура страницы Слоттированные страницы Структура ячеек Объединение ячеек в слоттированные страницы Управление данными переменного размера Управление версиями Вычисление контрольной суммы Итоги Дополнительная литература Глава 4. Реализация B-деревьев Заголовок страницы Двоичный поиск Распространение операций разделения и слияния Перебалансировка Добавление только справа Сжатие Очистка и обслуживание Итоги Дополнительная литература Глава 5. Обработка транзакций и восстановление Организация буферизации данных Восстановление Управление параллелизмом Итоги Дополнительная литература Глава 6. Варианты B-дерева Копирование при записи Абстрагирование обновлений узлов Ленивые B-деревья FD-деревья Bw-деревья Кэш-независимые B-деревья Итоги Дополнительная литература Глава 7. Журналированное хранилище LSM-деревья Чтение, запись и увеличение пространства Подробнее о реализации Неупорядоченное LSM-хранилище Параллелизм в LSM-деревьях Многоуровневое совмещение журналов LLAMA и тщательное многоуровневое совмещение Итоги Дополнительная литература Часть I . Заключение ЧАСТЬ II ЧАСТЬ II. Распределенные системы Основные определения Глава 8. Введение и обзор Конкурентное выполнение Общее состояние в распределенной системе Абстракции распределенных систем Задача двух генералов Невозможность Фишера—Линча—Патерсона Синхронность системы Модели отказов Итоги Дополнительная литература Глава 9. Обнаружение отказов Контрольные пакеты и эхо-запросы Детектор отказа с накопленным уровнем подозрительности Сплетни и обнаружение отказов Обратный взгляд на проблему обнаружения отказов Итоги Дополнительная литература Глава 10. Выбор лидера Алгоритм забияки Аварийное переключение к следующему в очереди Оптимизация с кандидатами и обычными узлами Алгоритм с приглашениями Кольцевой алгоритм Итоги Дополнительная литература Глава 11. Репликация и согласованность Обеспечение доступности Печально известная теорема CAP Общая память Упорядочение Модели согласованности Модели сеансов Согласованность в конечном счете Настраиваемая согласованность Реплики-свидетели Строгая согласованность в конечном счете и структуры CRDT Итоги Дополнительная литература Глава 12. Антиэнтропия и распространение Исправление при чтении Чтение с запросом хэш-суммы Передача подсказки Деревья Меркла Битовая карта векторов версий Распространение сплетен Итоги Дополнительная литература Глава 13. Распределенные транзакции Обеспечение атомарности операций Двухфазная фиксация Трехфазная фиксация Распределенные транзакции с использованием протокола Calvin Распределенные транзакции с использованием протокола Spanner Секционирование базы данных Распределенные транзакции с использованием библиотеки Percolator Исключение координации Итоги Дополнительная литература Глава 14. Консенсус Рассылка Атомарная рассылка Паксос Raft Византийский консенсус Итоги Дополнительная литература Часть II. Заключение Дополнительная литература Об авторе Об обложке