Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение проблемы [ править ]

Распределенные службы [ править ]

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

Конечный автомат [ править ]

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

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

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

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

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

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

Отказоустойчивость [ править ]

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

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

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

Как правило, система, поддерживающая 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]

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

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

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

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

Системный сбой [ править ]

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

Аудит и обнаружение сбоев [ править ]

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

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

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

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

Приложение: Расширения [ править ]

Журнал ввода [ править ]

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

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

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

Контрольные точки [ править ]

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

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

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

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

Реконфигурация [ править ]

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

Выход [ править ]

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

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

Присоединение [ править ]

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

В конечный автомат добавляется новый ввод под названием JOIN . Реплика передает эту команду системе точно так же, как запрос клиента. Все исправные реплики добавляют узел присоединения к системе после обработки этого Ввода. Новая реплика должна соответствовать состоянию системы перед присоединением (см. « Передача состояния» ).

State Transfer [ править ]

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

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

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

Оптимизация передачи состояния [ править ]

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

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

Выборы лидера (для Paxos) [ править ]

Paxos [7] - это протокол для достижения консенсуса, который может использоваться в качестве протокола для реализации Consensus Order.

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

Разрешение конфликтов [ править ]

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

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

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

Историческая справка [ править ]

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

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

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

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

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

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Реплицированное видео конечных автоматов на MIT TechTV
  • Apache Bookkeeper - реплицированная служба журналов, которую можно использовать для создания реплицированных конечных автоматов.