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

Referências

links externos