Подтвердить что ты не робот

Каковы более быстрые алгоритмы, связанные с Paxos, для консенсуса в распределенных системах?

Я читал Lamport документ на Paxos. Я также слышал, что он практически не используется на практике по причинам производительности. Какие алгоритмы обычно используются для консенсуса в распределенных системах?

4b9b3361

ОТВЕТЫ

Ответ 1

Не уверен, что это полезно (так как это не из реальной информации о производстве), но в нашем курсе "распределенные системы" мы изучали вместе с Paxos Chandra-Toueg и < сильные > алгоритмы Mostefaoui-Raynal (из последних наш профессор особенно любил).

Ответ 2

Если производительность является проблемой, подумайте о том, нужны ли вам все сильные гарантии последовательности, которые дает Paxos. См. http://queue.acm.org/detail.cfm?id=1466448 и http://incubator.apache.org/cassandra/. Поиск в Paxos оптимизирован, и я получаю хиты, но я подозреваю, что ослабление некоторых требований будет покупать вас больше, чем настройка протокола.

Ответ 3

Система Paxos, которую я запускаю (которая поддерживает действительно большие веб-сайты), находится на полпути между Basic-Paxos Multi-paxos. Я планирую переместить его в полную реализацию Multi-Paxos.

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

Как и Chubby Google, моя система запускается как служба и также может хранить данные в качестве контейнера конфигурации. (Я использую конфигурацию свободно, я слышал, что Google использует Chubby для DNS.) Эти данные не изменяются так часто, как пользовательский ввод, поэтому ему не требуется высокая пропускная способность для записи. Чтение, с другой стороны, чрезвычайно быстро, потому что оно полностью реплицировано, и вы можете читать из любого node.

Обновление

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

Ответ 5

Вы должны проверить проект Apache Zookeeper. Он используется в производстве Yahoo! и Facebook среди других.

http://hadoop.apache.org/zookeeper/

Если вы ищете научные статьи, описывающие это, это описано в документе atenix ATC'10. Консенсусный протокол (вариант Paxos) описан в статье в DSN'11.

Ответ 6

Google задокументировал, как они сделали быстрые paxos для своего мегазвезды в следующем документе: Ссылка.

Ответ 7

С Multi-Paxos, когда лидер галопирует, он может ответить клиенту на запись, когда он услышал, что большинство узлов записало значение на диск. Это так же хорошо и эффективно, как вы можете получить, чтобы сохранить гарантии последовательности, которые делает Paxos.

Обычно люди используют что-то вроде paxos, например zookeeper, как внешнюю службу (выделенный кластер), чтобы обеспечить согласованность критически важной информации (кто заблокировал то, кто является лидером, кто находится в кластере, что такое конфигурация кластера) затем выполните менее строгий алгоритм с меньшими гарантиями последовательности, который зависит от специфики приложения (например, векторных часов и объединенных братьев и сестер). Краткий ebook распределенные системы для удовольствия и прибыли в качестве хорошего обзора альтернатив.

Обратите внимание, что множество баз данных конкурируют на скорости, используя рискованные значения по умолчанию, которые могут быть согласованы с контентом и могут потерять данные в сетевых разделах. Серия блога Aphry на Jepson показывает, хорошо ли известно, что системы openows несут данные. Нельзя обманывать теорему CAP; если вы настроите системы для безопасности, тогда они в конечном итоге делают о том же обмене сообщениями, и тот же диск записывает как paxos. Так что вы действительно не можете сказать, что Paxos медленно, вы должны сказать: "Часть системы, которая нуждается в согласованности в сетевых разделах, требует минимального количества сообщений и флеш-дисков за операцию, а это медленная".

Ответ 8

Paxos является оптимальным с точки зрения производительности согласованных протоколов, по крайней мере, с точки зрения количества сетевых задержек (что часто является доминирующим фактором). Очевидно, что невозможно достичь уверенности в достижении консенсуса при допуске до неудач f без единой двусторонней связи по меньшей мере (f-1) других узлов между запросом клиента и соответствующим подтверждением, а Paxos достигает этой нижней границы. Это дает жесткую привязку к задержке каждого запроса к протоколу, основанному на консенсусе, независимо от его реализации. В частности, Raft, Zab, Viewstamped Replication и все другие варианты на консенсусных протоколах имеют одинаковое ограничение производительности.

Одна вещь, которую можно улучшить со стандартного Paxos (также Raft, Zab,...), состоит в том, что есть выдающийся лидер, который в конечном итоге делает больше, чем его справедливая доля в работе, и поэтому может оказаться немного узкое место. Существует протокол, известный как "Эгалитарный Паксос", который распространяет нагрузку на нескольких лидеров, хотя он смутно усложняет ИМО, применим только к определенным доменам и по-прежнему должен подчиняться нижней границе количества раундов в каждом запросе. Более подробную информацию см. В документе "Больше консенсуса в эгалитарных парламентах" Морару и др.

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

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