CS Fundamentals Trainer · Guias
O teorema CAP e os modelos de consistência
O que o CAP realmente diz, um experimento de partição CP versus AP, quóruns (R + W > N), o espectro do linearizável ao eventual e o PACELC.
13 min de leitura
O teorema CAP é o resultado mais citado e mais mal citado dos sistemas distribuídos. O slogan "escolha duas entre consistência, disponibilidade e tolerância a partições" está errado de um jeito que importa. Este guia diz o que o teorema realmente afirma, mostra isso em um pequeno experimento e depois cobre entre o que você realmente escolhe na prática: os modelos de consistência e o trade-off de latência que vale até quando nada está quebrado.
1. O que o teorema diz
Eric Brewer o conjecturou em 2000, e Seth Gilbert e Nancy Lynch provaram uma versão precisa em 2002 [1]. Três propriedades de um serviço replicado:
- Consistência (C): aqui significa linearizabilidade: toda operação parece ter efeito em um instante entre o seu início e o seu fim, de modo que uma leitura depois de uma escrita concluída vê essa escrita (ou uma posterior), como se houvesse uma única cópia dos dados. É uma noção forte, não o "C" do ACID.
- Disponibilidade (A): toda requisição que chega a um nó sem falha recebe uma resposta (que não seja erro), em tempo finito.
- Tolerância a partições (P): o sistema continua funcionando mesmo quando a rede perde ou atrasa mensagens entre os nós.
O teorema: quando a rede está particionada, um sistema não pode ser ao mesmo tempo consistente e disponível.
O argumento é curto. Separe duas réplicas por uma partição. Um cliente grava x = 1 de um lado. Outro cliente lê x do outro lado. Esse nó tem duas escolhas: responder com o valor antigo (disponível, mas não consistente: a leitura perdeu uma escrita concluída) ou se recusar a responder até conseguir falar com o outro lado (consistente, mas não disponível). Não há uma terceira opção.
2. Por que "escolha duas" engana
- Você não pode escolher abrir mão do P. Redes perdem pacotes, enlaces falham, um nó pausa para coleta de lixo e parece morto. Se o seu sistema abrange mais de uma máquina, partições vão acontecer, então o P não é um item de cardápio. O que você escolhe é o que fazer quando uma acontece: continuar consistente ou continuar disponível.
- Só diz respeito ao momento de uma partição. Quando a rede está saudável, você pode ter os dois. O teorema não diz nada sobre a operação normal.
- As definições são estreitas. "Disponível" significa que todo nó sem falha responde a toda requisição; um sistema que apenas responde à maioria das requisições, ou só do lado majoritário, não é "A" no sentido do teorema. "Consistente" significa linearizabilidade, nada mais fraco. Os sistemas reais ficam em um espectro, e Martin Kleppmann observa que as definições de consistência e disponibilidade do CAP são ambíguas e não correspondem ao que os bancos de dados reais oferecem, e propõe descrever um sistema pelo comportamento de suas operações quando a rede está lenta (uma estrutura de "sensibilidade ao atraso") [2].
- Não é uma afirmação sobre qualidade. Nenhuma das escolhas é "melhor". Depende do quanto custa uma resposta errada.
3. Um pequeno experimento
Simulei cinco nós guardando um carrinho de compras e cortei a rede em um grupo de dois (A, B) e um grupo de três (C, D, E). Depois gravei no carrinho dos dois lados e li de volta. Dois modos:
- CP (consistente, tolerante a partições): uma escrita ou leitura só é permitida no lado que tem a maioria dos nós (aqui, três de cinco).
- AP (disponível, tolerante a partições): todo nó atende requisições com o que tem, e os conflitos são reparados depois que a partição se desfaz (aqui com "a última escrita vence").
Resultado:
CP during partition: A (minority side): unavailable, no majority
D (majority side): ok -> reads [milk,bread]
after heal, the minority catches up: [milk,bread] (nothing was lost)
AP during partition: A: ok (cart = [milk,eggs])
D: ok (cart = [milk,bread]) <- two different carts
after heal + last-write-wins: [milk,bread] (the other write is lost)
O sistema CP disse "não" ao cliente do lado minoritário e nunca mostrou um carrinho errado. O sistema AP respondeu a todos, produziu duas versões divergentes e, quando a partição se desfez, a adição de um cliente (eggs) foi descartada em silêncio. Esse é o trade-off: um erro agora ou um conflito para resolver depois.
Aqui está o modelo (um pequeno script em Python que você pode executar como está). Cada nó guarda (version, value) para uma chave. Uma partição divide os nós em grupos que não conseguem se falar. No modo CP, um grupo precisa de uma maioria estrita para ler ou gravar; no modo AP, cada grupo atende requisições com os seus próprios nós, e o repair aplica a última escrita vence (a maior versão) depois que a partição se desfaz.
class Cluster:
def __init__(self, names, mode):
self.data = {n: {} for n in names} # node -> {key: (version, value)}
self.mode, self.groups, self.clock = mode, [set(names)], 0
def partition(self, *groups): self.groups = [set(g) for g in groups]
def heal(self): self.groups = [set(self.data)]
def group_of(self, node): return next(g for g in self.groups if node in g)
def _need_majority(self, node):
if self.mode == "CP" and len(self.group_of(node)) <= len(self.data) // 2:
raise RuntimeError("unavailable: no majority")
def write(self, via, key, value):
self._need_majority(via)
self.clock += 1
for n in self.group_of(via): # only the nodes this node can reach
self.data[n][key] = (self.clock, value)
def read(self, via, key):
self._need_majority(via)
return self.data[via].get(key)
def repair(self, key): # after healing: the highest version wins
best = max(d[key] for d in self.data.values() if key in d)
for d in self.data.values(): d[key] = best
for mode in ("CP", "AP"):
c = Cluster("ABCDE", mode)
c.write("A", "cart", "[milk]")
c.partition("AB", "CDE")
for via, value in (("A", "[milk,eggs]"), ("D", "[milk,bread]")):
try: c.write(via, "cart", value); print(mode, via, "write ok")
except RuntimeError as e: print(mode, via, "write refused:", e)
c.heal(); c.repair("cart")
print(mode, "after heal:", c.data["A"]["cart"][1])
Ao executá-lo, ele mostra que no modo CP a escrita por A é recusada e o carrinho termina como [milk,bread], e no modo AP as duas escritas funcionam e o carrinho também termina como [milk,bread], porque bread carregava a versão mais alta e eggs se foi.
Um sistema AP real pode evitar a perda silenciosa mantendo as duas versões e mesclando-as (um carrinho de compras pode ser mesclado tomando a união dos itens). Os armazenamentos no estilo Dynamo usam version vectors para detectar que duas escritas foram concorrentes, e os CRDTs (conflict-free replicated data types) são estruturas de dados projetadas para que qualquer ordem de mesclagem dê o mesmo resultado.
4. Quóruns: como os armazenamentos replicados escolhem o lado
Tome N réplicas de cada item. Uma escrita precisa ser confirmada por W delas e uma leitura precisa consultar R delas. Se
R + W > N
então todo conjunto de leitura e todo conjunto de escrita se sobrepõem em pelo menos uma réplica, de modo que uma leitura sempre contata uma réplica que viu a última escrita confirmada. Verifiquei por força bruta para N = 3 e N = 5: para todo R e W, "todo conjunto de leitura intersecta todo conjunto de escrita" é verdadeiro exatamente quando R + W > N.
| N | W | R | Efeito |
|---|---|---|---|
| 3 | 2 | 2 | Equilibrado; tolera uma réplica com falha tanto para leituras quanto para escritas |
| 3 | 3 | 1 | Leituras rápidas, as escritas precisam de todas as réplicas |
| 3 | 1 | 3 | Escritas rápidas, as leituras precisam de todas as réplicas |
| 3 | 1 | 1 | R + W = 2 não é maior que 3: sem garantia; rápido, pode ler dados obsoletos |
Cuidado: quóruns sobrepostos são necessários para a garantia, mas não suficientes para a linearizabilidade completa em um armazenamento real. Escritas concorrentes, problemas de relógio, quóruns "sloppy" que aceitam escritas em outros nós durante uma falha e falhas parciais durante uma escrita podem produzir leituras obsoletas ou perdidas. Os algoritmos de consenso (Raft, Paxos) acrescentam as peças que faltam: um único líder por termo, logs ordenados e commit por maioria.
5. Modelos de consistência: o espectro
Do mais forte ao mais fraco. Cada modelo permite mais comportamentos e custa menos coordenação.
| Modelo | O que um cliente pode observar | Exemplo |
|---|---|---|
| Linearizável | Comporta-se como uma cópia; uma escrita concluída é vista por toda leitura posterior | Um serviço de locks, eleição de líder, o saldo de um banco |
| Sequencial | Todos veem as operações em uma única ordem, consistente com a ordem de cada cliente, mas não necessariamente com o tempo real | Alguns logs replicados |
| Causal | Operações relacionadas por causalidade (uma resposta depois da mensagem que ela responde) são vistas em ordem por todos; as não relacionadas podem diferir | Comentários e respostas |
| Read your writes (garantia de sessão) | Depois que eu escrevo, minhas próprias leituras veem o que escrevi | Edições de perfil |
| Monotonic reads (garantia de sessão) | Nunca vejo os dados voltarem no tempo | Um feed que não "desatualiza" |
| Eventual | Se as escritas param, todas as réplicas convergem para o mesmo valor, eventualmente | DNS, muitos caches, armazenamentos estilo Dynamo com R e W baixos |
O meio-termo prático: as garantias de sessão, como read-your-writes e monotonic reads, são baratas (direcione o usuário a uma réplica ou lembre uma versão) e eliminam a maior parte do que os usuários percebem como "inconsistente". A seção sobre réplicas do guia de cache mostra o mesmo problema do lado da aplicação (estratégias de cache). Não confunda isso com os níveis de isolamento de uma transação de banco de dados, que tratam de transações concorrentes em um banco (níveis de isolamento de transação); a serializabilidade estrita combina as duas ideias.
6. PACELC: e quando nada está quebrado?
Daniel Abadi observou que o CAP só descreve o caso de falha, enquanto o trade-off entre consistência e latência existe o tempo todo [3]. Sua formulação, o PACELC: se há uma Partição, escolha Adisponibilidade ou Consistência; Else (operação normal), escolha Latência ou Consistência.
O motivo é a física: para ser fortemente consistente, uma escrita precisa ser confirmada por réplicas que podem estar em outros data centers, então custa pelo menos uma ida e volta entre regiões (dezenas a centenas de milissegundos). Um sistema pode responder mais rápido confirmando após uma réplica local e replicando em segundo plano, ao preço de leituras obsoletas. Assim:
- Um sistema construído para baixa latência em todo lugar costuma escolher PA/EL: disponível durante as partições, baixa latência no resto do tempo, consistência mais fraca.
- Um sistema construído para correção costuma escolher PC/EC: consistente nos dois casos, pagando em latência e em disponibilidade durante as partições.
- Existem designs mistos (PA/EC, PC/EL), e muitos bancos de dados permitem escolher por requisição (por exemplo, um nível de consistência em cada leitura ou escrita).
Trate os rótulos como um jeito de fazer a pergunta certa, não como classificações exatas de produtos; os padrões e as opções dos fornecedores mudam.
7. Como escolher
Pergunte o que custa uma resposta errada em comparação com nenhuma resposta:
| Necessidade | Incline-se para | Por quê |
|---|---|---|
| Dinheiro, contagens de estoque que não podem vender além do disponível, nomes de usuário únicos, eleição de líder, locks | Consistência (CP, linearizável) | Uma leitura obsoleta causa dano real; um erro é melhor |
| Feeds sociais, contadores de visualizações, "curtidas", catálogos de produtos, recomendações, DNS | Disponibilidade (AP, eventual) | Um pouco obsoleto não tem problema; indisponível tem |
| Carrinho de compras | Disponibilidade com uma regra de mesclagem | Perder uma venda por indisponibilidade é pior que uma mesclagem para resolver |
| Dados que os próprios usuários editam | Read your writes no mínimo | As pessoas notam suas próprias mudanças sumindo |
Lembre também que a escolha pode diferir por funcionalidade dentro de um mesmo produto: use um armazenamento consistente para pagamentos e um eventualmente consistente para feeds de atividade.
8. Erros comuns
- "Nosso banco de dados é CA." Um sistema distribuído não pode optar por não ter partições. Um banco de dados de um único nó é trivialmente "CA", porque não há nada a particionar.
- Tratar o C do CAP como o C do ACID, ou "disponibilidade" como "alto uptime". As palavras são usadas em um sentido específico e estreito.
- Ignorar o caso normal. Na maior parte do tempo não há partição; latência e consistência são o trade-off diário (PACELC).
- Supor que um quórum, sozinho, dá linearizabilidade. Veja a seção 4.
- Confiar em timestamps de máquinas diferentes para a "última escrita vence". Os relógios derivam, então a "última" escrita pode ser a mais antiga. Prefira versões ou relógios lógicos e seja explícito sobre o que se perde.
- Não testar partições. Ferramentas como o Jepsen testam bancos de dados reais sob partições e muitas vezes descobrem que as garantias documentadas não valem em todos os casos. Escreva os seus próprios testes de falha.
9. Perguntas que entrevistadores gostam de acrescentar
"Dá para ser CP e AP ao mesmo tempo?"
Por requisição, sim: o mesmo armazenamento pode oferecer leituras fortes para algumas chamadas e leituras obsoletas rápidas para outras. Para uma operação durante uma partição, não.
"Um sistema com líder por maioria (Raft) é CP?"
Sim, no sentido usual: o lado minoritário não consegue eleger um líder nem fazer commit, então fica indisponível para escritas, enquanto o lado majoritário continua consistente.
"Como os dois lados se reconciliam depois de uma partição?"
Última escrita vence (simples, perde dados), version vectors que guardam as duas e pedem à aplicação que mescle, CRDTs que mesclam automaticamente, ou uma regra específica do seu domínio (união dos itens do carrinho, máximo de um contador).
"Consistência eventual significa que os dados podem ficar errados para sempre?"
Não. Significa que as réplicas convergem se as atualizações param. As perguntas são quanto dura o "eventualmente" (em geral de milissegundos a segundos) e o que a aplicação faz com leituras obsoletas nesse meio-tempo.
10. Coisas a mencionar em uma entrevista
- Enuncie o teorema corretamente: durante uma partição você escolhe entre consistência (linearizabilidade) e disponibilidade; o P não é opcional.
- Dê o argumento da prova em um parágrafo, com duas réplicas.
- Nomeie o espectro de consistência e as garantias de sessão.
- Traga o PACELC e o custo de latência da consistência mesmo quando tudo funciona.
- Explique
R + W > Ne seus limites. - Escolha por funcionalidade e diga o que custa uma resposta errada.
Resumo rápido
- CAP: em uma partição, um sistema replicado precisa escolher entre consistência linearizável e disponibilidade.
- Partições não podem ser evitadas, então a escolha real é C ou A durante uma.
- Na simulação, o lado CP devolveu um erro e não perdeu nada; o lado AP respondeu e perdeu uma atualização.
R + W > Nfaz os quóruns de leitura e de escrita se sobreporem, mas não é a história toda.- Consistência é um espectro: linearizável, sequencial, causal, garantias de sessão, eventual.
- PACELC: mesmo sem partições, você troca latência por consistência.
- Decida por funcionalidade pelo custo de uma resposta errada versus nenhuma resposta.
Fontes
- Seth Gilbert e Nancy Lynch, Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services, ACM SIGACT News, 2002. A prova do teorema.
- Martin Kleppmann, A Critique of the CAP Theorem, 2015. Sobre a ambiguidade das definições do CAP e uma alternativa de sensibilidade ao atraso.
- Daniel Abadi, Consistency Tradeoffs in Modern Distributed Database System Design, IEEE Computer, 2012. PACELC.
- Eric Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, 2012.
- Giuseppe DeCandia et al., Dynamo: Amazon's Highly Available Key-value Store, SOSP 2007. Quóruns, version vectors e o exemplo do carrinho de compras.
- Diego Ongaro e John Ousterhout, In Search of an Understandable Consensus Algorithm (Raft), 2014.
- Kyle Kingsbury, Jepsen: análises de bancos de dados distribuídos sob falhas.
Pratique este tema: System Design System Design › Distributed systems