CAP e PACELC

O BoxOffice chega à Europa. Para dar aos fãs em Lisboa a mesma experiência rápida dos fãs em São Paulo, o time roda o banco do inventory em duas regiões, cada uma com uma cópia completa dos assentos, replicando entre si. Numa tarde, durante a abertura das vendas de um festival, o enlace transatlântico entre as regiões degrada e depois cai. As duas regiões estão vivas; as duas continuam recebendo requisições "Reservar assento A-12". Cada região tem agora duas opções para cada requisição: responder com o que sabe (e arriscar vender o assento A-12 dos dois lados do oceano) ou recusar até o enlace voltar (e perder a venda). Não há terceira opção. É esse dilema que o teorema CAP formaliza.

O teorema CAP, conjecturado por Eric Brewer em 2000 e provado por Seth Gilbert e Nancy Lynch em 2002¹, afirma que um armazenamento de dados replicado não consegue garantir ao mesmo tempo as três propriedades a seguir:

As três propriedades

Consistência (C) : Toda leitura devolve a escrita mais recente, ou um erro. No CAP, "consistência" significa linearizabilidade: as réplicas se comportam como se houvesse uma única cópia (veja Linearizabilidade).

Disponibilidade (A, availability) : Toda requisição recebida por um nó que não falhou recebe uma resposta que não é erro — mesmo que ela não contenha a escrita mais recente. Note o rigor: todo nó que não falhou, não "na maior parte do tempo".

Tolerância a partições (P) : O sistema continua operando quando a rede se particiona — divide os nós em grupos que estão vivos, mas não conseguem trocar mensagens (ou as trocam com atraso ilimitado).

Uma partição, passo a passo

A mesma requisição, tratada por um sistema que escolhe consistência (CP) e por um que escolhe disponibilidade (AP):

Nenhuma das respostas é "errada" em abstrato: o sistema CP recusa em vez de arriscar uma venda em dobro; o sistema AP atende todo fã e precisa reconciliar depois. Qual das duas é aceitável depende dos dados e do negócio — não da marca do banco de dados.

Sistemas CP e AP

CP — consistente e tolerante a partições

Durante uma partição, os nós que não conseguem confirmar o estado mais recente (tipicamente o lado minoritário) recusam requisições. Quando a partição se resolve, eles se atualizam antes de voltar a atender.

flowchart LR
    CA(["Fã A"]) -->|"1 · reservar A-12"| A[("Nó A (maioria)<br/>A-12 = HELD")]
    A -.-x|"2 · replicar ✗ partição"| B[("Nó B (minoria)<br/>A-12 = FREE")]
    CB(["Fã B"]) -->|"3 · A-12 está livre?"| B
    B -->|"4 · erro: sem quórum"| CB

• Exemplos: etcd, ZooKeeper, Consul, Spanner, CockroachDB; PostgreSQL com replicação síncrona; MongoDB com leituras e escritas por maioria.
• Use quando: uma resposta errada é pior do que nenhuma resposta — estoque, dinheiro, identidade, liderança, locks.

AP — disponível e tolerante a partições

Durante uma partição, todo nó continua respondendo com os dados que tem. As réplicas divergem e convergem depois que a partição se resolve (consistência eventual), resolvendo conflitos com LWW, vetores de versão ou CRDTs (Consistência eventual).

flowchart LR
    CA(["Fã A"]) -->|"1 · curtir evento 42"| A[("Nó A<br/>curtidas = 101")]
    A -.-x|"2 · replicar ✗ partição"| B[("Nó B<br/>curtidas = 100")]
    CB(["Fã B"]) -->|"3 · ler curtidas"| B
    B -->|"4 · 100 (desatualizado)"| CB
    A ==>|"5 · partição resolvida: merge"| B

• Exemplos: Cassandra e DynamoDB nas configurações padrão, CouchDB, Riak, DNS, CDNs, a maioria dos caches.
• Use quando: uma resposta um pouco desatualizada é melhor do que nenhuma — catálogo, recomendações, contadores, carrinhos, feeds.

