Eleição de líder em sistemas distribuídos

Eleição de líder é a simples ideia de conceder alguns poderes especiais a algo (um processo, um host, uma thread, um objeto ou uma pessoa) em um sistema distribuído. Esses poderes especiais podem incluir a capacidade de atribuir trabalho, de modificar uma parte dos dados ou até a responsabilidade de processar todas as solicitações no sistema.

A eleição de líder é uma ferramenta importante para melhorar a eficiência, reduzir a coordenação, simplificar arquiteturas e reduzir operações. Por outro lado, a eleição de líder pode introduzir novos modos de falha e gargalos de escalabilidade. Além disso, a eleição de líder pode dificultar a sua avaliação da exata de um sistema.

Devido a essas complicações, nós consideramos cuidadosamente outras opções antes de implementar a eleição de líder. Para processamento de dados e fluxos de trabalho, muitos dos mesmos benefícios da eleição de líder podem ser alcançados com serviços de fluxo de trabalho como o AWS Step Functions, mas evitando muitos dos riscos. Para outros sistemas, nós geralmente implementamos APIs idempotentes, bloqueio otimístico e outros padrões que tornam um único líder desnecessário.

Neste artigo, discuto alguns dos prós e contras da eleição de líder em geral e como a Amazon aborda a eleição de líder em nossos sistemas distribuídos, incluindo insights sobre falha do líder.

Há várias maneiras de eleger um líder, que variam de algoritmos como o Paxos e software como o Apache ZooKeeper até hardware personalizado e concessões. As concessões são o mecanismo de eleição de líder mais utilizado na Amazon. As concessões são relativamente simples de entender e implementar e oferecem tolerância a falhas integrada. As concessões funcionam com um único banco de dados que armazena o líder atual. Em seguida, a concessão exige que o líder emita uma pulsação periodicamente para mostrar que ainda é o líder. Se o líder existente deixar de emitir essa pulsação após algum tempo, outros candidatos a líder podem tentar assumir.

Evitamos depender do tempo em sistemas distribuídos, mesmo com o ótimo recurso de sincronização de tempo no Amazon Elastic Compute Cloud (Amazon EC2). É difícil garantir que os relógios do sistema em um cluster estejam sincronizados o suficiente para depender dessa sincronização para ordenar ou coordenar operações distribuídas. Na Amazon, os sistemas distribuídos só usam o tempo para consumo humano. As concessões dependem do tempo. No entanto, dependem somente da duração do tempo decorrido localmente, não do horário em um relógio de parede que é sincronizado com vários servidores que precisam estar de acordo com esse horário.

O código-fonte do cliente de bloqueio do DynamoDB oferece exemplos e detalhes relacionados à eleição de líder. No entanto, descobrimos que, embora as concessões e os bloqueios sejam conceitualmente simples, a implementação correta pode ser sutil. As implementações exigem o entendimento de como um servidor está medindo a duração do tempo local. Por exemplo, se um servidor ou uma biblioteca que mede o tempo considerasse que o tempo retrocedeu algumas vezes, ele interromperia as pressuposições sobre durações de tempo integradas às concessões. As durações evitam os problemas com a sincronização global do relógio, que fazem com que os servidores parem de concordar sobre que horas são, de segundos ignorados ao desvio do relógio local ao longo do tempo devido à alta utilização contínua da CPU.

Um problema maior sobre concessões, e sobre todos os tipos de bloqueios distribuídos, é garantir que o líder esteja trabalhando apenas enquanto mantém o bloqueio. Na realidade, é muito difícil garantir que o líder mantenha o bloqueio. Consideramos importante garantir que um líder em uma rede lenta ou com perdas não acredite que esteja mantendo bloqueios por mais tempo do que realmente está. De maneira similar, as pausas para coleta de lixo entre um bloqueio que está sendo verificado e o trabalho que está sendo feito podem levar a um comportamento incorreto. Na prática, a proteção contra esses problemas geralmente é o maior desafio.

O DynamoDB e o ZooKeeper oferecem clientes de bloqueio simples baseados em concessões que fornecem eleição de líder tolerante a falhas. A menos que haja necessidades específicas, preferimos esses clientes, pois acreditamos que eles fornecem a maneira mais fácil e testada de implementar a eleição de líder. As equipes da Amazon preferem evitar a criação de uma implementação personalizada de eleição de líder. Em vez disso, favorecemos os clientes existentes que são bem testados e comprovados na prática.

A eleição de líder é um padrão amplamente empregado na Amazon. Por exemplo:

• Quase todos os sistemas que usam sistemas tradicionais de gerenciamento de bancos de dados relacionais (RDBMSs) dependem da eleição de líder para selecionar um banco de dados de líderes que processe todas as gravações e, algumas vezes, todas as leituras. Nesses sistemas, a eleição pode ser automatizada, mas frequentemente é feita manualmente por um operador humano.
• Amazon EBS distribui leituras e gravações para um volume maior do que o de muitos servidores de armazenamento. Para garantir a consistência, ele usa a eleição de líder ele escolhe primários para cada área do volume, que ordenam as leituras e gravações. Se aquele primário falha, as cópias seguidoras assumem usando o mesmo mecanismo de eleição de líder. No Amazon EBS, a eleição de líder garante consistência e, ao mesmo tempo, melhora a performance evitando a coordenação no plano de dados. O DynamoDB, o Amazon Quantum Ledger Database (Amazon QLDB) e o Amazon Kinesis (Kinesis) usam abordagens similares pelo mesmo motivo.
• A Biblioteca de Cliente do Kinesis (KCL) usa concessões para garantir que cada fragmento do Kinesis seja processado por um proprietário, facilitando a expansão do processamento de streams do Kinesis.

