Qual é o raciocínio por trás do teorema da PAC?

21

http://en.wikipedia.org/wiki/CAP_theorem

http://www.cs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf

Eu acho que não é muito simples porque apenas dois dos

  1. Consistência
  2. Disponibilidade
  3. Tolerância de partição

pode ser válido para qualquer sistema de banco de dados distribuído. Essa conjectura foi comprovada, mas existe uma maneira mais fácil de ver por que isso provavelmente se aplica?

Não estou procurando uma prova, apenas uma boa maneira de entender por que esse teorema pode fazer sentido. Qual é o raciocínio?

lazer
fonte

Respostas:

23

OK, vamos imaginar que você tenha um banco de dados distribuído. Digamos que você tenha um nó no Oregon e um na Califórnia. A teoria do CAP diz que você terá problemas ao configurar esse tipo de banco de dados.

Por exemplo, se você consultar dados de um banco de dados, eles deverão ser iguais aos dados do outro banco de dados. Isso garante que qualquer valor que você tenha em um banco de dados esteja garantido no outro ( consistência da teoria da PAC). Isso permite atualizar os dados em um banco de dados e consultá-los em outro, obtendo os mesmos resultados.

Um computador que atualiza dados no Oregon transfere os dados para a Califórnia

Quando atualizamos os dados no nó do Oregon, eles são enviados para o nó da Califórnia, para que os bancos de dados sejam consistentes. Para manter a consistência de verdade, precisamos garantir que os dois bancos de dados obtenham a atualização antes que eles tenham permissão para salvar verdadeiramente os dados (confirmação em duas fases usando transações distribuídas). Em outras palavras, se o banco de dados da Califórnia não puder salvar os dados por algum motivo (por exemplo, falha no disco rígido), o banco de dados no Oregon não salvará os dados e falhará na transação.

O problema com transações distribuídas como a acima ocorre quando queremos ter alta disponibilidade. Nesse cenário acima, o processo de tentativa de sincronizar os dois bancos de dados é um processo muito, muito lento. (Imagine, precisamos enviar os dados do Oregon para a Califórnia, garantir que eles cheguem lá, garantir que os dois bancos de dados tenham bloqueios nos dados etc.) Isso causa grandes problemas quando queremos um sistema que seja rápido e responsivo, mesmo durante tempos de alta demanda. (Isto é o disponibilidade do teorema da PAC.)

Normalmente, o que fazemos para garantir alta disponibilidade é usar a replicação em vez de transações distribuídas. Portanto, em vez de garantir que a Califórnia possa aceitar os dados, basta ir em frente e armazená-los no nó do Oregon e depois enviar os dados para a Califórnia quando chegarmos a eles. Isso garante que sempre podemos armazenar os dados, independentemente de a Califórnia estar pronta para armazenar os dados ou não.

O nó do Oregon atualiza os dados enquanto a Califórnia os lê.  Mais tarde, os dados são movidos para a Califórnia

Isso melhora a disponibilidade, mas à custa da consistência. Veja, se alguém atualiza os dados no Oregon e alguém (ao mesmo tempo) lê os dados na Califórnia, não está obtendo os novos dados - os bancos de dados não são mais consistentes. De fato, eles não serão consistentes até o Oregon enviar os dados para a Califórnia!

Portanto, esse é o compromisso de Disponibilidade-vs VS-Consistência.

Tolerância de partição é o terceiro aspecto da teoria da PAC. Particionamento é, nesse contexto, a idéia de que um banco de dados (ou outro sistema distribuído) pode quebrar em seções separadas e ainda funcionar corretamente.

A questão é: o que acontece quando os dois bancos de dados estão sendo executados corretamente, mas o link do Oregon para a Califórnia é cortado?

O Oregon está sendo atualizado enquanto o nó da Califórnia está sendo lido.  A rede entre os nós é cortada.

Se atualizarmos o banco de dados no Oregon, precisamos levar os dados para a Califórnia de uma maneira ou de outra (transação distribuída ou replicação). No entanto, se o link entre os dois for cortado, o sistema ficará particionado e os bancos de dados não serão mais vinculados.

Quando isso acontece, suas opções são parar de permitir atualizações (para manter a consistência) ao custo da disponibilidade ou permitir que as atualizações (para manter a disponibilidade) ao custo da consistência.

Como você pode ver, a tolerância da partição cria trocas diretas entre Consistência e Disponibilidade.


Obviamente, há mais do que isso, mas esses são alguns exemplos de como esses três aspectos principais dos sistemas distribuídos funcionam um contra o outro. A explicação de Julian Browne da teoria da PAC é um excelente lugar para aprender mais.

Richard
fonte
Resposta relacionada por Remus Rusanu.
9116 Nick Chammas
Com uma imagem muito mais bonita nisso!
Richard