WikiDer > Репликация конечного автомата

State machine replication

В Информатика, репликация конечного автомата или же подход с конечным автоматом - это общий метод реализации отказоустойчивой службы путем репликации серверов и координации взаимодействия клиентов с репликами серверов. Этот подход также обеспечивает основу для понимания и разработки протоколов управления репликацией.[1]

Определение проблемы

Распределенные услуги

Распределенное программное обеспечение часто структурировано с точки зрения клиентов и услуг. Каждая служба состоит из одного или нескольких серверов и экспортирует операции, которые клиенты вызывают, отправляя запросы. Хотя использование одного централизованного сервера является самым простым способом реализации службы, полученная в результате служба может быть отказоустойчивой только так, как процессор, выполняющий этот сервер. Если такой уровень отказоустойчивости неприемлем, необходимо использовать несколько серверов, которые выходят из строя независимо.[нужна цитата] Обычно реплики одного сервера выполняются на отдельных процессорах распределенной системы, и протоколы используются для координации взаимодействия клиента с этими репликами. Физическая и электрическая изоляция процессоров в распределенной системе гарантирует независимость отказов серверов, если это необходимо.

Государственный аппарат

Основная статья: Конечный автомат

Для последующего обсуждения Государственный аппарат будет определен как следующий набор значений [2] (Смотрите также Мучная машина и Машина Мура):

  • Набор состояния
  • Набор Входы
  • Набор Выходы
  • Функция перехода (Вход × Состояние → Состояние)
  • Функция вывода (Вход × Состояние → Выход)
  • Выдающееся государство под названием Старт.

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

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

Обычно системы, основанные на репликации конечного автомата, добровольно ограничивают свои реализации на использование конечные автоматы чтобы упростить восстановление после ошибок.

Отказоустойчивость

Детерминизм - идеальная характеристика для обеспечения отказоустойчивости. Интуитивно понятно, что если существует несколько копий системы, ошибка в одной из них будет заметна как отличие состояния или вывода от других.

Небольшой вычет показывает, что минимальное количество копий, необходимое для обеспечения отказоустойчивости, составляет три; один имеет неисправность, а два других, с которыми мы сравниваем State и Output. Двух копий недостаточно, так как невозможно определить, какая из них неисправна.

Дальнейший вывод показывает, что система с тремя копиями может поддерживать не более одного отказа (после чего она должна исправить или заменить неисправную копию). Если произойдет сбой более чем одной копии, все три состояния и выхода могут отличаться, и не будет возможности выбрать, какое из них является правильным.

В общем, система, поддерживающая F-отказы, должна иметь 2F + 1 копии (также называемые репликами).[3] Дополнительные копии используются в качестве доказательства, чтобы решить, какие из копий верны, а какие нет. Частные случаи могут улучшить эти оценки.[4]

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

Неудачные реплики останавливать не нужно; они могут продолжать работать, в том числе генерировать ложные или неправильные выходные сигналы.

Особый случай: отказоустойчивый

Теоретически, если отказавшая реплика гарантированно остановится без генерации выходных данных, потребуется только F + 1 реплик, и клиенты могут принять первый выходной сигнал, сгенерированный системой. Ни одна из существующих систем не достигает этого предела, но он часто используется при анализе систем, построенных на вершине отказоустойчивого уровня (поскольку отказоустойчивый уровень обеспечивает семантику отказоустойчивости для всех уровней над ним).

Особый случай: византийская неудача

Вызываются ошибки, при которых реплика отправляет разные значения в разных направлениях (например, правильные выходные данные для некоторых других реплик и неправильные выходы для других). Византийские неудачи.[5] Византийские сбои могут быть случайными, ложными или злонамеренными интеллектуальными атаками. 2F + 1 реплик с некриптографическими хэшами достаточно, чтобы пережить все незлонамеренные византийские сбои (с высокой вероятностью). Для злонамеренных атак требуются криптографические примитивы для достижения 2F + 1 (с использованием подписей сообщений), или могут применяться некриптографические методы, но количество реплик должно быть увеличено до 3F + 1.[5]

