Зачем нужна модель распределённой системы

Доска 1 — модель: узлы, каналы, сообщения и пользователи

Приветствую всех вас. Завершилось тягостное жаркое лето, и мы готовы погрузиться с вами в науку. Наш курс называется «Теория отказоустойчивых распределённых систем», и я начну с того, что объясню, почему я назвал его именно так: вариантов ведь было много. Он не называется, скажем, «Теория распределённых алгоритмов» — он называется «Теория распределённых систем». Почему?

Не то чтобы мне нужно вам объяснять, что современный мир без распределённых систем представить себе сложно. Вы пишете кому-то твит, отправляете сообщение, ставите лайк в Тиндере — и за всеми этими привычными вещами скрывается гигантская сложная распределённая архитектура, инфраструктура, которую вы не наблюдаете, но которая существует где-то в облаках: обрабатывает сотни тысяч запросов в секунду, двигает бешеные объёмы данных, хранит сотни тысяч петабайт. Современный мир огромен, и чтобы обслуживать весь этот поток запросов, операций и информации, нужны распределённые системы, причём самого разного типа.

Давайте я перечислю, какие распределённые системы вообще бывают. Я не ожидаю, что вы знакомы со всеми, — по ходу курса мы с ними разберёмся. Например, бывают key-value хранилища. Что это такое? По сути, гигантская хеш-таблица: система, у которой есть операция Set(k,v)\mathrm{Set}(k, v) — записать по ключу kk значение vv — и операция Get(k)\mathrm{Get}(k) — получить значение по ключу kk. Это буквально обычный unordered_map или, скорее, map, потому что в таких хранилищах упорядоченность всё-таки поддерживается. Да, они распределённые, но по модели данных это хеш-таблицы.

Какие бывают ещё системы? Бывают распределённые файловые системы: они позволяют хранить гигантские файлы, которые не помещаются на одну машину, или гигантское количество файлов, которые в одну машину тоже не помещаются. Бывают довольно странные звери — сервисы координации. Что это такое? Пока объяснить сложно: это распределённые системы, которые нужны для того, чтобы строить другие распределённые системы. Здесь можно привести очень простую аналогию: по сути это пачка атомиков. Интуиция очень содержательная, но познакомимся мы с ней чуть позже. Что ещё бывает? Бывают очереди сообщений. Наконец, бывают базы данных — какие-то таблицы, колонки, строчки, запросы. Целый зоопарк.

Я сейчас даже не говорю о том, как они устроены, — я говорю о том, что это просто разные модели данных: очереди, таблицы, файлы, атомики, хеш-таблицы. Очень много всего. Но обратите внимание: выписывая эти слова, я нигде не пишу слово «распределённые», потому что очередь можно представить себе и нераспределённой. Базы данных бывают нераспределённые — у вас, наверное, есть курс, где вы изучаете просто базы данных. Файловые системы — вот у вас просто на ноутбуке. Словари бывают просто в памяти, а бывают локальные key-value хранилища, которые обеспечивают персистентность, — LevelDB, RocksDB. У них такое же API, чуть пошире, конечно, но данные они хранят на жёстком диске, то есть ограничены ёмкостью одной машины. И всё же это тот же самый key-value storage.

Так вот, почти всё это можно представить себе без слова «распределённое», а мы будем говорить про такие системы именно как про распределённые, всё время добавляя к ним это слово. Зачем? Зачем нам делать что-то распределённым? Вопрос очень простой, но разобраться с ним нужно с самого начала. Причин несколько. Первая причина — в одну машину просто всё не помещается. Сложно представить, что весь поток данных людей со всего мира уместится на один жёсткий диск. Распределённые файловые системы, которые хранят ваши данные в облаках, хранят не гигабайты и не сотни гигабайт — они хранят сотни петабайт, тысячи петабайт данных. Нужен не один диск, не сто дисков и, может быть, даже не десятки тысяч, а сотни тысяч дисков, чтобы все эти данные уместить; нужно много машин.

Под масштабируемостью я понимаю здесь следующее: мы можем свободно добавлять новые вычислительные ресурсы и новые дисковые ёмкости, система может горизонтально расти, не испытывая при этом проблем, и продолжать адаптироваться к растущей нагрузке. Это первая причина делать что-то распределённым. Вторая причина с количеством информации не связана — в конце концов, распределённые системы не только про большие данные. У нас в конце курса будут блокчейны, и, скажем, блокчейн биткоина помещается в одну машину: он большой, там сотни гигабайт, но он умещается. Информация, которую хранит сервис координации ZooKeeper, тоже умещается в одну машину — вся целиком. Тем не менее мы хотим добавлять новые узлы.

Зачем? Потому что конкретная машина может отказать. Мы говорим про физический мир, всё это работает в физическом мире, а в физическом мире абсолютно надёжного не бывает ничего. Один жёсткий диск может работать долго, но когда вы берёте тысячу жёстких дисков, то, скорее всего, каждый день что-то ломается и вы что-то меняете. В большом кластере у вас всегда есть машины, которые сейчас находятся на обслуживании и выключены. И, конечно, система должна уметь работать в таких условиях: она должна переживать сбои отдельных узлов и скрывать их от пользователя, оставаться для пользователя доступной и адаптироваться к сбоям сама, не требуя человеческого вмешательства.

Третья причина, почему мы хотим делать что-то распределённым, снова связана с блокчейнами. Может быть, мы не хотим доверять каким-то конкретным машинам — одной машине или даже группе машин, — потому что они могут оказаться злоумышленниками. Они могут обманывать нас и другие машины, а мы хотим, чтобы наша система была к этому устойчива. Это сложная задача, сложный аспект, и говорить о нём мы будем только в последней трети курса.

Итак, мы понимаем, почему говорим про системы и почему говорим про системы распределённые. Здесь нужно сказать следующее: у вас параллельно читается курс про распределённые системы, и там у вас будут распределённая файловая система HDFS, key-value storage Cassandra и HBase, сервис координации ZooKeeper, message queue Kafka, база данных Spanner — и про что-то из этого даже я вам расскажу. Зачем же мы здесь? Дело в том, что в том курсе вы будете изучать эти распределённые системы с позиции пользователя или инженера, который выстраивает в большой компании или в маленьком стартапе инфраструктуру обработки данных. Вам нужно собирать данные от пользователей, как-то их агрегировать, обрабатывать, делать персонализацию, собирать логи — какие угодно задачи. Вы будете изучать эти системы с позиции разработчика, который оперирует ими как готовыми кубиками и склеивает их: будете изучать их API, гарантии, свойства.

Мы же собрались здесь для другого. Мы собрались потому, что хотим научиться эти системы писать. Тем, как они будут использованы, мы интересоваться не будем — мы ожидаем, что вы это либо сами понимаете, либо узнаете в параллельном месте. Здесь мы рассуждаем с позиции разработчика: нам интересно, как эти системы написать. Но задача эта, конечно, абсолютно необъятная. Написать распределённую систему за три месяца, за четыре месяца, за полгода невозможно: обычно их пишут группами из пяти-десяти крепких опытных разработчиков и пишут даже не один год. Три года, пять лет — абсолютно нормальные цифры, и писать продолжают, потому что процесс не заканчивается никогда.

Выглядит непонятно: как же мы собираемся изучать что-то настолько сложное? Ответ такой. Промышленные распределённые системы, промышленная инфраструктура действительно очень сложны, там огромное количество инженерных аспектов. Вы должны думать про кэши, про авторизацию, про конфигурации, про rate limiting — миллион вещей, без которых промышленную систему, эффективно и надёжно работающую под нагрузкой, представить нельзя. Но если мы всё это в какой-то степени отбросим и посмотрим на суть, на ядро, от которого зависят свойства таких систем, картина упрощается. Что я под этим понимаю?

