Внедрение протокола Raft: Часть 1 — Выбор мастера

Переведено сEli BenderskyизСерия блогов, разрешенный первоначальным автором.

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

• Преамбула:представлять
• Часть 1: Выбор мастера (данная статья)
• Вторая часть:Директива и репликация журнала
• третья часть:Долговечность и оптимизация

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

структура кода

Краткий обзор структуры кода реализации Raft является общим для всех частей этой серии.

Обычно Raft реализуется как объект, в который можно встроить какой-либо сервис. Так как мы не будем собственно разрабатывать сервис, а только изучим сам протокол Raft, мы создали простойServerтип, который обертываетConsensusModuleТипы, чтобы попытаться максимально изолировать наиболее интересные части кода:

Модуль согласованности (CM) реализует ядро ​​алгоритма Raft, вraft.goв файле. Этот модуль абстрагирует детали сети и подключения к другим репликам в кластере,ConsensusModuleЕдинственными полями, связанными с сетью, являются:

// id 是一致性模块中的服务器ID
id int

// peerIds 是集群中所有同伴的ID列表
peerIds []int

// server 是包含该CM的服务器. 该字段用于向其它同伴发起RPC调用
server *Server

В реализации каждая реплика Raft обращается к другим репликам в кластере как к «равноправным». Каждый одноранговый узел в кластере имеет уникальный числовой идентификатор, а также список, в котором записан его идентификатор однорангового узла.serverПоле указывает на модульServer*(существуетserver.goреализовано в ), последнее может позволитьConsensusModuleОтправляйте сообщения коллегам. Мы увидим, как это делается позже.

Цель этого дизайна — исключить все детали сети и сосредоточиться на самом алгоритме Raft. Короче говоря, чтобы сравнить статью Raft с этой реализацией. тебе просто нужноConsensusModuleклассы и их методы.ServerКод представляет собой очень простую веб-инфраструктуру на языке Go с некоторыми тонкими сложностями, необходимыми для тщательного тестирования. Я не буду тратить время на обсуждение этого в этой серии статей. Но если что-то непонятно, не стесняйтесь спрашивать.

Состояние плот-сервера

В общем, Raft CM — это конечный автомат с 3 состояниями.^[1]:

Потому что в преамбуле много места отведено объяснению того, как Raft может помочь.выполнитьконечный автомат, поэтому здесь может быть небольшая путаница, но необходимо уточнить, что терминология здесь *状态Смысл другой. Raft — это алгоритм, который реализует произвольный реплицированный конечный автомат, но Raft также содержит внутри небольшой конечный автомат. в последующих главах где-тоЧто означает state*, можно понять из контекста, если нет, то обязательно укажу.

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

Как упоминалось ранее, Raft используетсильное лидерствоМодель. Лидер отвечает на запрос клиента и добавляет новую запись в журнал и скопировать ее в других подписчиков. Каждый следующий последователь готов взять на себя руководство, чтобы предотвратить провал лидерства или прекратить общение. Это также с вышеуказанного рисунка追随者К候选人(Candidate)transition("Подождать тайм-аут, начать выборы").

Условия

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

Но на этом метафора заканчивается, потому что выборы лидера в Рафте все же сильно отличаются от реальных выборов. В Raft выборы более синергичны, и цель кандидатов не состоит в том, чтобы победить любой ценой — все кандидаты имеют общую цель иметь в любой данный срокподходящеесервер побеждает на выборах. Что такое «соответствующий», будет подробно рассмотрено позже.

таймер выборов

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

просить: Разве все последователи не станут кандидатами одновременно?

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

просить: Что делать, если фолловер отключен (разделен) от кластера? Разве она не начнет выборы, потому что не получила известие от лидера?

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

Одноранговый RPC

В протоколе Raft между одноранговыми узлами передаются два типа запросов RPC. Подробные параметры и правила см. в документеFigure 2, илиприложение. Вот краткое описание двух запросов:

• RequestVote(RV): Используется только в состоянии кандидата. Во время раунда выборов кандидаты через этот интерфейс запрашивают голоса у коллег. Возвращаемое значение содержит флаг согласия на голосование.
• AppendEntries(AE): Используется только в состоянии лидера. Лидер реплицирует записи журнала последователям через этот RPC, который также используется для отправки тактов. Этот запрос RPC периодически отправляется подписчику, даже если нет записей журнала для репликации.

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

