Анализ и реализация алгоритма Raft

алгоритм Raft

Raft — это алгоритм консенсуса для распределенных систем, он не так сложен для понимания, как Paxos, его реализация намного проще, чем у Paxos, а производительность сравнима с Paxos, он широко используется в Etcd, Consul и т. д. Раньше я использовал Consul в службе контейнеров и, кстати, читал статью об алгоритме Raft, а затем прошел лабораторную работу 2 курса распределенной системы mit6.824, чтобы попрактиковаться в языке Go. Исключения, вызванные случайным временем выборов и смоделированным сбоем узла в эксперименте, могут не появиться, пока вы не запустите его сотни раз.После реализации вам нужно протестировать несколько раз, чтобы убедиться, что тест пройден. Код реализации моего алгоритма Raft находится здесь6.824-2017-raft, дополнительные ссылки на другие коды см. в README. Лаб1 курса 6.824 — выполнить упрощенную версию MapReduce, реализация относительно проста, см. код6.824-2017-mapreduce. Если есть какая-то ошибка, пожалуйста, поправьте меня.

1 Обзор

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

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

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

2 Скопируйте конечный автомат

Алгоритмы согласованности предлагаются в контексте реплицированных конечных автоматов. В реплицированном автомате серверы в кластере генерируют одну и ту же реплику из одного и того же состояния.Даже если некоторые из серверов не работают, клиент может продолжать выполнять операции.Реплицированный конечный автомат можно использовать для решения многих проблем отказоустойчивости. в распределенных системах. В больших распределенных системах обычно есть лидер кластера, такой как GFS, HDFS и т. д., которые обычно используют отдельный конечный автомат репликации для управления выбором лидера и информацией о конфигурации для устранения сбоев лидера. Кроме того, существуют Chubby и ZooKeeper, которые используют реплицированные конечные автоматы.

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

Копировать диаграмму конечного автомата

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

Алгоритмы согласованности, применяемые к реальным системам, обычно имеют следующие характеристики:

  • обеспечить безопасность. Безопасен при всех не византийских общих условиях, включая задержку в сети, разделы, потерю пакетов, нарушение порядка и т. д.
  • Высокая доступность. Система доступна до тех пор, пока доступно большинство (более половины) серверов в кластере. Например, кластер из 5 серверов может использоваться для отключения 2 серверов без ущерба для обслуживания.
  • Не зависит от времени для обеспечения согласованности журнала. Неправильные часы и большие задержки сообщений в худшем случае приводят к проблемам с доступностью.
  • В обычных условиях, пока большинство серверов в кластере отвечают на вызовы процедур, команда может завершиться, а несколько медленных серверов не повлияют на общую производительность системы.

3 Алгоритм плота

Алгоритм Raft разделен на две части: выбор лидера и репликация журнала.Вот очень яркая анимация, иллюстрирующая реализацию алгоритма Raft., здесь есть очень хорошая статья, объясняющая изменения членов и снимки журнала, см.Углубленный Raft – изменение членства
.

3.1 Выборы лидера

Прежде всего, разберитесь с несколькими состояниями узлов в Raft: Follower, Candidate, Leader. Переход состояния показан на рисунке ниже.

Диаграмма перехода состояния узла плота

  • Узел в состоянии Follower находится в случайном периоде тайм-аута (называемом тайм-аутом выборов, обратите внимание, что период тайм-аута выбирается каждый раз случайным образом, этот период тайм-аута обычно составляет 150-300 миллисекунд, и я установил его на 300 + мс в эксперименте) RPC, которые не получают голоса или не регистрируют репликацию и пакеты пульса, перейдут в состояние кандидата.

  • Узлы в состоянии «Кандидат» немедленно начнут голосовать. Сначала он отдает свой голос, а затем отправляет голоса другим узлам, этот запрос называетсяRequest Vote RPC. Если будет получено более половины голосов узла, он переключится в состояние Лидер. Если вы проголосуете за другой узел или найдете инструкцию по обновлению термина (например, предвыборное голосование по обновлению термина и инструкции по копированию журнала), он перейдет в состояние подписчика. Если по тайм-ауту выборов не будет набрано более половины голосов, сохраните статус «Кандидат» и начните новый тур предвыборного голосования.

  • Узел в состоянии лидера будет отправлять его периодически (на этот раз это время HeartbeatTimeout, которое обычно намного меньше тайм-аута выборов, а бит, который я установил в эксперименте, равен 50 мс).AppendEntriesЗапросы RPC к другим узлам. Если найдена инструкция по обновлению владения, она переходит в состояние Подписчика.

