• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Бакалавриат 2021/2022

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

Направление: 01.03.02. Прикладная математика и информатика
Когда читается: 4-й курс, 1, 2 модуль
Формат изучения: без онлайн-курса
Охват аудитории: для своего кампуса
Язык: русский
Кредиты: 5

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

Аннотация

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

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

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

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

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

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

  • Модель распределенной системы. Время
    Модель распределенной системы: снаружи – внутри – узлы и модель передачи сообщений, снаружи – конкурентный атомарный объект. Моделирование сети, сбоев и часов. Время, виды часов (кварцевые, атомные), дрейф. Невозможность синхронизации часов без дрейфа в синхронной сети с неопределенностью при доставке сообщений. GPS и синхронизация часов, применение GPS и атомных часов в распределенных системах: TrueTime. Практика: Надежная передача по ненадежному каналу, протокол TCP. Программирование распределенных систем. Язык Go. Фреймворк для реализации распределенных алгоритмов.
  • Репликация, отказоустойчивый атомарный регистр
    Мотивирующий пример: K/V хранилище, репликация, линеаризуемость, composability, репликация read/write регистра. Наивные кворумные операции и нарушение линеаризуемости. Случай одного писателя, двухфазное чтение, аналогия со свободой от блокировок в многопоточных алгоритмах, док-во линеаризуемости. Случай многих писателей, согласованный выбор временных меток, физическое время / двухфазная запись. Дальнейшие направления: переконфигурация набора реплик, обобщение на более сложные операции, рестарты реплик. Практика: Отказы в реальных системах, failure domains. Устройство отказоустойчивого локального хранилища для key/value хранилища. B+-деревья и LSM-деревья, read/write amplification, поведение на hdd/ssd.
  • State Machine Replication, Atomic Broadcast и Consensus
    Примитив Atomic (Totally Ordered) Broadcast. AB как транспорт команд, алгоритм репликации произвольного автомата, доказательство линеаризуемости. Пример – распределенная файловая система. Нетривиальные моменты: большие автоматы, шардирование и транзакции, недетерминизм, таймауты на клиенте и семантика exactly-once. Задача Consensus, эквивалентность AB и Consensus, алгоритм сведения. Свойства safety и liveness. Практика: Распределенные файловые системы, GFS, первоначальный дизайн и его мотивация, эволюция. K/V хранилище поверх надежной файловой системы.
  • Невозможность консенсуса
    Граница n > 2f. Теорема FLP о невозможности консенсуса в асинхронной сети со сбоями для детерминированных процессов. Практические следствия. Детекторы сбоев.
  • Single-Decree Paxos
    История алгоритма: статья Part Time Parliament, греки и репликация, статья Paxos Made Simple. Общая идея алгоритма, протокол, разбор сценариев. Интуиция для фазы Prepare. Понятие выбора, контрпример для большинства аксепторов с одним значением. Доказательство корректности. FLP и сценарий лайвлока – dueling proposers. Извлечение выбранного значения. Оптимизации.
  • Multi-Paxos, RAFT
    Эффективная реализация Atomic Broadcast, общая схема RSM, репликация лога команд. Примеры применения RSM в реальных системах. Multi-Paxos: независимые инстансы консенсуса в для каждого слота лога. Выбор лидера, алгоритм Лэмпорта и его недостатки, ортогональность выбора лидера и репликации, ситуация двух лидеров. Пайплайнинг, ускорение протокола на быстром пути до одного RTT. Масштабирование фазы Prepare на суффикс лога, понятие эпохи. Правила коммита команды лога. Практика: Алгоритм RAFT: роли, термы, фазы выбора лидера и репликации Алгоритм выбора лидера в терме. Нетривиальные сценарии, правила коммита и правила голосования. Сравнение RAFT и Multi-Paxos. Разбор промышленной реализации RAFT.
  • Paxos Made Live
    Применение Multi-Paxos в промышленной системе. Выбор числа реплик. Расположение реплик в физическом мире, failure domains. Задача переконфигурации: наивный подход, служебная команда в протоколе Multi-Paxos, ɑ-метод. Read-only операции, кворумное подтверждение, использование часов и leader leases. Групповой коммит. Компактификация лога и снимки состояния. Снимки: персистентность, CoW и fork, fuzzy snapshots. Устройство лога команд: сегментирование, чексуммы, преаллокация и fsync. Практика: Консенсус как сервис: Google Chubby и Apache ZooKeeper. Применение ZK в распределенных системах: HDFS, Kafka Сrash consistency и файловые системы
  • Распределенные транзакции
    Транзакции, ACID, изоляция транзакций, сериализуемость, аномалии. Алгоритмы 2PL и SI. Двухфазный коммит, Google Percolator. Google Spanner.
  • Верификация, формальные методы
    Проблемы дизайна и верификации распределенных систем, стандартные подходы к верификации. Формальная спецификация и explicit model checking. Граф конфигураций для распределенной системы в асинхронной модели. Масштаб моделей для практической проверки и почему такого масштаба достаточно. Свойства safety и liveness для распределенных систем, линейная темпоральная логика (LTL), выражение типичных свойств для конкурентных / распределенных алгоритмов / объектов в LTL. Язык TLA+. Разбор спецификаций TLA+ для Single Decree Paxos, RAFT, протокол репликации в Kafka. Техники моделирования распределенных алгоритмов и систем на TLA+. Языки PlusCal / Promela для моделирования многопоточных алгоритмов. Пример для лок-фри структур данных. Трансляция PlusCal в TLA+. Fault Injection на примере фреймворка Jepsen: инструменты для внедрения сбоев сети / времени, различные сценарии партишенов, тестирование линеаризуемости.
  • Византийские сбои
    Византийская модель сбоев. Причины византийского поведения. Почему промышленные системы не учитывают византийские сбои. Аутентификация и цифровые подписи. Граница n > 3f для задачи консенсуса, переход через границу в византийской модели и модели с отказами узлов. Рандомизированный алгоритм Ben-Or, кворумы для византийских алгоритмов. Криптографические инструменты: хэш-функции, цифровые подписи, сертификаты, TLS
  • Practical Byzantine Fault-Tolerance
    Репликация автомата в византийском окружении. Public Key Infrastructure. Получение ответа от византийской системы. Варианты византийского поведения primary. Фазы Pre-Prepare и Prepare. Rotating primary, протокол перехода через эпоху, кворумные сертификаты. Фаза Commit. Снимки состояния автомата. Цифровые подписи и коды аутентификации сообщений. Zyzzyva. Практика: Разбор реализации PBFT.
  • Bitcoin и блокчейны
    Общая схема электронных денег, граф транзакций и цифровые подписи. Проблема double spending и лог транзакций, задача репликация лога в византийском окружении. Децентрализация и публичность, анонимность и псевдонимность, динамический набор реплик и публичные ключи в качестве адресов. Блокчейн, блоки, транзакции, gossiping. Децентрализованная лотерея – PoW, форки, стабилизация, атака 51%, finality. Мотивация майнеров и эмиссия монет. Блокчейн через линзы классических алгоритмов репликации, сравнение с PBFT. Дополнительные темы: selfish mining, шардирование и транзакции между блокчейнами (atomic swaps), анонимность и доказательства с нулевым разглашением
  • Финал
    Ретроспективная лекция. Сквозные сюжеты, важные параллели и связи, интуиция. Разбор домашних заданий.
Элементы контроля

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

  • неблокирующий Домашние задания
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.7 * Домашние задания + 0.3 * Экзамен
Список литературы

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

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

  • Diego Ongaro, & John Ousterhout. (n.d.). search of an understandable consensus algorithm (extended version). http://ramcloud.stanford.edu/raft.pdf. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.A4E9E649
  • 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
  • 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
  • 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

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

  • 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
  • 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