Реплицированные машины состояний
Алгоритмы консенсуса обычно возникают в контексте реплицированными машинами состояний. При таком подходе машины состояний на сборке серверов вычисляют идентичные копии того же состояния и могут продолжать работать, даже если некоторые серверы не работают. Репликационные машины состояний используются для решения различных проблем с отказоустойчивостью в распределенных системах Например, крупномасштабные системы, которые имеют одного лидера кластера, такого как GFS, HDFS, и RAMCloud , обычно используют отдельную реплицированную машину состояний для управления выборами и конфигурацией хранения информации.
Репликационные машины состояний обычно реализуются используя реплицированный журнал. Каждый сервер хранит журнал, содержащий последовательность команд, конечный автомат выполняется по порядку. Каждый журнал содержит одинаковые команды в том же порядке, поэтому каждый конечный автомат обрабатывает ту же последовательность команд. Поскольку машины состояний детерминированы, каждый вычисляет такое же состояние и одну и ту же последовательность выходов. Сохранение повторяющегося журнала является задачей согласованного алгоритма. Модуль консенсуса на сервере получает команды от клиентов и добавляет их в свой журнал. Он связывается с модулями консенсуса по другим серверам, чтобы каждый журнал в конечном итоге содержал одинаковые запросы в том же порядке, даже если некоторые серверы были остановлены. После правильной репликации команд каждый серверный конечный автомат обрабатывает их в порядке журнала, а выходы возвращаются клиентам. В результате появляются серверы для формирования единого, высоконадежного конечного автомата.
Консенсусные алгоритмы для практических систем обычно имеют следующие свойства:
• Они обеспечивают безопасность (никогда не возвращают неверный результат) при всех невизантийских условиях, включая задержку сети, разделение и потерю пакетов, дублирование, и переупорядочение
• Они полностью функциональны (доступны), если любое большинство серверов работают и могут связываться друг с другом и с клиентами. Таким образом, типичный кластер из пяти серверов может себе позволить иметь два сбойных сервера. Предполагается, что серверные остановки временны, сервера могут быть перезапущены в стабильное состояние хранения и присоединиться к кластеру.
• Они не зависят от времени, чтобы обеспечить согласованность журналов.
• В общем случае команда может завершаться, когда большинство серверов кластера ответили на один раунд удаленных вызовов (медленные серверы не должны влиять на общую производительность системы).