Delivered at:: Big Data and Information Retrieval School

Course type:: Elective course

When:: 4 year, 1, 2 module

Instructors

Lipovsky, Roman

Талипов Камиль Илгизарович

Полная версия программы учебной дисциплины

Аннотация

Курс посвящен теории, лежащей в основе современных промышленных распределенных систем: файловых систем, очередей сообщений, 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 * Экзамен

Bachelor’s Programme 'Applied Mathematics and Information Science'

Theory of Fault-Tolerant Distributed Systems

Instructors

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

Аннотация

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

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

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

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

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

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

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

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