Внедрить таймеры выборов

Пора начинать работать над кодом. Если не указано иное, все приведенные ниже примеры кода взяты изэтот файл. я не буду ставитьConsensusModuleВсе поля структуры - можно посмотреть в файле кода.

Наш модуль CM реализует таймер выборов, выполняя следующую функцию в goroutime:

func (cm *ConsensusModule) runElectionTimer() {
    timeoutDuration := cm.electionTimeout()
    cm.mu.Lock()
    termStarted := cm.currentTerm
	cm.mu.Unlock()
	cm.dlog("election timer started (%v), term=%d", timeoutDuration, termStarted)

    /*
	  循环会在以下条件结束：
	  1 - 发现不再需要选举定时器
	  2 - 选举定时器超时，CM变为候选人
	  对于追随者而言，定时器通常会在CM的整个生命周期中一直在后台运行。
	*/
    ticker := time.NewTicker(10 * time.Millisecond)
	defer ticker.Stop()
	for {
		<-ticker.C

		cm.mu.Lock()
        // CM不再需要定时器
		if cm.state != Candidate && cm.state != Follower {
			cm.dlog("in election timer state=%s, bailing out", cm.state)
			cm.mu.Unlock()
			return
		}
		
        // 任期变化
		if termStarted != cm.currentTerm {
			cm.dlog("in election timer term changed from %d to %d, bailing out", termStarted, cm.currentTerm)
			cm.mu.Unlock()
			return
		}

		// 如果在超时之前没有收到领导者的信息或者给其它候选人投票，就开始新一轮选举
		if elapsed := time.Since(cm.electionResetEvent); elapsed >= timeoutDuration {
			cm.startElection()
			cm.mu.Unlock()
			return
		}
		cm.mu.Unlock()
	}
}

Сначала позвонивcm.electionTimeout()Выберите (псевдо-) случайное время ожидания, которое мы здесь варьируем от 150 до 300 мс, как предложено бумагой. картинаConsensusModuleКак и большинство методов вrunElectionTimerОбъект структуры блокируется первым при доступе к свойствам. Этот шаг важен, потому что мы хотим поддерживать как можно больше параллелизма, что является одной из сильных сторон Go. Это также означает, что код должен выполняться последовательно и не может быть распределен между несколькими обработчиками событий. Однако запросы RPC также выполняются одновременно, поэтому мы должны защитить общую структуру данных. Мы представим обработчик RPC позже.

Тикер с периодом 10 мс запускается в основном цикле. Есть более эффективные способы реализации ожидания события, но код, написанный таким образом, самый простой. Цикл будет выполняться каждые 10 мс.Теоретически таймер может спать в течение всего процесса ожидания, но это приведет к падению скорости отклика сервиса и затруднению отладки/отслеживания операций в логе. Мы проверим, соответствует ли статус ожидаемому^[2], а также изменился ли срок, и если есть какие-то вопросы, мы останавливаем таймер выборов.

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

Кандидат на

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

1. Переключите состояние на кандидата и увеличьте срок, ведь именно этого требует алгоритм для каждых выборов.
2. Отправьте запросы RV другим партнерам и попросите их проголосовать за себя в этом раунде выборов.
3. Дождитесь возвращаемого значения RPC-запроса и посчитайте, достаточно ли у нас голосов, чтобы выйти в лидеры.

В Go эту логику можно реализовать в функции:

