Название курса

All happy databases are alike; each unhappy database is unhappy in its own way

– Leo Tolstoy? , Anna Concurrenina

---

Лекции

Презентации лекций располагаются в папке lectures

• Distributed system definition
• Consistency models
• Distributed system testing [Jepsen & Maelstrom]
• CRDT (Greg)
• Consensus Intro [Reliable broadcast & FLP & Quorum systems]
• Consensus [Single and multi decree Paxos]
• Consensus [RAFT]
• Transactions
• Byzantine faults ?
• Blockchains (Илья) ?

---

Задачи

• Echo!
• Timestamp Oracle
• Broadcast
• ...

Если задача имеет несколько профилей. Успешная сдача любого, засчитывает успешную сдачу всех предыдущих (профили идут по возрастанию: 1,2,...)

---

Проектная работа (Consensus)

Для получения за курс оценки "отлично" необходимо реализовать протокол конченсуса по выбору. Подробности в папке consensus

---

Работа с репозиторием и CI

Пререквизиты:

• Unix-like операционная система (для windows - WSL 1/2 , VirtualBox, etc...)

  NB: Вы можете помочь с нативной поддержкой windows!

• Установленные docker, make, git, github cli и тулинг вашего языка программирования локально. Несмотря на то, что сборка ваших программ будет производиться в контейнере, разработка - нет (пока).

• Авторизируйтесь через github cli, это потребуется для сдачи задач: gh auth login. Следуйте инструкциям по выбору удобного способа авторизации.

Структура репозитория

├── Dockerfile
├── lecture
├── maelstrom
│   ├── doc
│   │   ├── protocol.md
│   │   ├── results.md
│   │   ├── services.md
│   │   └── workloads.md
│   ├── lib
│   │   └── maelstrom.jar
│   └── maelstrom
├── Makefile
├── README.md
└── tasks
    ├── echo
    │   ├── maelstrom.env
    │   └── README.md
    ├── task-2
    │   ├── maelstrom.env
    │   └── README.md
    └── tso
        ├── maelstrom.env
        └── README.md

Вам (студентам) можно только добавлять исходный код в папки задач. Редактирование ЛЮБЫХ иных существующих файлов СТРОГО ЗАПРЕЩЕНО, включая env файлы в папках задач.

Makefile

Репозиторий управляется через систему сборки make.

Доступные переменные:

• TASK - название задачи (соответствует имени директории задачи).

• PROG_LANG - язык программирования.

  Доступные варианты:

  • rust
  • go

• PROFILE - профиль тестирования задачи. Доступные профили можно найти в файле profiles.yml, они выступают yaml ключами.

Доступные target-ы:

• sim - собирает программу и запускает тесты задачи локально.

  Обязательные переменные:

  • TASK
  • PROG_LANG
  • PROFILE

  Пример:

  make sim TASK=echo PROG_LANG=rust PROFILE=1

• clean-jepsen - удаляет артифакты jepsen во всех директориях задач.

• submit - сдать задачу на проверку.

  Обязательные переменные:

  • TASK
  • PROG_LANG
  • PROFILE

  Пример:

  make submit TASK=echo PROG_LANG=rust PROFILE=1

• reject - отменить сдачу задачи.

  Обязательные переменные:

  • TASK
  • PROG_LANG
  • PROFILE

  Пример:

  make reject TASK=echo PROG_LANG=rust PROFILE=1

• template - создать шаблон проекта под задачу

  Обязательные переменные:

  • TASK
  • PROG_LANG

  Пример:

  make template TASK=echo PROG_LANG=rust

Сдача задач CI

После создания шаблона, вы ведёте разработку задачи в её папке на ветке main. Для того, чтобы сдать задачу необходимо вызвать make submit из ветки main, на которой вы сделали задачу. Предварительно ничего коммитить не нужно, это будет сделанно за вас. Если до этого сдача данной задачи уже производилась, данная попытка будет стёрта (будет удалён пр из репозитория организации). Также предварительно будут запущены локальные тесты, и если они успешны, будет открыто окно для комментария. В открывшемся окне укажите ваши группу и ФИО. Будет создан пр в репозиторий организации, на котором прогонятся тесты. make submit можно вызывать неограниченное число раз для любых задач. После успешного make submit вы вернётесь на ветку main. Все ваши изменения будут удалены, репозиторий вернётся в исходное состояние. Если вы хотите отменить сдачу задачи, вы можете вызвать make reject. При этом вам прийдётся заного писать код её решения в случае повторной сдачи.

NB: Помните, любой способ обмануть систему проверки, например редактируя yml файлы, карается обнулением задачи безапелляционно.

Доступные ЯП и шаблоны проектов

Для выполнение задач доступен ограниченные набор ЯП. При этом вы можете использовать ЛЮБЫЕ библиотеки. О некоторых из них будет сказано дополнительно.

Доступные ЯП:

• Rust

  Решение задачи разрабатывается в рамках одного crate-а. ЗАПРЕЩАЕТСЯ использовать кастомные сборки (наличие файла build.rs). В качестве асинхронного рантайма рекомендую использовать tokio. Для абстрагирования от работы с сырым stdin/stdout maelstrom-а существуюет библиотека maelstrom-rust-node.

• Go

  Решение задачи разрабатывается в рамках одного модуля. Для абстрагирования от работы с сырым stdin/stdout maelstrom-а существуют библиотека maelstrom-go.

NB: О добалении своего ЯП будет сказано в конце.

---

Теcтирующая система

Для тестирования задач используется система Maelstrom, построенная на базе фреймворка Jepsen.

Во время тестирования Maelstrom создаёт mock-сеть, объединяющую несколько узлов в кластер. Каждый узел в этой сети - это экземпляр вашего исполняемого файла. Узлы общаются между собой и сервиcами Maelstrom посредством простого json-протокола поверх stdin/stdout, описанного в документации.

Для симуляции запросов используются внутренние instance-ы клиентов Maelstrom. Во время тестирования они создают поток запросов, соответствующий определённому профилю.

Maelstrom будет пытаться всячески сломать вашу программу с помощью различных fault-injection-ов, например разрезая сеть на несколько кластеров или создавая таймауты при пересылке сообщений. Точный список fault-injection-ов находится в .yml файлах каждой задачи.

По результатам тестирования Maelstrom формирует папку с артифактами, включающую текстовое и визуальное описание произошедшего во время тестирования вашего кластера.

По плану курса будет отдельная лекция, посвящённая тестированию распределённых систем, в рамках которой мы поближе познакомимся с этой системой.

NB: Jepsen выводит свои логи в синтаксисе clojure, советую ознакомиться с языком.

NB: Для более тесного знакомства c Jepsen, советую начать с данного сайта

---

Добавление своего языка программирования

Если вам чем-то не понравились доступные ЯП, вы можете добавить свой! Для этого вы создаёте отдельный пр в main ветку репозитория со следующими изменениями:

• Описание default template-а для проекта выше в списке доступных ЯП.
• Установка инструментов языка в контейнер Dockerfile.
• Добавление языка во все условные (ifeq) make target-ы в Makefile.
• Установка инструменов в CI: файл ./github/workflows/сi.yml.

Критерии принятия нового языка:

• Решённая задача Echo!, демонстрирующая, что ваши изменения работают. (Перед мержом она убирается, поэтому советую добавлять её в пр отдельным коммитом).
• Работающий make template