RAFT

Алгоритм для решения задач консенсуса
Является протоколом семейства Paxos

Он нужен чтобы несколько участников смогли совместно решить произошло ли событие

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

В кластере raft каждый из серверов в каждый момент времени находится в одном из трех состояний:

1. leader - обрабатывает все клиентские запросы, является источником истины всех данных в логе, поддерживает лог фоловеров
2. follower - пассивный сервер который слушает новые записи от лидера и редиректит к нему клиентские запросы
3. candidate - специальное состояние, возможное только во время выбора нового лидера

При нормальном состоянии кластера только один сервер является лидером

Raft делит время на отрезки произвольной длины - сроки

Новый срок начинается в момент появления кандидата
Если кандидат получает большинство голосов - он становится лидером до конца этого срока
Если голоса разделились и не получается вычислить нового лидера, то срок заканчивается по таймауту и начинается новый срок
Такая ситуация называется split vote, она отображена на картинке ниже

Номер срока инкрементируется с каждым сроком и служит логическим timestamp в кластере raft
Он помогает серверам определять какая информация сейчас самая актуальная

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

Серверы взаимодействуют запросами и ответами

• RequestVote - используется кандидатами во время выборов, содержит номер срока отправителя и метаданные о логе кандидата
  Ответ содержит номер срока отвечающего и голос: true/false
• AppendEntries - для репликации лога лидера и для heartbeat
  Содержит номер срока лидера, записи для добавления (или без записей в случае heartbeat) и метаданные о логе лидера
  В ответе от фоловера: номер срока и статус добавления записей true/false

Фоловер остается фоловером пока получает сообщения от текущего лидера или кандидата
Лидер периодически рассылает heartbeat

Если фоловер не получает долгое время сообщений от лидера, то он сам попытается стать лидером и инициирует выборы

Для инициализации выборов фоловер увеличивает номер своего срока и переходит в состояние Кандидат
Голосует сам за себя, рассылает запрос RequestVote остальным серверам и ждет одного из трех дальнейших событий:

1. Победа в выборах большинством голосов (включая свой)
   Каждый сервер голосует за первого достучавшегося кандидата
   При условии нечетного количества серверов, большинство голосов сможет набрать только один кандидат
   Победитель становится лидером и начинает рассылать heartbeat
2. Проигрыш. Кандидат получил сообщение от действующего лидера текущего срока (другого кандидата выбрали быстрее этого кандидата), или кандидат получил сообщение от любого сервера более старшего срока (значит выборы в которых учавствует кандидат уже не актуальны)
   В любом из этих двух случаев кандидат признает нового лидера/срок и становится фоловером
3. Кандидат не получает большинство голосов за некоторый таймаут. Такое может быть когда несколько фоловеров становятся кандидатами. В таком случае выборы заканчиваются без лидера и начинается новый срок (selection timeout выставляет программист)

Лидер ответсвеннен за ведение лога
Он принимает клиентские запросы с командами, кладет новые записи в свой лог и отсылает AppendEntries всем фоловерам
Когда запись будет отреплецирована на большую часть фоловеров она начинает считаться закоммиченной и лидер отвечает клиенту
Для неотвечающих фоловеров он будет ретраить AppendEntries до бесконечности

Логи в кластере raft:

В верхней части квадрата номер срока в который была порождена запись
Цвет также указывает на срок
В нижней части квадрата сама запись (положить 3 в X)
Каждая запись помимо команды также содержит в себе номер срока (как на картинке)

Гарантии надежности:

• Election Safety - в рамках одного срока может быть выбран только один лидер
• Leader Append-Only - лидер только дописывает записи в конец лога (не удаляет и не изменяет)
• Log Matching - если два лога содержат запись с одинаковым номером срока и индексом, то логи идентичны вплоть до этой записи
• Leader Completeness - закоммиченная в данный срок запись будет включена в логи всех последующих лидеров
• State Machine Safety - когда сервер коммитит запись с каким-то индексом, никакой другой сервер не закоммитит другую запись с таким же индексом