Подход с использованием государственной машины

Предыдущее интуитивное обсуждение подразумевает простой метод реализации отказоустойчивого сервиса в терминах конечного автомата:

  1. Разместите копии конечного автомата на нескольких независимых серверах.
  2. Получать клиентские запросы, интерпретируемые как входные данные для конечного автомата.
  3. Выберите порядок входов.
  4. Выполните входы в выбранном порядке на каждом сервере.
  5. Отвечайте клиентам с помощью выходных данных конечного автомата.
  6. Отслеживайте реплики на предмет различий в состоянии или выводе.

В оставшейся части этой статьи подробно рассматривается этот метод.

Приложение содержит обсуждение типичных расширений, используемых в реальных системах, таких как логирование, Контрольно-пропускные пункты, Реконфигурация, и State Transfer.

Заказ входов

Критическим шагом в построении распределенной системы конечных автоматов является выбор порядка обработки входных данных. Поскольку все исправные реплики прибудут в одно и то же состояние и выход при одинаковых входных данных, обязательно, чтобы входные данные подавались в эквивалентном порядке для каждой реплики. В литературе было предложено много решений.[2][6][7][8][9]

А Видимый канал это канал связи между двумя объектами, активно участвующими в системе (например, клиентами и серверами). Пример: клиент к серверу, сервер к серверу

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

Когда все пути связи являются видимыми и не существуют скрытых каналов, частичный глобальный порядок (Причинный порядок) может быть выведено из схемы коммуникации.[8][10] Причинный порядок может быть получен независимо каждым сервером. Входы в конечный автомат могут выполняться в причинном порядке, гарантируя согласованное состояние и выход для всех исправных реплик.

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

Проблема голосования за Один значение группой независимых сущностей называется Консенсус. По расширению, серии значений может быть выбрано серией консенсусных примеров. Эта проблема усложняется, когда участники или их среда общения могут столкнуться с ошибками.[3]

Входы могут быть упорядочены по их положению в серии экземпляров консенсуса (Консенсусный порядок).[7] Порядок согласования может быть получен независимо каждым сервером. Входы в конечный автомат могут выполняться в согласованном порядке, гарантируя согласованное состояние и выходные данные для всех исправных реплик.

Оптимизация причинно-следственной связи и согласованного порядка
В некоторых случаях доступна дополнительная информация (например, часы реального времени). В этих случаях можно достичь более эффективного причинно-следственного или консенсусного упорядочения для входных данных с уменьшенным количеством сообщений, меньшим количеством раундов сообщений или меньшими размерами сообщений. Смотрите ссылки для деталей [1][4][6][11]
Дальнейшие оптимизации доступны, когда учитывается семантика операций конечного автомата (например, операции чтения и записи). См. Ссылки Обобщенный Паксос.[2][12]

Отправка результатов

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

Системная ошибка

Если нет большинства реплик с одним и тем же выходом, или если меньше, чем большинство реплик возвращает выход, произошел сбой системы. Ответ клиента должен быть уникальным. Выход: FAIL.

Аудит и обнаружение сбоев

Постоянная незапланированная компрометация реплики называется Отказ. Доказательства сбоя получить трудно, поскольку реплика может просто медленно реагировать,[13] или даже солгать о своем статусе.[5]

Неисправные реплики всегда будут содержать одно и то же состояние и давать одинаковые выходные данные. Этот инвариант позволяет обнаруживать отказы путем сравнения состояний и выходных данных всех реплик. Обычно реплика с состоянием или выходом, которая отличается от большинства реплик, объявляется неисправной.

Распространенная реализация - передача контрольных сумм текущего состояния реплики и недавних выходных данных между серверами. Процесс аудита на каждом сервере перезапускает локальную реплику, если обнаружено отклонение.[14] Криптографическая безопасность не требуется для контрольных сумм.

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

Приложение: Расширения

Журнал ввода

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

Один из способов - сохранить серию входных данных в журнале. Во время временного поведения реплики могут запрашивать копии записи журнала из другой реплики, чтобы заполнить недостающие входные данные.[7]

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

