Алгоритм Raft

Page 1 of 1
1

Archive - read only

19:48:10

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

WеniZAY

19:49:22

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

Процедура голосования повторяется, пока не будет выбран лидер.

WеniZAY

19:50:18

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

WеniZAY

19:50:43

Интересные факты
Алгоритм, очень похожий на Raft, начал использоваться в ключевых системах Яндекса задолго до появления оригинальной статьи.

Алгоритм Raft

Page 1 of 1
1