Teorema CAP - CAP theorem
Na ciência da computação teórica , o teorema CAP , também chamado de teorema de Brewer em homenagem ao cientista da computação Eric Brewer , afirma que qualquer armazenamento de dados distribuído pode fornecer apenas duas das três garantias a seguir :
- Consistência
- Cada leitura recebe a gravação mais recente ou um erro.
- Disponibilidade
- Cada solicitação recebe uma resposta (sem erro), sem a garantia de que contém a gravação mais recente.
- Tolerância de partição
- O sistema continua a operar apesar de um número arbitrário de mensagens serem descartadas (ou atrasadas) pela rede entre os nós.
Quando ocorre uma falha de partição de rede, deve-se decidir se
- cancelar a operação e, assim, diminuir a disponibilidade, mas garantir a consistência ou
- prossiga com a operação e, assim, forneça disponibilidade, mas haja risco de inconsistência.
Assim, se houver partição de rede, deve-se escolher entre consistência e disponibilidade. Observe que a consistência conforme definida no teorema CAP é bastante diferente da consistência garantida nas transações do banco de dados ACID .
Eric Brewer argumenta que o conceito frequentemente usado "dois entre três" pode ser um tanto enganoso porque os projetistas de sistema só precisam sacrificar a consistência ou a disponibilidade na presença de partições, mas que em muitos sistemas as partições são raras.
Explicação
Nenhum sistema distribuído está protegido contra falhas de rede, portanto , o particionamento de rede geralmente deve ser tolerado. Na presença de uma partição, fica-se com duas opções: consistência ou disponibilidade . Ao escolher consistência em vez de disponibilidade, o sistema retornará um erro ou um tempo limite se uma determinada informação não puder ser garantida como atualizada devido ao particionamento da rede. Ao escolher disponibilidade em vez de consistência, o sistema sempre processará a consulta e tentará retornar a versão mais recente disponível da informação, mesmo que não possa garantir que esteja atualizada devido ao particionamento da rede.
O CAP é freqüentemente mal interpretado como uma escolha, em todos os momentos, de uma das três garantias de abandono. Na verdade, a escolha é entre consistência e disponibilidade apenas quando ocorre uma partição ou falha de rede. Quando não há falha na rede, a disponibilidade e a consistência podem ser satisfeitas.
O CAP tem sido usado por muitos fornecedores de banco de dados NoSQL como uma justificativa para não fornecer consistência ACID transacional, alegando que o teorema CAP “prova” que é impossível fornecer escalabilidade e consistência ACID ao mesmo tempo. No entanto, um olhar mais atento ao teorema do CAP e, em particular, a formalização por Gilbert & Lynch, revela que o teorema do CAP não se refere de forma alguma à escalabilidade, mas apenas à disponibilidade (o A no CAP).
Os sistemas de banco de dados projetados com as garantias ACID tradicionais em mente, como RDBMS, escolhem consistência em vez de disponibilidade, enquanto sistemas projetados em torno da filosofia BASE , comum no movimento NoSQL , por exemplo, escolhem disponibilidade em vez de consistência.
O teorema PACELC baseia-se no CAP, afirmando que, mesmo na ausência de particionamento, há outra compensação entre latência e consistência.
História
De acordo com Eric Brewer , cientista da computação de Berkeley, da Universidade da Califórnia, o teorema apareceu pela primeira vez no outono de 1998. Foi publicado como o princípio CAP em 1999 e apresentado como uma conjectura por Brewer no Simpósio de 2000 sobre Princípios de Computação Distribuída (PODC). Em 2002, Seth Gilbert e Nancy Lynch do MIT publicaram uma prova formal da conjectura de Brewer, tornando-a um teorema .
Em 2012, Brewer esclareceu algumas de suas posições, incluindo por que o conceito frequentemente usado "dois entre três" pode ser um tanto enganoso, porque os projetistas de sistema precisam apenas sacrificar a consistência ou a disponibilidade na presença de partições; existem técnicas de gerenciamento e recuperação de partição. Brewer também notou a definição diferente de consistência usada no teorema CAP em relação à definição usada no ACID .
Um teorema semelhante declarando o trade-off entre consistência e disponibilidade em sistemas distribuídos foi publicado por Birman e Friedman em 1996. O resultado de Birman e Friedman restringiu este limite inferior para operações não comutáveis.
A tecnologia Blockchain sacrifica consistência para disponibilidade e tolerância de partição, mas é obtida por meio da validação entre os nós ao longo do tempo, com a impressão resultante de que o teorema não é válido.
Veja também
- Falácias da computação distribuída
- Teorema PACELC
- Paxos (ciência da computação)
- Raft (ciência da computação)
- Triângulo de Zooko
Referências
links externos
- CAP doze anos depois: como as "regras" mudaram , artigo de Brewer de 2012 sobre CRDTs (tipos de dados replicados livres de conflito)
- Spanner, TrueTime e o Teorema CAP
- Uma crítica ao teorema CAP
- Por favor, pare de ligar para os bancos de dados CP ou post do blog de AP Kleppmann de 2015 que corresponde à publicação de "A Critique of the CAP Theorem"