Если мы посмотрим на масштабируемость — насколько система может свободно горизонтально расширяться; если мы посмотрим на отказоустойчивость — сколько сбоев узлов такая система способна пережить; если мы посмотрим на модель согласованности, которая объясняет пользователю, как нужно думать о поведении распределённой системы (эта тема, к нашему счастью, у нас ещё продолжится), — то окажется, что все эти свойства, очень важные для пользователя, по сути единственно важные для пользователя, не зависят от тех сотен тысяч или миллионов строк кода, которые в распределённых системах написаны. Эти ключевые свойства зависят от очень простых задач. Вернее, простых не в том смысле, что они легки, — наоборот, они очень сложны; они просты в постановке. Как выбрать из нескольких узлов в сети лидера? Как обнаружить сбойный узел? Как узлам договориться об общем значении, об общем выборе? Вот задачи, от которых всё зависит; формулируются они очень просто, и ровно о них мы в этом курсе будем говорить — и об алгоритмах, которые эти задачи решают, вернее, пытаются решать.

Алгоритмы мы, конечно, не будем брать с потолка — мы будем к ним приходить, исходя из архитектурных потребностей. То есть мы будем отталкиваться от распределённых систем, разбираться, как они могли бы быть устроены и какое у них должно быть хотя бы API (даже это часто уже не очевидно), разбирать их на части и постепенно понимать, что в этой части нам нужно решить такую задачу, а в этой — такую, и выяснять, как этого можно достичь. Ровно поэтому курс называется «Теория распределённых систем», а не алгоритмов: мы говорим про те алгоритмы, которые востребованы в индустрии. Мы не будем говорить про разнообразные задачи, которые математики придумывают и с удовольствием решают, — они нам не интересны. Нам интересно то, с чем вы можете столкнуться в реальности, и, конечно, покроем мы не всё. Но акцент у нас всё же будет на теории, потому что нам важно понимать эти задачи, понимать, в каких ограничениях они решаются или, наоборот, неразрешимы, и какими алгоритмами можно достичь цели.

Слово «отказоустойчивых» я уже прокомментировал. Нам важно, чтобы эти системы переживали отказы узлов, отказы сети, разделения сети — partitions. То есть всё, что в физическом мире может сломаться, мы в этом курсе будем стараться пережить. И это такой вызов вашей фантазии: когда вы пишете код, вы должны думать, а что может пойти не так и почему этот код может работать неверно. В конце концов, когда мы будем говорить про блокчейны, там можно полагать, что неверно может работать вообще всё и сомнению можно подвергать всё. Это довольно любопытно.

Так постепенно мы приходим к алгоритмам. Но прежде чем говорить об алгоритмах — а сегодня мы этого делать как раз не будем, мы будем говорить о них почти на всех следующих лекциях, но не сегодня, — нужно понять, чего нам для разговора о них не хватает. Эти алгоритмы распределённые, они работают в физическом мире, они должны переживать отказы. И очень важно понимать, как эти алгоритмы с физическим миром взаимодействуют, как они этот физический мир наблюдают. А устроен он чертовски сложно. Сегодня на лекции я про это говорить не буду — я буду говорить об этом на семинаре, покажу, что в физическом мире бывает и насколько разнообразным он бывает.

Скажем, у нас будут узлы, которые общаются по сети. А сеть — чертовски сложная штука. Серверы установлены в серверных стойках, стойки объединены коммутаторами в сложную коммутационную фабрику, дико затейливую, — картинки про это мы посмотрим. Поверх этой сети работает транспортный протокол TCP, который устроен безумно сложно и в разных местах по-разному; про него пишут вот такие книги. И, в конце концов, если вы пишете узлы, ваша распределённая система написана, скажем, на языке Go: под вами сложный процессор, под вами сложная операционная система, под вами рантайм Go, где есть собственный планировщик, сборщик мусора и много всего затейливого, о чём вы, наверное, уже что-то знаете. Думать обо всём этом, придумывая алгоритмы и ожидая, что что-то может в этом сломаться, было бы чудовищно сложно. Обычно мы так и не делаем.

Когда вы приходите в университет, с чего вы начинаете изучать программирование? С алгоритмов. Вы придумываете алгоритмы сортировки и сразу их пишете. При этом вы не изучаете перед этим, как устроены компьютер, операционная система, процессор, — вас это до определённой степени не беспокоит. Потому что у вас есть модель вычислений, как это говорят. Ваш алгоритм сортировки работает в виртуальной памяти — это гигантский массив байт, и можно обращаться к произвольной его ячейке, у вас есть операция произвольного доступа. И вам говорят: доступ к любым двум ячейкам стоит одинаково. И вы такие: ну хорошо, пошёл писать сортировку. Написали, а потом кто-то говорит: на самом деле нет, врут. Есть две соседние ячейки и две далёкие, и доступ к ним стоит по-разному, потому что в процессоре есть кэши.

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

— Пока всё понятно?

Тогда нужно начать и подумать, что же такое для нас распределённая система, как мы собираемся её себе представить. Да очень просто: давайте рисовать кружочки и стрелочки. Что такое кружочки? Это узлы системы (node) — отдельные компьютеры, на которых крутятся сетевые сервисы, способные друг с другом общаться. Как они общаются? Они пересылают друг другу сообщения (message). Давайте для простоты пока считать, что между каждой парой узлов есть просто прямой провод — канал (link), по которому эти сообщения двигаются. Вот такая нехитрая конструкция. Выглядит она, конечно, немножко проще, чем реальный мир, про который я уже упоминал. Но наша цель как раз и состоит в том, чтобы разобраться, можем ли мы заменить всю сложную реальность вот такой очень скромной, даже убогой картинкой.

Чего мы ожидаем от нашей модели, какова её цель? В отличие от алгоритмов, которые что-то сортируют и ищут, от модели мы ждём не столько операций в первую очередь, сколько гарантий. У нас есть провод, мы отправляем по нему сообщение — у нас есть операция Send(m,p)\mathrm{Send}(m, p): отправить сообщение mm узлу pp. За какое время это сообщение дойдёт? Понятно, что моментально оно дойти не может: провод длинный, есть скорость света, и быстрее отправить сообщение мы не можем. Скорее всего, мы отправляем медленнее, и интересно разобраться, почему. А есть ли верхняя граница на время доставки сообщения? И вообще, будет ли это сообщение доставлено?

Операцию Send\mathrm{Send} мы будем считать асинхронной — это как запись в сокет: мы записали в сокет, но не знаем, доставят это или нет и когда доставят. Само завершение Send\mathrm{Send} здесь ничего не означает. Рано или поздно где-то на узле-получателе должен сработать обработчик: сообщение откуда-то доставлено. Вот таких вопросов мы от нашей модели и ждём, и нам нужны ответы на эти вопросы.

Но прежде чем говорить отдельно о том, как мы моделируем узлы и как моделируем каналы, нужно разобраться, чего этой картинке не хватает — чего-то ещё очень важного. Есть деталь мира, которую опустить на самом деле невозможно, которую мы обязаны здесь нарисовать. Да, нам нужны пользователи, которые взаимодействуют с системой. В конце концов, это же не вещь в себе — нам нужны пользователи, которые задают системе какие-то запросы. Поэтому саму систему — узлы и каналы между ними — я обведу пунктиром: эта граница отделяет систему от её пользователей, которые остаются снаружи.

Давайте я буду сегодня считать, что наша система — это как раз key-value storage, который умеет выполнять команды Set(k,v)\mathrm{Set}(k, v) и Get(k)\mathrm{Get}(k). Кажется, это довольно просто и всем должно быть понятно: хеш-таблицу все в своей жизни видели. Всё остальное мы сотрём. Итак, у нас есть пользователи. Вот этот пользователь отправляет системе команду Set(k,x)\mathrm{Set}(k, x) — пишет по ключу kk значение xx. И когда-то система отвечает ему подтверждением записи, ack\mathrm{ack}: она говорит ему, что всё, я надёжно сохранила твою запись.

Что это для нас означает? Видимо, что система где-то запомнила этот xx на каком-то жёстком диске, и, скорее всего, даже не на одном, потому что мы — система, key-value хранилище — должны переживать смерть любого узла. Даже если узел, который принял и обработал эту запись, откажет, другие товарищи должны её сохранить. Как это происходит, для нас пока не важно: мы пока не строим алгоритм, об этом в следующий раз.

