Uma prova ilustrada do Teorema de CAP

o teorema de CAP é um teorema fundamental em sistemas distribuídos que afirma que qualquer sistema distribuído pode ter no máximo duas das seguintes três propriedades.

• Consistency
• Availability
• Partition tolerance

This guide will summarize Gilbert and Lynch’s specification and proof of the CAP Theorem with pictures!

What is the CAP Theorem?

o teorema de CAP afirma que um sistema distribuído não pode simultaneamente ser consistente, disponível e tolerante à partição. Parece simples, mas o que significa ser consistente? disponível? tolerante à partição? O que quer dizer com um sistema distribuído? Nesta seção, introduziremos um sistema distribuído simples e explicaremos o que significa que o sistema esteja disponível, consistente e tolerante à partição. Para uma descrição formal do sistema e das três propriedades, por favor, consulte o artigo de Gilbert e Lynch.

a Distributed System

Let’s consider a very simple distributed system. O nosso sistema é composto por dois servidores, $ G_1 e $G_2$. Ambos os servidores estão mantendo o controle da mesma variável, $v$, cujo valor é inicialmente $v_0$. $G_1$ e $G_2$ podem se comunicar entre si e também podem se comunicar com clientes externos. Eis como o nosso sistema se parece.

um cliente pode pedir para escrever e ler em qualquer servidor. Quando um servidor recebe um pedido, ele executa quaisquer cálculos que deseja e, em seguida, responde ao cliente. Por exemplo, aqui está o aspecto de uma escrita.

e aqui está o aspecto de uma leitura.

agora que estabelecemos o nosso sistema, vamos rever o que significa para o sistema ser consistente, disponível e tolerante à partição.

consistência

aqui está como Gilbert e Lynch descrevem consistência.

qualquer operação de leitura que começa depois que uma operação de gravação for concluída, deve devolver esse valor, ou o resultado de uma operação de escrita

Em um sistema coerente, uma vez que um cliente escreve um valor para qualquer servidor e obtém uma resposta, ele espera obter esse valor (ou um mais fresco valor) de volta a partir de qualquer servidor lê a partir de.

aqui está um exemplo de um sistema inconsistente.

o nosso cliente escreve $v_1$ para $G_1$ e $G_1$ reconhece, mas quando lê de $G_2$, recebe dados obsoletos: $v_0$. Por outro lado, aqui está um exemplo de um sistema consistente.

neste sistema, $G_1$ duplica o seu valor para us $G_2$ antes de enviar uma confirmação para o cliente. Assim, quando o cliente lê de $G_2$, ele obtém o valor mais atualizado de $v$: $v_1$.

disponibilidade

eis como Gilbert e Lynch descrevem a disponibilidade.

cada pedido recebido por um nó que não falha no sistema deve resultar numa resposta

num sistema disponível, se o nosso cliente enviar um pedido a um servidor e o servidor não tiver estoirado, então o servidor deve eventualmente responder ao cliente. O servidor não está autorizado a ignorar os pedidos do cliente.

tolerância à partição

aqui está como Gilbert e Lynch descrevem partições.

a rede será autorizada a perder arbitrariamente muitas mensagens enviadas de um nó para outro

isto significa que quaisquer mensagens $g_1$ e $G_2$ enviadas um para o outro podem ser retiradas. Se todas as mensagens fossem retiradas, o nosso sistema ficaria assim.

nosso sistema tem que ser capaz de funcionar corretamente apesar de partições de rede arbitrárias, a fim de ser tolerante à partição.

Prova

Agora que temos familiarizar-nos com a noção de consistência, disponibilidade e partição de tolerância, podemos provar que um sistema não pode, simultaneamente, ter todos os três.

assumir por contradição que existe um sistema que é consistente, disponível e tolerante à partição. A primeira coisa que fazemos é dividir o nosso sistema. Parece isto.

a seguir, temos o pedido do nosso cliente para que os$ v_1 $ sejam escritos a $ G_1$. Uma vez que o nosso sistema está disponível, $G_1$ deve responder. Uma vez que a rede é dividida, no entanto, $G_1$ não pode replicar seus dados para $G_2$. Gilbert e Lynch chamam a esta fase de execução $\alpha_1$.

em seguida, temos o nosso cliente emitir um pedido de leitura para $G_2$. Mais uma vez, como o nosso sistema está disponível, $G_2$ deve responder. E como a rede está dividida, $G_2$ não pode atualizar seu valor de $G_1$. Ele devolve $ v_0$. Gilbert e Lynch chamam a esta fase de execução $\alpha_2$.

$G_2$ retorna $v_0$ para o nosso cliente depois que o cliente já tinha escrito $v_1$ para $G_1$. Isto é inconsistente.

assumimos a existência de um sistema consistente, disponível, tolerante à partição, mas apenas mostramos que existe uma execução para qualquer sistema em que o sistema age de forma inconsistente. Assim, tal sistema não existe.