Теория отказоустойчивых распределенных систем — различия между версиями
M8hew (обсуждение | вклад) (Новая страница: «== Теория отказоустойчивых распределенных систем == Осенний курс по выбору для студентов…») |
M8hew (обсуждение | вклад) |
||
| (не показано 12 промежуточных версии этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Теория отказоустойчивых распределенных систем == | == Теория отказоустойчивых распределенных систем == | ||
| − | + | Обязательный осенний курс для студентов 4 курса специализации РС ПМИ ФКН ВШЭ. | |
| − | Занятия проводятся онлайн по | + | Занятия проводятся онлайн по субботам c 9.30 в [https://us06web.zoom.us/j/9624371278?pwd=WEN6a2hvaU9pR0xpalY2T3JHV0QwUT09 zoom] |
'''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | '''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis]. | ||
| − | '''Записи пар''': | + | '''Записи пар''': [https://disk.yandex.ru/d/sbYrPpVALsUsgw тут] |
'''Текущая ведомость''': TBD | '''Текущая ведомость''': TBD | ||
| Строка 13: | Строка 13: | ||
== Формула оценки == | == Формула оценки == | ||
| − | Оценка за курс | + | Оценка за курс ставиться по следующей формуле (О<sub>Дз1</sub> + О<sub>Дз2</sub> + О<sub>Дз3</sub> + О<sub>Экз</sub>)*4/3, где максимальная отметка |
| + | * за Дз1 1 балл | ||
| + | * за Дз2 3 балла | ||
| + | * за Дз3 2 балла | ||
| + | * за Экз 2 балла | ||
| − | + | == Домашние задания == | |
| − | + | '''Задание 1''' | |
| − | + | ||
| − | + | ||
| − | + | Напишите систему, вычисляющую интеграл от некоторой функции. | |
| − | + | Мастер (клиент) находит рабочие узлы (сервера) через IP broadcast(через UDP) — рассылает стартовое сообщение по всем адресам подсети, на которое рабочие узлы, слушающие на своих TCP портах чтобы принять запрос от мастера уже после того, как он их нашёл и знает, куда стучаться отвечают. Затем каждому рабочему узлу даётся отрезок, он вычисляет на нём интеграл и отправляет ответ мастеру. Мастер складывает ответы серверов и получает итоговый результат. | |
| − | + | ||
| − | + | Требования: | |
| + | * если после раздачи заданий сервера становятся недоступны (выключаются / происходит разрыв сети), но хотя бы один сервер доступен, программа это детектирует, раздаёт работу доступным серверам вместо отключившихся и даёт верный ответ | ||
| + | * если недоступный сервер снова появляется в сети и пытается послать ответ, это не приводит к ошибке, в частности, результат по соотв. отрезку не будет учтён дважды | ||
| + | * если недоступный сервер появился в сети, мастер должен уметь присылать на него новые задачи (например, отключился какой-то ещё сервер) | ||
| − | + | Задачу прошу сделать на чистом С, пользуясь API сетевых сокетов. Лучше всего на UNIX-like системе, хотя на Windows в общем сокеты похожие. | |
| − | + | ||
| − | ''Deadline: | + | Обязательно показать работу программы с полной / частичной потерей пакетов, дублированием, задержками. Рекомендую утилиту tc или iptables. |
| + | |||
| + | ''Литература:'' | ||
| + | * Стивенс У. Р. "Разработка сетевых приложений", гл. 2, 3, 4, 5, 7 | ||
| + | |||
| + | '''Deadline: 24 ноября 23:00''' | ||
'''Задание 2''' | '''Задание 2''' | ||
| − | + | Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой). При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft). | |
| − | # | + | |
| − | # | + | Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.<br> |
| − | # | + | Отдельным пунктом — реализация линеаризуемого атомарный CAS |
| + | |||
| + | # Система должна выполнять CRUD операции — create/read/update/delete | ||
| + | # При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики | ||
| + | # Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния | ||
| + | # Максимальное количество реплик фиксированное. | ||
| + | |||
| + | Задачу предпочтительнее решать на Go, Python. Допустимо на C++, C#, Java | ||
| + | |||
| + | '''Deadline: 15 декабря 23:00''' | ||
| − | |||
'''Задание 3''' | '''Задание 3''' | ||
| − | + | Нужно реализовать 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 по её локальному времени, хотя событие создания было причиной события удаления — не попадитесь в эту ловушку! | |
| − | + | ||
| − | + | Каждая реплика будет отдельным HTTP сервером, который позволит менять поля в множестве через запрос PATCH, в котором будет передаваться изменяемое подмножество полей как JSON. Реплики должны при наличии соединения между собой синхронизовывать состояние, при отсутствии соединения — работать автономно. | |
| + | |||
| + | Система должна обладать свойством strong eventual consistency. | ||
| + | |||
| + | Вопросы: | ||
| + | - физическое и логическое время | ||
| + | - happens before, соисполняемость | ||
| + | - broadcast и в частности causal broadcast | ||
| + | - CRDT | ||
| + | - CAP теорема, линеаризуемость, eventual consistency, strong eventual consistency | ||
| + | |||
| + | '''Deadline: 18 декабря 23:00''' | ||
| + | |||
| + | == Программа экзамена == | ||
| − | + | 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. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
Текущая версия на 11:22, 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 ноября 23:00
Задание 2
Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой). При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft).
Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.
Отдельным пунктом — реализация линеаризуемого атомарный CAS
- Система должна выполнять CRUD операции — create/read/update/delete
- При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики
- Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния
- Максимальное количество реплик фиксированное.
Задачу предпочтительнее решать на Go, Python. Допустимо на C++, C#, Java
Deadline: 15 декабря 23:00
Задание 3
Нужно реализовать 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 по её локальному времени, хотя событие создания было причиной события удаления — не попадитесь в эту ловушку!
Каждая реплика будет отдельным HTTP сервером, который позволит менять поля в множестве через запрос PATCH, в котором будет передаваться изменяемое подмножество полей как JSON. Реплики должны при наличии соединения между собой синхронизовывать состояние, при отсутствии соединения — работать автономно.
Система должна обладать свойством strong eventual consistency.
Вопросы: - физическое и логическое время - happens before, соисполняемость - broadcast и в частности causal broadcast - CRDT - CAP теорема, линеаризуемость, eventual consistency, strong eventual consistency
Deadline: 18 декабря 23:00
Программа экзамена
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.