А пока этот пользователь отправил запрос, получил ответ и, возможно, рассказал о своей выполненной команде другому пользователю — Васе. Вася узнал о том, что запись выполнена, и пошёл читать по ключу kk: он отправляет системе Get(k)\mathrm{Get}(k). И он, видимо, ожидает, что получит в ответ от системы значение xx. Смотрите: на картинке и тут стрелочка, и тут стрелочка, — но мне сейчас важно сказать, что между этими двумя пользователями есть причинная связь: Вася начал читать уже после того, как первый пользователь получил подтверждение записи.

Взгляд клиента, каналы, синхронность и сбои

Доска 2 — снаружи система выглядит как конкурентный объект; конкурентная история операций

Доска 3 — partition и split brain; иерархия каналов, модели синхронности, safety/liveness и типы сбоев

Не знаю, сталкивались ли вы в своей жизни с распределёнными системами, работали ли вы с ними, — но в любом случае вам это очень скоро предстоит. Представьте себя на месте Пети или Васи: где-то стоит огромный кластер из ста или тысячи машин, и вы хотите в него что-то записать. Скорее всего, вы напишете очень простой код — примерно такой псевдокод, я даже не знаю, на каком это языке: client = KVStore(addr), а затем client.Set(k, x). Точку с запятой ставим — язык нас не ограничивает. И это не то чтобы похоже на отправку сообщения: это вполне себе синхронный код. Вы делаете Set, и когда вызов завершается, вы ожидаете, что операция записи в систему действительно завершилась. Конечно, вам могут вернуть и Future, но пока бог с ним — пусть операция будет синхронной.

На что я здесь намекаю? В вашем коде, в коде клиента, система выглядит не как тысяча узлов, а вот как такая переменная, на которой вы выполняете операции. И вы не единственный, кто так делает: вас таких много. Отсюда важный вывод: внутри системы удобно говорить про модель, которая называется message passing, — есть узлы, которые обмениваются друг с другом сообщениями, и это единственный их способ поговорить (на самом деле не совсем единственный, но об этом позже). А вот снаружи разумно использовать другую модель — ровно ту, которую мы изучали весь прошлый семестр, модель разделяемой памяти. Сетевой адрес addr — это как будто бы имя разделяемой переменной, и вы вызываете на ней методы как будто бы из разных потоков; просто потоки эти живут на разных машинах.

Так что для пользователей — для Пети и Васи, кажется, их так звали, — вся ваша система выглядит как некоторый конкурентный объект. Петя вызывает на нём операцию Set(k, x), а Вася — операцию Get(k), и эти операции расположены на оси времени вот так. Но вообще говоря, одновременно с этим какой-то третий клиент может делать свою запись по тому же самому ключу, но уже нового значения: Set(k, y). И тут возникает довольно содержательный вопрос: а что вообще это чтение должно вернуть, когда у нас есть две конкурирующие записи? Какая из них первая, какая вторая? Может ли клиент, который делает чтение, чего-то ожидать от системы? Это сложный вопрос, мы поговорим про него как раз через неделю, с этого и начнём.

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

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

Итого: внутри у нас message passing, снаружи — shared memory. Понятие модели согласованности, которое появится у нас из этой второй модели, как раз и было выдумано в таком контексте. Весной я об этом не рассказывал, потому что своё настоящее содержание понятие модели согласованности, linearizability, обретает именно в контексте распределённых систем, где есть разные узлы. И давайте я сразу закину на будущее: картинка с отрезочками, которые пересекаются во времени, называется History — конкурентная история.

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

Мы говорим: у нас есть пара узлов и между ними есть прямой провод. В реальности, конечно, не так: у вас сложный кластер из ста тысяч машин, объединённых дико сложной конструкцией. Почему же мы собираемся всё-таки говорить о прямом проводе? Есть у вас какие-то мысли по этому поводу?

— TCP-соединения.

Да, это верно: узлы наблюдают TCP-соединения, а TCP-соединение — это ровно абстракция прямого провода, причём надёжного провода. Так что мы можем сказать, что прямой провод как будто бы есть, и не думать обо всех промежуточных роутерах и маршрутизаторах. Реальный промышленный код будет об этом думать, и почему — мы чуть позже разберёмся, но пока мы это упрощаем.

Мы сказали, что сообщение не может долететь моментально, но нужно разобраться, за какое время оно всё-таки обязано долететь и обязано ли долететь вообще. Давайте начнём со второго вопроса, то есть со сбоев: что может случиться с сообщением? Скажу так, как пишут об этом в книгах по распределённым системам, которые я не рекомендую вам читать. Там вводят понятие Fair-loss link — честно теряющий канал. Пусть есть два узла, aa и bb, и узел aa отправляет узлу bb сообщение mm бесконечно много раз, вызывая Send(m, p). Тогда узел bb получит это сообщение тоже бесконечно много раз. Если переводить на человеческий язык, это значит, что не бывает такого момента, после которого сообщения вдруг перестанут приходить и больше никогда не дойдут. Повторяться и дублироваться они, конечно, могут.

С таким каналом нам работать неудобно, и код писать неудобно, когда любое сообщение может потеряться. Поэтому поверх такой абстракции, поверх линка, который не гарантирует ни доставку, ни доставку exactly once, мы можем построить надёжный, или совершенный, канал — Reliable link, он же Perfect link. Он гарантирует следующее: каждое отправленное сообщение будет доставлено, и ровно один раз, при условии, что оба узла живые и не умрут. Интуитивно понятно, как это сделать, — TCP в приближении так и работает. У вас есть ретраи, есть уникальные идентификаторы, получающая сторона может обнаруживать дубли и игнорировать их, а вы на месте отправителя будете отправлять сообщение до тех пор, пока вам не подтвердят, что оно получено. Представьте себе буквально TCP.

В книгах и учебниках обычно говорят: ну хорошо, давайте жить в такой модели. Мне кажется, что это ерунда и так делать нельзя, потому что о какой доставке exactly once можно говорить в реальном мире? В пределах одного TCP-соединения этого достичь можно: в конце концов, вы пишете байты в сокет, и с другой стороны их принимают ровно в таком же порядке и в таком же количестве, а сериализация потока байт в сообщения — это уже технические детали. Почему же так рассуждать всё-таки нельзя? Да потому что узел bb может взять и перезагрузиться. У вас есть надёжная абстракция надёжного канала, вы отправляете в него сообщение, узел bb даже что-то получает и начинает обрабатывать, а потом перезагружается — кто-то задел провод. Соединение рвётся, и вместе с этим разрывом пропадают все гарантии: что-то из отправленного уже не будет доставлено.

Поэтому ожидать, что всё отправленное дойдёт, — очень странная затея. Я предлагаю говорить чуть сложнее: мы рассуждаем не про физические провода, а про соединения, и соединение либо гарантирует доставку, либо скажет вам, что оно порвалось. Это уже больше похоже на реальность и, как мы увидим, ничего нам не осложнит. Как всё это сматчить с настоящим работающим кодом, мы увидим в домашних работах и обсудим на семинарах. То есть никакого обмана здесь не будет: я как раз подстраиваю нашу лекцию под ту реальность, с которой мы столкнёмся.

Хорошо, сообщение будет доставлено — или нам скажут, что непонятно, что произошло. А за какое время оно будет доставлено? Можем ли мы чего-то здесь ожидать?

— Можно ограничить задержку константой.

Это хорошо, но на самом деле это очень сильное требование. Вы говорите, что есть некоторая константа Δ\Delta и задержка при доставке любого сообщения ограничена этой самой Δ\Delta: delay(m)⩽Δ\mathrm{delay}(m) \leqslant \Delta. Хотим ли мы добавить в нашу модель такую гарантию? Я бы сказал, что идея вообще разумная: теория теорией, а вы строите в своём дата-центре какую-то хорошую сеть, которая будет работать быстро, — иначе зачем вам её строить, нужно всех уволить и заняться чем-то другим. Хорошая сеть может доставлять сообщения между парой узлов за миллисекунду. Почему бы эту миллисекунду не взять за Δ\Delta и не написать такое неравенство в нашей модели?

