A conjectura de Brewer e a viabilidade de serviços web consistentes, disponíveis e tolerantes a partições

Título original: Brewer's Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services

PublicadoACM SIGACT News

Saiu em uma revista, congresso ou livro, que normalmente avaliam o trabalho antes de aceitar. Mesmo assim, um único estudo nunca é a palavra final.

Resumo

Ao projetar serviços web distribuídos, há três propriedades comumente desejadas: consistência, disponibilidade e tolerância a partições. É impossível obter as três. Nesta nota, provamos essa conjectura no modelo de rede assíncrona e depois discutimos soluções para esse dilema no modelo parcialmente síncrono.

Tradução nossa do resumo original dos autores, em inglês.

Análise de pesquisa

Escrita pelo Kurz, não pelos autores do paper. O resumo acima é dos próprios autores.

Última revisão
Versão
1.0

Visão geral

No PODC 2000, Eric Brewer fez uma palestra convidada, "Towards robust distributed systems", em que conjecturou que um serviço web não consegue oferecer ao mesmo tempo consistência, disponibilidade e tolerância a partições. As três palavras não tinham significado preciso, então a afirmação não podia ser provada nem refutada. Esta nota, publicada no ACM SIGACT News em junho de 2002, é o artigo que transformou o slogan em teorema e lhe deu o nome "CAP" usado pelos trabalhos seguintes.

Ela pertence à família de resultados de impossibilidade que começou com o FLP. Os dois usam o modelo assíncrono, em que um nó não distingue uma mensagem perdida de uma atrasada, e os dois se apoiam em um argumento de indistinguibilidade. A nota também ajuda a entender por que a máquina de estados replicada do Paxos e do Raft não pode prometer responder a todo cliente durante uma partição.

Vale conhecer antes: linearizabilidade (cada operação parece ocorrer em um único instante, numa ordem que respeita o tempo real), o modelo assíncrono de troca de mensagens e a diferença entre segurança ("nada de ruim acontece") e vivacidade ("algo de bom acontece eventualmente").

Contribuição

  • Definições precisas. Consistência vira consistência atômica (linearizável) de um objeto de leitura e escrita. Disponibilidade significa que toda requisição recebida por um nó que não falhou deve receber resposta, sem limite de tempo. Tolerância a partições significa que a rede pode perder arbitrariamente muitas mensagens entre nós.
  • O teorema de impossibilidade. No modelo assíncrono, nenhum objeto de leitura e escrita garante disponibilidade e consistência atômica em todas as execuções justas, inclusive nas que perdem mensagens (Teorema 1).
  • Um corolário mais forte. O mesmo vale mesmo que a atomicidade só seja exigida nas execuções sem perda de mensagens (Corolário 1.1), porque nesse modelo um algoritmo não distingue mensagem perdida de mensagem atrasada.
  • Um mapa do que é possível. Quaisquer duas das três propriedades podem ser obtidas: atômico e tolerante a partições, atômico e disponível, ou disponível e tolerante a partições, cada caso com um exemplo simples.
  • Uma saída. Num modelo parcialmente síncrono o corolário deixa de valer, e a nota define a consistência Delayed-t, uma garantia mais fraca com limite explícito de tempo.

Metodologia

A nota é um argumento formal, sem implementação nem experimento. A prova de impossibilidade divide os nós em dois conjuntos não vazios, G1 e G2, e supõe que toda mensagem entre eles se perde. Uma escrita de um valor diferente do valor inicial v0 termina em G1, porque o serviço é disponível. Uma leitura posterior em G2 também precisa terminar, de novo por disponibilidade, mas G2 não distingue essa execução de uma em que a escrita nunca aconteceu, e por isso devolve v0. A leitura começa depois do fim da escrita, o que contradiz a atomicidade.

