Компьютерные науки

Методы использования СУБД в интернет-приложениях

Программа об архитектуре современных систем хранения данных. Рассматриваются реляционные и NoSQL базы, транзакции, распределенные кластеры, теорема CAP и алгоритмы консенсуса.
Студентов 792 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание В курсе изучаются топологии и алгоритмы современных систем управления базами данных. Разбираются механизмы кэширования, классические алгоритмы организации данных и управление блокировками. Особое внимание уделяется распределенным системам, оптимистичным алгоритмам управления транзакциями, а также протоколам репликации и достижения консенсуса, таким как Paxos и RAFT. Материал адресован разработчикам высоконагруженных web-приложений и архитекторам баз данных.
Цели
  • Сформировать понимание архитектуры современных систем управления базами данных.
  • Раскрыть механизмы управления транзакциями и блокировками в СУБД.
  • Систематизировать знания об алгоритмах консенсуса в распределенных системах.
Чему я научусь?
  • Оценивать фундаментальные компромиссы при выборе систем хранения данных.
  • Анализировать алгоритмы репликации и управления распределенными транзакциями.
  • Применять методы кэширования для повышения производительности интернет-приложений.

Авторы

Блих Евгений
Блих Евгений
Осипов Константин
Осипов Константин
Цисык Роман
Цисык Роман
Чему я научусь?
  • Оценивать фундаментальные компромиссы при выборе систем хранения данных.
  • Анализировать алгоритмы репликации и управления распределенными транзакциями.
  • Применять методы кэширования для повышения производительности интернет-приложений.

Учебный план

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

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^