Я не против, чтобы мы в это верили — чтобы мы верили, что так бывает. Важно, чтобы мы не рассчитывали, что так бывает абсолютно всегда. Мы можем ожидать, что сеть работает быстро, например, в каких-то частях нашего алгоритма. Но, наверное, мы хотим, чтобы алгоритм был устойчив к тому, что эта гарантия возьмёт и нарушится, потому что физический мир мы не можем заставить работать именно так. Компьютер может сломаться, в нём может быть просто баг. Или какой-нибудь администратор ошибётся с конфигурацией сети. В одной статье Google говорится, что они уже всё зарезервировали себе в своих системах, в своей инфраструктуре, — вот только люди ошибаются, и с этим невозможно ничего сделать.

Так что давайте считать, что никакой Δ\Delta у нас всё же нет. Модель с такой константой называется синхронной, и я даже не буду писать это слово на доске, потому что таких систем не бывает. Мы будем жить в асинхронной модели, Asynchronous, в которой никакой верхней границы на время доставки сообщения нет и закладываться на неё мы не должны. Здесь важно вот что: если наш алгоритм корректно работает в таких предположениях, не ожидая ни конечного времени доставки, ни какой-то верхней границы, то он безусловно сможет работать и в реальном мире, где может быть всё хорошо, а может быть иногда плохо. Он будет к этому устойчив.

Минимальная задача алгоритма — не делать плохо. Это называется свойством Safety: система не должна уходить в плохие состояния. Например, она не должна нас обманывать: мы записали что-то, потом пошли, прочитали, а она говорит, что ничего нет, — странная ситуация, похожая на обман. Такого система делать не должна. И когда мы будем говорить о таких гарантиях алгоритма, мы будем доказывать их именно в асинхронной системе, не предполагая ничего.

Но в то же время систему, которая не врёт, построить очень легко: пусть она просто ни на что не отвечает. Обмануть нас она не сможет, но она бесполезна. Поэтому система всё-таки должна иногда делать что-то хорошее — не просто не делать плохого, а делать хорошее. Это называется свойством Liveness.

Когда мы говорим о таких свойствах, разумно немного изменить нашу модель и сказать не то, что у нас нет гарантий на время доставки, а чуть иначе. Жизнь устроена так: есть ось времени, и некоторое время мы живём в асинхронной модели, когда всё плохо, а потом в какой-то волшебный момент t∗t^* эта гарантия начинает соблюдаться. Такая модель называется уже не асинхронной, а частично синхронной — Partial Synchrony. При этом, конечно, алгоритму t∗t^* неизвестно: возможно, в какой-то момент станет хорошо, и алгоритм должен сам к этому как-то адаптироваться.

Чем меньше параметров в нашей модели, тем нам легче с ней жить. Но нам же нужно алгоритмы строить, теоремы доказывать. В асинхронной модели параметров нет вообще: ограничения на время доставки не существует. Предположений становится меньше — задача становится сложнее, а теоремы становятся проще. Доказывать что-то про Safety, то есть про то, что система не делает плохого, удобно в асинхронной модели; доказывать, что система делает что-то хорошее, удобно в частично синхронной. Так что мы можем между ними переключаться в зависимости от наших целей.

И обратите внимание: мы не говорим про какие-то доли, про 99%. Мы хотим максимально огрублять мир, потому что он сложен. Для нас 99% не существует, это для нас ничто в математике: у нас либо всегда, либо этого нет.

С сетью более-менее понятно: мы поговорили про гарантии доставки, поговорили про время — вот я его нарисовал. Есть ещё одно интересное явление, которое наша модель, вообще говоря, уже учитывает неявно, но в реальности оно интересно само по себе. Это Partition — когда сеть раскалывает кластер на две части. Связность в пределах одной части сохраняется: вот эти три узла могут свободно друг с другом говорить, и в этой части тоже. Но линки, которые пересекают Partition, перестают работать.

В итоге ваша система раскалывается на две части, и хуже того — она раскалывает ещё и клиентов. Вот есть два клиента, которые работают с одной половиной системы, и есть какие-то клиенты, которых я не нарисовал, работающие со второй половиной. Раньше у вас была одна система, а теперь стало две. И будет очень скверно, если эти две системы начнут работать независимо. Сама ситуация раскола называется Partition, а ситуация, когда в случае Partition система начинает работать независимо в двух частях, называется Split Brain. Наверное, мы не хотим, чтобы наши системы работали вот так, и это будет всегда очень интересный аспект в наших задачах.

Про сеть закончили, говорим про отдельные узлы. Как мы их моделируем? Устроены они сложно, мы это знаем, мы такое уже писали прошлой весной и этой весной. Видимо, сейчас мы хотим всю эту сложность упростить. Давайте скажем, что каждый узел — это автомат, или актор, который работает однопоточно: он принимает сообщения из сети и вызывает какой-то обработчик. Когда обработчик вызван, узел меняет своё внутреннее состояние, переходит в новое и, возможно, отвечает в сеть какими-то новыми сообщениями. Никакого параллелизма внутри нет.

Насколько это разумно? Я вас на самом деле всему научил, чтобы ответить на этот вопрос, и теперь могу объяснить. Конечно же, реальные программы, реальные узлы распределённых систем и наш код в домашних работах будут многопоточными, точнее — многофайберными. Там будут файберы, Future, Promise — всё, что мы делали; там будет concurrency. Но в домашних работах в весеннем семестре мы намеренно отделили все эти файберы и Future от потоков: ни Fiber, ни Future про потоки не знали, они знали про executor’ы, про какие-то странные сервисы, которые умеют запускать задачи.

Так вот, можно представить себе, что реальная программа исполняется на пуле потоков, а можно представить, что все эти Fiber и Future бегут на executor’е, который называется ManualExecutor и просто по пинку выполняет очередную задачу. Он может быть однопоточным, он может быть абсолютно детерминированным. Вы можете писать конкурентный код, который будет исполняться в одном потоке, — собственно, так мы и писали наши самые простые Fiber в прошлом семестре. Так что формально Fiber и Future вполне вписываются в модель, где вызываются callbacks. Мы и об этом уже говорили: всё в конце концов построено на event loop’ах и callbacks. Так что то, что видит разработчик, — это не то же самое, что происходит на уровне этой картинки.

Итак, в теоремах мы рассуждаем про узлы как про очень простые однопоточные акторы. Что с ними плохого может происходить, какие сбои они способны испытывать на себе? Про сбои и потери на линках мы поговорили, теперь про узлы. Самый простой случай — когда узел просто взрывается. Не то что взрывается физически — у него отказал диск; то есть он просто выключается и больше никогда не включается. Это самый простой отказ, который мы хотим переживать. Чуть более сложное — это рестарты, рестарты плюс крэши: узел может перезагружаться. И когда мы говорим про рестарты, то должны сразу добавить к модели узла какое-то персистентное состояние.

Время и часы в распределённой системе

Доска 4 — интерфейс часов и два применения меток: ordering (враг — skew) и timeout (враг — drift)

Доска 5 — оценка задержки по round-trip и модель для нижней оценки

Доска 6 — конструкция shift: неразличимые исполнения и нижняя оценка ε ⩾ u/2

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

Итак, сеть и узлы мы разобрали, про клиентов тоже поговорили коротко. Что осталось? Какой ещё аспект реальности мы не учли? Про клиентов важно не то, как они устроены — клиенты это тоже узлы, в конце концов, — а то, как они видят систему; это модель согласованности, те самые истории и картинки. Про это я пока рассказал коротко, подробно будет в следующий раз.

Ресурсы? Память, конечная и так далее. Я не думаю, что алгоритм может исчерпать бесконечную память, это сложно себе представить: вы же не думаете про ограничение памяти, когда говорите про алгоритмы сортировки. Жёсткий диск и процессор у нас есть, мы всё это в каком-то виде уже учли.

С чем ещё из физического мира взаимодействуют узлы? С каким понятием — очень важным и очень хитрым, на самом деле? У нас есть сеть, у нас есть ресурсы для исполнения, процессор, грубо говоря. Представьте себе модель акторов, или какие-нибудь автоматы с коллбэками, или TCP-соединение — это всё вы знаете. Что ещё знают узлы, знают программы про физический мир? Они знают про время.

