https://www.wikicshse.ru/index.php?action=history&feed=atom&title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BE%D1%82%D0%BA%D0%B0%D0%B7%D0%BE%D1%83%D1%81%D1%82%D0%BE%D0%B9%D1%87%D0%B8%D0%B2%D1%8B%D1%85_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BCТеория отказоустойчивых распределенных систем - История изменений2026-06-06T13:55:48ZИстория изменений этой страницы в викиMediaWiki 1.45.3https://www.wikicshse.ru/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%BE%D1%82%D0%BA%D0%B0%D0%B7%D0%BE%D1%83%D1%81%D1%82%D0%BE%D0%B9%D1%87%D0%B8%D0%B2%D1%8B%D1%85_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D1%85_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC&diff=1695&oldid=previmported>M8hew: Migrated current public revision from wiki.cs.hse.ru2024-12-16T08:22:52Z<p>Migrated current public revision from wiki.cs.hse.ru</p>
<p><b>Новая страница</b></p><div>== Теория отказоустойчивых распределенных систем ==<br />
<br />
Обязательный осенний курс для студентов 4 курса специализации РС ПМИ ФКН ВШЭ.<br />
<br />
Занятия проводятся онлайн по субботам c 9.30 в [https://us06web.zoom.us/j/9624371278?pwd=WEN6a2hvaU9pR0xpalY2T3JHV0QwUT09 zoom]<br />
<br />
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis].<br />
<br />
'''Записи пар''': [https://disk.yandex.ru/d/sbYrPpVALsUsgw тут]<br />
<br />
'''Текущая ведомость''': TBD<br />
<br />
== Формула оценки == <br />
<br />
Оценка за курс ставиться по следующей формуле (О<sub>Дз1</sub> + О<sub>Дз2</sub> + О<sub>Дз3</sub> + О<sub>Экз</sub>)*4/3, где максимальная отметка <br />
* за Дз1 1 балл<br />
* за Дз2 3 балла<br />
* за Дз3 2 балла<br />
* за Экз 2 балла<br />
<br />
== Домашние задания ==<br />
<br />
'''Задание 1'''<br />
<br />
Напишите систему, вычисляющую интеграл от некоторой функции.<br />
<br />
Мастер (клиент) находит рабочие узлы (сервера) через IP broadcast(через UDP) — рассылает стартовое сообщение по всем адресам подсети, на которое рабочие узлы, слушающие на своих TCP портах чтобы принять запрос от мастера уже после того, как он их нашёл и знает, куда стучаться отвечают. Затем каждому рабочему узлу даётся отрезок, он вычисляет на нём интеграл и отправляет ответ мастеру. Мастер складывает ответы серверов и получает итоговый результат.<br />
<br />
Требования:<br />
* если после раздачи заданий сервера становятся недоступны (выключаются / происходит разрыв сети), но хотя бы один сервер доступен, программа это детектирует, раздаёт работу доступным серверам вместо отключившихся и даёт верный ответ<br />
* если недоступный сервер снова появляется в сети и пытается послать ответ, это не приводит к ошибке, в частности, результат по соотв. отрезку не будет учтён дважды<br />
* если недоступный сервер появился в сети, мастер должен уметь присылать на него новые задачи (например, отключился какой-то ещё сервер)<br />
<br />
Задачу прошу сделать на чистом С, пользуясь API сетевых сокетов. Лучше всего на UNIX-like системе, хотя на Windows в общем сокеты похожие.<br />
<br />
Обязательно показать работу программы с полной / частичной потерей пакетов, дублированием, задержками. Рекомендую утилиту tc или iptables.<br />
<br />
''Литература:''<br />
* Стивенс У. Р. "Разработка сетевых приложений", гл. 2, 3, 4, 5, 7<br />
<br />
'''Deadline: 24 ноября 23:00'''<br />
<br />
<br />
'''Задание 2'''<br />
<br />
Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой). При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft).<br />
<br />
Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.<br><br />
Отдельным пунктом — реализация линеаризуемого атомарный CAS<br />
<br />
# Система должна выполнять CRUD операции — create/read/update/delete<br />
# При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики<br />
# Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния<br />
# Максимальное количество реплик фиксированное.<br />
<br />
Задачу предпочтительнее решать на Go, Python. Допустимо на C++, C#, Java<br />
<br />
'''Deadline: 15 декабря 23:00'''<br />
<br />
<br />
'''Задание 3'''<br />
<br />
Нужно реализовать operation-based conflict-free replicated data type как map ключ -> значение, last writer wins. (Last-Write-Wins-Element-Set). Обеспечить reliable broadcast with causal order, нельзя просто брать физические timestamps с разных реплик для определения, кто более свежий. Например, если на реплике А добавили значение, она синхронизовала это с репликой B, потом на реплике B значение удалили, то по локальному физическому времени реплики A добавление значения может быть "позже" удаления на реплике B по её локальному времени, хотя событие создания было причиной события удаления — не попадитесь в эту ловушку!<br />
<br />
Каждая реплика будет отдельным HTTP сервером, который позволит менять поля в множестве через запрос PATCH, в котором будет передаваться изменяемое подмножество полей как JSON. Реплики должны при наличии соединения между собой синхронизовывать состояние, при отсутствии соединения — работать автономно.<br />
<br />
Система должна обладать свойством strong eventual consistency.<br />
<br />
Вопросы:<br />
- физическое и логическое время<br />
- happens before, соисполняемость<br />
- broadcast и в частности causal broadcast<br />
- CRDT<br />
- CAP теорема, линеаризуемость, eventual consistency, strong eventual consistency<br />
<br />
'''Deadline: 18 декабря 23:00'''<br />
<br />
== Программа экзамена ==<br />
<br />
1. Понятие распределённой системы.<br />
<br />
Понятие распределённой системы и основные свойства таких систем. Применение распределённых систем для решения прикладных задач. Клиент-серверная модель. Удалённый вызов процедур.<br />
<br />
2. Модели распределённых систем.<br />
<br />
Модели сети: синхронная, асинхронная, частично синхронная. Модели сбоев: аварийные отказы, аварийные отказы с восстановлением, византийские отказы. Задачи о двух генералах и о византийских генералах.<br />
<br />
3. Часы и упорядочивание событий.<br />
<br />
Физические часы и проблема монотонности календарного времени. Проблема рассинхронизации физических часов. Протокол NTP. Отношение предшествования между событиями (happens before). Логические часы: часы Лампорта, векторные часы.<br />
<br />
4. Основы сетевых протоколов.<br />
<br />
Основные принципы работы Интернета. Протокол IP и IP-адресация, NAT. Транспортные протоколы TCP и UDP. Работа с сетевыми сокетами в UNIX-системах на языке C.<br />
<br />
5. Сетевые протоколы уровня приложения.<br />
<br />
HTTP версий 1, 2 и 3. Построение REST API для удалённого вызова процедур. Шифрование канала с помощью TLS.<br />
<br />
6. Алгоритмы множественной рассылки сообщений (broadcast).<br />
<br />
Надёжная и ненадёжная рассылка сообщений. Эпидемические (gossip) протоколы рассылки.<br />
Гарантии на порядок доставки: доставка в порядке отправки (FIFO order), в порядке причинно-следственной связи между событиями (causal order), в одинаковом для всех получателей порядке (total order), в порядке отправки и одинаково для всех получателей (FIFO total order). Требования к сообщениям и их взаимосвязь с гарантиями на порядок доставки: идемпотентность, коммутативность, коммутативность одновременных.<br />
<br />
7. Репликация<br />
<br />
Понятие о репликации. Устойчивость к сбоям. Репликация с лидером и без лидера. Метод конечного автомата. Кворум. Согласованность в смысле чтения после записи, в смысле линеаризуемости чтения и записи, в смысле линеаризуемости атомарной операции «сравнить и записать». CAP-теорема. Согласованность в конечном счёте, сильная согласованность в конечном счёте.<br />
<br />
8. Задача консенсуса и протоколы достижения консенсуса.<br />
Задача консенсуса и число консенсуса. FLP-теорема. Выборы лидера в системе с репликацией. Алгоритмы Paxos и Raft.<br />
<br />
9. Распределённые транзакции.<br />
<br />
Понятие атомарной транзакции. Изоляция транзакций. Атомарная фиксация транзакций (commit), протокол двухфазной фиксации.<br />
<br />
10. Совместное редактирование документов.<br />
<br />
Понятие бесконфликтного реплицируемого типа данных (conflict-free replicated data type). Разрешение конфликтов с применением логических часов, с частичными обновлениями и с полным состоянием. Операциональное преобразование. Разрешение конфликтов при совместном редактировании текстовых документов.<br />
<br />
11. Византийские протоколы.<br />
<br />
Алгоритмы для достижения контенсуса в системах с византийскими сбоями. Атака Сивиллы и методы защиты: proof of work, proof of stake.</div>imported>M8hew