Как избежать раздвоения мозга, голосов и кворума [закрыто]

Предположим, у вас есть n процессов, n & gt; 2. Вы хотите договориться между собой, что нужно быть активным. Поэтому им нужно проголосовать друг за друга, чтобы определить, кто из них активен.

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

Мыmust никогда не имейте двух активных одновременно, поэтому, если они не могут быть уверены, лучше, чтобы никто не был активным. (Т.е. мы хотим избежать раскола мозга)

Единственный доступный механизм связи между ними - паб-суб-обмен сообщениями (не точка-точка).

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

Дизайн? Какие сообщения нужно публиковать?

Ответы на вопрос(3)

Посмотрите, как это делают протоколы маршрутизации (OSPF и IS-IS), и посмотрите, подходит ли вам это. Они выбирают лидера (а в случае OSPF - резервного лидера).

 djna27 авг. 2009 г., 10:34
Нас беспокоил сам процесс выборов. Спасибо за предложение. этоroutergod.com/sevenofnine/ospf_part_2.html статья описывает, что происходит, но не дает подробностей. Для меня проблема заключается в том, как бороться с ненадежными коммуникациями и избегать возможности раскола мозга.
 27 авг. 2009 г., 15:36
Эта ссылка только объясняет краткий обзор. Взгляните на некоторые документы cisco или книгу «Маршрутизация TCP / IP».

Я не совсем уверен в сообщениях в пабе.

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

 djna10 июл. 2009 г., 07:30
обмен сообщениями pub-sb, подразумевающий, что каждый участник может передавать информацию, но не может быть уверен, что другие участники видят ее. Во всяком случае, ваш ответ на самом деле тот, о котором мы думали и который нам очень понравился. Недостатком является то, что у нас на самом деле есть только 2 узла, и поэтому в ухудшенном режиме теряется половина работы.
Решение Вопроса

Теория:

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

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

На практике мы преодолеваем это, используя детекторы отказов для симуляции синхронной системы.

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

Практические решения:

Хотя проблема в целом довольно сложная, получить работающие системы гораздо проще. Имеются готовые реализации Paxos или эквивалентные алгоритмы.Apache Zookeeper это лучшее, что я знаю. Что касается вашей конкретной проблемы, я уверен, что это будет ваш самый быстрый маршрут. Существуют и другие реализации Paxos, и также возможно создать что-то на виртуальных IP-инструментах с избыточностью сети, таких какWackamole, Я считаю, что высокопроизводительные версии большинства коммерческих баз данных предлагают функции кворума как (дорогой) вариант.

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

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

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

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

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

 djna10 июл. 2009 г., 07:37
Спасибо за это подробное объяснение и ссылки. Я согласен с тем, что ослабление ограничений для упрощения решения - это путь, который мы должны изучить. [Теперь я могу повторить эпитафию Спайка Миллигана, когда вернусь в команду ». Видите, я же говорил, что это сложно!».
 08 окт. 2013 г., 08:48
Для ясности Zookeeper реализует ZAB «Zookeeper Atomic Broadcast» который соответствует абстрактным Paxos, но отличается от Classic Paxos тем, что сообщения сохраняют первичный порядок, что очень важно во многих сценариях.

Ваш ответ на вопрос