Бакалавриат
2020/2021
Теория отказоустойчивых распределенных систем
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
4-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, 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), анонимность и доказательства с нулевым разглашением
- ФиналРетроспективная лекция. Сквозные сюжеты, важные параллели и связи, интуиция. Разбор домашних заданий.
Список литературы
Рекомендуемая основная литература
- 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