Мы предполагаем, что время есть: есть какая-то общая ось времени, и любое событие, которое происходит в нашей системе, имеет на этой оси какую-то координату. Беда в том, что мы ничего про это не знаем — доступа ко времени мы не имеем. Что у нас есть вместо времени? У нас есть часы. В теории часы для нас — это функция c(t)→vc(t) \to v, которая по времени возвращает нам некоторое значение. В идеале она возвращает c(t)=tc(t) = t; в идеале она к тому же дискретна, но такие часы мы и хотели бы иметь. В коде, конечно же, у нас не функция с аргументом, у нас просто Now() без аргументов, и мы получаем из неё только это самое значение.

А в физическом мире у нас некоторый часовой механизм, то есть некоторый физический процесс, который считает какие-то колебания. У вас есть часы с кукушкой и маятником; у вас есть завод пружинных механических часов, который двигает какие-то шестерёнки; у вас есть кварцевые часы, где батарейка и кристалл кварца, который вибрирует около 32 тысяч раз в секунду; у вас есть атомные часы, про которые мы сейчас поговорим. Важно, что это объекты физического мира, и, как всё в физическом мире, эти объекты несовершенны — они совсем не тождественные функции. И чтобы разобраться, в чём их несовершенство и как это касается нас, нужно сначала понять, а как, собственно, мы собираемся использовать время в алгоритмах.

У нас есть Now(), оно возвращает нам временные метки, timestamps, текущее время. Пусть у нас есть t1t_1 и t2t_2. Какие две фундаментально разные операции мы можем с ними делать? Мы можем сравнить два показания времени, t1<t2t_1 < t_2, и мы можем вычесть из большего меньшее, t2−t1t_2 - t_1. Какой-то обман в этом уже есть, но ладно.

Короче говоря, мы можем сравнивать мгновенные показания времени, а можем замерять интервалы времени. Давайте подумаем, зачем мы это делаем, и начнём со второго: зачем мы вычитаем? Зачем в распределённой системе замерять интервалы времени?

— Таймауты.

Таймауты, да. Таймауты устанавливать. А зачем устанавливать таймауты, можно как-то обобщить? Зачем они нам нужны в наших задачах? Это называется failure detection — обнаруживать сбои.

Например, вы клиент, вы отправляете запрос в систему. Хотя вы и не наблюдаете вот эту распределённость, в конечном итоге ваш запрос приземляется на какую-то — пусть случайную — машину в этом кластере. Допустим, вы отправили запрос и ждёте; клиентская библиотека ждёт, ждёт, проходит пять секунд, вам не отвечают, вы беспокоитесь. Может быть, узел, на который вы приземлились, вообще умер и ничего вам не ответит — нужно пойти к другому узлу. Вот это failure detection.

Или ваша система выбирает среди пяти узлов какой-то узел, который мы называем лидером и который будет координировать остальных. И этот лидер, чтобы напоминать о себе, что он вообще ещё жив, отправляет другим узлам специальные сообщения — heartbeats, скажем, раз в пять секунд. И вот вы сидите, ждёте, а вам ничего не приходит; и вы думаете: наверное, с лидером что-то случилось, наверное, нужно выбрать другого. В обоих случаях вы используете timeout, то есть читаете какие-то показания часов и вычитаете их друг из друга.

Сравнение времени чуть сложнее, и про это мы как раз будем говорить в следующую лекцию — она почти целиком этому будет посвящена. Мгновенные показания времени мы сравниваем для того, чтобы упорядочивать события, и это второе применение временных меток: t1<t2t_1 < t_2 даёт нам ordering. Вернёмся на этот рисунок. Пусть был Петя, он сделал запись xx, получил подтверждение и рассказал об этом Васе, а Вася вместо того, чтобы читать, сделал новую запись: было xx, стало yy. Запись xx безусловно случилась до записи yy. И мы ожидаем, что если потом пойти в систему и спросить, что сейчас находится по ключу kk в нашей хеш-таблице, нам вернут, конечно, yy. Для этого системе нужно понять, что в неё записали xx, записали yy, и yy — более свежая запись.

Как этого можно было бы надёжно достичь? Пусть узел, который получил запись xx, присвоил ей временную метку — показание локальных часов. Ось времени я сотру, всё равно мы её не видим. Итак, какой-то узел получил запись xx и решил, что текущее время 12:00; отлично, пусть запись xx будет аннотирована этим timestamp.

Потом запись завершилась, клиент отправил другому клиенту уведомление, тот сделал запись yy, эта запись приземлилась на другую машину, и другая машина присвоила ей временную метку 11:59. Почему? Потому что часы у них просто показывали разное время. Получилось, что для системы запись xx была позже, чем запись yy — а система про эту коммуникацию между клиентами ничего не знает, она происходит за её пределами. Беда.

Итого, враг для ordering’а — это то, что называется skew, рассинхронизированные часы. Часы показывают разное время на разных узлах: в одно и то же физическое время дают нам разные timestamp’ы. И тогда вот это применение часов ломается. А в случае failure detection нам вредит другое явление, которое называется дрейфом. У нас есть идеальная функция времени, идеальные часы, которые по tt возвращают tt — производная единичная. Дрейф о том, что производная на самом деле не единичная: часы могут тикать иногда быстрее, иногда медленнее, чем идёт физическое время, чем идут идеальные часы. Не так-то просто объяснить, как именно это нам повредит — это тема не самой ранней лекции, мы через два месяца об этом поговорим.

Но пока можно отметить, что физические часы этому явлению очень подвержены, и даже кварцевые часы здесь очень плохи. Есть такой параметр, который производитель часового механизма печатает на упаковке: parts per million, миллионные доли. Для кварцевых часов это порядка 20 ppm. То есть за одну секунду часы могут отклониться от идеального хода на 20 микросекунд, а значит, за сутки они накопят примерно 1,7 секунды ошибки. И это кварцевые часы; у механических всё ещё хуже.

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

Это последняя деталь нашей модели, и оставшееся время я потрачу на то, есть ли здесь какая-то надежда: можно ли часы синхронизировать. Дрейф — это уже беда, с ним всё. А можно ли как-то свести часы на разных узлах к одним и тем же показаниям? Причём нам не особенно важно, чтобы они показывали физическое время — нам достаточно, чтобы они показывали одно и то же. Можем ли мы этого добиться?

Представим себе очень простой мир, где есть два узла, и n1n_1 хочет как-то свести свои часы с часами n2n_2. Что он может сделать? Он может отправить сообщение узлу n2n_2 и спросить: который час? Это был момент времени t1t_1. Ответ он получит в момент t2t_2, а в ответе n2n_2 пришлёт ему значение t3t_3 — показание своих часов в момент получения запроса.

Чего не хватает узлу n1n_1 для счастья? Видимо, не хватает задержки этого ответного сообщения, вот этого dd. Как мы можем его аппроксимировать? Какой-нибудь best effort можно предложить?

— Посмотреть на среднюю задержку в сети.

— Да нет, вот прямо сейчас: мы уже отправили сообщение и уже получили ответ. Возьмём d≈(t2−t1)/2d \approx (t_2 - t_1)/2 — лучше, чем ничего. Предположение здесь такое, что сеть у нас работает симметрично.

Давайте теперь покажем, что на самом деле это не такая уж тупая идея — что сильно лучше мы и не сможем. Пусть кто-нибудь пришёл и сказал нам, что у него есть алгоритм синхронизации часов. Сначала наложим некоторые ограничения на мир. Предположим, что любое сообщение доставляется в промежутке delay(m)∈[Δ−u, Δ]\mathrm{delay}(m) \in [\Delta - u,\ \Delta], где Δ\Delta — верхняя граница времени доставки сообщения, а uu — неопределённость, uncertainty. То есть сеть работает не совсем за константное время, она позволяет себе некоторый интервал.

Почему здесь написано не [a,b][a, b], а именно Δ−u\Delta - u? Потому что, видимо, что-то в наших рассуждениях будет зависеть от этого uu. И мы предполагаем, что дрейфа вообще нет, что часы не дрейфуют.

