Принципы организации распределенных баз данных

Description

В книге представлено подробное описание распределенных и параллельных баз данных с учетом новейших технологий. Авторы затрагивают такие темы, как проектирование распределенных и параллельных БД, контроль распределенных данных, распределенная обработка запросов и транзакций, интеграция баз данных. Отдельная глава посвящена обработке больших данных (в частности, обсуждаются распределенные системы хранения, потоковая обработка данных, платформы MapReduce и Spark, анализ графов и озера данных). Обработка веб-данных рассматривается с акцентом на технологию RDF, получившую широкое распространение. В конце глав 2–12 приводятся упражнения, позволяющие закрепить теоретический материал. На сопроводительном сайте читатели найдут информацию об основах реляционных баз данных, обработке запросов, управлении транзакциями и компьютерных сетях. Предисловие От издательства Введение 1.1. Что такое распределенная система баз данных? 1.2. История распределенных СУБД 1.3. Различные способы доставки данных 1.4. Обещания распределенных СУБД 1.4.1. Прозрачное управление распределенными и реплицированными данными 1.4.2. Обеспечение надежности с помощью распределенных транзакций 1.4.3. Повышенная производительность 1.4.4. Масштабируемость 1.5. Вопросы проектирования 1.5.1. Проектирование распределенной базы данных 1.5.2. Контроль распределенных данных 1.5.3. Распределенная обработка запросов 1.5.4. Распределенное управление конкурентностью 1.5.5. Надежность распределенной СУБД 1.5.6. Репликация 1.5.7. Параллельные СУБД 1.5.8. Интеграция баз данных 1.5.9. Альтернативные подходы к распределению 1.5.10. Обработка больших данных и NoSQL 1.6. Архитектуры распределенных СУБД 1.6.1. Архитектурные модели для распределенных СУБД 1.6.1.1. Автономность 1.6.1.2. Распределение 1.6.1.3. Гетерогенность 1.6.2. Клиент-серверные системы 1.6.3. Одноранговые системы 1.6.4. Системы управления мультибазами данных 1.6.5. Облачные вычисления 1.7. Библиографические замечания Проектирование распределенных и параллельных баз данных 2.1. Фрагментация данных 2.1.1. Горизонтальная фрагментация 2.1.1.1. Требования к  дополнительной информации 2.1.1.2. Главная горизонтальная фрагментация 2.1.1.3. Производная горизонтальная фрагментация 2.1.1.4. Проверка корректности 2.1.2. Вертикальная фрагментация 2.1.2.1. Требования к  дополнительной информации 2.1.2.2. Алгоритм кластеризации 2.1.2.3. Алгоритм расщепления 2.1.2.4. Проверка корректности 2.1.3. Гибридная фрагментация 2.2. Размещение 2.2.1. Дополнительная информация 2.2.2. Модель размещения 2.2.2.1. Полная стоимость 2.2.2.2. Ограничения 2.2.3. Методы решения 2.3. Комбинированные подходы 2.3.1. Методы секционирования, безразличные к рабочей нагрузке 2.3.2. Методы секционирования, учитывающие рабочую нагрузку 2.4. Адаптивные подходы 2.4.1. Обнаружение изменений рабочей нагрузки 2.4.2. Обнаружение проблемных участков 2.4.3. Инкрементная реконфигурация 2.5. Каталог данных 2.6. Заключение 2.7. Библиографические замечания Упражнения Контроль распределенных данных 3.1. Управление представлениями 3.1.1. Представления в централизованных СУБД 3.1.2. Представления в распределенных СУБД 3.1.3. Обслуживание материализованных представлений 3.2. Контроль доступа 3.2.1. Избирательный контроль доступа 3.2.2. Мандатный контроль доступа 3.2.3. Распределенный контроль доступа 3.3. Контроль семантической целостности 3.3.1. Централизованный контроль семантической целостности 3.3.1.1. Спецификация ограничений целостности 3.3.1.2. Проверка целостности 3.3.2. Распределенный контроль семантической целостности 3.3.2.1. Определение распределенных ограничений целостности 3.3.2.2. Проверка распределенных ограничений целостности 3.3.2.3. Итоги обсуждения распределенного контроля целостности 3.4. Заключение 3.5. Библиографические замечания Упражнения Распределенная обработка запросов 4.1. Общий обзор 4.1.1. Задача обработки запроса 4.1.2. Оптимизация запроса 4.1.2.1. Пространство поиска 4.1.2.2. Модель стоимости 4.1.2.3. Стратегия поиска 4.1.3. Уровни обработки запросов 4.1.3.1. Декомпозиция запроса 4.1.3.2. Локализация данных 4.1.3.3. Распределенная оптимизация 4.1.3.4. Распределенное выполнение 4.2. Локализация данных 4.2.1. Редукция для главной горизонтальной фрагментации 4.2.1.1. Редукция с помощью выборки 4.2.2. Редукция с помощью соединения 4.2.3. Редукция для вертикальной фрагментации 4.2.4. Редукция для производной фрагментации 4.2.5. Редукция для гибридной фрагментации 4.3. Порядок соединений в распределенных запросах 4.3.1. Деревья соединений 4.3.2. Порядок соединений 4.3.3. Алгоритмы на основе полусоединений 4.3.4. Сравнение соединения и полусоединения 4.4. Распределенная модель стоимости 4.4.1. Функции стоимости 4.4.2. Статистика базы данных 4.5. Оптимизация распределенных запросов 4.5.1. Динамический подход 4.5.2. Статический подход 4.5.3. Гибридный подход 4.6. Адаптивная обработка запроса 4.6.1. Процесс адаптивной обработки запросов 4.6.1.1. Отслеживаемые параметры 4.6.1.2. Адаптивные реакции 4.6.2. Вихревой подход 4.7. Заключение 4.8. Библиографические замечания Упражнения Распределенная обработка транзакций 5.1. Основные понятия и терминология 5.2. Распределенное управление конкурентностью 5.2.1. Алгоритмы на основе блокировки 5.2.1.1. Централизованный алгоритм 2PL 5.2.1.2. Распределенный 2PL 5.2.1.3. Управление распределенными взаимоблокировками 5.2.2. Алгоритмы на основе временных меток 5.2.2.1. Базовый алгоритм упорядочения временных меток 5.2.2.2. Консервативный УВМ-алгоритм 5.2.3. Многоверсионное управление конкурентностью 5.2.4. Оптимистические алгоритмы 5.3. Распределенное управление конкурентностью с помощью изоляции моментальных снимков 5.4. Надежность распределенных СУБД 5.4.1. Протокол двухфазной фиксации 5.4.2. Варианты 2PC 5.4.2.1. Протокол 2PC с предполагаемой отменой 5.4.2.2. Протокол 2PC с предполагаемой фиксацией 5.4.3. Обработка отказов узлов 5.4.3.1. Протоколы завершения и восстановления для 2PC 5.4.3.2. Протокол трехфазной фиксации 5.4.4. Разделение сети 5.4.4.1. Централизованные протоколы 5.4.4.2. Протоколы на основе голосования 5.4.5. Протокол достижения консенсуса Paxos 5.4.6. Архитектурные соображения 5.5. Современные подходы к горизонтальному масштабированию управления транзакциями 5.5.1. Spanner 5.5.2. LeanXcale 5.6. Заключение 5.7. Библиографические замечания Упражнения Репликация данных 6.1. Согласованность реплицированных баз данных 6.1.1. Взаимная согласованность 6.1.2. Взаимная согласованность и согласованность транзакций 6.2. Стратегии управления обновлениями 6.2.1. Энергичное распространение обновлений 6.2.2. Ленивое распространение обновлений 6.2.3. Централизованные методы 6.2.4. Распределенные методы 6.3. Протоколы репликации 6.3.1. Энергичные централизованные протоколы 6.3.1.1. Единственный главный узел с ограниченной прозрачностью репликации 6.3.1.2. Единственный главный узел с полной прозрачностью репликации 6.3.1.3. Ведущая копия с полной прозрачностью репликации 6.3.2. Энергичные распределенные протоколы 6.3.3. Ленивые централизованные протоколы 6.3.3.1. Единственный главный узел с ограниченной прозрачностью репликации 6.3.3.2. Единственный главный или ведущий узел с полной прозрачностью репликации 6.3.4. Ленивые распределенные протоколы 6.4. Групповая коммуникация 6.5. Репликация и отказы 6.5.1. Отказы и ленивая репликация 6.5.2. Отказы и энергичная репликация 6.6. Заключение 6.7. Библиографические замечания Упражнения Интеграция баз данных – системы управления мультибазами данных 7.1. Интеграция баз данных 7.1.1. Методология проектирования снизу вверх 7.1.2. Сопоставление схем 7.1.2.1. Гетерогенность схем 7.1.2.2. Подходы на основе лингвистического сопоставления 7.1.2.3. Сопоставление на основе ограничений 7.1.2.4. Сопоставление на основе обучения 7.1.2.5. Комбинированные подходы к сопоставлению 7.1.3. Интеграция схем 7.1.4. Отображение схем 7.1.4.1. Создание отображения 7.1.4.2. Обслуживание отображений 7.1.5. Очистка данных 7.2. Обработка мультибазовых запросов 7.2.1. Проблемы обработки мультибазовых запросов 7.2.2. Архитектура обработки мультибазового запроса 7.2.3. Переписывание запросов с помощью представлений 7.2.3.1. Терминология Datalog 7.2.3.2. Переписывание в случае ГКП 7.2.3.3. Переписывание в случае ЛКП 7.2.4. Оптимизация и выполнение запроса 7.2.4.1. Моделирование гетерогенной стоимости 7.2.4.2. Гетерогенная оптимизация запроса 7.2.5. Трансляция и выполнение запроса 7.3. Заключение 7.4. Библиографические замечания Упражнения Параллельные системы баз данных 8.1. Цели 8.2. Параллельные архитектуры 8.2.1. Общая архитектура 8.2.2. Архитектура с общей памятью 8.2.2.1. Равномерный доступ к памяти (UMA) 8.2.2.2. Неравномерный доступ к памяти (NUMA) 8.2.3. Архитектура с общим диском 8.2.4. Архитектура без разделения ресурсов 8.3. Размещение данных 8.4. Параллельная обработка запросов 8.4.1. Параллельные алгоритмы обработки данных 8.4.1.1. Параллельные алгоритмы сортировки 8.4.1.2. Параллельные алгоритмы соединения 8.4.2. Оптимизация параллельных запросов 8.4.2.1. Пространство поиска 8.4.2.2. Модель стоимости 8.4.2.3. Стратегия поиска 8.5. Балансировка запроса 8.5.1. Проблемы параллельного выполнения 8.5.2. Внутриоператорная балансировка нагрузки 8.5.3. Межоператорная балансировка нагрузки 8.5.4. Внутризапросная балансировка нагрузки 8.6. Отказоустойчивость 8.7. Кластеры баз данных 8.7.1. Архитектура кластера баз данных 8.7.2. Репликация 8.7.3. Балансировка нагрузки 8.7.4. Обработка запросов 8.8. Резюме 8.9. Библиографические замечания Упражнения Управление данными в одноранговых системах 9.1. Инфраструктура 9.1.1. Неструктурированные P2P-сети 9.1.2. Структурированные P2P-сети 9.1.3. Суперодноранговые P2P-сети 9.1.4. Сравнение P2P-сетей 9.2. Отображение схем в P2P-системах 9.2.1. Попарное отображение схем 9.2.2. Отображение на основе методов машинного обучения 9.2.3. Отображение на основе общего согласия 9.2.4. Отображение схем методами информационного поиска 9.3. Запросы в P2P-системах 9.3.1. Получение первых k результатов 9.3.1.1. Базовые методы 9.3.1.2. Запросы типа «первые k» в неструктурированных системах 9.3.1.3. Запросы типа «первые k» в DHT-системах 9.3.1.4. Запросы типа «первые k» в суперодноранговых системах 9.3.2. Запросы с соединением 9.3.3. Запросы по диапазону 9.4. Согласованность реплик 9.4.1. Базовая поддержка в DHT 9.4.2. Актуальность данных в DHT 9.4.3. Урегулирование реплик 9.4.3.1. OceanStore 9.4.3.2. P-Grid 9.4.3.3. APPA 9.5. Блокчейн 9.5.1. Определение блокчейна 9.5.2. Инфраструктура блокчейна 9.5.2.1. Создание транзакции 9.5.2.2. Группировка транзакций в блоки 9.5.2.3. Консенсусная проверка блока 9.5.3. Блокчейн 2.0 9.5.4. Проблемы 9.6. Заключение 9.7. Библиографические замечания Упражнения Обработка больших данных 10.1. Распределенные системы хранения 10.1.1. Google File System 10.1.2. Сочетание объектного и файлового хранения 10.2. Каркасы для обработки больших данных 10.2.1. Обработка данных в  Map­Re­duce 10.2.1.1. Архитектура Map­Re­duce 10.2.1.2. Языки высокого уровня для Map­Re­duce 10.2.1.3. Реализация операторов базы данных в Map­Re­duce 10.2.2. Обработка данных с помощью Spark 10.3. Управление потоковыми данными 10.3.1. Потоковые модели, языки и операторы 10.3.1.1. Модели данных 10.3.1.2. Модели и языки потоковых запросов 10.3.1.3. Потоковые операторы и их реализация 10.3.2. Обработка запросов к потокам данных 10.3.2.1. Выполнение оконного запроса 10.3.2.2. Управление нагрузкой 10.3.2.3. Обработка не по порядку 10.3.2.4. Многозапросная оптимизация 10.3.2.5. Параллельная обработка потоков данных 10.3.3. Отказоустойчивость СПД 10.4. Платформы для анализа графов 10.4.1. Разбиение графа 10.4.2. Map­Re­duce и анализ графов 10.4.3. Специализированные системы анализа графов 10.4.4. Ориентированная на вершины пошагово-синхронная модель 10.4.5. Ориентированная на вершины асинхронная модель 10.4.6. Ориентированная на вершины модель сбора–обработки–распространения 10.4.7. Ориентированная на разделы пошагово-синхронная модель 10.4.8. Ориентированная на разделы асинхронная модель 10.4.9. Ориентированная на разделы модель сбора–обработки–распространения 10.4.10. Ориентированная на ребра пошагово-синхронная модель 10.4.11. Ориентированная на ребра асинхронная модель 10.4.12. Ориентированная на ребра модель сбора–обработки–распространения 10.5. Озера данных 10.5.1. Озера данных и хранилища данных 10.5.2. Архитектура 10.5.3. Проблемы 10.6. Заключение 10.7. Библиографические замечания Упражнения NoSQL, NewSQL и полихранилища 11.1. Причины появления NoSQL 11.2. Хранилища ключей и значений 11.2.1. DynamoDB 11.2.2. Другие хранилища ключей и значений 11.3. Документные хранилища 11.3.1. MongoDB 11.3.2. Другие документные хранилища 11.4. Хранилища с широкими столбцами 11.4.1. Bigtable 11.4.2. Другие хранилища с широкими столбцами 11.5. Графовые СУБД 11.5.1. Neo4j 11.5.2. Другие графовые базы данных 11.6. Гибридные склады данных 11.6.1. Многомодельные NoSQL-системы 11.6.2. СУБД типа NewSQL 11.6.2.1. F1 11.6.2.2. LeanXcale 11.7. Полихранилища 11.7.1. Слабо связанные полихранилища 11.7.1.1. BigIntegrator 11.7.1.2. Forward 11.7.1.3. QoX 11.7.2. Сильно связанные полихранилища 11.7.2.1. Polybase 11.7.2.2. HadoopDB 11.7.2.3. Estocada 11.7.3. Гибридные системы 11.7.3.1. Spark SQL 11.7.3.2. CloudMdsQL 11.7.3.3. BigDAWG 11.7.4. Заключительные замечания 11.8. Заключение 11.9. Библиографические замечания Упражнения Управление веб-данными 12.1. Управление веб-графом 12.2. Поиск в вебе 12.2.1. Обход веба роботом 12.2.2. Индексирование 12.2.2.1. Структурный индекс 12.2.2.2. Текстовый индекс 12.2.3. Ранжирование и анализ ссылок 12.2.4. Поиск по ключевым словам 12.3. Запросы к вебу 12.3.1. Веб как слабо структурированные данные 12.3.2. Языки веб-запросов 12.4. Вопросно-ответные системы 12.5. Поиск и опрос скрытого веба 12.5.1. Обход скрытого веба 12.5.1.1. Запрос через поисковый интерфейс 12.5.1.2. Анализ страниц результатов 12.5.2. Метапоиск 12.5.2.1. Выделение резюме содержимого 12.5.2.2. Категоризация баз данных 12.6. Интеграция веб-данных 12.6.1. Веб-таблицы и фьюжн-таблицы 12.6.2. Семантический веб и проект Linked Open Data 12.6.2.1. XML 12.6.2.2. RDF 12.6.2.3. Навигация и опрос в проекте LOD 12.6.3. Вопросы качества данных при интеграции веб-данных 12.6.3.1. Очистка структурированных веб-данных 12.6.3.2. Слияние веб-данных 12.6.3.3. Качество источника веб-данных 12.7. Библиографические замечания Упражнения Предметный указатель