func (cm *ConsensusModule) startElection() {
  cm.state = Candidate
  cm.currentTerm += 1
  savedCurrentTerm := cm.currentTerm
  cm.electionResetEvent = time.Now()
  cm.votedFor = cm.id
  cm.dlog("becomes Candidate (currentTerm=%d); log=%v", savedCurrentTerm, cm.log)

  var votesReceived int32 = 1

  // 向其它所有服务器发送RV请求
  for _, peerId := range cm.peerIds {
    go func(peerId int) {
      args := RequestVoteArgs{
        Term:        savedCurrentTerm,
        CandidateId: cm.id,
      }
      var reply RequestVoteReply

      cm.dlog("sending RequestVote to %d: %+v", peerId, args)
      if err := cm.server.Call(peerId, "ConsensusModule.RequestVote", args, &reply); err == nil {
        cm.mu.Lock()
        defer cm.mu.Unlock()
        cm.dlog("received RequestVoteReply %+v", reply)

        // 状态不是候选人，退出选举（可能退化为追随者，也可能已经胜选成为领导者）
        if cm.state != Candidate {
          cm.dlog("while waiting for reply, state = %v", cm.state)
          return
        }

        // 存在更高任期（新领导者），转换为追随者
        if reply.Term > savedCurrentTerm {
          cm.dlog("term out of date in RequestVoteReply")
          cm.becomeFollower(reply.Term)
          return
        } else if reply.Term == savedCurrentTerm {
          if reply.VoteGranted {
            votes := int(atomic.AddInt32(&votesReceived, 1))
            if votes*2 > len(cm.peerIds)+1 {
              // 获得票数超过一半，选举获胜，成为最新的领导者
              cm.dlog("wins election with %d votes", votes)
              cm.startLeader()
              return
            }
          }
        }
      }
    }(peerId)
  }

  // 另行启动一个选举定时器，以防本次选举不成功
  go cm.runElectionTimer()
}

Кандидаты сначала проголосуют за себя - будутvotesReceivedИнициализируется до 1 и назначаетсяcm.votedFor = cm.id.

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

Вот просто демонстрация того, как реализован RPC:

cm.server.Call(peerId, "ConsensusModule.RequestVote", args, &reply);

Мы используемConsensusModule.serverсохранено вServerуказатель для инициирования удаленного вызова и указатьConsensusModule.RequestVotesВ качестве имени метода запроса он в конечном итоге вызовет одноранговый сервер, указанный первым параметром.RequestVoteметод.

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

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

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

Обратите внимание здесьstartElectionМетоды неблокирующие. Метод обновляет некоторое состояние, запускает пакет горутин и возвращает значение. Следовательно, в горутине также должен быть запущен новый таймер выборов — что и делает последняя строка кода. Это гарантирует, что еслиЭтот раундНа выборах нет результата, и новый тур выборов начнется после истечения таймера. Это также объясняетrunElectionTimerСтатус проверяется: если текущие выборы действительно превращают сервер в лидера, то одновременно работающийrunElectionTimerВозвращает непосредственно, когда наблюдается, что состояние сервера отличается от ожидаемого значения.

быть лидером

Мы видели, что когда результаты голосования показывают, что побеждает текущий сервер,startElectionВызовstartLeaderметод, код выглядит следующим образом:

func (cm *ConsensusModule) startLeader() {
  cm.state = Leader
  cm.dlog("becomes Leader; term=%d, log=%v", cm.currentTerm, cm.log)

  go func() {
    ticker := time.NewTicker(50 * time.Millisecond)
    defer ticker.Stop()

    // 只要当前服务器是领导者，就要周期性发送心跳
    for {
      cm.leaderSendHeartbeats()
      <-ticker.C

      cm.mu.Lock()
      if cm.state != Leader {
        cm.mu.Unlock()
        return
      }
      cm.mu.Unlock()
    }
  }()
}

На самом деле это довольно простой метод: все содержимоестук сердцаТаймер — эта горутина будет вызываться каждые 50 мс, пока текущий CM является лидеромleaderSendHeartbeats. НижеleaderSendHeartbeatsСоответствующий код:

func (cm *ConsensusModule) leaderSendHeartbeats() {
  cm.mu.Lock()
  savedCurrentTerm := cm.currentTerm
  cm.mu.Unlock()

  // 向所有追随者发送AE请求
  for _, peerId := range cm.peerIds {
    args := AppendEntriesArgs{
      Term:     savedCurrentTerm,
      LeaderId: cm.id,
    }
    go func(peerId int) {
      cm.dlog("sending AppendEntries to %v: ni=%d, args=%+v", peerId, 0, args)
      var reply AppendEntriesReply
      if err := cm.server.Call(peerId, "ConsensusModule.AppendEntries", args, &reply); err == nil {
        cm.mu.Lock()
        defer cm.mu.Unlock()
        // 如果响应消息中的任期大于当前任期，则表明集群有新的领导者，转换为追随者
        if reply.Term > savedCurrentTerm {
          cm.dlog("term out of date in heartbeat reply")
          cm.becomeFollower(reply.Term)
          return
        }
      }
    }(peerId)
  }
}

Логика здесь чем-то похожа на startElection, запуская горутину для каждого узла для отправки запросов RPC. Запрос RPC здесь не имеет содержимого журнала.AppendEntries(AE), играющий роль сердцебиения в Raft.

