Распределенная фиксация и консенсус

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

Definition

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

Scope

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

Core questions

• Как двухфазная фиксация обеспечивает атомарную фиксацию между узлами?
• Почему двухфазная фиксация может блокироваться и как трехфазная фиксация решает эту проблему?
• Как протоколы консенсуса, такие как Paxos и Raft, поддерживают согласованность реплик?
• Как консенсус связан с атомарной фиксацией в реплицированных базах данных?
• Как сбои и сетевые разделения влияют на гарантии, предоставляемые этими протоколами?

Key concepts

• атомарная фиксация
• двухфазная фиксация (2PC)
• координатор и участники
• блокировка и проблема отказа координатора
• трехфазная фиксация (3PC)
• Paxos
• Raft
• реплицированный журнал / репликация конечного автомата

Key theories

Двухфазная фиксация

Координатор просит всех участников подготовиться (проголосовать) и затем, только если все проголосуют «да», приказывает им зафиксировать; протокол гарантирует атомарность, но блокируется, если координатор выходит из строя, пока участники находятся в неопределенном состоянии.

Неблокирующая фиксация

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

Консенсус для реплицированного состояния

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

Clinical relevance

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

History

Двухфазная фиксация была ранним стандартом для распределенной атомарности; Скин и Стоунбрейкер проанализировали ее блокирующее поведение в 1983 году и мотивировали создание трехфазной фиксации. Paxos Лэмпорта (опубликован в 1998 году) обеспечил отказоустойчивый консенсус, а Raft (Онгаро и Остерхаут, 2014) предложил более понятную альтернативу; оба теперь лежат в основе репликации в широко используемых распределенных базах данных.

Debates

Атомарная фиксация против консенсуса для реплицированных транзакций

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

Key figures

• Leslie Lamport
• Dale Skeen
• Diego Ongaro
• John Ousterhout

Seminal works

• lamport1998
• skeen1983
• ongaro2014

Frequently asked questions

Почему двухфазная фиксация блокируется, и является ли это проблемой?

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

Чем консенсус отличается от атомарной фиксации?

Атомарная фиксация требует единогласного согласия на фиксацию — любой единственный голос «против» или сбой может привести к отмене. Консенсус требует согласия только большинства по значению и может продолжать работу, несмотря на сбой меньшинства узлов. Базы данных используют атомарную фиксацию для транзакций между шардами и консенсус для поддержания согласованности реплик каждого шарда.