Какая разница между Paxos и W + R >= N в Кассандре?

Ответ 1

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

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

Рассматривая описания, такие как https://cloudant.com/blog/dynamo-and-couchdb-clusters/, похоже, что Dynamo не основано на инфраструктуре, которая гарантирует согласованность для своей системы кворума - так что это очень умные или режущие углы? Согласно http://muratbuffalo.blogspot.co.uk/2010/11/dynamo-amazons-highly-available-key.html, система "Динамо" подчеркивает доступность до степени согласованности. В тезисе говорится: "Динамо жертвует согласованностью при определенных сценариях сбоя", Фактически, позже становится ясно, что "Динамо" жертвует согласованностью даже при отсутствии сбоев: "Динамо" может стать непоследовательным в присутствии множества одновременных запросов на запись, поскольку реплики могут расходиться из-за множества координаторов ". (конечная цитата)

Таким образом, похоже, что в случае кворумов, реализованных в "Динамо" , Paxos обеспечивает более надежные гарантии.

Ответ 2

Да, Paxos предоставляет гарантии, которые не предоставляются системами типа Dynamo и их кворумами для чтения и записи. Разница заключается в том, как обрабатываются отказы и что происходит во время записи. После успешной записи обе системы ведут себя одинаково. Данные будут сохранены и доступны для чтения после этого (до перезаписывания или удаления) и т.д.

Разница возникает во время записи и после сбоев. Пока вы не получите успешный ответ от узлов W при написании чего-либо в последовательных системах, тогда данные могут быть записаны на некоторые узлы, а не на другие, и нет гарантии, что вся система согласна с текущим значением. Если вы попытаетесь прочитать данные в этот момент, некоторые клиенты могут вернуть новые данные и вернуть старые данные. Другими словами, система не сразу согласована. Это связано с тем, что записи не являются атомарными по узлам в этих системах. Как правило, механизмы "исцеляют" несогласованность, подобную этой, и "в конечном итоге" система снова станет последовательной (т.е. Чтения снова будут всегда возвращать одно и то же значение, пока не будет написано что-то новое). Именно по этой причине их часто называют "в конечном итоге последовательными". Несоответствия могут (и будут) появляться, но они всегда будут устранены и согласованы в конечном итоге.

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

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

Ответ 3

Paxos и кворум W + R > N пытаются решить несколько разные проблемы. Paxos обычно описывается как способ репликации конечного автомата, но на самом деле это скорее распределенный журнал: каждый элемент, записанный в журнал, получает индекс, а на разных серверах в конечном итоге хранятся те же элементы журнала + их индекс. (Репликационный конечный автомат может быть достигнут путем записи в журнал входов на конечный автомат, и каждый сервер повторяет конечный автомат на согласованных входах в соответствии с их индексом). Вы можете больше узнать о Paxos в блоге, я написал здесь.

Кворум W + R > N решает проблему совместного использования одного значения между несколькими серверами. В академиях это называется "общий регистр". Общий регистр имеет две операции: чтение и запись, где мы ожидаем, что чтение вернет значение предыдущей записи.

Итак, Paxos и W + R > N кворум живут в разных доменах и имеют разные свойства (например, Paxos сохраняет упорядоченный список элементов). Однако Paxos можно использовать для реализации общего регистра, а кворум W + R > N можно использовать для реализации распределенного журнала (хотя и очень неэффективно).

Говоря все вышеизложенное, иногда кворумы W + R > N не реализованы в их "полностью надежном" способе, так как для этого потребуется более одного раунда связи. Таким образом, в системах с низкой задержкой возможно, что их реализация W + R > N кворумов обеспечивает более слабые свойства (например, конфликтующие значения могут существовать).

Подводя итог, теоретически, Paxos и W + R > N могут достичь тех же целей. Практически это было бы очень неэффективно, и каждый из них был бы лучше для чего-то другого. Более того, W + R > N не всегда реализуется полностью, тем самым сканируя некоторые свойства согласованности для скорости.

Обновление: Paxos поддерживает очень общую модель отказа: сообщения могут быть удалены, узлы могут аварийно завершаться и перезапускаться. Схема кворума W + R > N имеет множество реализаций, многие из которых предполагают меньше общих отказов. Таким образом, разница между ними также зависит от предположения о возможных отказах, которые поддерживаются.

Ответ 4

Нет никакой разницы. Определение кворума гласит, что любое пересечение двух кворумов не пусто. Простой мажоритарный кворум является примером НЕ определения. Взгляните на статью доктора Лампорта "Вертикальный Паксос", где он дал другую возможную конфигурацию кворумов.

Multi-decree paxos protocol (AKA Multi-Paxos), в устойчивом состоянии это всего лишь двухфазное принятие. Изменение номера бюллетеней необходимо только тогда, когда лидер не работает.

Протокол репликации Zookeeper (ZAB) и RAFT основаны на Paxos. Различия в обнаружении ошибок и переходе после отказа лидера.