Распределённые системы — различия между версиями

Версия 12:00, 4 сентября 2020

О курсе

Курс для студентов 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 репозиторий: https://github.com/osukhoroslov/hse-ds-2020

План курса

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

Лекции

Будет 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 от итоговой оценки.

Проверочные работы

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

Экзамен

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

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

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

ДЗ – средняя оценка за домашние задания

ПР — средняя оценка за проверочные работы

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

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