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:

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

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:

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.

NWREfeito
322Equilibrado; tolera uma réplica com falha tanto para leituras quanto para escritas
331Leituras rápidas, as escritas precisam de todas as réplicas
313Escritas rápidas, as leituras precisam de todas as réplicas
311R + 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.

ModeloO que um cliente pode observarExemplo
LinearizávelComporta-se como uma cópia; uma escrita concluída é vista por toda leitura posteriorUm serviço de locks, eleição de líder, o saldo de um banco
SequencialTodos veem as operações em uma única ordem, consistente com a ordem de cada cliente, mas não necessariamente com o tempo realAlguns logs replicados
CausalOperações relacionadas por causalidade (uma resposta depois da mensagem que ela responde) são vistas em ordem por todos; as não relacionadas podem diferirComentários e respostas
Read your writes (garantia de sessão)Depois que eu escrevo, minhas próprias leituras veem o que escreviEdições de perfil
Monotonic reads (garantia de sessão)Nunca vejo os dados voltarem no tempoUm feed que não "desatualiza"
EventualSe as escritas param, todas as réplicas convergem para o mesmo valor, eventualmenteDNS, 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:

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:

NecessidadeIncline-se paraPor 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, locksConsistê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, DNSDisponibilidade (AP, eventual)Um pouco obsoleto não tem problema; indisponível tem
Carrinho de comprasDisponibilidade com uma regra de mesclagemPerder uma venda por indisponibilidade é pior que uma mesclagem para resolver
Dados que os próprios usuários editamRead your writes no mínimoAs 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

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

Resumo rápido

  1. CAP: em uma partição, um sistema replicado precisa escolher entre consistência linearizável e disponibilidade.
  2. Partições não podem ser evitadas, então a escolha real é C ou A durante uma.
  3. Na simulação, o lado CP devolveu um erro e não perdeu nada; o lado AP respondeu e perdeu uma atualização.
  4. R + W > N faz os quóruns de leitura e de escrita se sobreporem, mas não é a história toda.
  5. Consistência é um espectro: linearizável, sequencial, causal, garantias de sessão, eventual.
  6. PACELC: mesmo sem partições, você troca latência por consistência.
  7. Decida por funcionalidade pelo custo de uma resposta errada versus nenhuma resposta.

Fontes

  1. 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.
  2. Martin Kleppmann, A Critique of the CAP Theorem, 2015. Sobre a ambiguidade das definições do CAP e uma alternativa de sensibilidade ao atraso.
  3. Daniel Abadi, Consistency Tradeoffs in Modern Distributed Database System Design, IEEE Computer, 2012. PACELC.
  4. Eric Brewer, CAP Twelve Years Later: How the "Rules" Have Changed, IEEE Computer, 2012.
  5. 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.
  6. Diego Ongaro e John Ousterhout, In Search of an Understandable Consensus Algorithm (Raft), 2014.
  7. Kyle Kingsbury, Jepsen: análises de bancos de dados distribuídos sob falhas.

Pratique este tema: System Design System Design › Distributed systems

Mais guias