Explorando a Teoria de Sistemas Distribuídos: Disponibilidade e Consistência

Um especialista técnico sênior do Alibaba introduz os algoritmos que superam os limites propostos no teorema CAP

Alibaba Tech Blocked Desbloquear Seguir Seguindo 8 de janeiro

Em sistemas distribuídos, disponibilidade e consistência são as questões predominantes mais básicas, razão pela qual sua relação tem sido objeto de extenso estudo. O conhecido teorema da CAP define sua relação como mutuamente exclusiva em ambientes distribuídos em larga escala, onde o terceiro fator em tais sistemas, a tolerância à partição, não pode ser tratado como uma variável. Em uma tentativa de contornar essas questões, o protocolo Paxos, vencedor do prêmio Turing, já foi proposto para maximizar a eficiência da disponibilidade e consistência em tais sistemas. Para abordar ainda mais os problemas prevalentes neste algoritmo Paxos, o protocolo ZAB foi posteriormente desenvolvido a partir de um algoritmo original, indo muito além da otimização básica para melhorar seu predecessor.

Com base nos insights do especialista técnico sênior do Alibaba, Jiandu, este artigo apresenta o teorema CAP e descreve como os algoritmos mencionados acima são aplicados a sistemas distribuídos para equilibrar melhor a disponibilidade, a consistência e a tolerância à partição.

Desafios em sistemas distribuídos

Sistemas distribuídos são sistemas de componentes que estão localizados em diferentes computadores em rede e se comunicam e coordenam suas ações transmitindo mensagens uns aos outros. Dentro desses sistemas, a consistência é um status em que todos os nós (ou componentes) podem acessar a versão mais recente dos dados, o que é fácil de implementar em um cenário independente usando memória compartilhada e bloqueios.

No entanto, existem duas grandes limitações ao armazenamento de dados em uma máquina independente. Em primeiro lugar, a falha da máquina autônoma leva à indisponibilidade de todo o sistema. Em segundo lugar, a taxa de transferência do sistema é limitada pelo poder de computação da máquina autônoma.

Essas duas restrições, no entanto, podem ser superadas usando várias máquinas para armazenar várias cópias dos dados. Nesse cenário, o cliente responsável pela atualização atualiza simultaneamente várias cópias dos dados. Isso, então, aumenta o problema em potencial da rede entre várias máquinas que não conseguem se conectar. Se esse for o caso, o cliente responsável pela atualização não poderá se conectar a várias máquinas de uma só vez, tornando impossível garantir que a versão mais recente dos dados possa ser lida em todos os clientes.

Para ilustrar isso, vamos pegar o exemplo mostrado abaixo com três clientes e dois servidores. O cliente A é responsável por atualizar os dados. Para garantir que os dados no Servidor 1 e no Servidor 2 sejam consistentes, o Cliente A envia a gravação de X = 1 para o Servidor 1 e Servidor 2 simultaneamente. Mas quando ocorre uma partição de rede (uma rede indisponível) entre o Cliente A e o Servidor 2, se a gravação de X = 1 no Servidor 1 for bem sucedida, o Cliente B e o Cliente C lerão valores inconsistentes de X do Servidor 1 e Servidor 2. Para manter a consistência do valor X, a gravação de X = 1 deve falhar no Servidor 1 e no Servidor 2. Esse tipo de cenário é incorporado ao teorema CAP, que afirma que sob a premissa de tolerar partições de rede, a consistência de dados ou a disponibilidade de operações de gravação devem ser sacrificados.

Diagrama esquemático da teoria do PAC

Para resolver esse problema, uma opção seria o Cliente C ler e usar os valores X e as informações de versão no Servidor 1 e no Servidor 2 simultaneamente, conforme mostrado na figura abaixo. No entanto, o particionamento de rede também pode ocorrer entre o Cliente C e o Servidor 1, o que basicamente sacrifica a disponibilidade de leitura para disponibilidade de gravação e ainda não quebra o escopo do teorema CAP.

