Trabalho 3
: Raft
Entrega: Segunda 09 de dezembro 14:00
Este trabalho é uma tradução do
laboratório Lab2
do curso CS451/651 Distributed Systems.
O trabalho deve ser feito em
grupo de no máximo 2 pessoas.
Introdução
Neste trabalho, você implementará uma parte
do Raft, um
algoritmo de consenso para gerenciar log replicado.
Um serviço de acesso a um banco de dados pode
alcançar tolerância a falhas armazenando cópias de
seus dados em vários servidores de réplica. A replicação permite que o serviço
continue operando, mesmo que alguns de seus recursos apresentem falhas (falhas do servidor ou de comunicação). O problema é
que falhas podem fazer com que as réplicas mantenham cópias diferentes dos
dados.
O Raft gerencia as
réplicas de estado de um serviço e, em particular, ajuda o serviço a determinar
qual é o estado correto após falhas. Ele organiza as solicitações do cliente em
uma sequência, chamada log,
e garante que todas as réplicas concordem com o conteúdo do log.
Cada réplica executa as solicitações do cliente no log
na ordem em que aparecem no log, aplicando essas
solicitações à cópia local da réplica do estado do serviço. Como todas as
réplicas ativas vêem o mesmo conteúdo de log, todas
executam as mesmas solicitações na mesma ordem e, portanto, continuam tendo o
mesmo estado de serviço. Se um servidor falhar, mas depois se recuperar, o Raft cuidará de atualizar seu log.
O Raft continuará operando enquanto pelo menos a maioria
dos servidores estiver ativa e puder fazer uma comunicação ponto a ponto. Se
não houver essa maioria, o Raft não fará nenhum
progresso, mas continuará de onde parou, assim que a maioria puder se comunicar
novamente.
Neste laboratório, você implementará
o Raft como um tipo de objeto Go com métodos
associados, destinado a ser usado como um módulo. Um conjunto de instâncias de Raft se comunica através de RPC para manter logs replicados. Sua interface Raft
suportará uma sequência indefinida de comandos
numerados, também chamados de entradas de log. As
entradas são numeradas com números de índice. A entrada de log
com um determinado índice será eventualmente realizada no participante.
Somente o RPC pode ser usado para interação
entre diferentes instâncias do Raft. Por exemplo,
diferentes instâncias da sua implementação do Raft não têm permissão para compartilhar variáveis Go. Sua implementação não deve
usar arquivos.
Leia e compreenda o artigo sobre o Raft. Sua implementação deve
seguir a descrição do artigo, principalmente a Figura 2, pois é isso que os
testes esperam.
Política
de colaboração
Você deve escrever todo o código para entrega,
exceto o código que já é fornecido. Você deve gerar suas próprias soluções, ou
seja, não pode acessar a solução de outras pessoas, nem o código disponível na
rede. Você pode discutir as tarefas com outros grupos, mas não pode olhar ou
copiar o código um do outro. Não publique seu código nem o disponibilize para
futuros alunos de Sistemas Distribuídos - por exemplo, não torne seu código
visível no github.
Começando
Utilize o pacote de dados do trabalho 2. Fornecemos a você um código esqueleto e testes no src/raft, e um
sistema simples de RPC no src/labrpc.
Para entrar em funcionamento, execute os
seguintes comandos:
$ export GOROOT= Local de instalação do seu Go
$ export PATH=$PATH:$GOROOT/bin
$ export GOPATH=$HOME/451
$ cd $GOPATH
$ cd src/raft
$ go test –run 2A
Test (2A): initial election ...
--- FAIL: TestInitialElection (5.03s)
config.go:270: expected one leader, got 0
Test (2A): election after network failure ...
--- FAIL: TestReElection (5.03s)
config.go:270: expected one leader, got 0
...
$
Sua implementação deve passar pelo teste 2A.
$ go test
Test (2A): initial election
...
... Passed
Test (2A): election after network failure ...
... Passed
Test (2B): basic agreement
...
... Passed
...
PASS
ok raft 162.413s
O código
Implemente o Raft
adicionando código a raft/raft.go. Nesse arquivo, você encontrará um código esqueleto,
além de exemplos de como enviar e receber RPCs.
Sua implementação
deve suportar a seguinte interface que o testador usará. Você encontrará mais
detalhes nos comentários em raft.go.
// create a new Raft
server instance:
rf := Make(peers, me, persister, applyCh)
// start agreement on a new log entry:
rf.Start(command interface{})
(index, term, isleader)
// ask a Raft for its current term, and whether
it thinks it is leader
rf.GetState() (term, isLeader)
// each time a new entry is committed to
the log, each Raft peer
// should send an ApplyMsg
to the service (or tester).
type ApplyMsg
Um serviço chama Make
(peers, me,…) para criar um peer em Raft. O argumento peers é uma matriz de conexões RPC estabelecidas, uma para cada participante
Raft. O argumento me é o índice deste participante na
matriz de conexões. Start (command) solicita que o Raft inicie o processamento
para anexar comandos ao log replicado. Start () deve retornar
imediatamente, sem aguardar a conclusão desse processo. O serviço espera que
sua implementação envie um ApplyMsg para cada nova entrada de log confirmada no
argumento applyCh de Make ().
Seus participantes do Raft devem trocar RPCs usando o pacote labrpc Go fornecido a você. Ele é modelado como a biblioteca rpc
do Go, mas usa internamente os canais Go em vez de sockets.
O raft.go contém o código de um exemplo que
envia uma RPC (sendRequestVote ()) e que lida com uma RPC de entrada (RequestVote ()). O motivo pelo qual
você deve usar o labrpc em vez do pacote RPC da Go é que
o testador consegue solicitar ao labrpc para atrasar os RPCs,
reordená-los e excluí-los, de modo a
simular condições desafiadoras de rede sob as quais seu código deve funcionar
corretamente. Não modifique o labrpc porque seu código
será testado com o labrpc originalmente distribuído.
Tarefa
Implementar eleição de líder
e heartbeats (RPCs AppendEntries sem entradas no log). O objetivo é que um
único líder seja eleito, que o líder continue sendo o líder se não houver
falhas e que um novo líder assuma o controle se o antigo líder falhar ou se os
pacotes de/para o antigo líder forem perdidos. Execute go test -run 2A para testar seu código.
Dicas:
·
Adicione qualquer estado necessário
à struct Raft em raft.go. Você também
precisará definir uma estrutura para armazenar informações sobre cada entrada
de log. Seu código deve seguir a Figura 2 da versão
estendida do artigo sobre Raft o mais próximo
possível.
·
Use marshals apenas para os campos públicos em qualquer estrutura passada pelo RPC.
Campos públicos são aqueles cujos nomes começam com letras maiúsculas. Esquecer
de tornar públicos os campos nomeando-os com letras maiúsculas é a fonte mais frequente de erros nesse trabalho.
·
Preencha as estruturas RequestVoteArgs e RequestVoteReply. Modifique Make () para criar uma rotina go em segundo plano que
iniciará a eleição do líder periodicamente enviando RPCs de RequestVote quando um
participante não receber notícias de outro participante por um tempo. Dessa
maneira, um participante aprenderá quem é o líder, se ele já existe, ou se
tornará o líder. Implemente o método RPC RequestVote () para que os servidores
votem um no outro.
·
Para implementar
heartbeats, defina uma struct
RPC AppendEntries (embora você não precise de todos os seus argumentos) e peça ao líder
para enviá-los periodicamente. Escreva um método da RPC AppendEntries que redefina o tempo limite da eleição para que outros servidores não
ajam como líderes quando um já tiver sido eleito.
·
Certifique-se de que o tempo
limite das eleições em diferentes participantes nem sempre seja acionado ao
mesmo tempo, ou então todos os participantes votarão em si mesmos e ninguém se
tornará líder.
·
O testador exige que o líder envie
RPCs de heartbeat
não mais que dez vezes por segundo.
·
O testador exige que o seu Raft escolha um novo líder dentro de cinco segundos após a
falha do antigo líder (se a maioria dos participantes ainda conseguir se
comunicar). Lembre-se, no entanto, que a eleição do líder pode exigir várias
rodadas em caso de votação por partes (o que pode acontecer se os pacotes forem
perdidos ou se os candidatos escolherem, por azar, os mesmos tempos aleatórios
de retirada). Você deve escolher o tempo limite das eleições (e, portanto, os
intervalos de heartbeats) que sejam curtos o
suficiente para que seja muito provável que uma eleição seja concluída em menos
de cinco segundos, mesmo que isso exija várias rodadas.
·
A Seção 5.2 do artigo menciona o
tempo limite das eleições entre 150 e 300 milissegundos.
Esse intervalo só faz sentido se o líder envia heartbeats
consideravelmente mais frequentemente do que uma vez a cada 150 milissegundos. Como o testador limita você a 10 heartbeats por segundo, você terá que usar um tempo limite
de eleição maior que os 150 a
300 milissegundos do artigo, mas não tão grande que
um líder não seja eleito em cinco segundos.
·
Os pacotes de tempo e rand de Go podem ser úteis.
·
Se o seu código tiver problemas
para passar nos testes, leia a Figura 2 do artigo novamente; a lógica completa
da eleição do líder está espalhada por várias partes da figura.
·
Uma boa maneira de depurar seu
código é inserir instruções de impressão quando um participante envia ou recebe
uma mensagem e coletar a saída em um arquivo com o comando go test -run 2A> out. Em seguida, estudando o rastreamento de mensagens no arquivo out, você pode identificar onde sua implementação se desvia do protocolo
desejado. Talvez DPrintf em util.go seja útil para ativar e desativar a impressão enquanto problemas
diferentes são depurados.
·
Você deve verificar seu código
com go test -race e corrigir as corridas relatadas.
Procedimento de entrega
Antes de enviar,
execute todos os testes uma última vez. Você é responsável por garantir que o
seu código funcione.
Você deve enviar seu código via Classroom.