- PVSM.RU - https://www.pvsm.ru -
Итак, представим. В комнате заперты 5 котов, и чтобы пойти разбудить хозяина им необходимо всем вместе договориться между собой об этом, ведь дверь они могут открыть только впятером навалившись на неё. Если один из котов – кот Шрёдингера, а остальные коты не знают о его решении, возникает вопрос: «Как они могут это сделать?»
В этой статье я простым языком расскажу вам о теоретической составляющей мира распределённых систем и принципах их работы. А также поверхностно рассмотрю главную идею, лежащую в основе Paxos'а.
Когда разработчики пользуются облачными инфраструктурами, различными базами данных, работают в кластерах из большого числа узлов, они уверены, что данные будут целостными, сохранными и всегда доступными. Но откуда гарантии?
По сути, гарантии, которые у нас есть – это гарантии поставщика. Они описаны в документации примерно следующим образом: «Этот сервис достаточно надёжный, у него есть заданный SLA, не беспокойтесь, всё будет распределённо работать, как вы и ожидаете».
Мы склонны верить в лучшее, ведь умные дяди из больших компаний заверили нас, что всё будет хорошо. Мы не задаёмся вопросом: а почему, собственно, это вообще может работать? Есть ли какое-то формальное обоснование корректности работы таких систем?
Недавно я ездил на школу по распределённым вычислениям [1] и очень вдохновился этой темой. Лекции в школе больше напоминали занятия по математическому анализу, нежели нечто связанное с компьютерными системами. Но именно так в своё время и доказывались важнейшие алгоритмы, которыми мы пользуемся каждый день, сами того не подозревая.
В большинстве современных распределённых систем используется алгоритм консенсуса Paxos и его различные модификации. Самое крутое, что обоснованность и, в принципе, сама возможность существования этого алгоритма может быть доказана просто с помощью ручки и бумаги. При этом на практике алгоритм применяется в больших системах, работающих на огромном числе узлов в облаках.
У нас есть две армии – рыжая и белая. Белые войска базируются в осаждённом городе. Рыжие войска во главе с генералами А1 и А2 располагаются по двум сторонам от города. Задача рыжих – напасть на белый город и победить. Однако войско каждого рыжего генерала в отдельности меньше войска белых.
Условия победы для рыжих: оба генерала должны напасть одновременно, чтобы иметь численное преимущество над белыми. Для этого генералам А1 и А2 нужно договориться друг с другом. Если каждый будет нападать по отдельности, рыжие проиграют.
Чтобы договориться, генералы А1 и А2 могут посылать друг к другу гонцов через территорию белого города. Гонец может успешно добраться до союзного генерала или может быть перехваченным противником. Вопрос: есть ли такая последовательность коммуникаций между рыжими генералами (последовательность отправки гонцов от А1 к А2 и наоборот от А2 к А1), при которой они гарантировано договорятся о нападении в час Х. Здесь, под гарантиями понимается, что оба генерала будут иметь однозначное подтверждение, что союзник (другой генерал) точно атакует в назначенное время X.
Предположим, что А1 посылает гонца к А2 с посланием: «Давай нападем сегодня в полночь!». Генерал А1 не может напасть без подтверждения от генерала А2. Если гонец от А1 дошёл, то генерал А2 посылает подтверждение с сообщением: «Да, давай сегодня завалим белых». Но теперь генерал А2 не знает, дошёл его гонец или нет, у него нет гарантий, будет ли нападение одновременным. Теперь уже генералу А2 опять нужно подтверждение.
Если расписывать их коммуникацию дальше, выяснится следующее: сколько бы ни было циклов обмена сообщениями, нет способа гарантированно уведомить обоих генералов о том, что их сообщения получены (при условии, что любой из гонцов может быть перехвачен).
Задача двух генералов – это отличная иллюстрация очень простой распределённой системы, где есть два узла с ненадёжной коммуникацией. Значит у нас нет 100% гарантии того, что они синхронизируются. Про подобные проблемы только в более крупном масштабе далее в статье.
Распределённая система – это группа компьютеров (далее будем называть их узлами), которые могут обмениваться сообщениями. Каждый отдельный узел – это некоторая автономная сущность. Узел может самостоятельно обрабатывать задачи, но чтобы взаимодействовать с другими узлами, ему нужно посылать и принимать сообщения.
Как конкретно реализованы сообщения, какие протоколы используются – это нас не интересует в данном контексте. Важно, что узлы распределённой системы могут обмениваться друг с другом данными путем отправки сообщений.
Само определение выглядит не очень сложным, но нужно учитывать, что у распределённой системы есть ряд атрибутов, которые будут важны для нас.
Синхронная модель – мы точно знаем, что есть конечная известная дельта времени, за которую сообщение гарантированно доходит от одного узла до другого. Если это время вышло, а сообщение не пришло, мы можем смело говорить, что узел вышел из строя. В такой модели мы имеем предсказуемое время ожидания.
Асинхронная модель – в асинхронных моделях мы считаем, что время ожидания конечно, но не существует такой дельты времени, после которой можно гарантировать, что узел вышел из строя. Т.е. время ожидания сообщения от узла может быть сколь угодно долгим. Это важное определение, и мы поговорим об этом дальше.
Прежде, чем формально определить понятие консенсуса, рассмотрим пример ситуации, когда он нам нужен, а именно – State Machine Replication.
У нас есть некоторый распределённый лог. Нам бы хотелось, чтобы он был консистентным и содержал идентичные данные на всех узлах распределённой системы. Когда какой-то из узлов узнает новое значение, которое он собирается записать в лог, его задачей становится предложить это значение всем остальным узлам, чтобы лог обновился на всех узлах, и система перешла в новое консистентное состояние. При этом важно, чтобы узлы договорились между собой: все узлы согласились, что предложенное новое значение корректно, все узлы это значение приняли, и только в этом случае все могут записать в лог новое значение.
Иными словами: никто из узлов не возразил, что у него есть более актуальная информация, а предлагаемое значение неверное. Договоренность между узлами и согласие о едином верном принятом значении и есть консенсус в распределённой системе. Далее мы будем говорить об алгоритмах, которые позволяют распределённой системе гарантированно достигать консенсус.
Более формально мы можем определить алгоритм достижения консенсуса (или просто алгоритм консенсуса), как некоторую функцию, которая переводит распределённую систему из состояния А в состояние Б. Причем это состояние принято всеми узлами, и все узлы могут его подтвердить. Как выясняется, эта задача совсем не такая тривиальная, как кажется на первый взгляд.
Алгоритм консенсуса должен обладать тремя свойствами, чтобы система продолжала существовать и имела какой-то прогресс в переходе из состояния в состояние:
Здесь важно понимать, что узлы в рассматриваемой нами распределённой системе хотят договориться. То есть мы сейчас говорим про системы, у которых просто может что-то отказать (например, отказать какой-то узел), но в этой системе точно нет узлов, которые намеренно работают против других (задача византийских генералов). За счет этого свойства система остается консистентной.
Пока свойства алгоритма могут быть не совсем понятны. Поэтому проиллюстрируем на примере, какие стадии проходит простейший алгоритм консенсуса в системе с синхронной моделью обмена сообщениями, у которой все узлы функционируют как положено, сообщения не теряются и ничего не ломается (неужели такое и правда случается?).
Когда узел «Узел 1» посылает свой пропоуз, остальные узлы проверяют в своих логах данные по этому событию. Если никаких противоречий нет, узлы объявляют: «Да, у меня нет других данных по этому событию. Значение «О» – это самая свежая информация, которую мы заслужили».
В любом другом случае, узлы могут ответить «Узлу 1»: «Послушай! У меня есть более свежие данные по этой транзакции. Не «О», а кое-что получше».
На стадии голосования узлы приходят к решению: либо все принимают одно значение, либо кто-то из них голосует против, обозначив, что у него есть более свежие данные.
Таким образом алгоритм консенсуса в простом случае состоит из четырёх шагов: propose, голосование (voting), принятие (accept), подтверждение принятия (accepted).
Если на каком-то шаге мы не смогли достичь согласия, то алгоритм запускается заново, с учётом той информации, которую предоставят узлы, отказавшиеся подтверждать предлагаемое значение.
До этого всё было гладко, ведь речь шла про синхронную модель обмена сообщениями. Но мы-то знаем, что в современном мире мы всё привыкли делать асинхронно. Как же аналогичный алгоритм работает в системе с асинхронной моделью обмена сообщениями, где мы считаем, что время ожидания ответа от узла может быть сколь угодно долгим (к слову, выход узла из строя, можно тоже рассматривать как пример, когда узел может отвечать сколь угодно долго).
Теперь, когда мы знаем, как в принципе работает алгоритм консенсуса, вопрос к тем пытливым читателям, кто дошёл до этого места: сколько узлов в системе из N узлов с асинхронной моделью сообщений может выйти из строя, чтобы система по-прежнему могла достигать консенсуса?
Мы сейчас говорили про теорию, про математику. Что значит «консенсус не может быть достигнут», переводя с математического языка на наш – инженерный? Это значит, что «не всегда может быть достигнут», т.е. существует такой кейс, при котором консенсус не достижим. А что же это за случай?
Это как раз нарушение liveness property, описанное выше. У нас нет общего согласия, и система не может иметь прогресс (не может завершиться за конечное время) в случае, когда у нас нет ответа от всех узлов. Потому что в асинхронной системе у нас нет предсказуемого времени ответа, и мы не можем знать, вышел ли узел из строя или просто долго отвечает.
Но на практике мы можем найти решение. Пусть наш алгоритм может работать долго в случае отказов (потенциально может работать бесконечно). Но в большинстве ситуаций, когда большинство узлов корректно функционируют, мы будем иметь прогресс в системе.
На практике мы имеем дело с частично синхронными моделями коммуникаций. Частичная синхронность понимается так: в общем случае у нас асинхронная модель, но формально вводится некое понятие «global stabilization time» некоего момента времени.
Этот момент времени может не наступать сколь угодно долго, но однажды он должен наступить. Прозвенит виртуальный будильник, и с этого момента мы можем предсказать дельту времени, за которую сообщения дойдут. С этого момента система из асинхронной превращается в синхронную. На практике мы имеем дело именно с такими системами.
Paxos [4] – это семейство алгоритмов, которые решают проблему консенсуса для частично синхронных систем, при условии что какие-то узлы могут выходить из строя. Автором Paxos'а является Leslie Lamport [5]. Он предложил формальное доказательство существования и корректности алгоритма в 1989 году.
Но доказательство оказалось отнюдь нетривиальным. Первая публикация была выпущена только в 1998 году (33 страницы) с описанием алгоритма. Как оказалось, она была крайне сложной для понимания, и в 2001 году было опубликовано пояснение к статье, которое заняло 14 страниц. Объемы публикаций приведены для того, чтобы показать, что на самом деле проблема консенсуса совсем непростая, и за подобными алгоритмами лежит огромный труд умнейших людей.
Интересно, что сам Лесли Лэмпорт в своей лекции заметил, что во второй статье-пояснении есть одно утверждение, одна строчка (не уточнил какая), которая может быть по-разному трактована. И из-за этого большое количество современных реализаций Paxos работают не совсем корректно.
Подробный разбор работы Paxos'а потянет не на одну статью, поэтому я постараюсь очень коротко передать основную идею алгоритма. В ссылках в конце моей статьи вы найдете материалы для дальнейшего погружения в эту тему.
В алгоритме Paxos есть понятие ролей. Рассмотрим три основные (есть модификации с дополнительными ролями):
Один узел может совмещать несколько ролей в разных ситуациях.
Мы предполагаем, что у нас есть система из N узлов. И из них максимум F узлов может выходить из строя. Если F узлов выходит из строя, значит у нас в кластере должно быть, как минимум 2F + 1 узлов acceptor'ов.
Это нужно для того, чтобы у нас всегда, даже в худшей ситуации «хорошие», корректно работающие узлы имели большинство. То есть F + 1 «хороших» узлов, которые согласились, и финальное значение будет принято. В противном случае может быть ситуация, когда у нас разные локальные группы примут разное значение и не смогут между собой договориться. Поэтому нам нужно абсолютное большинство, чтобы победить в голосовании.
Алгоритм Paxos предполагает две больших фазы, которые в свою очередь разбиваются на два шага каждая:
Если лидеру ответило большинство узлов, и все они подтвердили новое значение, то новое значение считается принятым. Ура! Если же большинство не набрано или есть узлы, которые отказались принимать новое значение, то всё начинается сначала.
Вот так работает алгоритм Paxos. У каждого из этих этапов есть много тонкостей, мы практически не рассмотрели различные виды отказов, проблемы множественных лидеров и многое другое, но целью данной статьи является лишь на верхнем уровне познакомить читателя с миром распределённых вычислений.
Также стоит заметить, что Paxos — не единственный в своем роде, есть и другие алгоритмы, например, Raft [6], но это уже тема для другой статьи.
Уровень «новичок»:
Уровень «Лесли Лэмпорт»:
Автор: Ceridan
Источник [14]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/327559
Ссылки в тексте:
[1] школу по распределённым вычислениям: https://sptdc.ru
[2] задачу двух генералов: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B4%D0%B2%D1%83%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2
[3] византийских генералов: https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2
[4] Paxos : https://en.wikipedia.org/wiki/Paxos_(computer_science)
[5] Leslie Lamport: https://en.wikipedia.org/wiki/Leslie_Lamport
[6] Raft: https://raft.github.io/
[7] How Does Distributed Consensus Works?: https://medium.com/s/story/lets-take-a-crack-at-understanding-distributed-consensus-dad23d0dc95
[8] Paxos made simple. For real: https://medium.com/@nevverlander/paxos-made-simple-for-real-aa221be7d91b
[9] Decentralized Thoughts: https://ittaiab.github.io/
[10] Synchrony, Asynchrony and Partial synchrony: https://ittaiab.github.io/2019-06-01-2019-5-31-models/
[11] Impossibility of Distributed Consensus with One Faulty Process (FLP impossibility): https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
[12] The Part-Time Parliament: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[13] Paxos made simple: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[14] Источник: https://habr.com/ru/post/463469/?utm_campaign=463469&utm_source=habrahabr&utm_medium=rss
Нажмите здесь для печати.