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

← Предыдущая правка

Текущая версия от 08: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.

@@ Строка 7: / Строка 7: @@
 '''Лектор''': Алексей Неганов aka [https://t.me/bokareis @bokareis].
-'''Записи пар''': TBD
+'''Записи пар''': [https://disk.yandex.ru/d/sbYrPpVALsUsgw тут]
 '''Текущая ведомость''': TBD
@@ Строка 13: / Строка 13: @@
 == Формула оценки ==
-Оценка за курс состоит из оценки за задачи и зачета.
+Оценка за курс ставиться по следующей формуле (О<sub>Дз1</sub> + О<sub>Дз2</sub> + О<sub>Дз3</sub> + О<sub>Экз</sub>)*4/3, где максимальная отметка
+* за Дз1 1 балл
+* за Дз2 3 балла
+* за Дз3 2 балла
+* за Экз 2 балла
-Чтобы быть допущенным к зачету балл за задачи должен быть минимум 2.0
+== Домашние задания ==
+'''Задание 1'''
+Напишите систему, вычисляющую интеграл от некоторой функции.
-.0 за задачи — удовлетворительная отметка(4 балла) автоматом, можно получить "хорошо" на зачёте <br>
+Мастер (клиент) находит рабочие узлы (сервера) через IP broadcast(через UDP) — рассылает стартовое сообщение по всем адресам подсети, на которое рабочие узлы, слушающие на своих TCP портах чтобы принять запрос от мастера уже после того, как он их нашёл и знает, куда стучаться отвечают. Затем каждому рабочему узлу даётся отрезок, он вычисляет на нём интеграл и отправляет ответ мастеру. Мастер складывает ответы серверов и получает итоговый результат.
-.0 — хорошо (6 баллов) автоматом, можно получить "отлично" (8 баллов) <br>
-.0 — отлично (8 баллов) автоматом, можно получить максимум <br>
-== Домашние задания ==
+Требования:
+* если после раздачи заданий сервера становятся недоступны (выключаются / происходит разрыв сети), но хотя бы один сервер доступен, программа это детектирует, раздаёт работу доступным серверам вместо отключившихся и даёт верный ответ
+* если недоступный сервер снова появляется в сети и пытается послать ответ, это не приводит к ошибке, в частности, результат по соотв. отрезку не будет учтён дважды
+* если недоступный сервер появился в сети, мастер должен уметь присылать на него новые задачи (например, отключился какой-то ещё сервер)
-Домашние задания можно желательно сдавать на C/C++, Python, Go <br>
+Задачу прошу сделать на чистом С, пользуясь API сетевых сокетов. Лучше всего на UNIX-like системе, хотя на Windows в общем сокеты похожие.
-Допустимо на Java, C#
-'''Задание 1'''
+Обязательно показать работу программы с полной / частичной потерей пакетов, дублированием, задержками. Рекомендую утилиту tc или iptables.
-Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент.
+''Литература:''
-Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.
+* Стивенс У. Р. "Разработка сетевых приложений", гл. 2, 3, 4, 5, 7
-''Deadline: 18 октября''
+'''Deadline: 24 ноября 23:00'''
 '''Задание 2'''
-Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.
+Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой).  При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft).
-# Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
-# Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
+Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.<br>
-# Реализовать индекс как LSM-подобное дерево
+Отдельным пунктом — реализация линеаризуемого атомарный CAS
+# Система должна выполнять CRUD операции — create/read/update/delete
+# При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики
+# Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния
+# Максимальное количество реплик фиксированное.
+Задачу предпочтительнее решать на Go, Python. Допустимо на C++, C#, Java
+'''Deadline: 15 декабря 23:00'''
-''Deadline: 25 октября''
 '''Задание 3'''
