Uma ferramenta poderosa para obter consenso em um sistema distribuído
O Algoritmo Raft é um algoritmo de consenso distribuído concebido para ser fácil de compreender e implementar. É normalmente utilizado em sistemas distribuídos, como bases de dados e sistemas de ficheiros distribuídos, para garantir a consistência e a disponibilidade dos dados.
Algumas aplicações reais do Algoritmo Raft incluem etcd, CockroachDB, e TiDB.
Primeiro, vamos configurar um novo projeto TypeScript usando o Yarn. No seu terminal, execute os seguintes comandos:
yarn init -y
yarn add -D typescript
yarn tsc --init
Isso criará um novo projeto package.json instalará o compilador TypeScript como uma dependência de desenvolvimento e criará um arquivo tsconfig.json para o seu projeto.
Antes de começarmos a implementar o Algoritmo da Jangada, vamos definir alguns tipos e enums para representar os diferentes componentes do algoritmo.
type Term = number;
type LogIndex = number;enum NodeState {
FOLLOWER = "follower",
CANDIDATE = "candidate",
LEADER = "leader",
}
type NodeId = string;
type LogEntry = {
term: Term;
command: any;
};
type Log = LogEntry[];
type StateMachine = {
applyCommand: (command: any) => void;
};
type NodeConfiguration = {
id: NodeId;
stateMachine: StateMachine;
currentTerm: Term;
votedFor: NodeId | null;
log: Log;
};
type RequestVoteRPC = {
term: Term;
candidateId: NodeId;
lastLogIndex: LogIndex;
lastLogTerm: Term;
};
type RequestVoteResponse = {
term: Term;
voteGranted: boolean;
};
type AppendEntriesRPC = {
term: Term;
leaderId: NodeId;
prevLogIndex: LogIndex;
prevLogTerm: Term;
entries: LogEntry[];
leaderCommit: LogIndex;
};
type AppendEntriesResponse = {
term: Term;
success: boolean;
};
Estes tipos e enums irão representar os diferentes componentes do Algoritmo da Jangada, tais como termos, registos e nós.
Primeiro, vamos implementar o tipo requestVote que os candidatos usam para pedir votos aos seguidores. Veja como isso se parece:
const requestVote = (
configuration: NodeConfiguration,
rpc: RequestVoteRPC
): RequestVoteResponse => {
// If the RPC term is less than the current term, return a response with voteGranted set to false
if (rpc.term < configuration.currentTerm) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}// If the RPC term is greater than the current term, update the current term and vote for the candidate
if (rpc.term > configuration.currentTerm) {
configuration.currentTerm = rpc.term;
configuration.votedFor = rpc.candidateId;
}
// If the voter has already voted for a candidate in this term, return a response with voteGranted set to false
if (configuration.votedFor && configuration.votedFor !== rpc.candidateId) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}
// If the candidate's log is not up-to-date, return a response with voteGranted set to false
const lastLogIndex = configuration.log.length - 1;
const lastLogTerm = configuration.log[lastLogIndex].term;
if (lastLogTerm > rpc.lastLogTerm || (lastLogTerm === rpc.lastLogTerm && lastLogIndex > rpc.lastLogIndex)) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}
// Otherwise, return a response with voteGranted set to true
configuration.votedFor = rpc.candidateId;
return {
term: configuration.currentTerm,
voteGranted: true,
};
};
Esta função recebe um NodeConfiguration e um objeto RequestVoteRPC como entrada e devolve um objeto RequestVoteResponse objeto. Verifica o termo RPC, o termo atual do eleitor e o registo do eleitor para determinar se deve conceder um voto ao candidato.
De seguida, deixe o objeto appendEntries utilizem a função para replicar entradas de registo e gerir o índice de confirmação.
const appendEntries = (
configuration: NodeConfiguration,
rpc: AppendEntriesRPC
): AppendEntriesResponse => {
// If the RPC term is less than the current term, return a response with success set to false
if (rpc.term < configuration.currentTerm) {
return {
term: configuration.currentTerm,
success: false,
};
}// If the RPC term is greater than the current term, update the current term and set the node's state to follower
if (rpc.term > configuration.currentTerm) {
configuration.currentTerm = rpc.term;
configuration.state = NodeState.FOLLOWER;
}
// If the previous log index and term don't match the node's log, return a response with success set to false
const prevLogIndex = rpc.prevLogIndex;
const prevLogTerm = rpc.prevLogTerm;
if (configuration.log[prevLogIndex]?.term !== prevLogTerm) {
return {
term: configuration.currentTerm,
success: false,
};
}
// Otherwise, append the new entries to the log and return a response with success set to true
configuration.log = [...configuration.log.slice(0, prevLogIndex + 1), ...rpc.entries];
configuration.commitIndex = Math.min(rpc.leaderCommit, configuration.log.length - 1);
return {
term: configuration.currentTerm,
success: true,
};
};
Esta função recebe um NodeConfiguration e um objeto AppendEntriesRPC como entrada e devolve um objeto AppendEntriesResponse objeto. Verifica o termo RPC, o índice de registo anterior, o termo e o registo do nó para determinar se deve anexar as novas entradas ao registo.
Finalmente, vamos implementar o objeto startElection que os seguidores utilizam para iniciar uma nova eleição quando não receberam qualquer comunicação de um líder.
const startElection = (configuration: NodeConfiguration): void => {
// Increment the current term and set the node's state to candidate
configuration.currentTerm++;
configuration.state = NodeState.CANDIDATE;// Reset the votedFor field
configuration.votedFor = null;
// Request votes from other nodes
sendRequestVoteRPC(configuration);
};
const sendRequestVoteRPC = (configuration: NodeConfiguration): void => {
// Implementation omitted for brevity
// Sends a RequestVoteRPC to other nodes in the cluster
};
Esta função recebe um NodeConfiguration como entrada e incrementa o termo atual, define o estado do nó para um candidato e envia RequestVoteRPCs para outros nós do cluster.
Agora que implementámos as principais funções do Algoritmo da Jangada, vamos adicionar mais algumas funções para completar a implementação.
Primeiro, vamos adicionar a função handleRequestVoteRPC que é chamada quando um nó recebe um RequestVoteRPC.
const handleRequestVoteRPC = (
configuration: NodeConfiguration,
rpc: RequestVoteRPC
): RequestVoteResponse => {
// If the RPC term is less than the current term, return a response with voteGranted set to false
if (rpc.term < configuration.currentTerm) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}// If the RPC term is greater than the current term, update the current term and set the node's state to follower
if (rpc.term > configuration.currentTerm) {
configuration.currentTerm = rpc.term;
configuration.state = NodeState.FOLLOWER;
}
// If the node is already a leader or a candidate, return a response with voteGranted set to false
if (configuration.state === NodeState.LEADER || configuration.state === NodeState.CANDIDATE) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}
// If the node has already voted for another candidate in this term, return a response with voteGranted set to false
if (configuration.votedFor && configuration.votedFor !== rpc.candidateId) {
return {
term: configuration.currentTerm,
voteGranted: false,
};
}
// Otherwise, return the result of the requestVote function
return requestVote(configuration, rpc);
};
De seguida, vamos adicionar o handleAppendEntriesRPC que é chamada quando um nó recebe um AppendEntriesRPC.
const handleAppendEntriesRPC = (
configuration: NodeConfiguration,
rpc: AppendEntriesRPC
): AppendEntriesResponse => {
// If the RPC term is less than the current term, return a response with success set to false
if (rpc.term < configuration.currentTerm) {
return {
term: configuration.currentTerm,
success: false,
};
}// If the RPC term is greater than the current term, update the current term and set the node's state to follower
if (rpc.term > configuration.currentTerm) {
configuration.currentTerm = rpc.term;
configuration.state = NodeState.FOLLOWER;
}
// If the node is a leader, return a response with success set to false
if (configuration.state === NodeState.LEADER) {
return {
term: configuration.currentTerm,
success: false,
};
}
// Otherwise, return the result of the appendEntries function
return appendEntries(configuration, rpc);
};
Esta função recebe um NodeConfiguration e um objeto AppendEntriesRPC como entrada e devolve um objeto AppendEntriesResponse objeto. Primeiro, verifica o termo RPC e o estado do nó e, em seguida, devolve uma resposta com sucesso definido como falso ou chama a função appendEntries para determinar o resultado.
Finalmente, vamos adicionar a função advanceCommitIndex que é chamada quando um nó líder recebe um AppendEntriesResponse de uma maioria de seguidores.
const advanceCommitIndex = (
configuration: NodeConfiguration,
responses: AppendEntriesResponse[]
): void => {
// Sort the responses by term and index
responses.sort((a, b) => a.term !== b.term ? a.term - b.term : a.index - b.index);// Find the highest index that is included in a majority of responses
const majority = Math.floor(responses.length / 2) + 1;
let commitIndex = 0;
for (let i = 0; i < responses.length; i++) {
if (responses.slice(0, i + 1).filter((r) => r.success).length >= majority) {
commitIndex = responses[i].index;
}
}
// Set the commit index to the highest index that is included in a majority of responses
configuration.commitIndex = commitIndex;
};
Esta função recebe um NodeConfiguration e uma matriz de AppendEntriesResponse como entrada e atualiza o índice de confirmação do nó. Ele classifica as respostas por termo e índice e, em seguida, encontra o índice mais alto incluído na maioria das respostas.
Para compilar o código TypeScript para JavaScript, adicione o seguinte script ao diretório scripts no campo package.json ficheiro:
"scripts": {
"build": "tsc"
}
Para compilar o código, execute o seguinte comando:
yarn build
Também pode utilizar o comando --watch para recompilar automaticamente o código quando são efectuadas alterações:
yarn build --watch
Para utilizar as funções que implementámos nas secções anteriores, importe-as para o seu código e passe os argumentos necessários. Por exemplo:
import { NodeConfiguration, NodeState } from './nodeConfiguration';
import { requestVote, handleRequestVoteRPC } from './requestVote';
import { appendEntries, handleAppendEntriesRPC } from './appendEntries';
import { startElection } from './startElection';
import { advanceCommitIndex } from './advanceCommitIndex';// Create a new NodeConfiguration object and set its state to FOLLOWER
const configuration = new NodeConfiguration();
configuration.state = NodeState.FOLLOWER;
// Create a requestVote RPC object
const rpc = {
term: 1,
candidateId: 'node-1',
lastLogIndex: 0,
lastLogTerm: 1,
};
console.log(requestVote(configuration, rpc));
console.log(handleRequestVoteRPC(configuration, rpc));
const entries = [
{
term: 1,
command: 'foo',
},
{
term: 1,
command: 'bar',
},
];
const appendEntriesRPC = {
term: 1,
leaderId: 'node-2',
prevLogIndex: 0,
prevLogTerm: 1,
entries,
leaderCommit: 1,
};
console.log(appendEntries(configuration, appendEntriesRPC));
console.log(handleAppendEntriesRPC(configuration, appendEntriesRPC));
startElection(configuration);
const responses = [
{
term: 1,
index: 2,
success: true,
},
{
term: 1,
index: 2,
success: true,
},
{
term: 1,
index: 1,
success: true,
},
];
advanceCommitIndex(configuration, responses);
/*
Output:
{ term: 1, voteGranted: true }
{ term: 1, voteGranted: true }
{ term: 1, success: true }
{ term: 1, success: true }
null
null
*/
Para testar as funções que implementámos neste projeto, utilizaremos a função jest para testar a estrutura.
Primeiro, instale jest como uma dependência de desenvolvimento:
yarn add -D jest
Em seguida, crie um arquivo tests na raiz do projeto e crie um diretório nodeConfiguration.test.ts dentro dele.
No ficheiro nodeConfiguration.test.ts importe o ficheiro NodeConfiguration e escreva um teste para garantir que uma nova classe NodeConfiguration é criado com os valores predefinidos correctos:
import { NodeConfiguration } from '../nodeConfiguration';test('creates a new NodeConfiguration object with the correct default values', () => {
const configuration = new NodeConfiguration();
expect(configuration.id).toBeDefined();
expect(configuration.currentTerm).toBe(0);
expect(configuration.votedFor).toBeNull();
expect(configuration.log).toEqual([]);
});
Para executar os testes, adicione o seguinte script à pasta scripts no campo package.json ficheiro:
"scripts": {
"test": "jest"
}
De seguida, execute os testes executando o seguinte comando:
yarn test
Isto irá executar todos os testes no ficheiro tests e exibirá os resultados.
Em seguida, escreva testes para o requestVote e handleRequestVoteRPC funções. Para isso, crie um novo ficheiro chamado requestVote.test.ts no diretório tests e adicione os seguintes testes:
import { NodeConfiguration, NodeState } from '../nodeConfiguration';
import { requestVote, handleRequestVoteRPC } from '../requestVote';test('requestVote function returns voteGranted as true if RPC term is equal to current term and the node has not voted for another candidate in this term', () => {
const configuration = new NodeConfiguration();
configuration.state = NodeState.FOLLOWER;
configuration.currentTerm = 1;
const rpc = {
term: 1,
candidateId: 'node-1',
lastLogIndex: 0,
lastLogTerm: 1,
};
expect(requestVote(configuration, rpc)).toEqual({ term: 1, voteGranted: true });
})
test('handleRequestVoteRPC function does not update the node configuration if RPC term is less than current term', () => {
const configuration = new NodeConfiguration();
configuration.state = NodeState.FOLLOWER;
configuration.currentTerm = 2;
configuration.votedFor = 'node-2';
const rpc = {
term: 1,
candidateId: 'node-1',
lastLogIndex: 0,
lastLogTerm: 1,
};
handleRequestVoteRPC(configuration, rpc);
expect(configuration.currentTerm).toBe(2);
expect(configuration.votedFor).toBe('node-2');
});
test('handleRequestVoteRPC function does not update the node configuration if the node has already voted for another candidate in the current term', () => {
const configuration = new NodeConfiguration();
configuration.state = NodeState.FOLLOWER;
configuration.currentTerm = 1;
configuration.votedFor = 'node-2';
const rpc = {
term: 1,
candidateId: 'node-1',
lastLogIndex: 0,
lastLogTerm: 1,
};
handleRequestVoteRPC(configuration, rpc);
expect(configuration.currentTerm).toBe(1);
expect(configuration.votedFor).toBe('node-2');
});
Existem muitos outros testes unitários para adicionar seguindo o mesmo padrão.
Em conclusão, o algoritmo Raft é uma ferramenta poderosa para obter consenso num sistema distribuído. Seguindo o protocolo Raft, os nós do sistema podem chegar a um acordo sobre um conjunto consistente de comandos, mesmo em face de falhas e partições de rede.
Este artigo fornece uma implementação prática do algoritmo Raft em TypeScript. Embora essa implementação seja apenas um exemplo de como o algoritmo Raft pode ser implementado, ela serve como uma referência útil para entender os conceitos por trás do algoritmo e como eles podem ser aplicados na prática.
Também incluímos explicações técnicas detalhadas e referências de aplicações reais ao longo do artigo para entender melhor o algoritmo Raft e sua importância em sistemas distribuídos.
Em geral, o algoritmo Raft é um componente essencial de qualquer sistema distribuído e esperamos que este artigo tenha sido um recurso útil para entender sua implementação e aplicação.
