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

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

Две простых модели

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

Задача двух генералов

Это мысленный эксперимент, показывающий проблему сихнорнизации состояния двух систем по ненадёжному каналу связи.

Две армии, каждая руководимая своим генералом, готовятся к штурму города. Город слишком силён для взятия одной армией, поэтому генералам надо согласовать одновременное время атаки - штурм, предпринятый только одной армией, закончится для нее катастрофой. Обменяться сообщениями можно только через долину, которую контролирует враг. В этом случае посыльный может потеряться и не доставить сообщение.

Достичь согласия очень просто - достаточно одного сообщения со временем штурма и одного согласия. Проблема в том, что генералам невозможно разработать протокол, который мог бы за конечное число сообщений достоверно дать возможность скоординировать действия.

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

Как и в общении с людьми, если посмотреть на это философски. У нас нет телепатии, и мы не можем точно знать мысли другого человека. Для этого мы используем речь, текст, язык тела. И эти сообщения точно так же могут не дойти до получателя (в том числе быть проинтерпретированы неверно). В каком-то смысле общество - это большая распределённая система.

Задача византийских генералов

В византийской армии уже три или больше генералов хотят атаковать город. Все сообщения доставляются корректно, но есть новая проблема - генералы могут быть либо честными, либо предателями. У генералов два варианта приказа: «атаковать противника» или «отступать». Если все верные генералы атакуют, то Византия победит. Если все верные генералы отступят, то Византия сохранит свою армию. Но если из-за несогласованности некторые верные генералы атакуют, а некоторые отступят, то противник со временем по частям уничтожит всю армию.

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

У этой проблемы есть формальное доказательство, которое я пока опущу, что для точного решения необходимо, чтобы менее трети генералов были предателями. Если в системе 3f+1 генерал, не более f могут быть предателями.

В распределённых системах эта проблема находит практическое применение тем, где есть отношения доверия между участниками (а такие отношения есть в большинстве систем). Даже если взять систему «банк-магазин-покупатель»: магазин должен допускать, что покупатель может иметь плохие намерения; сервис платежей должен допускать, что кто-то может настроить фейковый магазин; покупатель тоже в свою очередь должен доверять маганизу, чтобы заказывать себе доставки, хотя он и сможет потом в банке оспорить транзакции, если его обманут. Это просто хороший пример того, как системы строятся на доверии между участниками, которые в том числе могут намеренно вредить другим.

Для систем, которые в своем функционировании умеют решать ситуации, где часть узлов может быть под контролем вредоносного актора, считаются Byzantine fault tolerant.

Модель распределённой системы

Модель распределённой системы фокусируется на описании системы с трёх точек зрения:

  • Поведение сети в системе;
  • Поведение узлов в системе;
  • Тайминг в системе.

Хорошим началом для проектирования алгоритма работы системы будет моделирование системы по этим трём компонентам.

Также важно отметить, что большинство распределённых алгоритмов полагают, что в сети осуществляется двунаправленное взаимодействие (point-to-point или unicast). В реальных сетях иногда допускается broadcast (например, поиск принтера в локальной сети). Но модель интернета - это всё-таки юникаст взаимодействие, поверх которого иногда вводится бродкаст.

Поведение сети

При двунаправленной коммуникации двух узлов мы можем наблюдать три разных поведения сети:

  • Надёжный канал. Сообщения получаются, только если были отправлены, их доставка гарантирована. Сообщения могут приходить в неверном порядке.
  • Защищённый канал. В нём сообщения могут быть утеряны, продублированы, или присланы в неверном порядке. В этом канале, если отправитель будет пытаться переотправлять сообщения, рано или поздно они дойдут.
  • Произвольный канал. Между участниками сообщения может встраиваться третий актор и осуществлять действия - подслушивать, изменять, переотправлять сообщения. В общем случае это MITM (Man in the middle).

Чтобы перейти от произвольного канала к защищённому, используется криптография и протокол TLS.

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

Поведение узлов

Каждый узел в системе исполняет алгоритм (программу). С точки зрения исполнения своих функций узел может вести себя следующим образом:

  • Crash-stop: узел может выйти из строя, и тогда он насовсем перестаёт выполнять программу.
  • Crash-recovery: узел может выйти из строя в любой момент и потерять состояние памяти. Но он может восстановиться и продолжить выполнять программу, и данные на диске переживут сбой.
  • Byzantine: узел может в том числе отклониться от своей программы. В такой модели сломанные узлы могут делать тчо угодно, в том числе сбоить или совершать зловредные действия.

Crash-stop моделирует ошибки аппаратного уровня (hardware), после таких ошибок узел, скорее всего, утрачен полностью (или надолго, как минимум, до его ремонта в датацентре). Crash-recovery больше похож на ошибки ПО (software), когда узел может быть перезагружен.

Византийская модель поведения лучше всего показывает узлы в реальных системах. При этом баги в ПО не относят к зловредному поведению, поскольку чаще всего большинство узлов системы (сильно больше трети) используют похожее ПО, и тогда в случае бага подобная система не могла бы считаться Byzantine fault-tolerant. Поэтому сбоем здесь считается более серьёзное отклонение от алгоритма.

Почему это важно? Потому что в зависимости от того, как мы моделируем поведение узлов в системе, нам могут потребоваться разные протоколы, чтобы делать систему устойчивой к отказам (fault tolerant). Очевидно, например, что в модели crash-recovery после наблюдения сбоя алгоритм должен допускать возвращение узла к работе, а отличие от crash-stop.

Тайминг

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

  • Синхронный. Задержка отправки сообщения всегда не превышает известную границу. Узлы в системе исполняют алгоритм с заданной скоростью.
  • Асинхронный. Сообщения могут быть задержаны произвольно, а узлы выполняют алгоритм за произвольное время. Гарантии тайминга отсутствуют полностью.
  • Частично синхронный. Система может входить в асинхронное состояние на конечные периоды времени, в остальное же время она синхронна.

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

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

Детектор ошибок

Первый шаг к сопротивлению сбоям в системе - это умение обнаруживать (детектировать) эти сбои. В распределённых системах за это отвечает алгоритм faliure detector. В crash-stop/crash-recovery системах в простом виде он определяет сбой, отправляя сообщение и ожидая ответ. Если ответа нет за определённый таймаут, узел помечается сбойным.

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

Такой идеальный детектор может существовать только в синхронной crash-stop системе с надёжным каналом связи. Если система частично сихнорнная, то в ней уже не может быть идеального детектора.

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

В частично синхронных системах существует практически примений дектор сбоев - eventually perfect failure detector. Его свойства следующие:

  • Он может временно помечать узел сбойным, даже если он рабочий.
  • Он может временно считать узел рабочим, даже если он вышел из строя.
  • Но в конце концов он всё-таки будет отмечать сбойными только те узлы, которые действительно засбоили.

Для построения высокодоступных систем (higly-available) критически необходимо наличие детектора, потому что он делает возможным проектировать отказоустойчивые алгоритмы и автоматическое восстановление от сбоев.