Что вообще значит в такой модели синхронизировать часы, которые не дрейфуют? Узлы должны выбрать себе к своим часам какую-то аддитивную поправку: синхронизированные часы на процессе ii в момент времени tt будут показывать sci(t)=ci(t)+oisc_i(t) = c_i(t) + o_i — показание физических часов плюс поправка. И пусть кто-то принёс нам алгоритм, который гарантирует, что через некоторое время поправки будут подобраны так, что показания синхронизированных часов на любых двух узлах отличаются друг от друга не более чем на некоторое ε\varepsilon: ∣sci(t)−scj(t)∣⩽ε|sc_i(t) - sc_j(t)| \leqslant \varepsilon. Насколько маленьким может быть это ε\varepsilon?

Рассуждения здесь довольно симпатичные, и они мне полезны, потому что показывают даже не столько конкретный результат, который мы сейчас получим, сколько общую технику, которую мы будем использовать и дальше. Мы сейчас будем играть за adversary, которому дали неизвестный алгоритм, и он будет портить ему жизнь. Мы построим два исполнения. Мы adversary, мы управляем миром: мы управляем сетью в заданных пределах, управляем локальными часами, можем подбирать их начальные показания. Два исполнения, которые мы построим, будут, во-первых, различны — в них узлы обязаны подбирать разные поправки; а с другой стороны, алгоритмы на узлах не смогут эти два исполнения отличить друг от друга, а потому выберут одинаковые поправки. Вот на этой коллизии и построится нижняя оценка.

Итак, рассматриваем два узла, n1n_1 и n2n_2. Мы ничего не знаем об алгоритме, но управляем сетью и говорим: пусть в сторону от n1n_1 к n2n_2 сообщения идут долго, максимально долго, насколько могут — за Δ\Delta. А в обратную сторону — максимально быстро, насколько нам это позволено, за Δ−u\Delta - u. Видите, сеть у нас уже асимметричная. Алгоритм работает, узлы синхронизируют часы, молодец. Назовём это исполнение α\alpha.

А теперь мы делаем операцию, которая называется сдвигом, shift. Все события, которые происходили на узле n1n_1, мы оставляем в тех же местах, но переворачиваем сеть: теперь в одну сторону сообщение летит очень быстро, за Δ−u\Delta - u, а в обратную — очень медленно, за Δ\Delta. Что произошло? Для узла n1n_1 не произошло вообще ничего, он не чувствует разницы: времена событий на n1n_1 остались те же. А узел n2n_2 чувствует разницу или нет? Для него событие получения сообщения съехало назад, причём ровно на uu.

И вообще-то он не тупой, он способен это понять: он посмотрит на свои часы. В первом исполнении он получил сообщение в 12:00, а здесь получает его в 11:59. Пока это не похоже на заявленную мной неразличимость.

Как же её добиться? Назовём первое исполнение α\alpha, а второе — α′\alpha'. В исполнении α′\alpha' мы перевернём сеть и одновременно переведём часы второго узла на +u+u: c2′(t)=c2(t)+uc'_2(t) = c_2(t) + u. Утверждается, что теперь, хотя во времени всё съехало, у n2n_2 нет никакой возможности это почувствовать, потому что времени он всё равно не знает — он знает только то, что ему показывают часы, а часы показывают ему то же самое. То есть исполнения α\alpha и α′\alpha' неразличимы для обоих узлов. Это, собственно, всё, что нам требовалось.

Смотрите, что мы получили. Мы запустили алгоритм в α\alpha и в α′\alpha', он синхронизировал часы. В обоих случаях синхронизированные часы узла n1n_1 не отличаются, потому что у него всё происходило одинаково. Посмотрим на синхронизированные часы первого узла — штрихованные или нет, неважно — в какой-то будущий момент t∗t^*, когда всё уже сошлось: они показывают какое-то время sc1(t∗)sc_1(t^*). Алгоритм обещает, что синхронизированные часы второго узла попадают в интервал от sc1(t∗)−εsc_1(t^*) - \varepsilon до sc1(t∗)+εsc_1(t^*) + \varepsilon, и это должно быть верно в обоих исполнениях.

А теперь подумаем, как устроены синхронизированные часы узла n2n_2. Алгоритм не чувствует разницы между двумя исполнениями, а значит, выберет одну и ту же аддитивную поправку o2o_2. Но физические часы второго узла в α′\alpha' сдвинуты на +u+u, поэтому sc2′(t∗)=sc2(t∗)+usc'_2(t^*) = sc_2(t^*) + u. Оба эти показания обязаны лежать в интервале шириной 2ε2\varepsilon вокруг sc1(t∗)sc_1(t^*), а различаются они ровно на uu. Следовательно, 2ε⩾u2\varepsilon \geqslant u, то есть ε⩾u/2\varepsilon \geqslant u/2. Никакой алгоритм синхронизации часов не может гарантировать расхождение меньше половины сетевой неопределённости — а значит, наша наивная оценка d≈(t2−t1)/2d \approx (t_2 - t_1)/2 по порядку величины оптимальна.

GPS и навигационные уравнения

Доска 7 — трилатерация и навигационные уравнения GPS

Вернёмся к нашей конструкции. Вместе с событиями на втором узле сдвинулись и его часы: теперь поправка задаётся как c2′(t)=c2(t)+uc'_2(t) = c_2(t) + u. Значит, синхронизированные показания часов узла n2n_2 в первом и во втором исполнении обязаны отличаться друг от друга ровно на uu — именно на столько, на сколько мы сдвинули всю его локальную картину мира. При этом по условию точности алгоритма и те, и другие показания должны отличаться от истинного значения не более чем на ε\varepsilon. Я не выписываю неравенства целиком, потому что это нудно, но если становится непонятно — скажите.

Итак, я утверждаю, что в отрезок длины 2ε2\varepsilon должен поместиться отрезок длины uu: ведь именно настолько отличаются показания часов второго узла в двух исполнениях. Отсюда 2ε⩾u2\varepsilon \geqslant u, то есть ε⩾u/2\varepsilon \geqslant u/2. Это просто подтверждение той интуиции, с которой мы начинали: сеть может быть асимметричной, и всё, что мы умеем, — это более-менее поделить пополам измеренное время round-trip, d≈(t2−t1)/2d \approx (t_2 - t_1)/2, что мы и делали. На доске эта величина так и подписана — uncertainty, неопределённость. Лучше мы сделать не можем.

В случае nn узлов оценка чуть-чуть меняется и становится немного печальнее: ε⩾(1−1n)u\varepsilon \geqslant \left(1 - \frac{1}{n}\right) u.

— А какая разница между этими двумя картинками?

Это просто картинка, которая иллюстрирует, как мы меняем поведение мира. Как работает сам алгоритм, я понятия не имею: он может работать произвольным образом, там просто какой-то обмен сообщениями. Я говорю лишь о том, как мы, adversary, доставляем эти сообщения и что показываем в часах. И утверждаю: если мы выполним операцию shift, алгоритм не сможет отличить два исполнения друг от друга. На узле n1n_1 вообще ничего не поменялось, мы его не трогали. На узле n2n_2 события сместились, часы сместились, нужная поправка стала другой — но разницы алгоритм не чувствует: для него ось немного съехала, и часы съехали в другую сторону, и как будто бы всё то же самое.

— Но мы же…

Ещё раз: здесь нарисовано не исполнение алгоритма, здесь нарисовано, как ведёт себя сеть.

— Почему она ведёт себя именно так? Почему мы не можем…

Потому что это наш произвол. Нам дали алгоритм и сказали: вот есть такая гарантия, которая соблюдается при соблюдении таких-то ограничений. Мы, соблюдая эти ограничения, выяснили, что ε\varepsilon ограничена снизу. Вот и всё.

— А от чего зависит алгоритм?

Алгоритм сам объявляет нам, что часы синхронизированы. Мы дождались момента, когда он завершился, посмотрели на часы — и они должны оказаться в этом интервале. Но они отличаются на uu, поэтому — всё очень плохо.

Почему плохо — нужно понять. Потому что даже если у нас есть самые точные часы, которые не дрейфуют (хотя таких не бывает), всё, что мы можем сделать, — это замерить время round-trip. Этим наши возможности ограничены. Мы не можем оценить асимметрию сети: чтобы оценивать асимметрию, нам нужно иметь синхронизированные часы, а чтобы иметь синхронизированные часы, нужно оценить асимметрию. И мы проиграли. Но иногда так бывает.