Otimização da disponibilidade a partir da figura anterior

O teorema da PAC

A ideia central por trás do teorema CAP é que os sistemas de compartilhamento de dados baseados em rede podem fornecer apenas duas das três garantias a seguir:

· Consistência (todos os nós lêem a versão mais recente dos dados)

· Disponibilidade (os dados são altamente disponíveis)

· Tolerância de partição (o particionamento de rede é tolerado e a rede não está disponível entre partições)

Para sistemas distribuídos em grande escala, o particionamento de rede é uma realidade que deve ser tolerada e, portanto, a única opção real é entre disponibilidade e consistência. O teorema CAP parece definir um final pessimista para sistemas distribuídos, onde os sistemas distribuídos populares são aparentemente julgados de acordo com a teoria. Por exemplo, o HBase é considerado um sistema CP, enquanto o Cassandra é considerado um sistema AP.

O teorema da CAP afirma que os dados em um sistema distribuído não podem obter disponibilidade e consistência simultaneamente. No entanto, em um sistema, muitas vezes há muitos tipos de dados. Alguns dados (por exemplo, o saldo de uma conta bancária) exigem consistência forte, enquanto outros dados (por exemplo, o número total de contas em um banco) não. Portanto, geralmente, o teorema é usado para dividir todo o sistema. A equipe do Alibaba, no entanto, vê o valor do teorema CAP como um guia para levar em consideração as características de vários dados ao projetar um sistema distribuído. Também é útil ao escolher cuidadosamente entre disponibilidade ou consistência dos dados quando há uma pequena probabilidade de ocorrer particionamento de rede.

Outro equívoco do teorema da PAC diz respeito à escolha de um problema sem otimizar os outros problemas ao projetar um sistema. O intervalo dos valores de disponibilidade e consistência não é apenas 0 e 1. O valor da disponibilidade pode ser definido como um intervalo contínuo entre 0 e 100%, enquanto a consistência pode ser dividida em vários níveis diferentes, como consistência forte, consistência fraca , leia e escreva consistência e consistência final. Para ser mais preciso, o que o teorema CAP define é que sob a condição de tolerância à partição, “consistência forte” e “disponibilidade final” não podem ser alcançadas simultaneamente.

