Инспектор
Спонсор: Mail.ru
Вы можете этот курс.
Курсы представлены компанией Mail.ru Group
Проекты: Технопарк, Техносфера
Канал на yotube.com: Технопарк Mail.ru Group
Форма обучения:
дистанционная
Стоимость самостоятельного обучения:
бесплатно
Доступ:
свободный
Документ об окончании:
Вам нравится? Нравится 27 студентам
Уровень:
Для всех
Длительность:
0:03:00
Студентов:
753
В курсе изучаются топологии, многообразия и основные принципы функционирования систем хранения и данных, а также алгоритмы, заложенные в основу как централизованных, так и распределённых систем, демонстрируются фундаментальные компромиссы присущих тем или иным решениям.
Дополнительные курсы
- SQL и процедурно-ориентированные языки
- Введение в реляционные базы данных
- Введение в модель данных SQL
- Основы проектирования приложений баз данных
- Введение в СУБД MySQL
- Администрирование MySQL
- Основы проектирования реляционных баз данных
- Распределенные базы и хранилища данных
- Базы данных: модели, разработка, реализация
План занятий
Занятие
Заголовок <<
Дата изучения
Многообразие решений для хранения данных
Модели данных классических и NoSQL систем. Модели консистентности. Семантика и допустимость овердрафта в интернет-приложениях.
Достоинства и недостатки реляционной модели для работы с данными в Интернет. Модель данных ключ-значение. Модель BigTable. Различия между документом и объектом. Понятие агрегата хранения. Управление схемой данных. Компромисс между консистентностью и производительностью. Конкурентный доступ к данным в клиент-серверной и полностью распределённой архитектуре. Пример графовых задач в РСУБД.
Оглавление
-
Классические и современные алгоритмы организации данных для двухуровневой памяти
B-деревья. Инвертированные списки. Многопроходная сортировка слиянием. Стоимостная модель DAM. Понятие cache-oblivious алгоритма. Базовые cache-oblivious алгоритмы. Понятие write amplification. Фрактальные деревья. LSM деревья. Блум-фильтры. Двухуровневые деревья. BitCask: архитектура AOF, архитектура keydir.
Оглавление
-
Кэширование как механизм повышения эффективности системы
Алгоритм Least Recently Used, реализация в СУБД, стратегия Midpoint insertion. Понятие online-алгоритма. Проблема «аренды лыж». Paging/caching как онлайн-алгоритм. Алгоритмы LFD (Longest Forward Distance), FIFO (First In, First Out). Консервативный алгоритм. Рандомизированный алгоритм MARK.
Оглавление
-
Архитектура СУБД
Методы обзора архитектуры СУБД. Жизненный цикл запроса: получение, парсинг (вторичные ключи), оптимизация на основе правил, чтение метаданных, проверка прав доступа, построение плана выполнения запроса, оценка и оптимизация плана, выполнение, отправка ответа. Управление блокировками. Формат хранения данных на диске. Журнал.
Оглавление
-
Транзакции
Свойства транзакции ACID (Atomicity, Consistency, Isolation, Durability). Атомарность, долговечность транзакций. Применение блокировок. Степень детализации. Принципы WAL. Физическое логирование. Минимальный bookkepping. Простые оптимизации журнала. Модель кэша. Восстановление после отказа, ускорение восстановления. Логирование завершённых транзакций. Изолированность транзакций (интуиция, двухфазная блокировка, формализация, теорема 2PL, граф сериализуемости).
Оглавление
-
Управление блокировками
Захват блокировок для обеспечения консистентности и изолированности транзакций. Матрица совместимости. Иерархия локов. Понятие deadlock’а. Алгоритмы для определения и предотвращения deadlock. Update lock, upgradable lock, granularity lock, intention lock, блокировки на отсутствующие записи. «Голодание» при захвате блокировок. Проблема снижения производительности 2PL-системы при перенасыщении. Блокировки на физическом уровне.
Оглавление
-
Оптимистичные алгоритмы управления транзакциями
Определение оптимистичных алгоритмов. Принцип валидации/сертификации, три фазы выполнения транзакции. Параллельная валидация. Валидация — за и против. Timestamp ordering: запись, чтение, откат. MVCC (многоверсионное управление конкурентным выполнением транзакций, Multi Version Concurrency Control).
Оглавление
-
Автоматизация роста распределённой системы
Функция шардинга. Garage Sharding: удвоение с помощью репликации. Плохие и хорошие шард-ключи. Табличная функция. Консистеное хэширование. Guava, Sumbur. Роутинг (умный клиент, координатор, прокси, локальный прокси на каждом сервере приложений, роутинг внутри БД). Ре-шардинг. Шардинг и изменение схемы данных.
Оглавление
-
Введение в распределённые системы. Протокол 2PC
Модель распределённой системы (способы коммуникации и координации, возможные сбои). Варианты модели. Свойства распределённой системы. Дилемма двух генералов. Варианты распределённых СУБД. Протокол 2PC: модель, роль и действия координатора, фаза подготовки, варианты восстановления, период неопределённости, рабочий процесс, действия участника, crash-safe TC, записи в журнал, пример блокировки алгоритма, производительность, оптимизация.
Оглавление
-
Репликация ДКА, алгоритмы Paxos
Задача репликации журнала. Требование к распределённому алгоритму в применении к Paxos. Распределённый ДКА: подход Paxos. Компоненты Paxos. Постановка проблемы взаимоисключающего выбора. Идентификация предложений. Основы, шаги, сценарии работы Paxos. Свойство Liveness. Multi-Paxos, его задачи. Выбор LSN для предложения. Способ выбора лидера. Оптимизация PREPARE-запросов. Протокол клиента. Изменение состава кворума.
Оглавление
-
Алгоритм RAFT
Обзор RAFT. Выборы лидера (возможные состояния участников, понятие периода (эпохи)). Нормальный режим (репликация журнала). Формат журнала, шаги RAFT при отсутствии сбоев, консистентность распределённого журнала. Проверки в AppendEntries. Безопасная смена лидера. Нейтрализация бывших лидеров. Исправление расхождений журналов, коммит записей текущего периода, записи из предыдущих периодов, полные правила для коммита. Протокол работы клиента. Изменение состава кворума. Изменение конфигурации кластера. Двойной консенсус.
Оглавление
-
-