Лекции Техносферы. 1 семестр. Методы использования СУБД в интернет-приложениях
[embedded content]Сегодня мы предлагаем вашему вниманию очередную публикацию в рамках постоянной рубрики «Лекции Техносферы». В этот раз вы можете изучить материалы по курсу «Методы использования СУБД в интернет-приложениях». Цель курса — изучение топологии, многообразия и основных принципов функционирования систем хранения данных, а также алгоритмов, заложенных в основу как централизованных, так и распределённых систем, демонстрация фундаментальных компромиссов присущих тем или иным решениям. Преподаватели курса: Константин Осипов kostja, Евгений Блих bigbes, Роман Цисык.
Лекция 1. Многообразие решений для хранения данных. Модели данных классических и NoSQL систем. Модели консистентности. Семантика и допустимость овердрафта в интернет-приложенияхДостоинства и недостатки реляционной модели для работы с данными в интернете. Модель данных ключ-значение. Модель BigTable. Различия между документом и объектом. Понятие агрегата хранения. Управление схемой данных. Компромисс между консистентностью и производительностью. Конкурентный доступ к данным в клиент-серверной и полностью распределённой архитектуре. Пример графовых задач в РСУБД.[embedded content]
Лекция 2. Классические и современные алгоритмы организации даных для двухуровневой памяти (Начало лекции в предыдущем видео, окончание в следующем)B-деревья. Инвертированные списки. Многопроходная сортировка слиянием. Стоимостная модель DAM. Понятие cache-oblivious алгоритма. Базовые cache-oblivious алгоритмы. Понятие write amplification. Фрактальные деревья. LSM деревья. Блум-фильтры. Двухуровневые деревья. BitCask: архитектура AOF, архитектура keydir.[embedded content]
Лекция 3. Кэширование как механизм повышения эффективности системы (часть 2) Алгоритм Least Recently Used, реализация в СУБД, стратегия Midpoint insertion. Понятие online-алгоритма. Проблема «аренды лыж». Paging/caching как онлайн-алгоритм. Алгоритмы LFD (Longest Forward Distance), FIFO (First In, First Out). Консервативный алгоритм. Рандомизированный алгоритм MARK.[embedded content]
Лекция 4. Архитектура СУБД Методы обзора архитектуры СУБД. Жизненный цикл запроса: получение, парсинг (вторичные ключи), оптимизация на основе правил, чтение метаданных, проверка прав доступа, построение плана выполнения запроса, оценка и оптимизация плана, выполнение, отправка ответа. Управление блокировками. Формат хранения данных на диске. Журнал.[embedded content]
Лекция 5. Транзакции Свойства транзакции ACID (Atomicity, Consistency, Isolation, Durability). Атомарность, долговечность транзакций. Применение блокировок. Степень детализации. Принципы WAL. Физическое логирование. Минимальный bookkepping. Простые оптимизации журнала. Модель кэша. Восстановление после отказа, ускорение восстановления. Логирование завершённых транзакций. Изолированность транзакций (интуиция, двухфазная блокировка, формализация, теорема 2PL, граф сериализуемости).[embedded content]
Лекция 6. Управление блокировками Захват блокировок для обеспечения консистентности и изолированности транзакций. Матрица совместимости. Иерархия локов. Понятие deadlock«а. Алгоритмы для определения и предотвращения deadlock. Update lock, upgradable lock, granularity lock, intention lock, блокировки на отсутствующие записи. «Голодание» при захвате блокировок. Проблема снижения производительности 2PL-системы при перенасыщении. Блокировки на физическом уровне.[embedded content]
Лекция 7. Оптимистичные алгоритмы управления транзакциями Определение оптимистичных алгоритмов. Принцип валидации/сертификации, три фазы выполнения транзакции. Параллельная валидация. Валидация — за и против. Timestamp ordering: запись, чтение, откат. MVCC (многоверсионное управление конкурентным выполнением транзакций, Multi Version Concurrency Control).[embedded content]
Лекция 8. Автоматизация роста распределённой системы Функция шардинга. Garage Sharding: удвоение с помощью репликации. Плохие и хорошие шард-ключи. Табличная функция. Консистеное хэширование. Guava, Sumbur. Роутинг (умный клиент, координатор, прокси, локальный прокси на каждом сервере приложений, роутинг внутри БД). Ре-шардинг. Шардинг и изменение схемы данных.[embedded content]
Лекция 9. Введение в распределённые системы. Протокол 2PC Модель распределённой системы (способы коммуникации и координации, возможные сбои). Варианты модели. Свойства распределённой системы. Дилемма двух генералов. Варианты распределённых СУБД. Протокол 2PC: модель, роль и действия координатора, фаза подготовки, варианты восстановления, период неопределённости, рабочий процесс, действия участника, crash-safe TC, записи в журнал, пример блокировки алгоритма, производительность, оптимизация.[embedded content]
Лекция 10. Репликация ДКА, алгоритмы Paxos Задача репликации журнала. Требование к распределённому алгоритму в применении к Paxos. Распределённый ДКА: подход Paxos. Компоненты Paxos. Постановка проблемы взаимоисключающего выбора. Идентификация предложений. Основы, шаги, сценарии работы Paxos. Свойство Liveness. Multi-Paxos, его задачи. Выбор LSN для предложения. Способ выбора лидера. Оптимизация PREPARE-запросов. Протокол клиента. Изменение состава кворума.[embedded content]
Лекция 11. Алгоритм RAFT Обзор RAFT. Выборы лидера (возможные состояния участников, понятие периода (эпохи)). Нормальный режим (репликация журнала). Формат журнала, шаги RAFT при отсутствии сбоев, консистентность распределённого журнала. Проверки в AppendEntries. Безопасная смена лидера. Нейтрализация бывших лидеров. Исправление расхождений журналов, коммит записей текущего периода, записи из предыдущих периодов, полные правила для коммита. Протокол работы клиента. Изменение состава кворума. Изменение конфигурации кластера. Двойной консенсус.[embedded content]
Предыдущие выпуски Технопарк: Техносфера: Подписывайтесь на youtube-канал Технопарка и Техносферы!
