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

Версия 11:20, 16 декабря 2024

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

Обязательный осенний курс для студентов 4 курса специализации РС ПМИ ФКН ВШЭ.

Занятия проводятся онлайн по субботам c 9.30 в zoom

Лектор: Алексей Неганов aka @bokareis.

Записи пар: тут

Текущая ведомость: TBD

Формула оценки

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

• за Дз1 1 балл
• за Дз2 3 балла
• за Дз3 2 балла
• за Экз 2 балла

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

Задание 1

Напишите систему, вычисляющую интеграл от некоторой функции.

Мастер (клиент) находит рабочие узлы (сервера) через IP broadcast(через UDP) — рассылает стартовое сообщение по всем адресам подсети, на которое рабочие узлы, слушающие на своих TCP портах чтобы принять запрос от мастера уже после того, как он их нашёл и знает, куда стучаться отвечают. Затем каждому рабочему узлу даётся отрезок, он вычисляет на нём интеграл и отправляет ответ мастеру. Мастер складывает ответы серверов и получает итоговый результат.

Требования:

• если после раздачи заданий сервера становятся недоступны (выключаются / происходит разрыв сети), но хотя бы один сервер доступен, программа это детектирует, раздаёт работу доступным серверам вместо отключившихся и даёт верный ответ
• если недоступный сервер снова появляется в сети и пытается послать ответ, это не приводит к ошибке, в частности, результат по соотв. отрезку не будет учтён дважды
• если недоступный сервер появился в сети, мастер должен уметь присылать на него новые задачи (например, отключился какой-то ещё сервер)

Задачу прошу сделать на чистом С, пользуясь API сетевых сокетов. Лучше всего на UNIX-like системе, хотя на Windows в общем сокеты похожие.

Обязательно показать работу программы с полной / частичной потерей пакетов, дублированием, задержками. Рекомендую утилиту tc или iptables.

Литература:

• Стивенс У. Р. "Разработка сетевых приложений", гл. 2, 3, 4, 5, 7

Deadline: 24 ноября

Задание 2

Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой). При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft).

Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.
Отдельным пунктом — реализация линеаризуемого атомарный CAS

1. Система должна выполнять CRUD операции — create/read/update/delete
2. При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики
3. Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния
4. Максимальное количество реплик фиксированное.

Задачу предпочтительнее решать на Go, Python. Допустимо на C++, C#, Java

Deadline: 8 декабря

Задание 3

CRDT

TBD

Программа экзамена

1. Понятие распределённой системы.

Понятие распределённой системы и основные свойства таких систем. Применение распределённых систем для решения прикладных задач. Клиент-серверная модель. Удалённый вызов процедур.

2. Модели распределённых систем.

Модели сети: синхронная, асинхронная, частично синхронная. Модели сбоев: аварийные отказы, аварийные отказы с восстановлением, византийские отказы. Задачи о двух генералах и о византийских генералах.

3. Часы и упорядочивание событий.

Физические часы и проблема монотонности календарного времени. Проблема рассинхронизации физических часов. Протокол NTP. Отношение предшествования между событиями (happens before). Логические часы: часы Лампорта, векторные часы.

4. Основы сетевых протоколов.

Основные принципы работы Интернета. Протокол IP и IP-адресация, NAT. Транспортные протоколы TCP и UDP. Работа с сетевыми сокетами в UNIX-системах на языке C.

5. Сетевые протоколы уровня приложения.

HTTP версий 1, 2 и 3. Построение REST API для удалённого вызова процедур. Шифрование канала с помощью TLS.

6. Алгоритмы множественной рассылки сообщений (broadcast).

Надёжная и ненадёжная рассылка сообщений. Эпидемические (gossip) протоколы рассылки. Гарантии на порядок доставки: доставка в порядке отправки (FIFO order), в порядке причинно-следственной связи между событиями (causal order), в одинаковом для всех получателей порядке (total order), в порядке отправки и одинаково для всех получателей (FIFO total order). Требования к сообщениям и их взаимосвязь с гарантиями на порядок доставки: идемпотентность, коммутативность, коммутативность одновременных.

7. Репликация

Понятие о репликации. Устойчивость к сбоям. Репликация с лидером и без лидера. Метод конечного автомата. Кворум. Согласованность в смысле чтения после записи, в смысле линеаризуемости чтения и записи, в смысле линеаризуемости атомарной операции «сравнить и записать». CAP-теорема. Согласованность в конечном счёте, сильная согласованность в конечном счёте.

8. Задача консенсуса и протоколы достижения консенсуса. Задача консенсуса и число консенсуса. FLP-теорема. Выборы лидера в системе с репликацией. Алгоритмы Paxos и Raft.

9. Распределённые транзакции.

Понятие атомарной транзакции. Изоляция транзакций. Атомарная фиксация транзакций (commit), протокол двухфазной фиксации.

10. Совместное редактирование документов.

Понятие бесконфликтного реплицируемого типа данных (conflict-free replicated data type). Разрешение конфликтов с применением логических часов, с частичными обновлениями и с полным состоянием. Операциональное преобразование. Разрешение конфликтов при совместном редактировании текстовых документов.

11. Византийские протоколы.

Алгоритмы для достижения контенсуса в системах с византийскими сбоями. Атака Сивиллы и методы защиты: proof of work, proof of stake.