Modelos CAP e de Consistência

Os modelos de consistência definem as garantias que um sistema replicado oferece sobre os valores retornados pelas leituras, e o teorema CAP delimita quais dessas garantias podem coexistir com a disponibilidade sob partições de rede.

Definition

Um modelo de consistência é um contrato entre um armazenamento de dados replicado e seus clientes, especificando os resultados permissíveis de leituras e escritas concorrentes; o teorema CAP afirma que, na presença de uma partição de rede, um armazenamento de dados distribuído não pode fornecer simultaneamente consistência linearizável e disponibilidade.

Scope

Este tópico abrange os modelos formais de consistência — linearizabilidade, consistência sequencial, consistência causal e consistência eventual — e sua ordenação por força; o teorema CAP, sua declaração precisa e prova; e refinamentos como o PACELC que também consideram o trade-off latência-consistência na ausência de partições. Ele fornece o vocabulário para especificar e comparar as garantias de sistemas replicados.

Core questions

• Como a linearizabilidade, a consistência sequencial, causal e eventual diferem em força?
• O que exatamente o teorema CAP proíbe e o que ele permite?
• Como as considerações de latência refinam o trade-off de consistência quando não há partição?

Key theories

Linearizabilidade e consistência sequencial

A linearizabilidade exige que cada operação pareça ter efeito atomicamente em algum instante entre sua invocação e resposta, consistente com o tempo real; a consistência sequencial dispensa o requisito de tempo real, exigindo apenas um único entrelaçamento legal que respeite a ordem de cada processo.

O teorema CAP

Gilbert e Lynch provaram que nenhum armazenamento de dados replicado pode garantir simultaneamente consistência linearizável e disponibilidade quando a rede pode descartar mensagens entre réplicas, forçando uma escolha durante as partições.

Refinamento PACELC

O PACELC estende o CAP ao observar que, mesmo sem uma partição, um sistema troca latência por consistência, de modo que os projetos são caracterizados por seu comportamento tanto durante as partições quanto na operação normal.

Clinical relevance

Todo banco de dados distribuído e serviço de armazenamento deve declarar um modelo de consistência, e os trade-offs CAP e PACELC explicam por que alguns sistemas priorizam a disponibilidade enquanto outros priorizam a consistência; compreendê-los é essencial para escolher e operar a infraestrutura de dados.

History

Lamport definiu a consistência sequencial em 1979 e Herlihy e Wing formalizaram a linearizabilidade em 1990; Brewer conjecturou o trade-off CAP em 2000, Gilbert e Lynch o provaram em 2002, e o reenquadramento PACELC de Abadi em 2012 esclareceu que a latência, e não apenas as partições, impulsiona as escolhas de consistência.

Debates

O CAP é frequentemente mal interpretado?

O CAP é frequentemente resumido como 'escolha dois de três', mas o resultado preciso apenas força uma escolha consistência-disponibilidade durante uma partição; críticos argumentam que essa simplificação excessiva obscurece o trade-off latência-consistência mais relevante no dia a dia, capturado pelo PACELC.

Key figures

• Eric Brewer
• Seth Gilbert
• Nancy Lynch
• Maurice Herlihy
• Jeannette Wing
• Leslie Lamport

Seminal works

• gilbert2002
• herlihy1990
• lamport1979

Frequently asked questions

O CAP significa que um sistema só pode ter duas das três características: consistência, disponibilidade e tolerância a partições?

Não exatamente. As partições são um fato das redes, não uma escolha de design, então a decisão real é o que fazer durante uma partição: sacrificar a consistência forte para permanecer disponível, ou sacrificar a disponibilidade para permanecer consistente. Quando não há partição, um sistema pode ser consistente e disponível.