Как и при обработке ответа RV, если RPC возвращает терм выше нашего собственного значения терма, текущий сервер становится последователем. Просто проверьте это здесьbecomeFollowerметод:

func (cm *ConsensusModule) becomeFollower(term int) {
  cm.dlog("becomes Follower with term=%d; log=%v", term, cm.log)
  cm.state = Follower
  cm.currentTerm = term
  cm.votedFor = -1
  cm.electionResetEvent = time.Now()

  // 启动选举定时器
  go cm.runElectionTimer()
}

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

Отвечать на RPC-запросы

До сих пор мы видели реализацию в кодеинициатива部分——启动RPC、计时器以及状态转换的部分。但是在我们看到服务器方法（其它同伴远程调用的过程）之前，演示的代码都是不完整的。 Мы начинаемRequestVoteНачинать:

func (cm *ConsensusModule) RequestVote(args RequestVoteArgs, reply *RequestVoteReply) error {
  cm.mu.Lock()
  defer cm.mu.Unlock()
  if cm.state == Dead {
    return nil
  }
  cm.dlog("RequestVote: %+v [currentTerm=%d, votedFor=%d]", args, cm.currentTerm, cm.votedFor)

  // 请求中的任期大于本地任期，转换为追随者状态
  if args.Term > cm.currentTerm {
    cm.dlog("... term out of date in RequestVote")
    cm.becomeFollower(args.Term)
  }

  // 任期相同，且未投票或已投票给当前请求同伴，则返回赞成投票；否则，返回反对投票。
  if cm.currentTerm == args.Term &&
    (cm.votedFor == -1 || cm.votedFor == args.CandidateId) {
    reply.VoteGranted = true
    cm.votedFor = args.CandidateId
    cm.electionResetEvent = time.Now()
  } else {
    reply.VoteGranted = false
  }
  reply.Term = cm.currentTerm
  cm.dlog("... RequestVote reply: %+v", reply)
  return nil
}

Обратите внимание, что здесь проверяется статус «мертвый», об этом позже.

Первый — это знакомая часть логики, которая проверяет, не устарел ли термин, и преобразует его в последователя. Если он уже является последователем, состояние не изменится, но другие свойства состояния будут сброшены.

В противном случае, если термин звонящего совпадает с нашим, и мы не голосовали за другого кандидата, мы голосуем за голосование. мы никогда не будемстарый терминИнициирован запрос RPC на голосование.

НижеAppendEntriesкод:

func (cm *ConsensusModule) AppendEntries(args AppendEntriesArgs, reply *AppendEntriesReply) error {
  cm.mu.Lock()
  defer cm.mu.Unlock()
  if cm.state == Dead {
    return nil
  }
  cm.dlog("AppendEntries: %+v", args)

  // 请求中的任期大于本地任期，转换为追随者状态
  if args.Term > cm.currentTerm {
    cm.dlog("... term out of date in AppendEntries")
    cm.becomeFollower(args.Term)
  }

  reply.Success = false
  if args.Term == cm.currentTerm {
    // 如果当前状态不是追随者，则变为追随者
    if cm.state != Follower {
      cm.becomeFollower(args.Term)
    }
    cm.electionResetEvent = time.Now()
    reply.Success = true
  }

  reply.Term = cm.currentTerm
  cm.dlog("AppendEntries reply: %+v", *reply)
  return nil
}

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

if cm.state != Follower {
  cm.becomeFollower(args.Term)
}

Q: А если сервер лидер - зачем становиться последователями других лидеров?

A: протокол Raft гарантирует наличие только одного лидера в любой момент времени. Если вы проводите собственное исследованиеRequestVoteлогика иstartElectionВ коде, который отправляет запрос RV, вы обнаружите, что в кластере не будет двух лидеров с одинаковым термином. Это условие распространяется на тех, кто считает, что в текущем туре выборов победили другие пэры.кандидатОчень важный.

состояние и горутины

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

последователь: когда CM инициализируется как ведомый или каждый раз, когда он выполняетсяbecomeFollowerметод, запустит новую горутину для запускаrunElectionTimer, что является партнерским действием подписчика. Обратите внимание, что несколько таймеров выборов могут работать одновременно в течение короткого периода времени. Предположим, что последователь получает запрос RV с более высоким сроком от лидера, это сработает один раз.becomeFollowerПозвоните и запустите новую горутину таймера. Но старая горутина естественным образом завершит работу, как только заметит изменение срока действия.

