Репликация конечного автомата
В информатике — репликация конечных автоматов ( SMR ) или подход конечных автоматов это общий метод реализации отказоустойчивой службы путем репликации серверов и координации взаимодействия клиентов с репликами серверов. Этот подход также обеспечивает основу для понимания и разработки протоколов управления репликацией. [1]
Определение проблемы
[ редактировать ]Распределенный сервис
[ редактировать ]Что касается клиентов и служб, каждая служба включает в себя один или несколько серверов и экспортирует операции, которые клиенты вызывают, отправляя запросы. Хотя использование одного централизованного сервера является самым простым способом реализации службы, полученная служба может быть настолько отказоустойчивой, насколько отказоустойчивым процессор, выполняющий этот сервер. Если такой уровень отказоустойчивости неприемлем, можно использовать несколько серверов, которые выходят из строя независимо друг от друга. Обычно реплики одного сервера выполняются на отдельных процессорах распределенной системы, а для координации взаимодействия клиентов с этими репликами используются протоколы.
Государственная машина
[ редактировать ]Для последующего обсуждения конечный автомат будет определен как следующий кортеж значений [2] (См. также машину Мили и машину Мура ):
- Набор государств
- Набор входов
- Набор выходов
- Функция перехода (Вход × Состояние → Состояние)
- Функция вывода (Вход × Состояние → Выход)
- Выдающееся государство под названием Старт.
Конечный автомат начинается с состояния, помеченного как Start. Каждый полученный ввод передается через функцию перехода и вывода для создания нового состояния и вывода. Состояние остается стабильным до тех пор, пока не будет получен новый входной сигнал, в то время как выходной сигнал передается соответствующему получателю.
Это обсуждение требует, чтобы конечный автомат был детерминированным : несколько копий одного и того же конечного автомата начинаются в состоянии «Начало», и, получив одни и те же входные данные в одном и том же порядке, они придут в одно и то же состояние, сгенерировав одинаковые выходные данные.
Обычно системы, основанные на репликации конечных автоматов, добровольно ограничивают свои реализации использованием конечных автоматов для упрощения устранения ошибок.
Отказоустойчивость
[ редактировать ]Детерминизм является идеальной характеристикой для обеспечения отказоустойчивости. Интуитивно понятно, что если существует несколько копий системы, ошибка в одной из них будет заметна как отличие состояния или вывода от других.
Небольшой вывод показывает, что минимальное количество копий, необходимое для обеспечения отказоустойчивости, равно трем; один с ошибкой, и два других, с которыми мы сравниваем состояние и выход. Двух копий недостаточно, поскольку невозможно определить, какая копия неисправна.
Дальнейшие выводы показывают, что система с тремя копиями может поддерживать не более одного сбоя (после чего она должна исправить или заменить неисправную копию). Если произойдет сбой более чем в одной копии, все три состояния и выхода могут различаться, и не будет возможности выбрать правильный.
В общем, система, поддерживающая отказы F, должна иметь 2F+1 копий (также называемых репликами). [3] Дополнительные копии используются в качестве доказательства, чтобы решить, какие из копий правильные, а какие ошибочные. Особые случаи могут улучшить эти границы. [4]
Все эти выводы предполагают, что реплики испытывают только случайные независимые сбои, такие как ошибки памяти или сбой жесткого диска. Сбои, вызванные репликами, которые пытаются солгать, обмануть или вступить в сговор, также могут быть обработаны с помощью подхода конечного автомата с отдельными изменениями.
Неисправные реплики не требуется останавливать; они могут продолжать работать, в том числе генерировать ложные или неверные выходные данные.
Особый случай: аварийный останов
[ редактировать ]Теоретически, если неисправная реплика гарантированно остановится без генерации выходных данных, требуются только реплики F+1, и клиенты могут принять первые выходные данные, сгенерированные системой. Ни одна из существующих систем не достигает этого предела, но он часто используется при анализе систем, построенных поверх уровня отказоустойчивости (поскольку уровень отказоустойчивости обеспечивает семантику отказоустойчивости для всех уровней выше него).
Особый случай: византийский провал
[ редактировать ]Ошибки, при которых реплика отправляет разные значения в разных направлениях (например, правильные выходные данные одним из своих собратьев-реплик и неправильные выходные данные другим), называются византийскими сбоями . [5] Византийские сбои могут быть случайными, ложными или злонамеренными, интеллектуальными атаками. Реплики 2F+1 с некриптографическими хэшами достаточны, чтобы пережить все незлонамеренные византийские сбои (с высокой вероятностью). Вредоносные атаки требуют криптографических примитивов для достижения 2F+1 (с использованием подписей сообщений), или можно применить некриптографические методы, но количество реплик должно быть увеличено до 3F+1. [5]
Подход конечного автомата
[ редактировать ]Предыдущее интуитивное обсуждение подразумевает простую технику реализации отказоустойчивого сервиса с точки зрения конечного автомата:
- Разместите копии конечного автомата на нескольких независимых серверах.
- Получайте клиентские запросы, интерпретируемые как входные данные для конечного автомата.
- Выберите порядок входных данных.
- Выполните входные данные в выбранном порядке на каждом сервере.
- Отвечайте клиентам с помощью выходных данных конечного автомата.
- Отслеживайте реплики на предмет различий в состоянии или выводе.
В оставшейся части статьи рассматриваются детали этой техники.
- Шаги 1 и 2 выходят за рамки этой статьи.
- Шаг 3 — критическая операция, см. Упорядочение входных данных .
- Шаг 4 описан в определении конечного автомата .
- Шаг 5, см. Отправка выходных данных .
- Шаг 6, см. Аудит и обнаружение сбоев .
В приложении содержится обсуждение типичных расширений, используемых в реальных системах, таких как ведение журнала , контрольные точки , реконфигурация и передача состояния .
Заказ входных данных
[ редактировать ]Критическим шагом в построении распределенной системы конечных автоматов является выбор порядка обработки входных данных. Поскольку все исправные реплики придут к одному и тому же состоянию и выходу, если им будут предоставлены одни и те же входные данные, крайне важно, чтобы входные данные передавались в эквивалентном порядке в каждой реплике. В литературе предложено множество решений. [2] [6] [7] [8] [9]
Видимый канал — это путь связи между двумя объектами, активно участвующими в системе (например, клиентами и серверами). Пример: клиент-сервер, сервер-сервер.
Скрытый канал — это путь связи, который не раскрывается системе.Пример: каналы клиент-клиент обычно скрыты; например, пользователи, общающиеся по телефону, или процесс, записывающий файлы на диск, которые читаются другим процессом.
частичный глобальный порядок ( причинный порядок ). Когда все пути связи являются видимыми каналами и скрытых каналов не существует, из схемы коммуникаций можно вывести [8] [10] Причинно-следственный порядок может быть установлен каждым сервером независимо. Входные данные в конечный автомат могут выполняться в причинно-следственном порядке, гарантируя согласованное состояние и выходные данные для всех исправных реплик.
В открытых системах часто встречаются скрытые каналы, и необходимо использовать более слабую форму упорядочения. Порядок входов может быть определен с использованием протокола голосования, результаты которого зависят только от видимых каналов.
Проблема голосования за одну ценность группой независимых субъектов называется консенсусом . В более широком смысле, ряд значений может быть выбран серией консенсусных примеров. Эта проблема усложняется, когда участники или их среда связи могут испытывать сбои. [3]
Входные данные можно упорядочить по их положению в серии экземпляров консенсуса ( Порядок консенсуса ). [7] Согласованный порядок может быть выведен каждым сервером независимо. Входные данные в конечный автомат могут выполняться в согласованном порядке, гарантируя согласованное состояние и выходные данные для всех исправных реплик.
- Оптимизация причинно-следственного и консенсусного порядка
- В некоторых случаях доступна дополнительная информация (например, часы реального времени). В этих случаях можно добиться более эффективного причинно-следственного или консенсусного упорядочения входных данных с меньшим количеством сообщений, меньшим количеством циклов сообщений или меньшими размерами сообщений. Подробности смотрите в ссылках [1] [4] [6] [11]
- Дальнейшие оптимизации доступны при учете семантики операций конечного автомата (например, операций чтения и записи). См. ссылки Обобщенный Паксос . [2] [12]
Отправка выходов
[ редактировать ]Клиентские запросы интерпретируются как входные данные для конечного автомата и обрабатываются в выходные данные в соответствующем порядке. Каждая реплика будет генерировать выходные данные независимо. Исправные реплики всегда будут выдавать один и тот же результат. Прежде чем будет отправлен ответ клиента, ошибочные выходы должны быть отфильтрованы. Обычно большинство реплик возвращают один и тот же результат, и этот результат отправляется в качестве ответа клиенту.
Системный сбой
[ редактировать ]- Если нет большинства реплик с одинаковыми выходными данными или если менее большинства реплик возвращают выходные данные, произошел сбой системы. Ответ клиента должен быть уникальным. Выход: FAIL.
Аудит и обнаружение сбоев
[ редактировать ]Постоянная незапланированная компрометация реплики называется сбоем . Доказательство сбоя получить сложно, так как реплика может просто медленно реагировать. [13] или даже лгать о его статусе. [5]
Исправные реплики всегда будут содержать одно и то же состояние и выдавать одни и те же выходные данные. Этот инвариант позволяет обнаруживать сбои путем сравнения состояний и выходных данных всех реплик. Обычно реплика, состояние или вывод которой отличается от большинства реплик, объявляется неисправной.
Обычной реализацией является передача контрольных сумм текущего состояния реплики и последних выходных данных между серверами. Процесс аудита на каждом сервере перезапускает локальную реплику, если обнаружено отклонение. [14] Криптографическая безопасность не требуется для контрольных сумм.
Возможно, локальный сервер скомпрометирован или процесс аудита неисправен, и реплика продолжает работать некорректно. Этот случай безопасно обрабатывается выходным фильтром, описанным ранее (см. Отправка выходных данных ).
Приложение: расширения
[ редактировать ]Входной журнал
[ редактировать ]В системе без сбоев входные данные могут быть отброшены после обработки конечным автоматом. Реалистичные развертывания должны компенсировать кратковременное безотказное поведение системы, такое как потеря сообщений, сетевые разделы и медленные процессоры. [14]
Один из методов — сохранить серию входных данных в журнале. Во время временного поведения реплики могут запрашивать копии записи журнала у другой реплики, чтобы заполнить недостающие входные данные. [7]
Обычно журнал не обязательно должен быть постоянным (он может храниться в памяти). Постоянный журнал может компенсировать длительные переходные периоды или поддерживать дополнительные функции системы, такие как контрольные точки и реконфигурация .
Контрольно-пропускные пункты
[ редактировать ]Если флажок не установлен, журнал будет расти до тех пор, пока не будут исчерпаны все доступные ресурсы хранилища. Для продолжения работы необходимо забыть записи журнала. Как правило, запись журнала может быть забыта, когда ее содержимое больше не актуально (например, если все реплики обработали входные данные, знание входных данных больше не требуется).
Распространенный метод управления размером журнала — сохранить дубликат состояния (называемый контрольной точкой ), а затем удалить все записи журнала, которые способствовали созданию контрольной точки. Это экономит место, когда дублируемое состояние меньше размера журнала.
Контрольные точки могут быть добавлены в любой конечный автомат, поддерживая дополнительный вход под названием CHECKPOINT . Каждая реплика поддерживает контрольную точку в дополнение к текущему значению состояния. Когда журнал становится большим, реплика отправляет команду CHECKPOINT точно так же, как запрос клиента. Система обеспечит обработку этой команды исправными репликами в том же порядке, после чего все записи журнала до контрольной точки могут быть удалены.
В системе с контрольными точками запросы на записи журнала, происходящие до контрольной точки, игнорируются. Реплики, которые не могут найти копии необходимой записи журнала, являются неисправными и должны повторно присоединиться к системе (см. Реконфигурация ).
Реконфигурация
[ редактировать ]Реконфигурация позволяет добавлять и удалять реплики из системы, пока запросы клиентов продолжают обрабатываться. Плановое обслуживание и сбой реплики являются распространенными примерами реконфигурации. Реконфигурация включает выход и присоединение .
Выход из дома
[ редактировать ]Когда сервер обнаруживает, что его состояние или выход неисправны (см. Аудит и обнаружение сбоев ), он может выборочно выйти из системы. Аналогично, администратор может вручную выполнить команду удаления реплики для обслуживания.
В конечный автомат добавляется новый вход под названием QUIT . [2] [6] Реплика отправляет эту команду в систему точно так же, как запрос клиента. Все исправные реплики удаляют завершающую реплику из системы при обработке этого ввода. В течение этого времени реплика может игнорировать все сообщения протокола. Если остается большинство исправных реплик, выход считается успешным. Если нет, то произошел системный сбой .
Присоединение
[ редактировать ]После выхода из строя вышедший из строя сервер может выборочно перезапуститься или повторно присоединиться к системе. Аналогичным образом администратор может добавить в группу новую реплику для увеличения емкости.
В конечный автомат добавляется новый вход под названием JOIN . Реплика отправляет эту команду в систему точно так же, как запрос клиента. Все исправные реплики добавляют в систему присоединяемый узел при обработке этого ввода. Перед присоединением новая реплика должна иметь актуальное состояние системы (см. «Передача состояния» ).
Государственная передача
[ редактировать ]Когда новая реплика становится доступной или старая реплика перезапускается, ее необходимо привести в текущее состояние перед обработкой входных данных (см. Присоединение ). Логично, что для этого необходимо применять все входные данные с самого начала системы в соответствующем порядке.
Типичные развертывания сокращают логический поток, выполняя передачу состояния самой последней контрольной точки (см. Контрольные точки ). Это предполагает прямое копирование состояния одной реплики в другую с использованием внеполосного протокола.
Контрольно-пропускной пункт может быть большим и требовать длительного периода перемещения. В течение этого времени в журнал могут быть добавлены новые входы. Если это произойдет, новая реплика также должна получить новые входные данные и применить их после получения контрольной точки. В типичных развертываниях новая реплика добавляется в качестве наблюдателя в протокол заказа перед началом передачи состояния, что позволяет новой реплике собирать входные данные в течение этого периода.
Оптимизация передачи состояний
[ редактировать ]Общие развертывания сокращают время передачи состояния, отправляя только те компоненты состояния, которые отличаются. Это требует знания внутреннего устройства конечного автомата. Поскольку передача состояния обычно представляет собой внеполосный протокол, этого предположения нетрудно достичь.
Сжатие — еще одна функция, обычно добавляемая в протоколы передачи состояний, уменьшающая общий размер передачи.
Выборы лидера (для Паксоса)
[ редактировать ]Паксос [7] представляет собой протокол для достижения консенсуса и может использоваться в качестве протокола для реализации порядка консенсуса.
Паксос требует единого лидера, чтобы обеспечить жизнеспособность. [7] То есть одна из реплик должна оставаться лидером достаточно долго, чтобы достичь консенсуса по поводу следующей операции государственной машины. На поведение системы не влияет, если лидер меняется после каждого экземпляра или если лидер меняется несколько раз за экземпляр. Единственное требование — чтобы одна реплика оставалась лидером достаточно долго, чтобы продвигать систему вперед.
Разрешение конфликтов
[ редактировать ]Вообще руководитель необходим только тогда, когда есть разногласия по поводу того, какую операцию выполнять. [11] и если эти операции каким-либо образом конфликтуют (например, если они не коммутируют). [12]
Когда предлагаются конфликтующие операции, лидер действует как единственный орган, который устанавливает порядок действий, определяя порядок операций, позволяя системе добиваться прогресса.
С Paxos несколько реплик могут одновременно считать себя лидерами. Это свойство делает выбор лидера на Паксосе очень простым, и любой алгоритм, гарантирующий «возможного лидера», будет работать.
Историческая справка
[ редактировать ]В начале 1980-х годов ряд исследователей опубликовали статьи о подходе, основанном на репликации конечных автоматов. Анита Борг описала реализацию отказоустойчивой операционной системы на основе реплицируемых конечных автоматов в статье 1983 года «Система сообщений, поддерживающая отказоустойчивость» . Лесли Лэмпорт также предложил подход на основе конечного автомата в своей статье 1984 года «Использование времени вместо тайм-аута в распределенных системах» . Позже Фред Шнайдер подробно изложил этот подход в своей статье «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие» .
Кен Бирман разработал модель виртуальной синхронизации в серии статей, опубликованных между 1985 и 1987 годами. Основная ссылка на эту работу — «Использование виртуальной синхронизации в распределенных системах» , в которой описывается Isis Toolkit, система, которая использовалась для создания Нью-Йоркской системы синхронизации. и швейцарские фондовые биржи, французская система управления воздушным движением, военный корабль AEGIS ВМС США и другие приложения.
В недавней работе Мигеля Кастро и Барбары Лисков подход к конечному автомату использовался в так называемой архитектуре «практической византийской отказоустойчивости» , которая воспроизводит особенно чувствительные сервисы с использованием версии оригинального подхода к конечному автомату Лэмпорта, но с оптимизацией, которая существенно повышает производительность.
Совсем недавно была также создана библиотека BFT-SMaRt, [15] высокопроизводительная византийская отказоустойчивая библиотека репликации конечных автоматов, разработанная на Java. Эта библиотека реализует протокол, очень похожий на PBFT, плюс дополнительные протоколы, которые предлагают передачу состояния и реконфигурацию хостов «на лету» (т. е. операции JOIN и LEAVE). BFT-SMaRt — это последняя попытка реализовать репликацию конечного автомата, которая до сих пор активно поддерживается.
Raft — алгоритм, основанный на консенсусе, был разработан в 2013 году.
По мотивам PBFT, Tendermint BFT [16] был представлен для частично асинхронных сетей и в основном используется для блокчейнов Proof of Stake.
Ссылки
[ редактировать ]- ^ Jump up to: а б Шнайдер, Фред (1990). «Реализация отказоустойчивых сервисов с использованием подхода конечного автомата: учебное пособие» (PS) . Обзоры вычислительной техники ACM . 22 (4): 299–319. CiteSeerX 10.1.1.69.1536 . дои : 10.1145/98163.98167 . S2CID 678818 .
- ^ Jump up to: а б с д Лэмпорт, Лесли (1978). «Внедрение надежных распределенных многопроцессных систем» . Компьютерные сети . 2 (2): 95–114. дои : 10.1016/0376-5075(78)90045-4 . Проверено 13 марта 2008 г.
- ^ Jump up to: а б Лэмпорт, Лесли (2004). «Нижние границы асинхронного консенсуса» .
- ^ Jump up to: а б Лэмпорт, Лесли; Майк Масса (2004). «Дешевый Паксос». Международная конференция по надежным системам и сетям, 2004 г. стр. 307–314. дои : 10.1109/DSN.2004.1311900 . ISBN 978-0-7695-2052-0 . S2CID 1325830 .
- ^ Jump up to: а б с Лэмпорт, Лесли; Роберт Шостак; Маршалл Пиз (июль 1982 г.). «Проблема византийских генералов» . Транзакции ACM в языках и системах программирования . 4 (3): 382–401. CiteSeerX 10.1.1.64.2312 . дои : 10.1145/357172.357176 . S2CID 55899582 . Проверено 2 февраля 2007 г.
- ^ Jump up to: а б с Лэмпорт, Лесли (1984). «Использование времени вместо таймаута для отказоустойчивых распределенных систем» . Транзакции ACM в языках и системах программирования . 6 (2): 254–280. CiteSeerX 10.1.1.71.1078 . дои : 10.1145/2993.2994 . S2CID 402171 . Проверено 13 марта 2008 г.
- ^ Jump up to: а б с д и Лэмпорт, Лесли (май 1998 г.). «Неполный парламент» . Транзакции ACM в компьютерных системах . 16 (2): 133–169. дои : 10.1145/279227.279229 . S2CID 421028 . Проверено 2 февраля 2007 г.
- ^ Jump up to: а б Бирман, Кеннет; Томас Джозеф (1987). «Использование виртуальной синхронизации в распределенных системах». Обзор операционных систем ACM Sigops . 21 (5): 123–138. дои : 10.1145/37499.37515 . hdl : 1813/6651 .
- ^ Лэмпсон, Батлер (1996). «Как построить высокодоступную систему, используя консенсус» . Проверено 13 марта 2008 г.
- ^ Лэмпорт, Лесли (июль 1978 г.). «Время, часы и порядок событий в распределенной системе» . Коммуникации АКМ . 21 (7): 558–565. дои : 10.1145/359545.359563 . S2CID 215822405 . Проверено 2 февраля 2007 г.
- ^ Jump up to: а б Лэмпорт, Лесли (2005). «Быстрый Паксос» .
- ^ Jump up to: а б Лэмпорт, Лесли (2005). «Общий консенсус и Паксос» .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Фишер, Майкл Дж.; Нэнси А. Линч; Майкл С. Патерсон (1985). «Невозможность распределенного консенсуса при одном ошибочном процессе» . Журнал Ассоциации вычислительной техники . 32 (2): 347–382. дои : 10.1145/3149.214121 . S2CID 207660233 . Проверено 13 марта 2008 г.
- ^ Jump up to: а б Чандра, Тушар; Роберт Гриземер; Джошуа Редстоун (2007). «Паксос ожил». Материалы двадцать шестого ежегодного симпозиума ACM по принципам распределенных вычислений (PDF) . стр. 398–407. дои : 10.1145/1281100.1281103 . ISBN 9781595936165 . S2CID 207164635 .
- ^ БФТ-СМаРТ . Репозиторий Google Code для библиотеки репликации BFT-SMaRt.
- ^ Бухман, Э.; Квон, Дж.; Милошевич, З. (2018). «Последние сплетни о консенсусе BFT». arXiv : 1807.04938 [ cs.DC ].
Внешние ссылки
[ редактировать ]- Видео о реплицируемых конечных автоматах на MIT TechTV
- Apache Bookkeeper — служба реплицированного журнала, которую можно использовать для создания реплицируемых конечных автоматов.