Neste capítulo apresento um protocolo chamado Raft. Uma solução possível para o problema de garantir consenso entre unidades de processamento em sistemas distribuídos.

O que é “consenso” e por que é importante

Imagine-se desenvolvendo um sistema que necessite um componente para “contar acessos” realizados em determinadas páginas de um site. 

Demandas por disponibilidade e resiliência geralmente são atendidas mediante adição de recursos redundantes.

A solução evidente para melhorar tais atributos é ponderar sobre a adição de mais “unidades de processamento”. Entretanto, daí nasce a dificuldade de garantir que todas mantenham o mesmo estado (em nosso exemplo, entradas e valores no dicionário).  Ou melhor, que todas as unidades “concordem” sobre quais são os valores atualizados. Ou seja, as “unidades de processamento” precisam manter consenso.

Sem consenso, não seria possível cumprir o objetivo funcional.

Em aplicações data centric é comum “transferir a responsabilidade” de garantir consenso para bancos de dados operando em cluster (para garantir confiabilidade).

O que é o Raft

Raft é um protocolo que, corretamente implementado, garante consenso em sistemas distribuídos. Ele foi desenvolvido como uma alternativa mais fácil de entender e implementar ao Paxos – outro protocolo, desenvolvido por Leslie Lamport, que ainda é um padrão de facto.

Raft, In Search of an Understandable Consensus Algorithm Excelente palestra ministrado pelos criadores do Raft, detalhando o funcionamento do protocolo. Acessar vídeo

Raft, assim como Paxos, habilita a aplicação de uma técnica conhecida como State Machine Replication que permite a conversão de algoritmos em versões distribuídas, tolerantes a falhas.

Implementing Fault-tolerant services using the State Machine Approach: a tutorial Fred Schneider compartilha nesse artigo uma abordagem geral para conversão de serviços em máquinas de estado que, por sua vez, podem ser distribuídas, viabilizando o desenvolvimento de serviços tolerantes a falhas. Acessar artigo

Conceitos fundamentais do Raft

Raft entende que há consenso quando a maioria simples de “unidades de processamento” cooperando (por exemplo, 3 nós em um cluster com 5) em determinado trabalho “concordam em aceitar” uma demanda. No exemplo indicado anteriormente, uma “atualização” no contador de acessos a um recurso seria “globalmente aceita” quando houvessem evidências de que ela pode ser aplicada na maioria simples dos nós.

A “orquestração” do trabalho, em um cluster operando Raft, é garantida por um nó operando como líder (leader), enquanto os demais operam como seguidores (followers). Todas as demandas de trabalho para o cluster são sempre realizadas através do nó-líder, ou encaminhadas para ela quando recebidas por um nó-seguidor.

Caso o nó-lider fique, por alguma razão, indisponível, ocorre a eleição de outro nó do cluster para esta função. Idealmente, todos os nós devem ter condições (implementação) de assumir a liderança. De qualquer forma, para que um nó se converta em líder, deve-se lançar como candidato.

O nó-lider mantem comunicação contínua, em intervalos regulares, com todos os nós-seguidores (heartbeat). O intuito é garantir que o “líder vive”.

Um nó-seguidor lança-se candidato sempre que ficar “tempo demais” sem receber notificações do nó-líder. Quando isso acontece, ele assume que o nó-líder está indisponível e assume que seu mandato (term) chegou ao fim. Envia, então, solicitações de votos a todos os nós do cluster e considera-se eleito caso receba confirmação da maioria simples.

O tempo em que um nó ocupa a liderança é considerado seu “mandato” (term). Os mandatos no cluster são identificados através de um contador incremental, atualizado sempre que um nó lança-se candidato.

Um nó-seguidor concordará em votar em outro nó, para assumir a liderança, quando 1) não estiver mais recebendo mensagens do nó-líder com mandato em vigência; 2) ele mesmo não tiver se lançado candidato; 3) ainda não tiver “votado” no term especificado no pedido de voto que recebeu.

Um nó-candidato que não receber votos suficientes (maioria simples) durante um período razoável (election timeout) pode iniciar uma nova campanha, incrementando o term, caso não tenha ainda sido contatado por un novo nó-líder.

