В этой статье мы разберем алгоритм консенсуса Paxos, обсудим, зачем он нужен, почему он работает, докажем его корректность и немного поговорим о проблемах практического применения.
Во многом это вольный пересказ статьи Лесли Лэмпорта.
Зачем нужен распределенный консенсус и что это такое?
Зачастую при работе распределенной системы (просто несколько серверов, обрабатывающих запросы пользователей или распределенная система хранения данных или что-то в этом роде) возникает необходимость принятия общих решений, например, на каком сервере запускать синглтон-сервис уровня кластера.
и куда его перенести, если сервер выйдет из строя.
Эта проблема просто решается, если есть арбитр, принимающий решения — админ-сервер.
Проблема в том, что арбитр становится единственной точкой отказа; его выход из строя может привести к полной или частичной неработоспособности системы, а его восстановление и восстановление работоспособности системы потребуют ручного вмешательства.
Очевидно, что отказоустойчивая система должна состоять из равноправных участников, способных договариваться между собой по общим вопросам – достигать консенсуса.
Обычно в результате переговоров выбирается арбитр (используются термины: руководитель, мастер) и дальнейшие вопросы, пока он в исправном состоянии, решаются через него.
Лесли Лэмпорт изначально хотел математически строго доказать, что консенсус в распределенной системе с ненадежными коммуникациями невозможен, но вместо этого изобрел и доказал алгоритм Paxos, который позволяет достичь такого консенсуса.
Описание алгоритма, которое можно найти, например, в Википедии Оно выглядит обманчиво простым и кратким, но его нелегко понять и еще труднее применить на практике.
Этот алгоритм имеет важные ограничения: он описывает процесс выбора только одного значения, но на практике необходимо принимать множество решений и для каждого последующего случая нужно будет создавать новый экземпляр алгоритма.
Предполагается также, что участники системы ведут себя не по-византийски, т.е.
выполняют свои обещания, не предоставляют ложных данных (не знаю истории, но чувствую, что репутация у византийцев была так себе)
О выборе и ролях
Понятие «выбор» (выбор решения, выбор значения) в контексте алгоритмов консенсуса отличается от обыденного.Если в реальной жизни сравнивать плюсы и минусы, то в случае алгоритма консенсуса выбор осуществляется из равнозначных вариантов, т.е.
подойдет любое значение/решение, главное определиться, какое конкретно из множества предложенных .
Это можно сравнить с тем, как вы втроем с друзьями приходите в пиццерию, где вся пицца одинаково хороша (или плоха) и пытаетесь выбрать, какую большую пиццу заказать на троих, к вам подходит единственный официант, а вы продолжаете с недоумением смотреть на меню.
С соседних столиков начинают предлагать: «Берите уже «Пепперон», не удерживайте меня, он не хуже всего остального» — вот это было предложение (предложение) и высказал его предложение (предлагающий).
Один из вас услышал это и подумал: «Ладно, пусть это будет пепперони».
Он - хозяин (акцептор) и только что принял (принять) предложение .
С другого столика кричат: «Тебе уже третий раз говорят — бери Маргариту и пусть у нас примут заказ» — это еще один предложение , а «это у тебя уже в третий раз» — это номер предложения (номер предложения), а «Маргарита» — смысл предложения (ценить).
Потом официант начинает расспрашивать вас, кто какие предложения принял.
Он - признание (художественнее) и если большинство (большинство) из вас приняло одно и то же предложение («Говорю вам в третий раз – Маргарита»), то это предложение называется выбрано (выбрано), и если большинство скажет это официанту, то официант узнает (узнать) о выбранной стоимости и сможет принять заказ.
Но, допустим, один из тех, кто принял третье предложение, застрял в смартфоне и не отвечает на вопрос официанта.
Смысл выбран, но узнать его невозможно — двое оставшихся в реальном мире друзей дают противоречивые ответы.
Начинается следующий раунд переговоров и, возможно, новое предложение будет принято, но приклеенный к смартфону участник продолжит читать хаб.
Итак, правильный алгоритм консенсуса устанавливает такие правила переговоров, что любое следующее выбранное значение будет совпадать с первым выбранным значением.
Посмотрите еще раз, это очень важный и совершенно замечательный момент: состояние системы (принятые значения) распределяются между узлами - каждый получатель знает только о том предложении, которое он принял, общее значение было выбрано, но может возникнуть ситуация, когда невозможно узнать и даже невозможно узнать, выбрано ли что-то.Итак, с терминологией и ролями мы разобрались:В этом случае переговоры продолжатся.
Но Paxos таков, что любое следующее значение, выбранное большинством получателей, будет совпадать с первым выбранным.
Сделанный выбор уже не изменится.
- Предложение - делать предложения .
- Хозяева — принимать предложения, и запомнить принятые( число И значение ).
В этом случае получатель примет первое полученное предложение и будет принимать последующие, даже если выбор уже сделан.
- Те, кто признает - узнать, какое было предложение выбрано (принято большинством участников).
О большинстве
Под большинством мы подразумеваем «более половины», т.е.N+1 из 2N+1 (и из 2N тоже) или более.
Требование принятия большинством очевидно: если бы выбор значения требовал принятия меньшим числом акцепторов (ровно половиной или меньше), то ничто не помешало бы вам выбрать несколько разных значений одновременно, т.е.
консенсуса не было бы.
были достигнуты.
Нам будет полезно знать, что любые два множества, составляющие большинство, имеют непустое пересечение.
При этом участие всех получателей в выборе не требуется; остальные приемники могут быть неисправны, и связь с ними может быть нарушена.
Таким образом, мы получаем, что система из 2N+1 участников способна пережить отказ N из них.
Глобальное время распределенной системы
Номер предложения мы уже упомянули.Каждое предложение (предложение) имеет номер.
В описании Лэмпорта это натуральное число таково:
- номер уникальный, у каждого предложения свой;
- Предлагающий использует большее число для каждого последующего предложения.
Получатель, приняв предложение, будет игнорировать предложения, сделанные «до» принятого (предложения «из прошлого»).
На практике номер предложения будет состоять из пары: значения счетчика предложений конкретного сервера и идентификатора сервера.
Построение правильного алгоритма
Значение в выбрано, если номер предложения м и смысл в был принят большинством получателей.После этого любое последующее выбранное значение (принимаемое большинством акцепторов) должно соответствовать выбранному.
в .
Это требование может быть выполнено, если после значения в был выбран, акцепторы будут принимать только предложения со значениями, равными в .
Получатель принимает то, что предлагают предлагающие, а это означает, что предыдущее требование, в свою очередь, может быть выполнено, если все предлагающие присутствуют во всех предложениях с номером п> м предлагать только ранее выбранное значение в .
Давайте представим, что мы доказываем последнее утверждение по индукции и попытаемся понять, чего не хватает для совершения индуктивного перехода.
Предложение (м, в) - был выбран, т.е.На строгом математическом языке это формулируется Лэмпортом так: для осуществления индукционного перехода необходимо, чтобы выполнялся следующий инвариант:их много С состоит из большинства акцепторов, и каждый из этих акцепторов принял оферту (м, в) .
Из предположения индукции также следует, что все предложения с номерами из диапазона от м до n-1 инклюзивный вопрос в (*).
Теперь вам нужно убедиться, что предложение с номером н тоже имело значение в .
Предположим, что существует множество С состоящий из большинства получателей и такой, что мы можем узнать смысл последнего предложения (с максимальным числом меньше н ), принимаемые приемниками из этого набора.
Допустим, количество этого «максимального» предложения равно к .
Поскольку многие С содержит хотя бы один приемник а из многих С , означает число к будет больше или равно номеру последнего принятого предложения получателем а , и номер последнего принятого предложения а будет больше или равно числу м (момент выбора значения), т.е.
к > = м , и, таким образом, в силу (*) смысл предложения к - это ранее выбранный в , мы будем использовать его для создания предложения (н,в) .
Таким образом, если мы можем гарантировать существование множеств С , то это обеспечит индуктивный переход.
Для любого в И н , если предложение (n, v) сделано (выдано), то существует множество С состоящая из большинства получателей и такая, что верно одно из двух: (a) ни один получатель из набора С не принял ни одного предложения с номером ниже н или (б) в - это значение предложения с наибольшим номером и наименьшим н среди всех предложений, принятых получателями из набора С .Для обеспечения существования описанного выше набора С планирую предложить н следует выяснить у большинства получателей, какой номер и значение последнего предложения они примут перед н .
Посмотрите на проблему: предлагающий может запросить у любого получателя номер и значение последнего принятого им предложения, но есть вероятность, что, уже отправив ответ, получатель примет следующее предложение и ответ, полученный предлагающим, будет быть устаревшим и бесполезным.
Чтобы избежать этого, Лэмпорт придумал следующее: пусть предлагающий не только спрашивает значение последнего принятого предложения, но и просит не принимать предложения с меньшим номером.
н .
В ответ от акцептанта предлагающий получит: 1) стоимость и номер последнего предложения, принятого акцептантом, и 2) обещание не принимать предложения с номерами ниже.
н .
Тогда информация о последнем принятом предложении, полученном в ответ, не устареет, и если ответы получены от большинства акцепторов, то эти акцепторы образуют необходимое множество.
С .
Как только набор С сформировано, предлагающий делает предложение (н,в) (Где в , как мы обсуждали выше, — это значение последнего предложения (предложения с максимальным номером), принятого получателями из множества С до момента н ).
Таким образом, мы получили правильный алгоритм консенсуса, где предложения вносятся в два этапа:
- Подготовительный этап:
- Предлагающий рассылает объявление о том, что он планирует сделать предложение.
н (вовремя н )
- Те, кто получит объявление, отправят обратно обещание не принимать предложения с номерами ниже.
н (до момента н ), а также последнее принятое предложение (количество и стоимость) или вообще не отвечать, если количество последнего принятого получателем предложения превышает н или если n входит в число предложений, которые принимающая сторона уже пообещала не принимать другому предлагающему.
- Предлагающий рассылает объявление о том, что он планирует сделать предложение.
- Предложение:
- Предлагающий, получив ответы от большинства акцепторов, выбирает в качестве значения предложение.
в значение из ответа с максимальным количеством предложений и отправляет предложение (н,в) .
- Получатель получает предложение (н, в) , обязан принять его, если, конечно, он не пообещал другому предлагающему не принимать предложения с меньшими номерами.
н* , Где п* > п .
- Предлагающий, получив ответы от большинства акцепторов, выбирает в качестве значения предложение.
Проблемы практического применения
Обмен сообщениями асинхронен, связь ненадежна, поэтому неизвестно, получит ли предлагающий хоть какие-то ответы; не дожидаясь необходимого количества обещаний, предлагающий повторит попытку со следующим предложением.Все это можно повторять еще долго.
Алгоритм не гарантирует достижения консенсуса.
Допустим, один предлагающий получает от большинства обещание не принимать предложения с номером меньше 1, второй, следующий за ним, получает от большинства обещание не принимать предложения с номером меньше 2. То есть.
Первое предложение больше не может быть выбрано.
Поняв, что его предложение не будет выбрано, первый предлагающий попытается добиться от большинства обещаний не принимать предложения с номером меньше 3. Теперь даже 2-е предложение не может быть принято.
И поэтому два предлагающих могут бесконечно склонять большинство получателей на ту или иную сторону, блокируя возможность достижения консенсуса.
Это можно исправить, введя в алгоритм случайные задержки, и, конечно, желательно как можно скорее убедиться, что есть только один предлагающий.
Для этого, когда необходимо принять несколько решений, при выборе следующего значения в качестве предлагающего используется лидер, выбранный на предыдущем шаге (в предыдущем экземпляре алгоритма).
Но тут возникает новая проблема: если мы выбрали лидера, ничто не мешает оставшимся узлам за ним инициировать новые выборы и выбрать между собой другого лидера, они смогут собрать кворум.
При этом предыдущий руководитель может ничего об этом не знать и будет продолжать действовать, полагая, что он здесь главный.
Еще одна сложность — нечестное византийское поведение, и для этого не обязательно наличие вредоносного ПО среди элементов системы.
Например, получатели должны запомнить свое обещание, сохранив его на диске; повреждение данных на диске (из-за сбоя или неосторожного удаления файлов оператором) приведет к византийскому поведению.
На практике даже данные в памяти могут быть повреждены с таким же печальным результатом.
Ошибки в коде также могут стать причиной византийского поведения.
Об этих и других проблемах алгоритма Paxos вы можете прочитать в интересной статье разработчиков Google. «Паксос стал живым – инженерная перспектива» , где рассказывают о своем опыте реализации распределенного консенсуса в проекте Chubby (внутренний корпоративный аналог Zookeeper) Таким образом, алгоритм Paxos — это не панацея, а просто замечательный небольшой фундаментальный блок наших знаний об отказоустойчивых распределенных системах.
Теги: #Алгоритмы #программирование #Анализ и проектирование систем #Распределенные системы #консенсус #Paxos #отказоустойчивость #алгоритм Paxos #Paxos #распределенная система #Лампорт
-
Gotouch — Карманный Проектор
19 Oct, 24 -
Разработка Css На Github
19 Oct, 24
