Распределённые системы

О курсе

Курс для студентов 3 курса в 1-2 модулях специализации РС.

Лектор: Сухорослов Олег Викторович

Семинарист: Новиков Глеб

Семинары проходят онлайн по пятницам (9:30-10:50) у группы 185. Ссылка на регулярную Zoom-конференцию: TODO

Семинарист: Орлов Никита

Семинары проходят на Покровке по вторникам (11:10-12:30) у группы 186.

Семинарист: Кутенин Данила

Приглашённый гость, возможный семинарист у межкампусной группы, если таковая наберётся.

Полезные ссылки

Телеграм-канал курса: https://t.me/hse_ds_course_2020

Телеграм-чат курса: https://t.me/joinchat/BgsrQlVlFUEaky--RdkyEQ

GitHub репозиторий: TODO

План курса

Может меняться

Лекции

Будет 15 лекций, примерный план лекций таков:

1. Введение. Распределенные системы. Примеры, преимущества, особенности, требования. Теоретические модели.
2. Варианты взаимодействия между процессами. Обмен сообщениями. Синхронные и асинхронные операции. Гарантии доставки, сохранение порядка. Модель запрос-ответ, RPC, идемпотентность.
3. Дизайн прикладного протокола, сериализация данных. Эволюция протокола HTTP, стиль REST. WebSockets. Bidirectional streaming в gRPC.
4. Взаимодействия в группе. Многоадресная рассылка (multicast). Гарантии и варианты реализации. Оверлейные сети. Распространение информации. Epidemic protocols, gossip, anti-entropy, rumor spreading.
5. Непрямое взаимодействие. Message queue, pubsub, DSM, tuple space.
6. Отказы. Обнаружение отказов. Свойства детектора отказов. Примеры реализации детектора. Сервис group membership.
7. Именование и поиск. Типы и варианты реализации. Поиск в локальной сети. DNS. Поиск в P2P-системах. DHT.
8. Высоконагруженные сервисы. Масштабирование. Репликация сервисов, балансировка нагрузки. Шардинг, consistent hashing и другие подходы.
9. Распределенные вычисления. Параллельная обработка запросов на кластере, закон Амдала, stragglers. Пакетная обработка данных, модель MapReduce.
10. Репликация данных. Варианты реализации (один лидер, несколько лидеров, кворумные чтения и запись). Согласованность, линеаризуемость, другие модели и гарантии.
11. Порядок событий. Физические и логические часы. Обнаружение конфликтов. Version vectors. CRDT.
12. Обзор некоторых классических распределенных алгоритмов. Mutual exclusion, consistent snapshots, leader election.
13. Безопасность в распределенных системах. Безопасный рандом. Криптография, симметричное и асимметричное шифрование. Электронные подписи, MAC. Криптографические хеш-функции. PKI, цифровые сертификаты. Примеры: Kerberos, TLS.
14. Координация и консенсус. Примеры задач, сводимых к консенсусу. Total Order Broadcast. 2PC. Задача консенсуса. FLP Impossibility. Обзор алгоритмов консенсуса, Paxos, Raft. Практические реализации, ZooKeeper.
15. Византийские отказы, BFT, блокчейн

Семинары

Семинары будут направлены на практические применения лекционного материала – разборы реально существующих систем, промышленных решений.

Все лекции и семинары будут записаны в репозитории в markdown вместе с другими материалами.

Домашние задания

Домашние задания направлены на реализацию того или иного куска лекционного/семинарского материала с уже подготовленным framework для тестирования и запуска. Основной язык нашего курса будет Python.

Планируется от 6 до 8 домашних заданий. За каждое задание вы получите оценку, среднее по всем домашним заданиям будет составлять 0.7 от итоговой оценки.

Самостоятельные работы

Планируется от 2 до 4 самостоятельных работ по материалам лекций и семинаров. О каждой из них будет сообщено за неделю до проведения. Среднее по всем самостоятельным работам будет составлять 0.3 от итоговой оценки.

Экзамен

Экзамена не будет, оценки выставляются по домашним заданиям и самостоятельным работам.

Итоговая оценка за курс

Итог = 0.7 * ДЗ + 0.3 * СР

ДЗ – средняя оценка за домашние задания СР — средняя оценка за самостоятельные работы по материалам лекций и семинаров

Округление арифметическое только в финальной оценке.

Автоматы не предусмотрены.