Глава 10. Выбор лидера

Один из алгоритмов выбора лидера, именуемый как алгоритм задиры (bully algorithm), ипользует ранги процессов для выявления своего нового лидера. Каждый процесс получает некий уникальный назначаемый ему ранг. В процессе проведения выборов процесс с наивысшим значением ранга становится лидером [MOLINA82].

Этот алгоритм стал известным благодаря своей простоте. Данный алгоритм носит название задиры по той причине, что узел с наивысшим значением ранга "быкует" прочие узлы чтобы они приняли его в качестве лидера. Он также известен под названием монархического выбора лидера: монархом становится собрат с наивысшим рейтингом после того как прежний перестаёт существовать.

Выборы запускаются когда один из имеющихся процессов замечает что в его системе отсутствует лидер (он не был инициализирован) или предыдущий лидер перестал отвечать на запросы и выполняется в три этапа (данные шаги описывают видоизменённый алгоритм выборов задиры [KORDAFSHARI05], поскольку он более компактный и ясный):

Рисунок 10-1 иллюстрирует обсуждённый алгоритм задиры выборов лидера:

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

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

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

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

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

Рисунок 10-2 показывает данный процесс с данной оптимизацией на своём месте:

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

Другой алгоритм пытается снизить требования в общем числе сообщений расщепляя все узлы на два подмножества: соискателей и обычные. в которых лишь один из имеющихся узлов кандидатов может в конечном итоге становиться лидером [MURSHED12].

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

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

Рисунок 10-3 отображает установленные этапы данного процесса выборов:

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

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

Рисунок 10-4 отображает шаги, исполняемые этим алгоритмом приглашения:

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

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

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

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

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

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

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

Как вы можете видеть, для правильной работы систем с лидером нам необходимо знать состояние текущего лидера (жив он или нет), так как для продолжения поддержки организации процессов и самого исполнения такой лидер должен быть рабочим и и достижим чтобы исполнять свои обязанности. Для выявления крушения лидера мы можем применять алгоритмы выявления отказов (см. Главу 9).

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

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

Многие алгоритмы консенсуса, включая Multi-Paxos и Raft, полагаются на некого лидера для координации. Тем не менее, являются ли выборы лидера тем же самым что и консенсус? Для выборов некого лидера нам требуется достичь согласия о его идентичности. Если мы способны достичь консенсуса относительно идентичности лидера, мы можем применять то же самое средство для достижения согласия по чему угодно [ABRAHAM13].

Значение идентичности некого лидера может изменяться без знания этого процессами, потому будет справедлив также и вопрос о том знает ли о своём лидере локально процесс. К примеру, алгоритм стабильного выбора лидера (stable leader election) использует раунды с уникальным стабильным лидером и выявление отказов на основании таймаутов для обеспечения того, что это лидер может оставаться в своём положении пока он не испытает крушения и является доступным [AGUILERA01].

Полагающиеся на выборы лидера алгоритмы часто допускают наличие присутствия множества лидеров и пытаются разрешать конфликты между этими лидерами настолько быстро, насколько это возможно. Например, это справедливо для Multi-Paxos (см. раздел Multi-Paxos), в котором способен продолжать лишь один из двух конфликтующих лидеров (доверенное лицо, proposers), а эти конфликты разрешаются сбором некого вторичного кворума, что обеспечивает тот факт, что не будут приняты значения от двух различных доверенных лиц.

В Raft (см. раздел Raft) может обнаружить, что его звание устарело, что подразумевает присутствие в этой системе другого лидера, и ему придётся обновлять это звание на более позднее.

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

Мы обсудим более подробно консенсус и выборы лидера в контексте консенсуса в Главе 14.