(Nota: “Ultimate availability” é usado aqui em vez de “100% disponibilidade”, já que um sistema distribuído composto por vários servidores é menor que 100% disponível mesmo se a consistência não for considerada. Se a disponibilidade de um único servidor for P, então a disponibilidade final de n servidores é. Essa fórmula significa que um sistema é considerado disponível desde que um ou mais servidores estejam disponíveis.

Embora seja impossível obter consistência forte e disponibilidade final simultaneamente, um deles pode ser selecionado de acordo com o tipo de dados para otimizar o outro. O protocolo Paxos é um algoritmo que otimiza a disponibilidade sob a premissa de garantir consistência forte.

O Protocolo Paxos

O protocolo Paxos propõe que se f + 1 nós de 2f + 1 nós em um sistema estiverem disponíveis, então o sistema como um todo está disponível e pode garantir consistência de dados forte, o que é uma grande melhoria para a disponibilidade. Se continuarmos a supor que a disponibilidade de nós únicos é P, então a disponibilidade normal de qualquer combinação de mais de f + 1 nós de 2f + 1 nós é P (total) =; e se assumirmos que P = 0,99, f = 2, P (total) = 0,99999901494, então a disponibilidade será melhorada de dois 9s para cinco 9s por nó. Isso significa que o tempo de inatividade anual de um sistema cairá de 87,6 horas para 0,086 horas, o que é suficiente para atender aos requisitos de 99,9999999% de aplicativos no planeta.

O protocolo Paxos compara a solicitação de gravação de cada parte dos dados a uma proposta. Cada proposta, com um número único, será encaminhada ao Proponente para envio e deve ser aceita por f + 1 nós de 2f + 1 para entrar em vigor. Os nós 2f + 1 são chamados de Quórum desta proposta e os nós entre o Quórum são chamados de Aceitadores.

Além disso, o processo do protocolo Paxos deve atender a duas condições. Em primeiro lugar, o aceitante deve aceitar a primeira proposta recebida. Em segundo lugar, se o valor V de uma proposta for aceito pela maioria dos Aceitadores, todas as propostas aceitas subsequentes também devem conter valores V (o valor V pode ser entendido como o conteúdo de uma proposta, que consiste em um ou mais Vs e um número de proposta ).

O processo do protocolo Paxos é dividido em duas fases. A primeira fase é a fase de preparação para o proponente aprender o estado mais recente da proposta e inclui os seguintes passos:

1. O proponente selecciona um número de proposta n e, em seguida, envia um pedido de preparação com o número n para mais de metade dos aceitantes.

2. Se um Aceitante receber uma solicitação de preparação com o número n e o valor de n for maior que o número de todas as solicitações de preparação às quais ele respondeu, então garante que nenhuma proposta com um número menor que n seja aceita. Enquanto isso, a maior proposta numerada aceita, se houver, é respondida.

A segunda fase do Paxos é a fase de submissão da proposta correta com base no estado aprendido e inclui as seguintes etapas:

1. Se o Proponente receber uma resposta de mais da metade dos Aceitadores para seus pedidos de preparação (numerados como n), então ele envia uma solicitação de aceitação para a proposta com o número n e o valor como v para Aceitadores, onde v é o valor da proposta com o maior número na resposta recebida. Se a resposta não contiver uma proposta, então v será um valor arbitrário.

2. Se um Aceitante receber uma solicitação de aceitação de uma proposta com número n, ela poderá aceitar a proposta, desde que não tenha respondido a uma solicitação de preparação com um número maior que n.

Um diagrama de tempo de visão geral do protocolo Paxos é mostrado abaixo.

O protocolo Paxos incorpora os componentes Client, Proposer, Acceptor e Learner

O processo do protocolo Paxos acima parece complicado porque a integridade do protocolo deve ser garantida sob um número de condições de contorno. Por exemplo, o valor inicial do teste deve estar vazio e os dois Proponentes devem enviar propostas simultaneamente. No entanto, o núcleo do protocolo Paxos pode ser simplesmente descrito como: o proponente primeiro aprende o conteúdo mais recente da proposta da maioria dos aceitantes e, em seguida, forma uma nova proposta com base na proposta aprendida com o maior número. Se a proposta é votada pela maioria dos Aceitadores, ela é aprovada. Como o conjunto dos Aceitadores que aprendem a proposta e os que aceitam a proposta são mais da metade do total, o Proponente pode definitivamente aprender o valor da proposta mais recente. Também deve haver um Acceptor público no conjunto Acceptor passado por duas propostas, e esse Acceptor público garante a consistência dos dados quando a restrição b for satisfeita. Portanto, o protocolo Paxos também é conhecido como o protocolo majoritário.

A força do protocolo Paxos é sua simplicidade. Qualquer mensagem no fluxo do protocolo Paxos pode ser perdida. A garantia de consistência não depende do sucesso de uma determinada entrega de mensagens, o que simplifica bastante o design de sistemas distribuídos. É extremamente compatível com as características de um possível particionamento de rede em um ambiente distribuído. Comparado com o “two-phase commit (2PC)” antes do protocolo Paxos, a consistência forte pode ser garantida, mas é altamente complexa e depende da disponibilidade de um único coordenador.

Apesar da eficácia do Paxos, o ZAB também surgiu como um protocolo poderoso.

O protocolo ZAB

Embora o protocolo Paxos esteja completo, ainda há alguns problemas a serem resolvidos ao aplicá-lo a um sistema distribuído real.

Primeiro, no cenário de vários Proponentes, a Paxos não garante que a primeira proposta enviada seja aceita primeiro. Não está claro o que deve ser feito para garantir que várias propostas sejam aceitas em ordem na aplicação real.

Além disso, o Paxos permite que vários Proponentes apresentem propostas, para que um problema de livelock possa ocorrer. Quando a proposta n não é concluída na segunda fase, o pedido de preparação da primeira fase da nova proposta n + 1 chegou ao aceitante. De acordo com o protocolo, o Aceitante responderá ao pedido de preparação da nova proposta e garantirá que não aceitará qualquer solicitação com número menor que n + 1, o que pode resultar na não aceitação da proposta. Da mesma forma, se a segunda fase da proposta n + 1 não for concluída e o Proponente que apresentou a proposta n já tiver apresentado a proposta n + 2, a proposta n + 1 também poderá falhar.

Por último, o protocolo Paxos estipula que, desde que o valor v de uma proposta seja aceito pela maioria dos Aceitantes, todas as propostas subseqüentes não poderão modificar o valor v. Na realidade, isso causa dificuldade quando há necessidade de modificar o valor v.

Em contrapartida, o algoritmo principal do ZooKeeper, ou ZAB, resolve os dois problemas mencionados acima com uma restrição simples: todas as propostas são encaminhadas para um único Líder (selecionado do Acceptors pelo algoritmo de eleição do líder) para enviar, e o Líder garante o pedido de várias propostas, evitando assim o problema de livelock causado por vários Proponentes.

O processo do protocolo ZAB é descrito por um diagrama de tempo, conforme mostrado na figura a seguir. Em comparação com o protocolo Paxos, a fase de preparação é omitida, porque o próprio Líder tem o estado mais recente da proposta, e o processo de aprender o conteúdo da proposta não é necessário. O Seguidor na figura corresponde ao Aceitante do protocolo Paxos e o Observador corresponde ao Aprendiz em Paxos.

Processo de trabalho do protocolo ZAB

Quando o ZAB introduz o Líder, ele também introduz um novo problema: o que acontece se o Líder falhar? A solução é eleger um novo líder. O processo de eleger o Líder é também um processo de resolução de propostas da Paxos, que não é discutido mais aqui.

Então, como o valor v da proposta pode ser modificado? Este não é o escopo do protocolo ZAB. Depois de estudar o código fonte do ZooKeeper, a equipe do Alibaba percebeu que o ZooKeeper fornece um conceito de znode e que ele pode ser modificado. O ZooKeeper registra um número de versão crescente e contínuo para cada znode. Qualquer modificação (create / set / setAcl) para znode aciona um processo de votação majoritária da Paxos. Depois que o voto é passado, o número de versão do znode é aumentado em 1. Isso é equivalente a usar vários protocolos Paxos de diferentes versões do znode para quebrar a limitação de que um único protocolo Paxos não pode modificar o valor da proposta.

No que diz respeito ao núcleo do algoritmo para garantir a consistência, o ZAB se baseia na idéia majoritária do Paxos, mas é a garantia de tempo global que ele fornece e o znode ZooKeeper modificável fornece ao usuário que faz o Paxos brilhar no código aberto mundo. O ZAB não fornece simplesmente uma implementação otimizada do algoritmo Paxos, deixando claro que o ZAB é um algoritmo diferente do Paxos.

Resumo

O teorema CAP apresenta a alegação de que o particionamento de rede é inevitável em um ambiente distribuído e que resulta em uma troca entre consistência e disponibilidade. O protocolo Paxos propõe um algoritmo extremamente simples para maximizar a disponibilidade e, ao mesmo tempo, garantir consistência. O protocolo ZAB do ZooKeeper simplifica ainda mais o Paxos e fornece uma garantia de tempo global que leva à ampla aplicação do Paxos em cenários industriais, tornando-se uma referência fundamental para o trabalho do Alibaba em computação.

(Artigo original de Li Jinhui ???)