Por todo o exposto, entende-se então que cada nó em um cluster operando Raft pode assumir um dos seguintes três papéis: líder, seguidor, candidato.

Arquitetura (proposta) de um “nó” Raft

Cada nó em um cluster Raft possuirá a implementação de dois serviços e uma estrutura de dados.

O primeiro serviço, um motor de consenso, é o responsável pela implementação do protocolo para relacionamento com outros nós e a atualização do log.

O log é uma estrutura de dados, implementada em sua forma mais simples como uma lista encadeada, que relaciona todos os comandos commited que devem ser processados pela máquina de estados.

O segundo serviço, a máquina de estados, é quem, efetivamente, processa os comandos relacionados no log.

A eleição do líder (leader election)

Todo nó em um cluster assume o status de follower por padrão.

Quando um follower fica tempo suficiente sem receber quaisquer mensagens de um leader (election timeout, randomizado entre 150ms e 300ms), alterna imediatamente seu estado para candidate e passa a solicitar votos para os demais participantes tentando iniciar um novo mandato (election term).

Um nó converte-se em líder quando recebe a maioria simples (número de nós, mais um [incluindo o dele]) de votos positivos dos participantes do cluster.

Se um número suficiente de votos não for obtido em tempo razoável (election timeout), o nó abandona sua candidatura.

O processo que define um líder para o cluster é conhecido como leader election.

Replicando dados (log Replication)

O funcionamento de um cluster Raft pode ser descrito como segue:

1. Todo comando recebido por um nó Raft, a partir de um cliente, é encaminhado para processamento pelo motor de consenso do nó-líder que o adiciona ao seu log em estado uncommited.
2. O nó-servidor envia entradas uncommited para que sejam replicadas nos logs dos nós-seguidores, também como uncommited.
3. Os nós-seguidores confirmam para o nó servidor o recebimento e a adição do comando em seus logs
4. O nó-servidor, ao receber confirmação da maioria simples dos nós-seguidores, muda o estado do comando, no log, para commited.
5. Cada nó-seguidor atualiza o estado do comando, no log, para commited
6. As máquinas de estado, em cada nó, processam comandos, ainda não processados, que estejam em estágio commited.
7. O nó-servidor, retorna sucesso para o cliente.

Caso o nó-líder não receba confirmações suficientes para um comando, ele é removido do log.

The Secret Lives of Data - Raft Ben Johnson conseguiu criar uma visualização tremendamente amistosa para como Raft funciona – gráfica e interativa. Vale a pena! Acessar artigo

Recuperando-se de partições de rede (network partitions)

Quando, eventualmente, ocorrer uma partição na rede do cluster (como, por exemplo, quando os nós encontram-se em dois datacenters separados), eventualmente poderá ocorrer uma nova eleição em uma das participações e, inclusive, a eleição de um novo líder caso existam elementos suficientes para obtenção de maioria simples.

A liderança com a partição com menos elementos não será capaz de aceitar alterações em função de não possuir maioria simples para que ocorra o commit. Já a liderança com a maioria poderá aceitar atualizações sem restrições.

Ao se desfazer a partição, o antigo líder receberá indicativo da presença de um novo líder com um “mandato” mais recente e deverá abdicar de sua posição.

Para pensar…

Construir sistemas escaláveis, disponíveis, confiáveis e resilientes não é tarefa simples. Invariavelmente, o projeto de tais sistemas demanda abordagens distribuídas que apresentam uma série de desafios difíceis de superar, com destaque para a gestão de consenso.

Em boa parte das situações, a gestão do consenso é obtida pela utilização de algum mecanismo de armazenamento – como banco de dados – distribuído. Entretanto, essa não precisa e nem deveria ser a única abordagem.

A utilização de estruturas de dados como quadtrees, por exemplo, tão úteis para serviços baseados em localização, é consideravelmente mais fácil em memória, logo pela adoção de um protocolo como Raft (ou Paxos).

Quadtrees (LBS) Interessado em saber mais sobre Quadtrees e sua adoção em sistemas LBS? Confira esse tópico em detalhes no “Manual do Arquiteto de Software” Acessar tópico