Контрольно-пропускные пункты

Если не установить этот флажок, журнал будет расти до тех пор, пока не исчерпает все доступные ресурсы хранения. Для продолжения работы необходимо забыть записи журнала. Как правило, запись в журнале может быть забыта, когда ее содержимое больше не актуально (например, если все реплики обработали вход, знание этого входа больше не требуется).

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

Контрольные точки могут быть добавлены в любой конечный автомат, поддерживая дополнительный ввод, называемый ПРОПУСКНОЙ ПУНКТ. Каждая реплика поддерживает контрольную точку в дополнение к текущему значению State. Когда журнал становится большим, реплика отправляет команду CHECKPOINT точно так же, как запрос клиента. Система гарантирует, что исправные реплики обрабатывают эту команду в том же порядке, после чего все записи журнала до контрольной точки могут быть отброшены.

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

Реконфигурация

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

Выход

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

В конечный автомат добавлен новый ввод под названием ПОКИДАТЬ.[2][6] Реплика передает эту команду системе точно так же, как запрос клиента. Все исправные реплики удаляют покидающую реплику из системы после обработки этого ввода. В это время реплика может игнорировать все сообщения протокола. Если остается большинство исправных реплик, завершение работы выполнено успешно. Если нет, то есть Системная ошибка.

Присоединение

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

В конечный автомат добавлен новый ввод под названием ПРИСОЕДИНИТЬСЯ. Реплика передает эту команду системе точно так же, как запрос клиента. Все исправные реплики добавляют узел присоединения к системе после обработки этого Ввода. Новая реплика должна соответствовать состоянию системы перед присоединением (см. State Transfer).

State Transfer

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

Типичные развертывания сокращают логический поток, выполняя передачу состояния самой последней контрольной точки (см. Контрольно-пропускные пункты). Это включает прямое копирование состояния одной реплики в другую с использованием внеполосного протокола.

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

Оптимизация передачи состояния
Обычные развертывания сокращают время передачи состояния, отправляя только компоненты состояния, которые отличаются. Это требует знания внутреннего устройства State Machine. Поскольку передача состояния обычно является внеполосным протоколом, этого предположения нетрудно достичь.
Сжатие - это еще одна функция, обычно добавляемая в протоколы передачи состояния, уменьшающая общий размер передачи.

Выборы лидера (для Paxos)

Паксос[7] является протоколом для достижения консенсуса и может использоваться в качестве протокола для реализации консенсусного порядка.

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

Решение конфликта
В общем, лидер нужен только тогда, когда есть разногласия по поводу того, какую операцию выполнять,[11] и если эти операции каким-то образом конфликтуют (например, если они не работают).[12]
Когда предлагаются конфликтующие операции, руководитель действует как единый авторитет, чтобы установить рекорд, определяя порядок операций, позволяя системе добиваться прогресса.

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

Историческое прошлое

В начале 1980-х годов ряд исследователей опубликовали статьи о подходе с тиражированием конечного автомата. Анита Борг описал реализацию отказоустойчивой операционной системы на основе реплицированных конечных автоматов в статье 1983 г. «Система сообщений, поддерживающая отказоустойчивость». Лесли Лэмпорт также предложил подход конечного автомата в своей статье 1984 г. «Использование времени вместо тайм-аута в распределенных системах». Фред Шнайдер позже разработал этот подход в своей статье. «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие».

Кен Бирман разработал виртуальная синхронность модели в серии статей, опубликованных между 1985 и 1987 гг. «Использование виртуальной синхронизации в распределенных системах», который описывает Isis Toolkit, систему, которая использовалась для создания Нью-Йоркской и Швейцарской фондовых бирж, французской системы управления воздушным движением, военного корабля AEGIS ВМС США и других приложений.

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