Outro item a considerar atentamente é o que acontece ao trabalho de um líder quando ele falha. Se um líder falhar durante uma tarefa, como o novo líder conclui essa tarefa? Se um líder falhar antes de tornar seu trabalho durável, o sistema ainda estará correto? Muitos tipos de sistema têm etapas distintas para "tornar o trabalho durável" e "comunicar aos outros que está concluído". Na Amazon, nossos sistemas sempre executam a primeira etapa antes da segunda (ou toleram perda de dados). Novamente, a idempotência é útil aqui. Ela permite que o novo líder redistribua com confiança o trabalho que o líder cessante pode ter concluído parcial ou totalmente, mas não comunicou a outros.

Para tolerar falhas, os sistemas distribuídos da Amazon não têm um único líder. Em vez disso, a liderança é uma propriedade que passa de servidor para servidor, ou de processo para processo. Em sistemas distribuídos, não é possível garantir que exista exatamente um líder no sistema. Em vez disso, geralmente pode haver um líder e pode haver zero ou dois líderes durante as falhas.

Como escolhemos o comportamento do sistema na falha do líder depende do que acontece em um sistema quando há dois líderes. Os sistemas que realizam trabalhos idempotentes geralmente podem tolerar dois líderes com perda mínima de eficiência. Com dois líderes, os sistemas podem alcançar maior disponibilidade e escolher abordagens de eleição de líder mais fracas.

Sistemas que definitivamente precisam de, no máximo, um líder são mais difíceis de criar do que sistemas de vários líderes. O sistema de eleição do líder deve sempre ser correto e consistente. E deve garantir que o líder cessante seja deposto antes da eleição de um novo líder, o que é mais difícil do que parece. Em sistemas distribuídos, geralmente é difícil saber se um sistema falhou ou se simplesmente continua a funcionar em alguma outra partição de rede. Na Amazon, garantimos que qualquer sistema com líder eleito lide com esse caso de borda.

Na Amazon, seguimos estas melhores práticas para a eleição de líder:

• Verificar o tempo restante da concessão (ou o status de bloqueio em geral) com frequência e principalmente antes de iniciar qualquer operação que tenha efeitos colaterais além do próprio líder.
• Considerar que as pausas provocadas por redes lentas, limites de tempo, novas tentativas e coleta de lixo podem fazer com que o tempo restante da concessão expire antes do que é esperado pelo código.
• Evitar concessões com emissão de pulsação em uma thread de segundo plano. Isso pode causar problemas de correção se a thread não puder interromper o código quando a concessão expirar ou a thread de emissão de pulsação se extinguir. Podem ocorrer problemas de disponibilidade se a thread de trabalho se extinguir ou parar enquanto a thread de emissão de pulsação permanecer na concessão.
• Ter métricas confiáveis que mostrem quanto trabalho um líder pode fazer em comparação com quanto está fazendo agora. Revise essas métricas com frequência e verifique se há planos de escalabilidade antes de ficar sem capacidade.
• Facilitar a localização de qual host é o líder atual e qual host foi o líder em um determinado momento. Mantenha uma trilha de auditoria ou log das alterações de liderança.
• Modelar e verificar formalmente a correção dos algoritmos distribuídos usando ferramentas como o TLA+. Isso captura bugs sutis, difíceis de observar e raros que podem surgir quando um aplicativo faz muitas pressuposições sobre as garantias fornecidas pelo protocolo de eleição do líder.

A eleição de líder é uma ferramenta importante usada em sistemas na Amazon para ajudar a tornar nossos sistemas tolerantes a falhas e mais fáceis de operar. No entanto, quando usamos a eleição de líder, avaliamos cuidadosamente as garantias que cada protocolo de eleição de líder fornece e, principalmente, as garantias que esses protocolos não fornecem.

Os sistemas da Amazon costumam usar a eleição de líder para garantir que a tolerância a falhas esteja integrada. Quando os sistemas usam a eleição de líder para garantir que pelo menos um servidor esteja processando uma tarefa, eles usam mecanismos separados para manter a correção diante de vários líderes simultâneos. Por exemplo, eles podem usar um banco de dados subjacente para garantir que, se dois líderes pensarem que estão mantendo uma concessão, eles não causem interferência entre si. Em vez de fazer suposições sobre as garantias fornecidas por uma implementação de concessão, nos concentramos na correção desses sistemas, geralmente na modelagem com técnicas como TLA+.

Apesar das nuances, a eleição de líder continua sendo uma ferramenta útil em nosso toolkit de sistemas distribuídos na Amazon, juntamente com padrões como idempotência e bloqueio otimista.

Para obter mais informações sobre como as concessões funcionam, consulte:

• Como fazer o bloqueio distribuído
• Burrows, The Chubby lock service for loosely-coupled distributed systems
• Gray e Cheriton, Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency