Сегодня мы предлагаем вашему вниманию очередную публикацию в рамках постоянной рубрики «Лекции Техносферы». В этот раз вы можете изучить материалы по курсу «Методы использования СУБД в интернет-приложениях». Цель курса — изучение топологии, многообразия и основных принципов функционирования систем хранения данных, а также алгоритмов, заложенных в основу как централизованных, так и распределённых систем, демонстрация фундаментальных компромиссов присущих тем или иным решениям. Преподаватели курса: Константин Осипов kostja, Евгений Блих bigbes, Роман Цисык.

Лекция 1. Многообразие решений для хранения данных. Модели данных классических и NoSQL систем. Модели консистентности. Семантика и допустимость овердрафта в интернет-приложениях

Достоинства и недостатки реляционной модели для работы с данными в интернете. Модель данных ключ-значение. Модель BigTable. Различия между документом и объектом. Понятие агрегата хранения. Управление схемой данных. Компромисс между консистентностью и производительностью. Конкурентный доступ к данным в клиент-серверной и полностью распределённой архитектуре. Пример графовых задач в РСУБД.

Лекция 2. Классические и современные алгоритмы организации даных для двухуровневой памяти

(Начало лекции в предыдущем видео, окончание в следующем)
B-деревья. Инвертированные списки. Многопроходная сортировка слиянием. Стоимостная модель DAM. Понятие cache-oblivious алгоритма. Базовые cache-oblivious алгоритмы. Понятие write amplification. Фрактальные деревья. LSM деревья. Блум-фильтры. Двухуровневые деревья. BitCask: архитектура AOF, архитектура keydir.

Лекция 3. Кэширование как механизм повышения эффективности системы (часть 2)

Алгоритм Least Recently Used, реализация в СУБД, стратегия Midpoint insertion. Понятие online-алгоритма. Проблема «аренды лыж». Paging/caching как онлайн-алгоритм. Алгоритмы LFD (Longest Forward Distance), FIFO (First In, First Out). Консервативный алгоритм. Рандомизированный алгоритм MARK.

Лекция 4. Архитектура СУБД

Методы обзора архитектуры СУБД. Жизненный цикл запроса: получение, парсинг (вторичные ключи), оптимизация на основе правил, чтение метаданных, проверка прав доступа, построение плана выполнения запроса, оценка и оптимизация плана, выполнение, отправка ответа. Управление блокировками. Формат хранения данных на диске. Журнал.

Лекция 5. Транзакции

Свойства транзакции ACID (Atomicity, Consistency, Isolation, Durability). Атомарность, долговечность транзакций. Применение блокировок. Степень детализации. Принципы WAL. Физическое логирование. Минимальный bookkepping. Простые оптимизации журнала. Модель кэша. Восстановление после отказа, ускорение восстановления. Логирование завершённых транзакций. Изолированность транзакций (интуиция, двухфазная блокировка, формализация, теорема 2PL, граф сериализуемости).

Лекция 6. Управление блокировками

Захват блокировок для обеспечения консистентности и изолированности транзакций. Матрица совместимости. Иерархия локов. Понятие deadlock’а. Алгоритмы для определения и предотвращения deadlock. Update lock, upgradable lock, granularity lock, intention lock, блокировки на отсутствующие записи. «Голодание» при захвате блокировок. Проблема снижения производительности 2PL-системы при перенасыщении. Блокировки на физическом уровне.

Лекция 7. Оптимистичные алгоритмы управления транзакциями

Определение оптимистичных алгоритмов. Принцип валидации/сертификации, три фазы выполнения транзакции. Параллельная валидация. Валидация — за и против. Timestamp ordering: запись, чтение, откат. MVCC (многоверсионное управление конкурентным выполнением транзакций, Multi Version Concurrency Control).

Лекция 8. Автоматизация роста распределённой системы

Функция шардинга. Garage Sharding: удвоение с помощью репликации. Плохие и хорошие шард-ключи. Табличная функция. Консистеное хэширование. Guava, Sumbur. Роутинг (умный клиент, координатор, прокси, локальный прокси на каждом сервере приложений, роутинг внутри БД). Ре-шардинг. Шардинг и изменение схемы данных.

Лекция 9. Введение в распределённые системы. Протокол 2PC

Модель распределённой системы (способы коммуникации и координации, возможные сбои). Варианты модели. Свойства распределённой системы. Дилемма двух генералов. Варианты распределённых СУБД. Протокол 2PC: модель, роль и действия координатора, фаза подготовки, варианты восстановления, период неопределённости, рабочий процесс, действия участника, crash-safe TC, записи в журнал, пример блокировки алгоритма, производительность, оптимизация.

Лекция 10. Репликация ДКА, алгоритмы Paxos

Задача репликации журнала. Требование к распределённому алгоритму в применении к Paxos. Распределённый ДКА: подход Paxos. Компоненты Paxos. Постановка проблемы взаимоисключающего выбора. Идентификация предложений. Основы, шаги, сценарии работы Paxos. Свойство Liveness. Multi-Paxos, его задачи. Выбор LSN для предложения. Способ выбора лидера. Оптимизация PREPARE-запросов. Протокол клиента. Изменение состава кворума.

Лекция 11. Алгоритм RAFT

Обзор RAFT. Выборы лидера (возможные состояния участников, понятие периода (эпохи)). Нормальный режим (репликация журнала). Формат журнала, шаги RAFT при отсутствии сбоев, консистентность распределённого журнала. Проверки в AppendEntries. Безопасная смена лидера. Нейтрализация бывших лидеров. Исправление расхождений журналов, коммит записей текущего периода, записи из предыдущих периодов, полные правила для коммита. Протокол работы клиента. Изменение состава кворума. Изменение конфигурации кластера. Двойной консенсус.

Предыдущие выпуски

Технопарк:

• 1 семестр. Web-технологии
• 1 семестр. Алгоритмы и структуры данных
• 1 семестр. С/С++
• 2 семестр. Базы данных
• 3 семестр. Проектирование высоконагруженных систем

Техносфера:

• 1 семестр. Алгоритмы интеллектуальной обработки больших объемов данных

Подписывайтесь на youtube-канал Технопарка и Техносферы!