Голосование на выборах требует двух условий:

  • Условие 1: срок узла, запрашивающего голосование, должен быть больше или равен этому узлу, и этот узел не голосовал за другие узлы (включая голосование за себя).
  • Условие 2: Журнал узла, запрашивающего голосование, должен быть узлом, содержащим последний журнал отправки, что является ограничением для обеспечения повышенной безопасности журнала. Как убедиться, что узел голосования по запросу содержит последний журнал коммитов? Срок последнего журнала двух узлов можно сравнить.Если срок отличается, обновляется журнал с большим сроком, если срок одинаковый, обновляется журнал с более длинным сроком.

3.2 Репликация журнала

Raft — это сильный механизм лидера, и журналы можно копировать только с лидера на другие узлы. Элемент журнала LogEntry включает три элемента: индекс, термин и команду. Где index — это индекс журнала, term — термин, а command — конкретное содержимое журнала. Формат журнала показан на следующем рисунке:

Схематическая диаграмма формата журнала Raft

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

  • Клиент отправляет запрос Лидеру.
  • Лидер получает запрос клиента и сначала добавляет команду запроса в качестве записи журнала (LogEntry) в свой собственный журнал.
  • Лидер то в ближайшемHeartbeat timeoutотправлено, когдаAppend Entries RPCДайте узел Follower.
  • После успешной отправки журнала:
    • В это время журнал находится в состоянии Uncommitted.Когда более половины узлов успешно добавляют журнал, лидер отправляет журнал в конечный автомат и возвращает клиенту, что журнал успешно записан.
    • и в следующемAppend Entries RPCУведомить другие узлы о необходимости отправки журнала.
    • Узлы-последователи отправляют журналы в свой собственный конечный автомат.
  • Если узел-лидер зависает, другие узлы-последователи переизберут нового лидера по истечении тайм-аута. И если есть время простоя или медленные узлы-последователи, лидер будет продолжать повторять попытки, пока не добьется успеха.

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

Несколько моментов о репликации журналов:

  • Команды одних и тех же записей журнала индексов и терминов, представленные на разных серверах, должны быть одинаковыми, иперед этой записью в журналеВсе записи журнала одинаковы.
  • Если запись журнала зафиксирована, все записи журнала, проиндексированные до нее, также должны быть зафиксированы.
  • Лидеры никогда не перезаписывают свои журналы. Если другие узлы состояния не согласуются с текущим журналом лидера, журнал необходимо обновить, включая запись новых журналов и удаление несогласованных журналов.
  • Логи, отправленные лидером, в будущем обязательно появятся у нового лидера.
  • Чтобы обеспечить безопасный журнал фиксации, лидер должен удовлетворять этим двум правилам фиксации (см. 4.3 для небезопасных случаев и 4.4 для безопасных случаев):
    • Записи журнала были реплицированы на большинство узлов Follower.
    • Leaderтекущий срокПо крайней мере одна из новых записей журнала реплицирована на большинство узлов-последователей.

Сроки и наличие:

Особенностью Raft является то, что безопасность не зависит от тайминга, и система не будет вызывать ошибок из-за проблем с таймингом, но доступность системы неизбежно будет зависеть от тайминга. В случае сбоя сервера выборы узла-кандидата будут неудачными и выборы будут запущены непрерывно, а у Рафта должен быть стабильный Лидер, иначе он не сработает. Выбор лидера является наиболее важной частью требований Raft к времени. Raft может избирать и поддерживать стабильного лидера, поэтому система должна соответствовать следующим требованиям к времени:

broadcastTime << electionTimeout << MTBF

Где BroadTime — это среднее время, в течение которого сервер параллельно отправляет RPC на другие серверы в кластере и получает ответ, selectionTimeout — это тайм-аут выбора, а MTBF — это среднее время между сбоями одного сервера. Время широковещательной передачи намного меньше, чем время наработки на отказ, чтобы гарантировать, что лидер продолжает отправлять пакеты пульса на узлы-ведомые, чтобы предотвратить инициирование выборов узлами-последователями. После краха лидера, теоретически, сервис недоступен примерно в течение времени selectionTimeout.

В соответствии с различными методами хранения время трансляции обычно устанавливается в диапазоне от 0,5 мс до 20 мс (в эксперименте интервал сердцебиения немного отличается, рекомендуется около 100 мс, я установил 50 мс), а время ожидания обычно составляет 10–500 мс (экспериментальная настройка). составляет 300+ мс). Обычно среднее время безотказной работы сервера обычно составляет месяцы или даже годы, и выполнить это требование несложно.

4 Анализ статуса репликации журнала Raft

4.1 Предыдущий журнал должен быть таким же, чтобы его можно было успешно скопировать

Значок состояния копирования 1