O corolário é provado por extensão: se existisse um algoritmo atômico sempre que todas as mensagens são entregues, toma-se uma execução com uma resposta não atômica, corta-se nessa resposta e estende-se o prefixo até uma execução justa em que toda mensagem é entregue. O resultado é não atômico, uma contradição. O modelo parcialmente síncrono dá a cada nó um temporizador, um limite conhecido t_msg para a entrega de mensagens (ou a mensagem se perde) e um limite conhecido t_local para o processamento. O Teorema 2 repete a prova com um longo período ocioso em G2, para que a escrita termine antes da leitura começar. A parte construtiva é um algoritmo centralizado com timeouts, provado correto em relação à definição Delayed-t.

Resultados

São resultados das provas, não de medições.

  • Teorema 1. Nenhum algoritmo no modelo assíncrono dá disponibilidade e consistência atômica em todas as execuções justas, incluindo as que perdem mensagens.
  • Corolário 1.1. A atomicidade não pode nem ser reservada às execuções sem perda, já que um algoritmo assíncrono não detecta mensagem perdida.
  • Teorema 2. A sincronia parcial não elimina a impossibilidade quando mensagens arbitrárias podem se perder.
  • Com temporizadores o corolário deixa de valer. Um nó que espera 2 * t_msg + t_local pelo nó central pode concluir que uma mensagem se perdeu e responder com o melhor valor que conhece. O resultado são dados atômicos quando as mensagens são entregues e possivelmente defasados quando não são.
  • Teorema 4. O algoritmo centralizado modificado é Delayed-t consistente: se passa um intervalo maior que t sem perda de mensagens, operações posteriores deixam de preceder, na ordem parcial, operações anteriores já concluídas. O artigo relaciona isso aos serviços de dados eventualmente serializáveis, mas com um limite explícito de tempo.

Análise crítica

O teorema é estreito, e esse é o seu valor, mas costuma ser citado de forma mais ampla do que foi provado.

  • A disponibilidade é forte e fraca ao mesmo tempo. Exige resposta de todo nó que não falhou mesmo isolado de todos os outros, mas não limita a latência, então "lento, porém respondendo no fim" conta como disponível. Serviços reais são avaliados por latência e pela fração de requisições atendidas, não por essa definição.
  • Consistência aqui é só linearizabilidade. O resultado nada diz sobre os modelos mais fracos que muitos bancos oferecem. A própria nota diz que disponibilidade com consistência mais fraca é alcançável, e esboça apenas um modelo desse tipo.
  • É uma afirmação sobre partições, não uma escolha permanente. "Dois de três" sugere um rótulo fixo para o sistema, mas o dilema só pesa enquanto a partição dura, e o algoritmo parcialmente síncrono do próprio artigo já muda de comportamento nesse momento.
  • O modelo é pequeno. Um único objeto de leitura e escrita, sem falhas de parada (a introdução as deixa de lado), um algoritmo centralizado como exemplo principal e uma prova Delayed-t de poucos parágrafos. Não trata de durabilidade, custo de replicação nem de transações com vários objetos.
  • Livro versus hoje. O artigo é uma nota de nove páginas no periódico, e a própria conclusão aponta "a maior parte dos dados, na maior parte do tempo" como trabalho teórico futuro. Trabalhos posteriores, incluindo a retrospectiva do próprio Brewer e o "Perspectives on the CAP Theorem" de Gilbert e Lynch, argumentam que o dilema é mais sutil que o slogan de 2000.

Pesquisas futuras

  • Tratar latência e um contínuo de níveis de consistência, e não só disponibilidade binária, já que serviços reais são avaliados pelos dois.
  • Sistemas que ficam consistentes e tornam as partições raras, como o Spanner, e outros que evitam coordenação quando possível, como o Calvin e o Eris.
  • Consistência causal como modelo que continua disponível sob partições, como no Saturn e no Antipode.
  • Formalizar "a maior parte dos dados, na maior parte do tempo", que o artigo cita como trabalho futuro.
  • Ler o resultado ao lado do FLP e do problema dos Generais Bizantinos como um conjunto de limites do que uma rede não confiável permite.

Texto completo

Carregando o paper…

Discussão · 0

Nenhum post ainda. Seja o primeiro a iniciar a discussão.