CAP Teorema: Capture essa idéia!

Nunca conhecer os princípios dos algoritmos distribuídos foi tão importante para um desenvolvedor de software. Hoje os sistemas apresentam escalas tão largas que só são possíveis de se tornarem reais com o uso de plataformas altamente distribuídas. Redes sociais tais como o Facebook e Twitter são exemplos desses sistemas. A consequência é que problemas há muito tempo conhecidos pelos estudiosos de Sistemas Distribuídos (SD), surgem repaginados e potencializados.

Considere o caso do Facebook como mero exemplo. De modo geral, queremos que essa ferramenta esteja online 100% do tempo, funcionando corretamente e com baixos tempos de resposta mesmo se, por algum motivo qualquer, algumas máquinas da infraestrutura estejam offline. Ou seja, o que queremos pode ser definido como:

Consistência: garante que qualquer operação de leitura que comece após uma operação de escrita, se atendida, deve retornar o valor escrito ou o resultado de uma escrita mais recente. De maneira mais simples isso pode significar que, ao fazer upload da minha foto no perfil do FB, quero que a mesma apareça para todos os meus amigos e não mais uma foto antiga qualquer.

Disponibilidade: garante que os dados do sistema estarão sempre à disposição, ou seja, todas as requisições ao sistema receberão uma resposta.

Tolerância a Partições: garante que mesmo quando falhas na conexão entre os nós ocorram, sendo potencialmente causadas pela falha de um ou mais nós, as requisições continuarão sendo atendidas.

Ocorre que recentemente, Eric Brewer, formulou uma conjectura que dizia que em qualquer sistema distribuído, em um modelo de rede assíncrono, apenas duas das três propriedades de disponibilidade, particionamento de dados e consistência podem ser simultâneamente garantidas [1]. Mais tarde, Gilbert e Lynch estabeleceram uma prova formal da conjectura transformando-o em um teorema[2]. Tal teorema é conhecido também pelo nome CAP o qual consiste em um acrônimo para Consistency, Availability e Partition Tolerance.

A Prova

Por contradição, vamos provar que não se pode ter as propriedades de consistência e disponibilidade de dados simultâneamente, mesmo em casos onde haja perda de mensagens de rede. Assim, assuma que existe um sistema onde os dados estão sempre disponíveis e consistentes, mesmo quando há partição na rede e algumas mensagens são perdidas. Suponha que a rede seja formada por dois nós {N1, N2} distintos e incomunicáveis. Segue que se uma operação de escrita acontece em N1, pela propriedade da disponibilidade, o valor inicial v0 será transformando em v1. Como N1 e N2 não se comunicam, N1 continuará com o valor inicial de v0. Supondo que nenhuma outra operação de escrita ocorra na rede, imagine que uma operação de leitura ocorre no valor v0 de N2. Pela propriedade da disponibilidade, essa operação gerará uma resposta que deve ser v0. Segue que os resultados das duas operações são distintos, contradizendo a hipótese de que havia consistência mesmo quando mensagens entre os nós eram perdidas.

Também podemos provar que o mesmo ocorre se considerarmos uma rede onde todas as mensagens são entregues. Nesse caso, a idéia principal é baseada no fato de que em um modelo assíncrono, um algoritmo não tem como determinar se uma mensagem foi perdida ou está atrasada na transmissão. Segue que se existisse um algoritmo capaz de garantir consistência em execuções onde não há perda de mensagens, então existiria um algoritmo que garantiria consistência em todos os tipos de execução, o que consiste em um absurdo de acordo com o provado no parágrafo anterior.

Intuitivo, não? O resultado prático do teorema CAP pode ser observado em muitos sistemas de armazenamento distribuídos. Esses sistemas apresentam combinações das três propriedades. BigTable da Google e o HBase da Yahoo! prezam pela consistência e disponibilidade. Por esse motivo são ditos sistemas CA (consistency and availability). Por outro lado, sistemas como o Dynamo da Amazon e o Cassandra, originalmente desenvolvido pelo Facebook, sacrificam a consistência a favor das outras duas propriedades, sendo chamados sistemas AP (availability and partitioning).

É importante notar que o teorema CAP assegura que as três propriedades não podem ser atendidas ao mesmo tempo, mas podem-se mesclar propriedades de acordo com o cenário em que se encontra o ambiente. Assim, algumas iniciativas apresentam um sistema híbrido como é o caso do PNUTS, desenvolvido pela Yahoo!.

Muitas pessoas argumentam que o Teorema CAP é incompleto por não classificar sistemas como esses ou por sugerir que o problema de gerenciamento de dados distribuído é apenas um trade-off entre disponibilidade e consistência. Daniel Abadi, professor da Universidade de Yale é uma dessas pessoas. Um artigo seu sobre o assunto pode ser encontrado aqui (http://dbmsmusings.blogspot.com/2010/04/problems-with-cap-and-yahoos-little.html).

Posições como a do Prof. Abadi têm se multiplicado na internet. Tanto que o próprio Eric Brewer já anunciou em seu twitter que precisa escrever outro artigo sobre o Teorema. Isso quer dizer que ainda há muita coisa a ser descoberta por trás dessas três letras. Quem se atreve?

Referências:

1- Brewer, E., Principles of Distributed Computing (PODC 2000): "Towards robust distributed systems." Portland, OR. July 2000.

2 - Nancy Lynch and Seth Gilbert, "Brewer's conjectures and the feasibility of consistent, available, partition-tolerant web services", ACM SIGACT News, Volume 33 Issue 2 (2002), pg. 51-59.