Теория отказоустойчивых распределенных систем

Бакалавриат 2024/2025

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 4-й курс, 1, 2 модуль

Формат изучения: без онлайн-курса

Охват аудитории: для своего кампуса

Преподаватели: Неганов Алексей Михайлович

Язык: русский

Кредиты: 5

Полная версия программы учебной дисциплины Задать вопрос

Аннотация

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, key/value хранилищ, баз данных. Эти системы хранят десятки и сотни петабайт данных, обслуживают многие тысячи запросов в секунду и масштабируются до сотен и тысяч машин, переживая при этом отказы дисков и питания, дрейф часов, задержки и нарушения связности сети, а потому устроены невероятно сложно. Но если посмотреть сквозь все инженерные детали и сотни тысяч строк кода, то окажется, что сложность, связанную с распределенностью, можно заключить в относительно простые модели и задачи: как узлам договориться о порядке доставки сообщений в асинхронной сети, как выбрать лидера среди равноправных машин, как добавить в систему еще один сервер или обнаружить сбойную машину. Именно от решения этих задач в конечном итоге будут зависеть важнейшие характеристики всей системы: границы ее отказоустойчивости, доступность при нестабильном поведении сети и модель согласованности данных. В курсе мы рассмотрим эти задачи, исследуем ограничения, которые накладывает на них модель сети и сбоев, и потрогаем практические алгоритмы, которые применяются в известных промышленных распределенных системах.

Цель освоения дисциплины

Научить студента видеть за распределенными системами ряд фундаментальных задач, которые определяют ключевые характеристики этих систем: отказоустойчивость, масштабируемость, доступность
Изучить различные модели сети и сбоев, исследовать ограничения, которые они накладывают на решения этих задач
Изучить ключевые алгоритмы, которые используются в промышленных распределенных системах
Научить студента ориентироваться в научной области, познакомиться с ключевыми академическими работами

Планируемые результаты обучения

Знает алгоритмы, которые используются в промышленных распределенных системах
Знает подходы к верификации распределенных систем, владеет формальными методами верификации
Знает теоретические модели, ключевые задачи и результаты о невозможности
Ориентируется в корпусе ключевых академических работ

Содержание учебной дисциплины

Модель распределенной системы и часы в ней
Модели согласованности, линеаризуемый регистр (алгоритм ABD)
Replicated State Machine, сведение к задаче консенсуса
Ограничения решений задачи консенсуса, FLP теорема
The Part-Time Parliament, алгоритм синода
Алгоритм Paxos, репликация лога
Алгоритм RAFT
Масштабирование RSM, шардирование
Транзакции в распределенной системе, Serialized Snapshot Isolation, Atomic commit
Транзакции в Google Spanner
Deterministic Transactions (Calvin) и client side транзакции в Percolator
Византийский консенсус, PBFT
Bitcoin, консенсус Накамото
HotStuff

Элементы контроля

Домашнее задание 3
Домашнее задание 2
Домашнее задание 1
Экзамен

Промежуточная аттестация

2024/2025 2nd module
Оценка за курс ставиться по следующей формуле (ОДз1 + ОДз2 + ОДз3 + ОЭкз)*4/3, где максимальная отметка за Дз1 1 балл за Дз2 3 балла за Дз3 2 балла за Экз 2 балла

Программа дисциплины