Сейчас я расскажу довольно странные вещи, про которые неочевидно, как они нам помогут, — но они помогут, и даже в первой домашней работе уже встретятся. Беда с часами состоит в том, что мы не можем оценить асимметрию в сети; оценить время round-trip мы можем. А может быть и так, что никакого round-trip у нас нет: коммуникация односторонняя, зато время доставки сообщения мы знаем довольно неплохо. Поэтому давайте забудем про распределённые системы на пять минут и поговорим про GPS — систему глобального позиционирования. Казалось бы, позиционирование в пространстве к нашему курсу не относится вообще никак, но относится оно довольно содержательно, и мы это скоро увидим.

Про что GPS? Вы находитесь где-то на плоской доске, вы должны знать, где вы находитесь, но не знаете — вы можете быть где угодно. И вот вам дают подсказку: есть точка x1x_1, и вы находитесь на расстоянии d1d_1 от неё. Вы понимаете, что находитесь на такой окружности — уже лучше. Дальше вам дают вторую подсказку: есть точка x2x_2, и вы на расстоянии d2d_2 от неё. Теперь у вас две альтернативы: одна здесь, другая здесь, и нужно сделать окончательный выбор. Для этого вам дают третью точку x3x_3 и расстояние d3d_3 — на рисунке получилась некоторая ерунда, но, наверное, вы поверите, что это была окружность с радиусом, хотя и не похоже.

Вот такой нехитрый способ найти себя на белой доске, в плоскости. И примерно так — очень грубо и совершенно неверно — работает GPS. Что такое точка xix_i? Это спутник, который летает: активных спутников GPS двадцать четыре, они летают по шести орбитам и что-то вам отправляют, а вы стоите здесь с ресивером и ждёте, когда что-нибудь получите. Сейчас мы будем разбираться, чего именно вы ждёте. В плоскости вам, кажется, достаточно трёх точек, чтобы себя найти, а GPS нужно четыре спутника, чтобы позиционировать вас в пространстве. Почему?

Трёхмерность здесь ни при чём, потому что вы же находитесь на сфере — у вас уже есть четвёртая поверхность-ограничение, это сама Земля; строго говоря, не сфера, но очень на неё похоже. И, скорее всего, вы не ошибётесь: у вас будут две альтернативы, одна из которых летает в космосе с огромной скоростью, а вторая стоит на Земле, так что выбрать несложно. Значит, четвёртый спутник нужен не потому, что мы живём в трёхмерном мире. Всё работает сложнее. В самом деле, откуда вы знаете расстояние до спутника? Откуда ресивер это знает? Сложно представить, что он настолько умный.

Поэтому следующий шаг немного усложним, добавим реализма. Вы вышли в лодке в туман, ночью, рыбачить. У вас есть карта и часы. На карте отмечены три маяка: вы знаете, где они находятся, но не знаете, где находитесь сами. Зато вы знаете, что маяки раз в пять минут издают пронзительный, уникальный гул — включается сирена, и расписание вам известно. Как вам это поможет?

— Измерять время между звуками маяков?

Нет. Наступают очередные пять минут, вы берёте часы и ждёте, пока услышите первый маяк. Замеряете дельту — сколько потребовалось звуку, чтобы достичь вас. И ваша система уравнений становится такой: ∣x−xi∣=ϑ Δti|x - x_i| = \vartheta\,\Delta t_i, где xix_i — известные координаты маяков, ϑ\vartheta — скорость сигнала (в аналогии с маяками это скорость звука, для GPS — скорость света), а Δti\Delta t_i — время, которое потребовалось сигналу сирены, чтобы до вас дойти.

— А это действительно так работает?

Надеюсь, что да; на абсолютную точность я не претендую. Вообще про GPS читают отдельный курс, если вы об этом. Я сейчас пытаюсь очень компактно объяснить, как это примерно работает, и веду к конкретной цели.

Но это всё равно не так. Где здесь обман? Даже если мы стоим на месте и даже если всё происходит точно по расписанию, мы на самом деле меряем не Δti\Delta t_i, а Δt~i\tilde{\Delta t}_i — дельту с волной, потому что она неправильная. На самом деле Δt~i=Δti+δ\tilde{\Delta t}_i = \Delta t_i + \delta, где δ\delta — сдвиг наших часов: наши часы показывают не совсем правильное время. Допустим, на маяках стоят атомные часы — потому что на спутниках GPS стоят атомные часы: они идут правильно, а наши, возможно, идут неправильно.

То, что получилось, называется навигационными уравнениями GPS: ∣x−xi∣=ϑ (Δti+δ)|x - x_i| = \vartheta\,(\Delta t_i + \delta) для i=1,…,4i = 1, \dots, 4. Сколько у нас здесь неизвестных? Три пространственные координаты и δ\delta, то есть неизвестные — это (x,y,z,δ)(x, y, z, \delta): четыре неизвестных, четыре уравнения, четыре спутника. К чему я вёл? К тому, что система GPS позиционирует нас не только в пространстве — она позиционирует нас во времени. И чтобы позиционировать нас в пространстве, ей необходимо синхронизировать часы на ресивере с часами космического сегмента спутников.

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

Какая здесь аналогия, какая связь? У нас здесь коммуникация только в одну сторону: каждый спутник периодически отправляет радиоволну и кодирует в ней показания часов на момент отправки. И за счёт того, что у нас нет той самой асимметрии, а скорость света мы знаем, мы можем считать, что умеем синхронизировать часы. Это, конечно, забавно, но пока непонятно, к чему всё это и почему в курсе про распределённые системы вдруг возник GPS.

TrueTime в Google Spanner

Доска 8 — TrueTime: интервальный API, гарантия пересечения и расширение интервала между синхронизациями

Всё это забавно, но пока непонятно, к чему я веду: почему в курсе про распределённые системы возник GPS? Ответ довольно удивительный, и он называется Google Cloud Spanner. Все вы знаете про Google, знаете, что там можно что-нибудь поискать, но для нас в этом курсе поисковая строчка значения не имеет. Нам важно, что Google — это облачный провайдер, который предоставляет вам вычислительные мощности в виде Google Cloud, дисковые ёмкости, персистентные диски, и в том числе отдаёт как сервис свою внутреннюю инфраструктуру. Вообще говоря, почти все системы из левой части доски, которые мы будем изучать, впервые написали именно в Google, написали об этом статьи, и мы эти статьи будем разбирать.

Spanner — одна из таких систем, которые Google предоставляет как сервис. Это геораспределённая база данных с таблицами и колонками. И чтобы её написать, инженерам Google потребовался новый подход к часам. Они используют часы в своём алгоритме, но часы не обычные: NTP им не подходит, потому что доверия ему нет. Они построили специальный сервис, который называется TrueTime — «правильное время». Этот сервис состоит из демонов на каждой машине кластера и некоторого количества time-серверов, стоящих в дата-центре.

Опишем сначала саму систему. На каждой машине вы можете спросить, без всякой коммуникации по сети, TT.Now()\mathrm{TT.Now}() — и вам вернут вместо точки во времени интервал [e,l][e, l]: earliest и latest. А система TrueTime гарантирует, что настоящее время находится внутри этого интервала. Казалось бы, сделать такое несложно: берёте любой кластер, ставите на нём NTP, который синхронизирует часы, пишете функцию, которая возвращает текущее показание часов плюс-минус пять минут, — TrueTime готов. Но это не очень полезная идея. Во-первых, такой алгоритм по-прежнему ничего не гарантирует, это всё ещё best effort; во-вторых, интервал у вас будет очень широким.

Разработчики сервиса TrueTime говорят разработчикам базы данных Spanner, что те могут полагаться на то, что настоящее время лежит в выданном интервале. Чуть формальнее: если вы задаёте запрос TT.Now()\mathrm{TT.Now}() в момент времени t0t_0 и получаете ответ в момент времени t1t_1, то [t0,t1]∩[e,l]≠∅[t_0, t_1] \cap [e, l] \neq \varnothing. Беда в том, что ни t0t_0, ни t1t_1 вы не знаете — вы знаете только то, что вам вернули. Так вот, вам это гарантируют, и вдобавок стремятся сделать ширину интервала как можно меньше: в пределах дата-центра достигаются значения ∣l−e∣⩽6 ms|l - e| \leqslant 6\ \text{ms}. На это можно прямо полагаться. И это некоторое нарушение того, что я рассказывал в середине лекции: там мы говорили, что никаких гарантий на дрейф часов нет, NTP их не давал, — а TrueTime гарантии даёт. Довольно любопытно, что Google работает в такой модели.

