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

2023/2024

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

Курс по выбору

Когда читается:

4-й курс, 1, 2 модуль

Преподаватель

Гузов Михаил Владиславович

Программа дисциплины

Аннотация

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, key/value хранилищ, баз данных. Эти системы хранят десятки и сотни петабайт данных, обслуживают многие тысячи запросов в секунду и масштабируются до сотен и тысяч машин, переживая при этом отказы дисков и питания, дрейф часов, задержки и нарушения связности сети, а потому устроены невероятно сложно. Но если посмотреть сквозь все инженерные детали и сотни тысяч строк кода, то окажется, что сложность, связанную с распределенностью, можно заключить в относительно простые модели и задачи: как узлам договориться о порядке доставки сообщений в асинхронной сети, как выбрать лидера среди равноправных машин, как добавить в систему еще один сервер или обнаружить сбойную машину. Именно от решения этих задач в конечном итоге будут зависеть важнейшие характеристики всей системы: границы ее отказоустойчивости, доступность при нестабильном поведении сети и модель согласованности данных. В курсе мы рассмотрим эти задачи, исследуем ограничения, которые накладывает на них модель сети и сбоев, и потрогаем практические алгоритмы, которые применяются в известных промышленных распределенных системах.

Цель освоения дисциплины

• Научить студента видеть за распределенными системами ряд фундаментальных задач, которые определяют ключевые характеристики этих систем: отказоустойчивость, масштабируемость, доступность
• Изучить различные модели сети и сбоев, исследовать ограничения, которые они накладывают на решения этих задач
• Изучить ключевые алгоритмы, которые используются в промышленных распределенных системах
• Научить студента ориентироваться в научной области, познакомиться с ключевыми академическими работами

Планируемые результаты обучения

• Знает алгоритмы, которые используются в промышленных распределенных системах
• Знает подходы к верификации распределенных систем, владеет формальными методами верификации
• Знает теоретические модели, ключевые задачи и результаты о невозможности
• Ориентируется в корпусе ключевых академических работ

Содержание учебной дисциплины

• Модель распределенной системы и часы в ней
• Модели согласованности, линеаризуемый регистр (алгоритм ABD)
• Replicated State Machine, сведение к задаче консенсуса
• Ограничения решений задачи консенсуса, FLP теорема
• The Part-Time Parliament, алгоритм синода
• Алгоритм Paxos, репликация лога
• Алгоритм RAFT
• Масштабирование RSM, шардирование
• Транзакции в распределенной системе, Serialized Snapshot Isolation, Atomic commit
• Транзакции в Google Spanner
• Deterministic Transactions (Calvin) и client side транзакции в Percolator
• Византийский консенсус, PBFT
• Bitcoin, консенсус Накамото
• HotStuff

Элементы контроля

• Домашнее задание 1
  Reliable Channel (Важное), необходимо реализовать надежный транспорт для коммуникациями между частями распределенной системы.
• Домашнее задание 2
  ABD (Важное), необходимо реализовать key-value хранилище с использованием доработанного алгоритма со 2-й лекции.
• Домашнее задание 3
  Single-Decree Paxos (Важное), необходимо реализовать алгоритм Синода, с 5-й лекции.
• Домашнее задание 4
  Multi-Paxos, необходимо реализовать key-value хранилище с использованием алгоритма Paxos с 6-й лекции.
• Домашнее задание 5
  Raft, необходимо реализовать key-value хранилище с использованием алгоритма Raft с 7-й лекции.
• Зачёт
  Зачет проводится в устной форме, на платформе Zoom или аналогичной. Студент получает билет, который включает в себя три вопроса из программы курса. Во время подготовки можно использовать любые материалы, в том числе интернет После ответа студенту могут быть заданы дополнительные вопросы по программе курса, а также предложены задачи на понимание теоретического материала. Такие задачи не требуют проведения вычислений. Оценка за зачет выставляется по 10-балльной шкале на основании общего впечатления преподавателя от ответа студента.

Промежуточная аттестация

• 2023/2024 учебный год 2 модуль
  Итог = Округление(Max(0.8 * ДЗ + 0.2 * З, 3.5 * ДЗВ)), где ДЗ — доля баллов полученная за домашние задания умноженная на 10, З — оценка за зачёт, ДЗВ – доля сданных важных задач из ДЗ.

Список литературы

Рекомендуемая основная литература

• Barbara Liskov. (n.d.). Chapter 7 From Viewstamped Replication to Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.C6D4326F
• Leslie Lamport, John Matthews, Mark Tuttle, & Yuan Yu. (2002). Specifying and Verifying Systems with TLA+. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.50C26A50
• Leslie Lamport. (2000). The part-time parliament. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.18E496B7
• Michael J Fischer, Nancy A Lynch, Michael S Paterson, & Coventry England. (1985). Impossibility of distributed consensus with one faulty process. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A8DAD60D
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.30DBEB
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.74E767E1
• Satoshi Nakamoto. (n.d.). Bitcoin: A peer-to-peer electronic cash system,” http://bitcoin.org/bitcoin.pdf. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E2C1762F
• Tushar Chandra, Robert Griesemer, & Joshua Redstone. (2007). Paxos made live: an engineering perspective. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.EC238F24
• Tushar Deepak Chandra, & Sam Toueg. (1996). Unreliable failure detectors for reliable distributed systems. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.706C61D1

Рекомендуемая дополнительная литература

• Herlihy, M. (2018). Atomic Cross-Chain Swaps. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsarx&AN=edsarx.1801.09515
• Miguel Castro, & Barbara Liskov. (1999). Practical Byzantine Fault Tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A9BB0A53
• Miguel Castro. (1999). Practical byzantine fault tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.77FEF0D
• Miguel Castro. (1999). Practical byzantine fault tolerance. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.BF8BF52B