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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
Строка 20: Строка 20:
  
 
== Домашние задания ==
 
== Домашние задания ==
−
 
−
Домашние задания можно желательно сдавать на C/C++, Python, Go <br>
 
−
Допустимо на Java, C#
 
  
 
'''Задание 1'''
 
'''Задание 1'''
  
−
Реализуйте LSM-дерево со строковыми ключами (levelled / tiered — на выбор). Дисковые компоненты должны поддерживать бинарный или иной логарифмический поиск без полной выгрузки в RAM. Обязательны Блум-фильтры для компонент. 
+
Напишите систему, вычисляющую интеграл от некоторой функции.
−
Напишите бенчмарки для вставки, чтения по ключу, чтения короткого диапазона.
+
  
−
''Deadline: 18 октября''
+
Мастер (клиент) находит рабочие узлы (сервера) через IP broadcast — рассылает стартовое сообщение по всем адресам подсети, на которое рабочие узлы, слушающие на своих TCP портах, отвечают. Затем каждому рабочему узлу даётся отрезок, он вычисляет на нём интеграл и отправляет ответ мастеру. Мастер складывает ответы серверов и получает итоговый результат.
  
 +
Требования:
 +
* если после раздачи заданий сервера становятся недоступны (выключаются / происходит разрыв сети), но хотя бы один сервер доступен, программа это детектирует, раздаёт работу доступным серверам вместо отключившихся и даёт верный ответ
 +
* если недоступный сервер снова появляется в сети и пытается послать ответ, это не приводит к ошибке, в частности, результат по соотв. отрезку не будет учтён дважды
 +
* если недоступный сервер появился в сети, мастер должен уметь присылать на него новые задачи (например, отключился какой-то ещё сервер)
  
−
'''Задание 2'''
+
Задачу прошу сделать на чистом С, пользуясь API сетевых сокетов. Лучше всего на UNIX-like системе, хотя на Windows в общем сокеты похожие.
  
−
Постройте обратный индекс для набора текстовых документов, используя Roaring bitmaps.
+
Обязательно показать работу программы с полной / частичной потерей пакетов, дублированием, задержками. Рекомендую утилиту tc или iptables.
−
# Построить индекс (хотя бы в памяти), что позволит выдавать документы, для которых верна булева формула о вхождении слов
+
−
# Для слов применить стеммирование / лемматизацию / очистку от стоп-слов
+
−
# Реализовать индекс как LSM-подобное дерево
+
  
−
''Deadline: 25 октября''
+
''Литература:''
 +
* Стивенс У. Р. "Разработка сетевых приложений", гл. 2, 3, 4, 5, 7
  
−
'''Задание 3'''
+
'''Deadline: 17 ноября'''
  
−
Взяв за основу индекс из задания 4:
 
−
# Реализовать поиск по префиксу
 
−
# Реализовать поиск по wildcard с помощью k-gram
 
  
−
''Deadline: 10 ноября''
+
'''Задание 2'''
  
−
'''Задание 4'''
+
Вы имитируете базу данных с репликами. Клиент отправляет данные на master сервера, с мастера данные реплицируются на другие узлы. Чтение распределяется равномерно по всем репликам (т. е. запрос клиента на чтение обслуживается не мастером, а какой-то репликой).  При потере мастера реплики должны проголосовать и выбрать нового мастера среди живых узлов, используя протокол консенсуса (Raft).
  
−
Взяв за основу индекс из задания 4:
+
Если мастер оживает и на нём есть какие-то несинхронизованные данные, то они должны обработаться разумным образом, а бывший мастер — стать одной из реплик.<br>
−
# Для каждого документа задать дополнительно атрибут даты и искать по диапазону дат, а так же по булевым формулам, содержащим условия на диапазоны дат
+
Отдельным пунктом — реализация линеаризуемого атомарный CAS
−
# Пусть у документа присутствуют две даты: начала и окончания жизни (последняя может быть не задана). Реализовать поиск документов,
+
−
#* валидных в диапазоне дат
+
−
#* появившихся в диапазоне дат
+
  
−
''Deadline: 17 ноября''
+
# Система должна выполнять CRUD операции — create/read/update/delete
 +
# При чтениях не надо данные от реплики прокачивать через мастер, данные должны идти с реплики на клиента. Для этого мастер может отвечать, например, 302 Found и давать заголовок Location с адресом реплики
 +
# Учитывайте семантику методов HTTP — PUT идемпотентный (и требует ID ресурса в запросе), POST — неидемпотентный, PATCH позволяет обновить ресурс частично и зависит от текущего состояния
 +
# Максимальное количество реплик фиксированное.
  
−
'''Задание 5'''
+
'''Deadline: 1 декабря'''
  
−
Построить позиционный индекс, что позволит выполнять фразовый поиск по документам.
 
  
−
''Deadline: 24 ноября''
+
'''Задание 3'''
−
 
+
−
'''Задание 6'''
+
−
 
+
−
Реализуйте FM-index для поиска по подстроке и тесты к нему.
+
−
 
+
−
''Deadline: 1 декабря''
+
−
 
+
−
'''Задание 7'''
+
−
 
+
−
Построить индекс, что позволит давать ранжированные результаты
+
−
# по TF-IDF
+
−
# согласно модели векторного пространства
+
−
# реализовать эффективное Inexact top K ранжирование
+
−
 
+
−
''Deadline: 8 декабря''
+
−
 
+
−
'''Задание 8'''
+
−
 
+
−
Построить индекс для dense vector (similarity) search, используя BERT для получения эмбеддингов
+
−
# используя Faiss для поиска
+
−
# понижая размерность самостоятельно (randomized PCA, LSH, кластеризация, etc)
+
−
 
+
−
''Deadline: 15 декабря''
+
−
 
+
−
'''Задание 9'''
+
  
−
Реализуйте k-d tree и бенчмарк для поиска точки в k-мерном пространстве. Покажите, как меняется скорость поиска с ростом параметра k.
+
CRDT
  
−
''Deadline: 22 декабря''
+
TBD
  
 
== Литература ==
 
== Литература ==

Версия 02:03, 8 ноября 2024

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

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

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

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

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

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

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

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

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

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

Задание 1

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

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

Требования:

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

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

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

Литература:

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

Deadline: 17 ноября


Задание 2

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

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

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

Deadline: 1 декабря


Задание 3

CRDT

TBD

Литература

  • Petrov, A. (2019). Database Internals: A deep dive into how distributed data systems work.
  • 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.
Источник — «http://wiki.cs.hse.ru/index.php?title=Теория_отказоустойчивых_распределенных_систем&oldid=87825»