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

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

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

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

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

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

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

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

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

Преподаватели: Гузов Михаил Владиславович

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

Кредиты: 5

Контактные часы: 56

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

Аннотация

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, 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

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

Домашнее задание 1
Reliable Channel (Важное), необходимо реализовать надежный транспорт для коммуникациями между частями распределенной системы.
Домашнее задание 2
ABD (Важное), необходимо реализовать key-value хранилище с использованием доработанного алгоритма со 2-й лекции.
Домашнее задание 3
Single-Decree Paxos (Важное), необходимо реализовать алгоритм Синода, с 5-й лекции.
Домашнее задание 4
Multi-Paxos, необходимо реализовать key-value хранилище с использованием алгоритма Paxos с 6-й лекции.
Домашнее задание 5
Raft, необходимо реализовать key-value хранилище с использованием алгоритма Raft с 7-й лекции.
Зачёт
Зачет проводится в устной форме, на платформе Zoom или аналогичной. Студент получает билет, который включает в себя три вопроса из программы курса. Во время подготовки можно использовать любые материалы, в том числе интернет После ответа студенту могут быть заданы дополнительные вопросы по программе курса, а также предложены задачи на понимание теоретического материала. Такие задачи не требуют проведения вычислений. Оценка за зачет выставляется по 10-балльной шкале на основании общего впечатления преподавателя от ответа студента.

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

2023/2024 учебный год 2 модуль
Итог = Округление(Max(0.8 * ДЗ + 0.2 * З, 3.5 * ДЗВ)), где ДЗ — доля баллов полученная за домашние задания умноженная на 10, З — оценка за зачёт, ДЗВ – доля сданных важных задач из ДЗ.

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