Как это связано с базами данных и как это связано с GPS — пока не ясно. Начну со второго. TrueTime работает на каждой машине, и в дата-центре, помимо обычных машин, которые пользуются этим сервисом, стоят так называемые time masters. Они бывают двух типов. Первый тип — машины с GPS-антеннами, которые синхронизируются с GPS. Разумеется, не для того, чтобы определить своё местоположение: это было бы довольно бессмысленно, серверы вообще стоят на месте. Антенна нужна, чтобы синхронизировать часы с теми атомными часами, которые летают по орбите. Второй тип серверов называется Armageddon masters — это машины с атомными часами, которые просто стоят внутри них. То есть атомные часы у вас есть и в космосе, и у себя; и те, и другие дублируются ради отказоустойчивости.

Исходя из всей этой информации каждая машина выводит себе оценку интервала earliest/latest. И выводит забавно. Раз в 30 секунд каждая машина общается с мастерами, у которых есть атомные часы или GPS-антенны, и получает от них оценку интервала. А потом, через, скажем, 25 секунд, приходите вы со своей программой — точнее, приходит Spanner — и спрашивает у TrueTime текущее время. Вот здесь была точка синхронизации t∗t^{*}, а вот пришли вы, в точке запроса tqt_q; между ними прошло время dd. Что вам TrueTime вернёт?

Вернуть тот же самый интервал нельзя: он был действительно разумен в момент синхронизации, именно там алгоритм давал гарантию, но с тех пор прошло время dd. Если ты хочешь вернуть [e+d, l+d][e + d,\, l + d], то беда в том, что настоящего dd ты не знаешь: пока ты это dd измеряешь, ты вычитаешь одно показание своих локальных часов из другого, а они дрейфуют. Поэтому могло пройти dd, а могло немного больше или немного меньше. Поэтому TrueTime закладывает между точками синхронизации дрейф в 200 ppm, то есть 200 микросекунд в секунду, — примерно в 10 раз больше, чем у обычных кварцевых часов; запас берётся с большим перебором. И возвращает вам не прежний интервал, а чуть пошире: [e+d(1−ρ), l+d(1+ρ)][e + d(1 - \rho),\, l + d(1 + \rho)]. Потом машина снова синхронизируется, интервал снова схлопывается — и получается такая пилообразная картинка.

С GPS мы всё это связали. Теперь свяжем с распределёнными системами — точнее, не свяжем: вы свяжете это сами в домашней работе. У нас будет симулятор, в нём можно симулировать TrueTime.

— А почему нельзя просто сдвинуть интервал на dd?

— Сдвинуть на dd ты должен, только учти, что могло пройти d(1−ρ)d(1 - \rho) или d(1+ρ)d(1 + \rho). И мы берём очень большой запас, гораздо больше реального. Сила TrueTime в том, что в точке синхронизации происходит магия — атомные часы, GPS, — а между точками ты просто берёшь заведомо завышенный дрейф, который гораздо больше, чем у твоих настоящих часов. То есть на этом маленьком интервале дрейф очень сильно пессимизируется, но за счёт того, что синхронизации довольно частые, интервал не вырастает больше 6 мс.

Вообще, страшные люди работают в Google. Прошлой осенью они написали статью Google Sundial и рассказали, что с тех времён, с 2012–2013 года, они над этим ещё поработали, и теперь умеют синхронизировать часы в кластере чуть ли не до наносекунд, что выглядит как полное безумие. Но этот алгоритм уже не алгоритм в смысле «работающий на узлах» — он встроен прямо в роутеры, прямо в сеть, потому что иначе невозможно. Так не всякий может сделать, так делает только Google: только они такой сервис построили и сами им пользуются. Это некоторый способ обойти нашу странную модель без параметров.

— Почему интервал только расширяется, а сужаться уже не может?

— Он сузится, когда произойдёт следующая синхронизация: ты выбросишь свою пессимизацию и получишь новый интервал от time masters. И смотри, твоя задача — не общаться по сети, сейчас объясню почему. Когда ты задаёшь запрос TT.Now()\mathrm{TT.Now}(), ты по сети ни с кем не общаешься: спрашиваешь у локальной машины и мгновенно получаешь время. Если ты будешь общаться по сети, это убьёт весь замысел, который мы разберём чуть позже. Итак, время нужно знать локально, но избегать синхронной коммуникации с другими узлами: асинхронно, в фоне, ты иногда общаешься с time masters, получаешь оценку, а потом её поддерживаешь, расширяя — за счёт ожидания дрейфа локальных ненадёжных кварцевых часов.

Так вот, почему я утверждаю, что время для распределённых алгоритмов важно, — это последняя мысль на сегодня. Зачем в распределённой системе TrueTime? Потому что время, часы — это некоторая хитрость, это общее разделяемое состояние между разными машинами в сети. Чтобы вам что-то сделать, вообще говоря, нужно, чтобы машины друг с другом поговорили, чтобы они что-то друг о друге узнали. А здесь что-то общее у них уже есть: у них есть время. Говорить явно, отправляя сообщения, они тоже могут — так вот, Google использует TrueTime в своей базе данных как раз для того, чтобы не разговаривать по сети.

Они строят не просто базу данных в кластере, они строят геораспределённую систему, в которой реплики и узлы стоят физически далеко друг от друга, в разных регионах. Когда вы общаетесь по сети внутри дата-центра, тайминги могут быть очень маленькими, порядка одной миллисекунды. А когда вы пересылаете байтики через Атлантику или с восточного побережья США, тайминги уже — сотни миллисекунд. И с помощью некоторой хитрости, которую вы придумаете в первой домашней работе, вы увидите, как эту потенциально долгую коммуникацию можно заменить на простое локальное ожидание: вы просто сидите и ничего не делаете, и за счёт этого что-то становится лучше. Но сидите мало — 6 миллисекунд, вместо того чтобы общаться долго и ждать 100 миллисекунд. Это большая хитрость, и работает она именно за счёт того, что время у узлов общее. Google пытается построить такие магические часы, которые дают это общее время с некоторой возможной ошибкой, и стремится сделать ошибку как можно меньше. Деталей пока никаких нет, но, надеюсь, интуиция стала чуть яснее: почему я об этом рассказывал и зачем был нужен GPS.

Итак, что из всего этого можно вынести? Почти всё можно забыть и сказать следующее: в пределах этого курса мы чаще всего живём в асинхронной модели. Это означает, что мы не делаем предположений о скорости доставки сообщений, не делаем предположений о скорости работы узлов — там, не знаю, сборка мусора началась, — и не делаем предположений о дрейфе часов. Так мы работаем в тех случаях, когда доказываем, что система не нарушает понятных гарантий, то есть когда доказываем safety: что система не делает ничего плохого.

Но когда нам потребуется сказать, что система иногда делает и что-то хорошее, без времени не обойтись: настоящий код, конечно же, использует время, он не может его игнорировать, в нём есть таймауты. Однако от таймаутов не должно зависеть safety, не должна зависеть корректность — от них должен зависеть только progress системы, то есть то, что клиент дожидается ответа. Так что когда мы доказываем, что система не делает ничего плохого, мы используем асинхронную модель, где нет вообще никаких параметров времени. А когда мы доказываем, что система делает что-то полезное и отвечает пользователю, мы привлекаем таймауты, какие-то оценки времени доставки сообщений и прочее. Но корректность, safety, от этого зависеть уже не должна. Надо каждый раз быть аккуратным и отделять одно от другого: время помогает, но, когда его предположения не соблюдаются, оно ничего не может сломать.

С моделью, кажется, я объяснил всё, что хотел. На семинаре мы поговорим о том, что происходит в реальности и насколько эта модель вообще разумна. Всё, перерыв, спасибо.