Плот (алгоритм)
 Талисман алгоритма консенсуса Raft. | |
| Сорт | Алгоритм консенсуса |
|---|---|
Raft — это консенсусный алгоритм, разработанный как альтернатива Paxos семейству алгоритмов . Он должен был быть более понятным, чем Paxos, за счет разделения логики, но формально он также доказал свою безопасность и предлагает некоторые дополнительные функции. [1] Raft предлагает общий способ распределения конечного автомата по кластеру вычислительных систем, гарантируя, что каждый узел в кластере согласовывает одну и ту же серию переходов состояний. Он имеет ряд эталонных реализаций с открытым исходным кодом, а также реализации с полной спецификацией на Go , C++ , Java и Scala . [2] Он назван в честь надежного, реплицируемого, избыточного и отказоустойчивого. [3]
Raft не является византийским отказоустойчивым алгоритмом (BFT); узлы доверяют избранному лидеру. [1]
Основы
[ редактировать ]Рафт достигает консенсуса через избранного лидера. Сервер в кластере raft является либо лидером , либо последователем и может быть кандидатом в конкретном случае выборов (лидер недоступен). Лидер отвечает за репликацию журналов для последователей. Он регулярно информирует подписчиков о своем существовании, отправляя сердцебиение. У каждого ведомого устройства есть тайм-аут (обычно от 150 до 300 мс), в течение которого он ожидает подтверждения от лидера. Тайм-аут сбрасывается при получении контрольного сигнала. Если пульс не получен, ведомый меняет свой статус на кандидата и начинает выборы лидера. [1] [4]
Подход к проблеме консенсуса в Raft
[ редактировать ]Raft реализует консенсус посредством лидерского подхода. В кластере есть один и только один избранный лидер, который несет полную ответственность за управление репликацией журналов на других серверах кластера. Это означает, что лидер может принимать решения о размещении новых записей и организации потока данных между ним и другими серверами, не консультируясь с другими серверами. Лидер возглавляет до тех пор, пока он не выйдет из строя или не отключится, и в этом случае избирается новый лидер.
Проблема консенсуса разлагается в Raft на две относительно независимые подзадачи, перечисленные ниже.
Выборы лидера
[ редактировать ]Когда существующий лидер выходит из строя или когда алгоритм инициализируется, необходимо выбрать нового лидера.
В этом случае новый терм в кластере начинается . Срок — это произвольный период времени на сервере, на который необходимо избрать нового лидера. Каждый срок начинается с выборов лидера. Если выборы завершены успешно (т.е. избран единственный лидер), срок полномочий продолжается с обычными операциями, организованными новым лидером. Если выборы провалились, начинается новый срок с новыми выборами.
Выборы лидера запускаются сервером - кандидатом . Сервер становится кандидатом, если он не получает сообщений от лидера в течение периода, называемого тайм-аутом выборов , поэтому он предполагает, что действующего лидера больше нет. Он начинает выборы с увеличения счетчика сроков, голосования за себя как нового лидера и отправки сообщения всем остальным серверам с просьбой проголосовать. Сервер будет голосовать только один раз за срок, в порядке очереди. Если кандидат получает сообщение с другого сервера с номером срока, превышающим текущий срок кандидата, то избрание кандидата считается проигранным, и кандидат превращается в последователя и признает лидера легитимным. Если кандидат получает большинство голосов, то он становится новым лидером. Если ни того, ни другого не происходит, например, из-за разделения голосов, то начинается новый срок и новые выборы. [1]
Raft использует случайный тайм-аут выборов, чтобы гарантировать быстрое решение проблем с разделением голосов. Это должно снизить вероятность разделения голосов, поскольку серверы не станут кандидатами одновременно: один сервер истечет по тайм-ауту, выиграет выборы, затем станет лидером и отправит контрольные сообщения на другие серверы, прежде чем кто-либо из последователей сможет стать кандидатом. . [1]
Репликация журналов
[ редактировать ]Лидер отвечает за репликацию журнала. Он принимает запросы клиентов. Каждый клиентский запрос состоит из команды, которую должны выполнить реплицированные конечные автоматы в кластере. После добавления в журнал лидера в качестве новой записи каждый запрос пересылается подписчикам в виде сообщений AppendEntries. В случае недоступности последователей лидер повторяет сообщения AppendEntries в течение неопределенного времени, пока запись журнала в конечном итоге не будет сохранена всеми последователями.
Как только лидер получает подтверждение от более чем половины своих последователей о том, что запись была реплицирована, лидер применяет запись к своему локальному конечному автомату, и запрос считается зафиксированным . [1] [4] Это событие также фиксирует все предыдущие записи в журнале лидера. Как только ведомый узнает, что запись в журнале зафиксирована, он применяет ее к своему локальному конечному автомату. Это обеспечивает согласованность журналов между всеми серверами кластера и соблюдение правила безопасности сопоставления журналов.
В случае сбоя лидера журналы могут остаться противоречивыми, при этом некоторые журналы старого лидера не будут полностью реплицированы через кластер. Затем новый лидер будет устранять несогласованность, заставляя последователей дублировать свой собственный журнал. Для этого лидер для каждого из своих последователей сравнит свой журнал с журналом последователя, найдет последнюю запись, в которой они согласны, затем удалит все записи, следующие после этой критической записи в журнале последователя, и заменит ее своим. собственные записи журнала. Этот механизм восстановит согласованность журналов в кластере, подверженном сбоям.
Безопасность
[ редактировать ]Правила безопасности на Рафте
[ редактировать ]Raft гарантирует каждое из этих свойств безопасности:
- Безопасность выборов: в течение определенного срока может быть избран не более одного лидера.
- Только добавление лидера: лидер может добавлять в свои журналы только новые записи (он не может ни перезаписывать, ни удалять записи).
- Сопоставление журналов: если два журнала содержат запись с одинаковым индексом и термином, то журналы идентичны во всех записях до заданного индекса.
- Полнота лидера: если запись в журнале зафиксирована в определенный период, то она будет присутствовать в журналах лидеров, начиная с этого периода.
- Безопасность конечного автомата: если сервер применил определенную запись журнала к своему конечному автомату, то никакой другой сервер не может применить другую команду для того же журнала.
Первые четыре правила гарантируются деталями алгоритма, описанного в предыдущем разделе. Безопасность государственной машины гарантируется ограничением избирательного процесса.
Безопасность государственной машины
[ редактировать ]Это правило обеспечивается простым ограничением: кандидат не может победить на выборах, если его журнал не содержит всех зафиксированных записей. Чтобы быть избранным, кандидат должен связаться с большей частью кластера, и, учитывая правила фиксации журналов, это означает, что каждая зафиксированная запись должна присутствовать по крайней мере на одном из серверов, с которыми связываются кандидаты.
Raft определяет, какой из двух журналов (хранящихся на двух разных серверах) является более актуальным, сравнивая индексный термин последних записей в журналах. Если в журналах есть последняя запись с разными терминами, то журнал с более поздним сроком является более актуальным. Если журналы заканчиваются одним и тем же термином, то тот журнал, который длиннее, является более актуальным.
В Raft запрос кандидата к избирателю включает информацию о журнале кандидата. Если его собственный журнал более актуален, чем журнал кандидата, избиратель отказывает кандидату в голосовании. Эта реализация обеспечивает правило безопасности конечного автомата.
Сбой подписчика
[ редактировать ]В случае сбоя подписчика запросы AppendEntries и голосования , отправленные другими серверами, не будут выполнены. Такие сбои обрабатываются серверами, которые бесконечно пытаются связаться со сбитым последователем. Если ведомый перезапустится, ожидающие запросы будут завершены. Если запрос уже был учтен до сбоя, перезапущенный фолловер его просто проигнорирует.
Сроки и доступность
[ редактировать ]В Raft время имеет решающее значение для выбора и поддержания постоянного лидера с течением времени, чтобы обеспечить идеальную доступность кластера. Стабильность обеспечивается соблюдением временных требований алгоритма:
BroadcastTime << ElectionTimeout << MTBF
- BroadcastTime — это среднее время, необходимое серверу для отправки запроса каждому серверу в кластере и получения ответов. Это связано с используемой инфраструктурой.
- MTBF (среднее время между сбоями) — это среднее время между сбоями сервера. Это также связано с инфраструктурой.
- ElectionTimeout аналогичен описанному в разделе «Выборы лидера». Это то, что должен выбрать программист.
Типичные значения для этих значений могут составлять от 0,5 до 20 мс для BroadcastTime , что означает, что программист устанавливает значение ElectionTimeout где-то между 10 и 500 мс. Между сбоями одного сервера может пройти несколько недель или месяцев, что означает, что значений достаточно для стабильного кластера.
Производственное использование Плота
[ редактировать ]- CockroachDB использует Raft на уровне репликации. [5]
- Etcd использует Raft для управления высокодоступным реплицированным журналом. [6]
- Hazelcast использует Raft для предоставления своей подсистемы CP — строго согласованного уровня для распределенных структур данных. [7]
- MongoDB использует вариант Raft в наборе репликации.
- Neo4j использует Raft для обеспечения согласованности и безопасности. [8]
- RabbitMQ использует Raft для реализации устойчивых реплицируемых очередей FIFO. [9]
- ScyllaDB использует Raft для метаданных (изменения схемы и топологии) [10]
- Splunk Enterprise использует Raft в кластере Search Head (SHC) [11]
- TiDB использует Raft с механизмом хранения TiKV. [12]
- YugabyteDB использует Raft в репликации DocDB [13]
- ClickHouse использует Raft для собственной реализации ZooKeeper . сервиса, подобного [14]
- Redpanda использует алгоритм консенсуса Raft для репликации данных. [15]
- Apache Kafka Raft (KRaft) использует Raft для управления метаданными. [16]
- NATS Messaging использует алгоритм консенсуса Raft для управления кластером Jetstream и репликации данных. [17]
- Camunda использует алгоритм консенсуса Raft для репликации данных. [18]
Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж Онгаро, Диего; Оустерхаут, Джон (2013). «В поисках понятного алгоритма консенсуса» (PDF) .
- ^ «Алгоритм консенсуса Raft» . 2014.
- ^ Почему название «Плот»?
- ^ Jump up to: а б Бен Б. Джонсон. «Плот: понятный распределенный консенсус» . Веб-сайт «Тайная жизнь данных» . Проверено 4 августа 2021 г.
- ^ «Уровень репликации | Документы CockroachDB» . www.cockroachlabs.com . Проверено 21 июня 2022 г.
- ^ «Рафт README» . github.com . Проверено 25 августа 2022 г.
- ^ «Подсистема КП» . docs.hazelcast.com . Проверено 24 декабря 2022 г.
- ^ «Лидерство, маршрутизация и балансировка нагрузки — Руководство по эксплуатации» . Платформа графических данных Neo4j . Проверено 30 ноября 2022 г.
- ^ «Очереди кворума» . КроликMQ . Проверено 14 декабря 2022 г.
- ^ «Путь ScyllaDB к строгой согласованности: новая веха» .
- ^ «Решение проблем с плотом» . Спланк . 24 августа 2022 г. Проверено 24 августа 2022 г.
- ^ «Плот и высокая доступность» . ПингКАП . 01.09.2021 . Проверено 21 июня 2022 г.
- ^ «Репликация | Документы YugabyteDB» . www.yugabyte.com . Проверено 19 августа 2022 г.
- ^ «КликХаус Хранитель» . clickhouse.com . Проверено 26 апреля 2023 г.
- ^ «Алгоритм консенсуса Raft» .
- ^ «Обзор KRaft | Слитная документация» . docs.confluent.io . Проверено 13 апреля 2024 г.
- ^ «Кластеризация JetStream» .
- ^ «Протокол консенсуса и репликации Raft» .
