Магистратура
2019/2020
Методы и системы обработки больших данных
Статус:
Курс по выбору (Науки о данных)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Бабенко Максим Александрович
Прогр. обучения:
Науки о данных
Язык:
русский
Кредиты:
8
Контактные часы:
56
Программа дисциплины
Аннотация
Курс посвящен архитектуре инфраструктурных распределенных систем. В курсе студенты познакомятся с такими понятиями, как: scalability, fault-tolerance, consensus, distributed storage, map-reduce, zookeeper, etc. У них будет возможность познакомиться с тем, какие проблемы стоят перед разработчиками распределённых систем и как они решаются в промышленных системах.
Планируемые результаты обучения
- Понимать типичные проблемы, решаемые с помощью распределенных систем. Быть знакомым с понятием распределенного алгоритма. Иметь представление о модели отказов в распределенных системах.
- Понимать, каким образом достигается отказоустойчивость и масштабируемость сервисов
- Иметь представление о репликации данных в распределённых системах
- Иметь представление об архитектуре систем MapReduce
Содержание учебной дисциплины
- Введение. Основы распределенных систем."Примеры распределенных систем; типичные проблемы, решаемые с помощью распределенных систем: масштабируемость, отказоустойчовость. Сложности, при проектированнии распределенных систем. Понятие распределенного алгоритма, свойства liveness и safety, оценка сложности. Модели отказов в распределенных системах. Постановка задачи mutual exclusion. Понятие времени в распределенной системе. Отношение happens-before, Lamport clock, vector clock. Алгоритм Лэмпорта. Централизованный алогоритм для mutual exclusion, его ограничения. Модели консистентности в распределенных системах. CAP-теорема."
- Архитектура распределенных stateful сервисов"Отказоустойчивость stateful сервисов. Replicated state machine. Постановка задачи консенсуса, atomic broadcast. FLP impossibility (без строгого доказательства). Алгоритм RAFT (2 лекции). Масштабируемость. Шардирование. DHT. Распределенные транзакции. Двухфазный коммит. Multi-tenant системы. Ограничение нагрузки, квотирование. Gossip-протоколы."
- Иммутабельные данные в распределенных системах"Репликация данных. Erasure кодирование для репликации. P2P системы, протокол BitTorrent."
- Архитектура систем Map-Reduce"Map-Reduce с точки зрения пользователя. Поиск узких место и оптимизация map-reduce программ. Распределенная сортировка в Map-Reduce. Планирование ресурсов в вычислительном кластере. Понятие fair-share."
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.3 * Домашняя работа 1 + 0.3 * Домашняя работа 2 + 0.4 * Экзамен
Список литературы
Рекомендуемая основная литература
- Артамонов, Д. (2009). Научно-Методические Основы Разработки Распределенных Систем Формирования Согласованных Решений. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.B9913DD4
- Задачи по математике с MATLAB & SIMULINK, Мещеряков, В. В., 2007
- Операционные системы. Т.2: Распределенные системы, сети, безопасность, Дейтел, Х. М., 2007
Рекомендуемая дополнительная литература
- Адаптивные и инвариантные алгоритмы обнаружения объектов на изображениях и их моделирование в Matlab : учебное пособие, Волков, В. Ю., 2014
- Зинкин, С. (2008). Элементы Технологии Иерархического Концептуального Моделирования И Реализации Систем И Сетей Хранения И Обработки Данных. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.58903025