кандидат: У кандидата также есть горутина таймера выборов, работающая параллельно, но, кроме того, у него есть несколько горутин, которые отправляют запросы RPC. Он имеет те же средства защиты, что и подписчики, чтобы остановить «старую» программу выборов, когда начнутся новые выборы. Важно иметь в виду, что выполнение горутин RPC может занять много времени, поэтому, если вызов RPC возвращается и они обнаруживают, что срок их действия истек, они должны закрыться незаметно.

лидер: лидер не выбирает временную горутину, но у него определенно есть горутина сердцебиения, которая выполняется каждые 50 мс.

В коде есть дополнительное состояние -Deadусловие. Это чисто для упорядоченного выключения СМ. Вызов метода «Stop» установит состояние «Dead», и все горутины завершатся сразу же после наблюдения этого состояния.

Выполнение этих горутин может вызывать беспокойство — что, если некоторые из них застряли в фоновом режиме? Или, что еще хуже, эти горутины продолжают протекать и бесконечно расти, что делать? Для этого и нужна проверка утечек, и проверка утечек также включена в некоторых тест-кейсах. Эти тесты будут выполнять нетрадиционную серию операций выбора Raft и гарантировать, что после завершения теста (после вызоваstopметод, дайте этим go-процедурам некоторое время для выхода).

Сервер вышел из-под контроля и увеличивается срок владения

Чтобы завершить этот раздел, давайте рассмотрим сложный сценарий, который может возникнуть, и то, как может реагировать Raft. Я нахожу этот пример интересным и поучительным. Здесь я пытаюсь представить это в виде истории, но лучше иметь бумажку для записи состояния каждого сервера. Если вы не понимаете этот пример - пожалуйста, напишите мне, и я буду рад сделать его более понятным.

Представьте себе кластер с тремя серверами A, B и C. Предположим, что A является лидером, начальный термин равен 1, и кластер работает идеально. Каждые 50 мс A отправляет запрос AE Heartbeat AE на B и C и получает своевременный ответ в течение нескольких миллисекунд. Каждый запрос AE будет сбрасывать B и C вelectionResetEventатрибуты, поэтому они также очень хотят продолжать быть последователями.

В какой-то момент из-за временного сбоя сетевого маршрутизатора возникает сетевой раздел между серверами B и A и C. A по-прежнему отправляет запросы AE каждые 50 мс, но эти запросы AE либо завершаются сбоем немедленно, либо завершаются сбоем из-за тайм-аута базового механизма RPC. Эй ничего не может с этим поделать, но это не такая уж большая проблема. Мы еще не рассмотрели репликацию журналов, но поскольку 2 из 3 серверов работают, кластер по-прежнему может отправлять клиентские команды.

Что насчет Б? Предположим, что при отключении его таймаут выбора установлен на 200 мс. Примерно через 200 мс после отключения BrunElectionTimerПоняв, что сообщение лидера не было получено во время ожидания выборов, B не мог сказать, кто виноват, поэтому он становится кандидатом и начинает выборы.

Таким образом, термин B станет равным 2 (в то время как термин A и C по-прежнему будет равен 1). B отправит запросы RV к A и C, попросив их проголосовать за себя; конечно, эти запросы будут потеряны в сети. не паникуй! в БstartElectionМетод также запускает другую горутину для выполнения.runElectionTimerзадача, скажем, эта горутина будет ждать 250 мс (помните, наш тайм-аут выбирается случайным образом между 150 мс-300 мс), чтобы увидеть, есть ли существенный результат от последних выборов. Поскольку B все еще полностью изолирован, ничего не произойдет, поэтомуrunElectionTimerбудет инициироватьеще один раундВыборы и увеличить срок до 3.

Таким образом, сервер B перезагружается и возвращается в сеть через несколько секунд, и в то же время срок B становится равным 8, потому что B время от времени инициирует выборы.

На данный момент проблема с сетевым разделом устранена, и B снова подключен к A и C.

Вскоре после этого пришел запрос AE, отправленный А. Напомним, что A отправляет сообщения пульса каждые 50 мс, даже если B не ответил.

BAppendEntriesвызывается, и задача, переносимая в ответном сообщении, равна 8.