Совсем недавно была также создана библиотека BFT-SMaRt,[15] высокопроизводительная византийская отказоустойчивая библиотека репликации конечного автомата, разработанная на Java. Эта библиотека реализует протокол, очень похожий на PBFT, плюс дополнительные протоколы, которые предлагают передачу состояния и изменение конфигурации хостов на лету (т.е. операции JOIN и LEAVE). BFT-SMaRt - это последняя попытка реализовать репликацию конечного автомата, которая все еще активно поддерживается.

Плоталгоритм, основанный на консенсусе, был разработан в 2013 году.

Мотивировано PBFT, Tendermint BFT[16] был введен для частично асинхронных сетей и в основном используется для блокчейнов Proof of Stake.

Рекомендации

  1. ^ а б Шнайдер, Фред (1990). «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие» (PS). Опросы ACM Computing. 22 (4): 299–319. CiteSeerX 10.1.1.69.1536. Дои:10.1145/98163.98167.
  2. ^ а б c d Лэмпорт, Лесли (1978). «Внедрение надежных распределенных многопроцессорных систем». Компьютерная сеть. 2 (2): 95–114. Дои:10.1016/0376-5075(78)90045-4. Получено 2008-03-13.
  3. ^ а б Лэмпорт, Лесли (2004). «Нижние границы для асинхронного консенсуса».
  4. ^ а б Лэмпорт, Лесли; Майк Масса (2004). Дешевые Паксо. Труды Международной конференции по надежным системам и сетям (DSN 2004). С. 307–314. Дои:10.1109 / DSN.2004.1311900. ISBN 978-0-7695-2052-0.
  5. ^ а б c Лэмпорт, Лесли; Роберт Шостак; Маршалл Пиз (июль 1982 г.). "Проблема византийских генералов". Транзакции ACM по языкам и системам программирования. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. Дои:10.1145/357172.357176. Получено 2007-02-02.
  6. ^ а б c Лэмпорт, Лесли (1984). «Использование времени вместо тайм-аута для отказоустойчивых распределенных систем». Транзакции ACM по языкам и системам программирования. 6 (2): 254–280. CiteSeerX 10.1.1.71.1078. Дои:10.1145/2993.2994. Получено 2008-03-13.
  7. ^ а б c d е Лэмпорт, Лесли (май 1998 г.). "Неполный парламент". ACM-транзакции в компьютерных системах. 16 (2): 133–169. Дои:10.1145/279227.279229. Получено 2007-02-02.
  8. ^ а б Бирман, Кеннет; Томас Джозеф (1987). «Использование виртуальной синхронности в распределенных системах». Материалы 11-го симпозиума ACM по принципам операционных систем (SOSP). 21 (5): 123. Дои:10.1145/37499.37515. HDL:1813/6651.
  9. ^ Лэмпсон, Батлер (1996). «Как построить высокодоступную систему, используя консенсус». Получено 2008-03-13.
  10. ^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе». Коммуникации ACM. 21 (7): 558–565. Дои:10.1145/359545.359563. Получено 2007-02-02.
  11. ^ а б Лэмпорт, Лесли (2005). «Быстрый Паксос».
  12. ^ а б Лэмпорт, Лесли (2005). «Обобщенный консенсус и Паксос». Цитировать журнал требует | журнал = (помощь)
  13. ^ Фишер, Майкл Дж .; Нэнси А. Линч; Майкл С. Патерсон (1985). «Невозможность распределенного консенсуса с одним ошибочным процессом». Журнал Ассоциации вычислительной техники. 32 (2): 347–382. Дои:10.1145/3149.214121. Получено 2008-03-13.
  14. ^ а б Чандра, Тушар; Роберт Гриземер; Джошуа Редстоун (2007). Paxos Made Live - инженерная перспектива (PDF). PODC '07: 26-й симпозиум ACM по принципам распределенных вычислений. С. 398–407. Дои:10.1145/1281100.1281103. ISBN 9781595936165.
  15. ^ БФТ-СМАРТ. Репозиторий Google Code для библиотеки репликации BFT-SMaRt.
  16. ^ Buchman, E .; Kwon, J .; Милошевич, З. (2018). «Последние слухи о консенсусе BFT». arXiv:1807.04938 [cs.DC].

внешняя ссылка