4.2 Последний срок лидера имеет журналы, которые были скопированы на большинство узлов (безопасность)

Значок состояния копирования 2

Как показано на рисунке, S1-S3 успешно реплицировали четвертый LogEntry в термине 2. В это время лидер должен включать четвертый LogEntry.Поэтому ни S4, ни S5 не могут быть избраны лидерами во время переизбрания, а четвертый журнал можно смело отправлять.

4.3 Лидер пытается зафиксировать журнал из более старого термина (небезопасно)

Значок состояния копирования 3

Как показано на рисунке выше, отправлять третий LogEntry в это время небезопасно, потому что если S5 будет выбран в качестве ведущего, третий журнал S1, S2 и S3 будет перезаписан.

4.4 Безопасный журнал отправки лидера

Значок состояния копирования 4

Как показано на рисунке выше, запись журнала 4 последнего термина лидера 4 была скопирована на большинство узлов S1-S3.В настоящее время S5 не может быть успешно выбран, а записи журнала 3 и 4 безопасны. Это подтверждает вышеизложенноеПо крайней мере одна новая запись журнала для текущего срока лидера была реплицирована на большинство узлов-последователей, прежде чем ее можно будет зафиксировать.

4.5 Смена лидеров приводит к несогласованности журналов

Смена лидера вызывает несогласованность журнала

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

  • Новому лидеру необходимо убедиться, что лог ведомого согласуется с ним.Если у ведомого есть несогласованные избыточные логи, его нужно удалить, а если логов меньше, то его нужно добавить. Например, (а) на следующей блок-схеме обработки нужно добавить отсутствующие журналы, а (б) — удалить несогласованные избыточные журналы, а затем добавить новые журналы.
  • Ведущий поддерживает список nextIndex для каждого Последователя, записывая индекс следующего журнала, который будет отправлен соответствующему узлу Последователя.
  • Если ведомому не удается реплицировать журнал, ведущему необходимо уменьшить nextIndex и повторить попытку.
Блок-схема обработки несогласованности журнала

5 Реализация Raft требует внимания к нескольким местам

Структура данных, необходимая для реализации Raft, уже завершена в документе, как показано ниже:

Raft реализует структуру данных и точки процесса
  • Сердцебиение лидера и репликация журнала могут использоваться какAppend Entries RPCЗапрос на отправку, может упростить код. В отличие от репликации журналов, параметр Entries пульсирующего RPC пуст.
  • Обратите внимание на два тайм-аута. Один из них — тайм-аут выборов, а другой — интервал репликации журнала (пульса). Тайм-аут выборовElectionTimeoutи интервал репликации журналаHeartbeatTimeoutВыбор двух тайм-аутов, обратите внимание, что интервал репликации должен быть намного меньше, чем тайм-аут выборов, т.е.HeartbeatTimeout << Electiontimeout. Тайм-аут выборов, установленный моим кодом, случайным образом устанавливается равным (300+Rand(100)) мс (исходная бумага требует 150-300 мс, но смысл в эксперименте в том, что лучше быть больше 300 мс, но тест может также пройти, если установлено значение 300+ms ), обратите внимание, что тайм-аут выборов должен быть случайным каждый раз, иначе выборы могут быть неудачными. Интервал репликации зафиксирован на уровне 50 мс (для статьи требуется в пределах 20 мс, а для эксперимента требуется около 100 мс. Тест показал, что интервал пульса в 50 мс может пройти тест, когда тайм-аут выборов составляет 300+ мс).
  • Обратите внимание на проблему блокировки, данные, совместно используемые несколькими сопрограммами, должны быть заблокированы и доступны.rf.mu.Lock(), не забудьте снять блокировку, используйтеdefer rf.mu.Unlock()хороший план. При тестировании не забудьте добавить обнаружение гонки данных.go test -race.
  • Будьте внимательны при отправке логовapplyLogs()В части отправки журнала функции должен быть отправлен элемент журнала, чей commitIndex больше, чем lastApplied, потому что несколько журналов могут быть отправлены одновременно, иначе произойдет ошибка.
  • Первый элемент массива лога rf.log не используется, в основном для совместимости с бумагой.Индекс лога начинается с 1. Обратите внимание, что если первый элемент массива в языке go равен nil, то будут проблемы с gob кодирование и декодирование, поэтому добавьте пустое пространство. LogEntry входит и заполняется.
  • Пока переменная, которая должна сохраняться машиной, изменяется, необходимо вызыватьrf.persist()Сопротивляться. Переменные, которые должны сохраняться каждым узлом:currentTerm, voteFor, log.
  • для оптимизацииAppend Entries RPCколичество кодов, см.Ссылка 3инструкция о.

6 ссылок

Категории