А вleaderSendHeartbeatsПосле получения этого ответа в методе проверьте термин в ответном сообщении и инициируйте более высокий термин, чем его собственный. A изменяет свой срок на 8 и становится последователем. Кластер временно потерял своего лидера.

Далее, в зависимости от сроков, могут возникнуть самые разные ситуации. B является кандидатом, но он мог отправить запрос RV до восстановления сети; C является последователем, но также становится кандидатом, поскольку запрос AE от A не получен в течение тайм-аута выборов; A становится последователем и также может стать кандидат из-за тайм-аута выборов.

Таким образом, любой из этих серверов может победить в следующем туре выборов, обратите внимание, что это только потому, что мы не копируем здесь никаких журналов. Как мы увидим в следующем разделе, на практике A и C могли добавить некоторые инструкции на стороне клиента, написанные, когда B был в автономном режиме, поэтому их журналы обновлены. Следовательно, В не станет новым лидером — будет новый тур выборов, и победит либо А, либо С. Мы еще раз обсудим этот сценарий в следующем разделе.

Если после отключения B не добавляется новая инструкция, вполне возможно заменить лидера после повторного подключения.

Это может показаться немного неэффективным — и это так. Смена лидера здесь не нужна, так как А очень здоров на протяжении всего сценария. Однако за счет эффективности в особых случаях гарантируется простота логики алгоритма, что также является одним из выборов, сделанных Raft. Эффективность алгоритма в общем случае (без каких-либо аномалий) важнее, поскольку кластер находится в таком состоянии 99,9% времени.

Следующий шаг

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

в кодовой базеREADMEФайл содержит подробные инструкции по взаимодействию с кодом, запуску тестовых случаев и наблюдению за результатами. Код поставляется с множеством тестов для конкретных сценариев (включая те, которые упоминались в предыдущих главах), и запуск тестового примера и просмотр журналов Raft имеет большой смысл для обучения. Обратите внимание, что код, вызываемыйcm.dlog(...)Все же? В репозитории имеется инструмент для визуализации этих журналов в файлах HTML, доступный по адресуREADMEИнструкции см. в документации. Запускайте код, просматривайте лог или добавляйте в код свой по желаниюdlog, чтобы лучше понять, когда выполняются разные части кода.

этой системычасть 2Описана более полная реализация Raft, где обрабатываются инструкции клиента и эти логи реплицируются по всему кластеру. Следите за обновлениями!

Прикрепил:

Рисунок 2 в документе Raft показан ниже, который кратко переведен и объяснен здесь. Некоторые из них касаются репликации и отправки журналов, которые можно заново понять после прочтения следующей статьи.

состояние

На сервере есть три типа полей состояния, которые будут представлены отдельно.

Постоянное состояние на всех серверах (обновляется до стабильного хранилища перед ответом на запросы RPC)

поле	иллюстрировать
currentTerm	Последний термин, полученный сервером (инициализируется 0 при запуске, монотонно увеличивается)
votedFor	Идентификатор кандидата, проголосовавшего за текущий срок (нуль, если нет)
log[]	записи журнала; каждая запись содержит инструкции, которые вошли в конечный автомат, и срок лидера, когда запись была получена (первый индекс равен 1)

Часто изменяемые поля состояния на всех серверах:

поле	иллюстрировать
commitIndex	Подтвердите максимальное значение индекса зафиксированной записи журнала (инициализируется равным 0, монотонно увеличивается)
lastApplied	Максимальное значение индекса записей журнала, применяемых к конечному автомату (инициализировано до 0, монотонно увеличивается)

Часто изменяемые поля состояния на ведущем сервере (повторно инициализируются после выборов):

поле	иллюстрировать
nextIndex[]	Для каждого сервера сохраните индекс следующей записи журнала для отправки на этот сервер (инициализируется последним индексом журнала лидера + 1).
matchIndex[]	Для каждого сервера сохраните максимальное значение индекса записей журнала, подтверждающих репликацию на этот сервер (инициализируется равным 0, монотонно увеличивается).

запрос АЭ

Запрос AEAppendRntriesЗапросы, инициированные лидером, используются для репликации клиентских инструкций последователям, а также используются для поддержания тактов.

параметры запроса

