В чем разница между Paxos и W + R ›= N в Кассандре?

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

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

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

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

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

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

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

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

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 имеет разные реализации, многие из которых предполагают менее общие отказы. Таким образом, разница между ними также зависит от предположения о возможных поддерживаемых сбоях.

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

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

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