Теория распределенных вычислений

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

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

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

Лекции будут выстроены в одну историю: мы начнем с выбора модели распределенной системы и очень простой задачи построения отказоустойчивой ячейки памяти, на примере которой изучим ключевые техники дизайна распределенных алгоритмов, затем перейдем к общему механизму репликации через Atomic Broadcast и изучим его связь с задачей консенсуса и ключевые результаты о невозможности, подробно разберем известный алгоритм Paxos и выведем из него Multi-Paxos или RAFT, а завершим курс византийской моделью и Bitcoin-ом, на который посмотрим через призму изученных ранее классических результатов и алгоритмов.