параметр	иллюстрировать
term	Срок лидеров
leaderId	ID лидера, подписчики могут перенаправить клиента
prevLogIndex	индекс записи, непосредственно предшествующей новой записи журнала
prevLogTerm	prevLogIndexсрок соответствующей записи
entries[]	Записи журнала, которые должны сообщать об ошибках (запросы пульса, когда они пусты; для эффективности можно отправить несколько журналов)
leaderCommit	лидерcommitIndex

возвращаемое значение

параметр	иллюстрировать
term	currentTerm, текущий термин, отвечает лидеру. лидер по самообновлению
success	Если подписчик сохранилprevLogIndexа такжеprevLogTermсоответствующие записи журнала, затем возвратtrue

Приемник реализует:

1. еслиterm < currentTerm,вернутьfalse;
2. если журналprevLogIndexСрок соответствующей записи иprevLogTermне подходит, вернитеfalse;
3. Если локально существующая запись в журнале конфликтует с новым журналом (индекс тот же, но термин другой), удалите локально существующую запись и все последующие записи;
4. Добавить все несохраненные новые записи в журнал;
5. еслиleaderCommit > commitIndex, будуcommitIndexУстановить какleaderCommitи меньшее значение в индексе последней записи.

Запрос на автодом

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

параметры запроса

поле	иллюстрировать
term	срок кандидата
candidateId	Идентификатор кандидата для запрашиваемого бюллетеня
lastLogIndex	Последняя запись в журнале кандидата соответствует индексу
lastLogTerm	Последняя запись в журнале кандидата соответствует сроку

возвращаемое значение

поле	иллюстрировать
term	currentTerm, текущий термин, ответ кандидату. кандидаты на самообновление
voteGranted	true указывает, что кандидат получил положительное голосование

Приемник реализует:

1. еслиterm < currentTermвернутьfalse;
2. еслиvotedForпусто или равноcandidateId, а журнал кандидата не менее нов, чем журнал получателя, за что проголосовали.

Правила ответа сервера

В соответствии с текущим состоянием сервера (роль, в которой он находится) отдельно вводятся:

Все серверы:

• еслиcommitIndex > lastApplied:УвеличиватьlastApplied,Будуlog[lastApplied]применяется к государственной машине;
• Если условие T, передаваемое в запросе или ответе RPC, выполняетсяT > currentTerm:настраиватьcurrentTerm = T, конвертировать в подписчиков.

Последователи:

• В ответ на кандидат и лидер запроса RPC;
• Если запрос AE от текущего лидера не получен в течение времени ожидания тайм-аута или голосование подано за кандидата: преобразовать в кандидата.

кандидат:

• Когда только что превратились в кандидата, начните выборы:
  • добавить текущий термин,currentTerm
  • проголосуй за себя
  • Сбросить таймер выборов
  • Отправлять запросы RV на все остальные серверы
• Если за большинство серверов проголосовали: стать лидером
• Если получен запрос AE от нового лидера: преобразовать в последователя
• Если время ожидания выборов истекло: начать новый тур выборов

лидер:

• При выборе: отправьте начальный пустой запрос AE (пульс) на каждый сервер, а также повторно отправьте запросы AE во время простоя, чтобы последователи не ждали тайм-аута;
• Если от клиента получена инструкция: добавить запись в локальный журнал, ответить клиенту после того, как новая инструкция будет применена к конечному автомату;
• Если индекс индекса последнего журнала удовлетворяет индексу следующего журнала последователя nextIndexindex ≥ nextIndex: Отправьте запрос AE ведомому, несущемуnextIndexВсе записи журнала, начинающиеся с:
  • В случае успеха: обновить соответствующий фолловерnextIndexа такжеmatchIndex;
  • Если AE не работает из-за несогласованности журнала: уменьшитеnextIndexИ попробуй еще раз;
• Если есть N, удовлетворитьN > commitIndex,большинствоmatchIndex[i] ≥ N,а такжеlog[N].term == currentTerm:настраиватьcommitIndex = N

---

1. Эта схема аналогична рисунку 4 в документе Raft. Напоминаем, в этой серии статей. Я предполагаю, что вы уже читали эту статью.↩︎

2. Проверка статуса подписчиков и кандидатов может показаться немного странной. Не мог ли сервер пройтиrunElectionTimerИнициировали выборы и вдруг стали лидером? Читайте дальше, чтобы узнать, как кандидат перезапустил счетчик выборов.↩︎