"CA"

Um sistema consistente e disponível enquanto não houver partições — na prática, um único nó, ou um cluster que simplesmente não decidiu o que fazer numa partição. Não é uma terceira opção real para um sistema distribuído.

PACELC: o trade-off que você paga todo dia

O CAP só fala de partições, que são raras. O PACELC de Daniel Abadi (2010–2012)³ acrescenta o trade-off que existe o tempo todo:

Se há uma Partição, escolha entre disponibilidade (A) e Consistência; E, senão (else, operação normal), escolha entre Latência e Consistência.

flowchart LR
    Q{"Há uma<br/>partição?"} -->|"sim · P"| PAC{"Disponibilidade<br/>ou Consistência?"}
    PAC -->|A| PA["PA: responde, talvez desatualizado"]
    PAC -->|C| PC["PC: recusa ou espera"]
    Q -->|"não · E (senão)"| ELC{"Latência<br/>ou Consistência?"}
    ELC -->|L| EL["EL: responde antes de<br/>as réplicas confirmarem"]
    ELC -->|C| EC["EC: espera<br/>as réplicas"]

O ramo else existe por causa da própria replicação: para ser consistente, uma escrita precisa esperar outras réplicas confirmarem (uma ou mais idas e voltas pela rede, talvez até outro continente); para ser rápida, precisa responder antes delas e aceitar que uma réplica pode ficar brevemente para trás.

Quanta latência a consistência custa?

A resposta é "uma ida e volta até onde estiverem as outras réplicas". Os tempos de ida e volta (RTT, round-trip time) abaixo são ordens de grandeza típicas, usadas aqui como suposições ilustrativas:

O simulador acima mostra a última linha sem partição nenhuma: no modo PC/EC cada escrita leva 184 ms, no modo PA/EL 4 ms — e o modo rápido paga com leituras velhas.

Essa tabela explica por que a maioria dos sistemas escolhe EC dentro de uma região (replicação síncrona ou por quórum entre zonas custa um ou dois milissegundos) e EL entre regiões (replicação assíncrona, ou particionar os dados por região de origem).

Projetos multirregião

Regiões falham — raramente, mas por inteiro — e o BoxOffice quer sobreviver a isso. Os trade-offs entre C, A e L ficam concretos em cinco topologias comuns:

Experimente. No cenário multi-region, rode o perfil load e depois derrube a região primária. Observe quanto tempo o DNS leva para desviar o tráfego (o TTL), quantas requisições falham durante a troca e o que acontece com as escritas que ainda não tinham sido replicadas. Depois reduza o TTL do DNS e repita.

Abrir o playground completo

Como se conecta

flowchart LR
    REP["Replicação<br/>(Replicação e Consistência)"] --> Q{"partição?"}
    Q -->|sim| CA{"C ou A"}
    Q -->|não| LC{"L ou C"}
    CA -->|C| MAJ["só o lado majoritário<br/>→ Consenso e Quóruns"]
    CA -->|A| MERGE["diverge e depois mescla<br/>LWW · CRDTs → Tempo e Relógios"]
    LC -->|C| SYNC["replicação síncrona<br/>entre zonas"]
    LC -->|L| ASYNC["replicação assíncrona,<br/>caches, CDN"]
    MAJ --> MR["projeto multirregião<br/>região de origem por evento"]
    ASYNC --> MR
    MR --> DR["failover e DR<br/>→ Confiabilidade"]

Componentes da paleta em que a escolha entre C, A e L é feita: sql (standby síncrono ou réplicas assíncronas) · nosql (quóruns ajustáveis) · cache e cdn (sempre EL) · dns (failover entre regiões, cenário multi-region). Continua em: Consenso e Quóruns, Confiabilidade — recuperação de desastres, Tráfego e Borda — DNS.

Pontos-chave