-Взяв за основу индекс из задания 4:
+Нужно реализовать 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 по её локальному времени, хотя событие создания было причиной события удаления — не попадитесь в эту ловушку!
-# Реализовать поиск по префиксу
-# Реализовать поиск по wildcard с помощью k-gram
+Каждая реплика будет отдельным HTTP сервером, который позволит менять поля в множестве через запрос PATCH, в котором будет передаваться изменяемое подмножество полей как JSON. Реплики должны при наличии соединения между собой синхронизовывать состояние, при отсутствии соединения — работать автономно.
+Система должна обладать свойством strong eventual consistency.
+Вопросы:
+- физическое и логическое время
+- happens before, соисполняемость
+- broadcast и в частности causal broadcast
+- CRDT
+- CAP теорема, линеаризуемость, eventual consistency, strong eventual consistency
+'''Deadline: 18 декабря 23:00'''
+== Программа экзамена ==
-''Deadline: 10 ноября''
+.  Понятие распределённой системы.
-'''Задание 4'''
+Понятие распределённой системы и основные свойства таких систем. Применение распределённых систем для решения прикладных задач. Клиент-серверная модель. Удалённый вызов процедур.
-Взяв за основу индекс из задания 4:
+.  Модели распределённых систем.
-# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
-# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
-#* валидных в диапазоне дат
-#* появившихся в диапазоне дат
-''Deadline: 17 ноября''
+Модели сети: синхронная, асинхронная, частично синхронная. Модели сбоев: аварийные отказы, аварийные отказы с восстановлением, византийские отказы. Задачи о двух генералах и о византийских генералах.
-'''Задание 5'''
+.  Часы и упорядочивание событий.
-Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
+Физические часы и проблема монотонности календарного времени. Проблема рассинхронизации физических часов. Протокол NTP. Отношение предшествования между событиями (happens before). Логические часы: часы Лампорта, векторные часы.
-''Deadline: 24 ноября''
+.  Основы сетевых протоколов.
-'''Задание 6'''
+Основные принципы работы Интернета. Протокол IP и IP-адресация, NAT. Транспортные протоколы TCP и UDP. Работа с сетевыми сокетами в UNIX-системах на языке C.
-Реализуйте FM-index для поиска по подстроке и тесты к нему.
+.  Сетевые протоколы уровня приложения.
-''Deadline: 1 декабря''
+HTTP версий 1, 2 и 3. Построение REST API для удалённого вызова процедур. Шифрование канала с помощью TLS.
-'''Задание 7'''
+.  Алгоритмы множественной рассылки сообщений (broadcast).
-Построить индекс, что позволит давать ранжированные результаты
+Надёжная и ненадёжная рассылка сообщений. Эпидемические (gossip) протоколы рассылки.
-# по TF-IDF
+Гарантии на порядок доставки: доставка в порядке отправки (FIFO order), в порядке причинно-следственной связи между событиями (causal order), в одинаковом для всех получателей порядке (total order), в порядке отправки и одинаково для всех получателей (FIFO total order). Требования к сообщениям и их взаимосвязь с гарантиями на порядок доставки: идемпотентность, коммутативность, коммутативность одновременных.
-# согласно модели векторного пространства
-# реализовать эффективное Inexact top K ранжирование
-''Deadline: 8 декабря''
+.  Репликация
-'''Задание 8'''
+Понятие о репликации. Устойчивость к сбоям. Репликация с лидером и без лидера. Метод конечного автомата. Кворум. Согласованность в смысле чтения после записи, в смысле линеаризуемости чтения и записи, в смысле линеаризуемости атомарной операции «сравнить и записать». CAP-теорема. Согласованность в конечном счёте, сильная согласованность в конечном счёте.
-Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
+.  Задача консенсуса и протоколы достижения консенсуса.
-# используя Faiss для поиска
+Задача консенсуса и число консенсуса. FLP-теорема. Выборы лидера в системе с репликацией. Алгоритмы Paxos и Raft.
-# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
-''Deadline: 15 декабря''
+.  Распределённые транзакции.
-'''Задание 9'''
+Понятие атомарной транзакции. Изоляция транзакций.  Атомарная фиксация транзакций (commit), протокол двухфазной фиксации.
-Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
+.  Совместное редактирование документов.
-''Deadline: 22 декабря''
+Понятие бесконфликтного реплицируемого типа данных (conflict-free replicated data type). Разрешение конфликтов с применением логических часов, с частичными обновлениями и с полным состоянием. Операциональное преобразование. Разрешение конфликтов при совместном редактировании текстовых документов.
-== Литература ==
+.  Византийские протоколы.
-* Petrov, A. (2019). Database Internals: A deep dive into how distributed data systems work.
+Алгоритмы для достижения контенсуса в системах с византийскими сбоями. Атака Сивиллы и методы защиты: proof of work, proof of stake.
-* Luo, C., & Carey, M. J. (2020). LSM-based storage techniques: a survey.
-* Schütze, H., Manning, C. D., & Raghavan, P. (2008). Introduction to information retrieval.
-* Lemire, D., Ssi‐Yan‐Kai, G., & Kaser, O. (2016). Consistently faster and smaller compressed bitmaps with roaring.
-* Grabowski, S., Raniszewski, M., & Deorowicz, S. (2017). FM-index for Dummies.
-* Navarro, G., & Mäkinen, V. (2007). Compressed full-text indexes.

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

Текущая версия от 08:22, 16 декабря 2024

Содержание