Distributed Database Internals — LSM vs B-tree, consenso, replicação e CAP/PACELC

Em 2007, Giuseppe DeCandia e outros engenheiros da Amazon publicaram um paper de 16 páginas chamado "Dynamo: Amazon's Highly Available Key-value Store". O paper descrevia o sistema interno que rodava o carrinho de compras da Amazon — um sistema desenhado com uma única obsessão: nunca falhar a operação de adicionar item ao carrinho, mesmo se metade dos data centers estivesse offline. Para conseguir isso, abriram mão de consistência forte (dois nós podem ter versões diferentes do carrinho ao mesmo tempo), abraçaram conflitos como resolúveis depois ("union dos itens nos dois carrinhos"), e usaram técnicas como consistent hashing, vector clocks, e gossip protocol que eram conceitos acadêmicos pouco aplicados na indústria. O paper se tornou a inspiração de uma geração inteira de bancos: Cassandra, Riak, Voldemort, DynamoDB (o serviço da AWS), todos descendem diretamente das ideias do Dynamo. Antes desse paper, "banco de dados" significava Postgres ou MySQL com replicação master-slave. Depois, o mundo entendeu que existia um espaço inteiro de tradeoffs diferentes — e que a escolha de banco era a escolha de quais tradeoffs aceitar.

Entender os internals desses bancos não é exercício acadêmico — é o que permite tomar decisões informadas em system design. "Vou usar Cassandra" sem entender LSM tree é uma decisão sem fundamento. "Vou usar Postgres" sem entender MVCC é igual. A escolha entre Cassandra, DynamoDB, CockroachDB, Postgres e MySQL deriva de quatro perguntas fundamentais: (1) qual é a razão entre reads e writes, (2) qual nível de consistência o produto exige, (3) qual é o padrão de acesso (queries ad-hoc vs por chave primária), e (4) onde o sistema precisa estar geograficamente. Este conceito não substitui o módulo 05 (Bancos de Dados) — aprofunda especificamente nos mecanismos internos que tornam cada escolha justificável ou não em system design.

LSM tree vs B-tree: a fronteira entre read-heavy e write-heavy

Toda escolha de banco começa com a estrutura de dados do storage engine. Postgres, MySQL/InnoDB, Oracle e SQL Server usam variações de B-tree. Cassandra, RocksDB, LevelDB, ScyllaDB e o storage do Kafka usam LSM tree (Log-Structured Merge tree). A diferença não é detalhe — define o que o banco faz bem e mal.

# B-TREE: a estrutura clássica desde 1970

# Estrutura:
# - Árvore balanceada de nodes em disco; tipicamente fan-out de 100-200 chaves por node
# - Cada lookup: descer da raiz até a folha, O(log_B(N)) acessos a disco
# - Update in-place: encontra a página, modifica, escreve de volta

# Write:
# 1. Localizar a página onde a chave deve estar (log N reads)
# 2. Modificar a página em memória
# 3. Escrever WAL (write-ahead log) para durabilidade
# 4. Eventualmente, fsync da página modificada para disco
# Cost: 1 random write para a página (após o WAL append)

# Read:
# 1. Descer a árvore: log N seek reads
# 2. Para queries com cache quente, primeiros níveis ficam em RAM → ~1 disk seek
# Cost: 1 random read no caso quente

# Características:
# + Reads consistentemente rápidos (1-3 random seeks)
# + Range scans são naturais (folhas linkadas em lista)
# + Update in-place: espaço crescimento previsível
# - Writes precisam encontrar e modificar página específica → random I/O
# - Splits/merges causam write amplification em hot ranges
# - Concurrent writes precisam de locking de página (contention)

# LSM TREE: a estrutura que dominou os sistemas write-heavy desde 2010s

# Estrutura:
# - Writes vão para um MEMTABLE (in-memory sorted structure, ex: skip list)
# - Quando o memtable enche, é flushed como um SSTABLE imutável no disco
# - SSTABLE = Sorted String Table: arquivo ordenado por chave, com index esparso
# - Background: compaction merge SSTables menores em maiores

# Write:
# 1. Append no WAL (sequential write)
# 2. Insert no memtable em memória (O(log N) na skip list)
# 3. Eventualmente: flush memtable → SSTable no disco (sequential write)
# Cost: ZERO random writes! Apenas sequential writes
# Throughput: 10x-100x mais que B-tree em workloads write-heavy

# Read:
# 1. Verificar memtable (RAM, rápido)
# 2. Se não encontrado: verificar SSTables, do mais novo para o mais antigo
# 3. Cada SSTable: bloom filter em RAM diz "talvez está aqui" ou "garantido que não"
# 4. Se bloom filter diz sim: lookup no index esparso + seek nos dados
# Cost: pode precisar verificar N SSTables = N seeks no pior caso
# Mitigação: bloom filters reduzem falsos lookups; compaction reduz N

# Compaction:
# - Tiered compaction: SSTables agrupadas por tamanho similar; merge cria SSTable maior
# - Leveled compaction: níveis L0..LN; cada nível tem 10x o tamanho do anterior
# - Importante: compaction é I/O em background; pode causar latência picos

# Características:
# + Writes EXTREMAMENTE rápidos (apenas appends e ops em memória)
# + Naturalmente "log-friendly" — bom para SSDs
# + Compressão melhor (SSTables imutáveis comprimem bem)
# - Reads podem ser mais lentos (multiple SSTables a verificar)
# - Compaction overhead: I/O constante em background; pode dobrar o write amplification
# - Delete não é instantâneo: cria um "tombstone" que persiste até a próxima compaction

# Comparação prática:
# Workload: 10k writes/s sustentado
#   B-tree (Postgres single instance): saturado em ~10-20k writes/s
#   LSM (Cassandra single node): confortável até 50-100k writes/s
# Workload: 100k reads/s com cache 90% hit
#   B-tree: latência P99 ~5ms (1 disk seek se cache miss)
#   LSM: latência P99 ~15ms (pode tocar 3-5 SSTables se cache miss)

# Quem usa o quê:
# B-tree: PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, MongoDB (WiredTiger)
# LSM: Cassandra, ScyllaDB, RocksDB (base de CockroachDB, TiDB, MyRocks), LevelDB,
#      HBase, BigTable, DynamoDB internals (variante proprietária)

MVCC: como Postgres faz transações concorrentes sem bloquear leituras

MVCC (Multi-Version Concurrency Control) é o mecanismo que permite ao Postgres oferecer snapshot isolation sem locking pesado de leitura. Cada linha tem várias versões; transações leem a versão consistente com seu snapshot. É uma das ideias mais elegantes em databases — e é o que faz Postgres ser preferido sobre MySQL para workloads OLTP complexos.

# Cada tupla (linha) no Postgres tem dois campos invisíveis:
# - xmin: ID da transação que inseriu/atualizou esta versão
# - xmax: ID da transação que deletou/substituiu (ou 0 se ainda viva)

# Cada transação T começa com um snapshot:
# - xmin_snapshot: menor TX ID ativo no momento do START
# - xip_list: lista de TXs em progresso no START
# - xmax_snapshot: maior TX ID atribuído + 1

# Regra de visibilidade (simplificada):
# Uma tupla é visível para a transação T se:
#   - tupla.xmin < T.xmax_snapshot (foi criada antes do START)
#   - tupla.xmin NOT IN T.xip_list (a TX criadora já tinha commitado quando T começou)
#   - tupla.xmax == 0 OR tupla.xmax > T.xmax_snapshot (não foi deletada)

# Exemplo concreto:
# T1 (TX 100) começa, snapshot = (xmin=99, xip=[], xmax=101)
# T2 (TX 101) começa, snapshot = (xmin=99, xip=[100], xmax=102)
#
# T1: UPDATE balance SET amount = 200 WHERE id = 1
#   → Cria nova versão da linha com xmin=100, xmax=0
#   → Marca versão antiga com xmax=100 (deletada por T1)
#
# T2 lê id=1 ANTES de T1 commitar:
#   → Encontra duas versões: (xmin=99, xmax=100) e (xmin=100, xmax=0)
#   → Versão antiga (xmin=99) é visível para T2 (99 < 102, 99 not in xip)
#     E xmax=100 está em T2.xip_list → trata como "ainda viva" para T2
#   → Versão nova (xmin=100) é INVISÍVEL para T2 (xmin=100 está em xip_list)
#   → T2 lê amount = valor antigo, mesmo concorrente com a atualização

# Vantagens do MVCC:
# + Readers nunca bloqueiam writers, e vice-versa
# + Snapshot consistency: T2 sempre vê o estado do banco no momento do START
# + Sem deadlocks típicos de locking pessimista
# + Long-running analytics queries (rodando por horas) não bloqueiam OLTP

# Custos do MVCC:
# - Bloat: versões antigas ocupam espaço até serem limpas por VACUUM
# - VACUUM precisa rodar periodicamente para reclaim de espaço
# - Tuple visibility check tem custo em cada read
# - Se uma transação fica MUITO tempo aberta, impede VACUUM de limpar tuplas → tabela bloat

# AUTOVACUUM: o processo background que limpa tuplas mortas
# - Por padrão dispara quando 20% da tabela é "dead"
# - Em tabelas com alta taxa de update, pode não dar conta → tuning manual

# Em escala (lição aprendida na prática):
# - Tabelas com muito UPDATE pesado em Postgres podem ter performance degradada por bloat
# - Mitigação: particionamento, UPDATE→DELETE+INSERT em alguns casos, ou usar Postgres 14+
#   com HOT updates (Heap-Only Tuples) onde possível
# - Para workloads write-extreme, considerar storage engine alternativo (MyRocks) ou
#   banco diferente (Cassandra para append-only, ScyllaDB para mixed)

Consistent hashing: por que sharding por range tem hotspots

O problema clássico de sharding: se você usar hash(key) % N e adicionar um servidor, quase todas as chaves precisam migrar (porque o módulo muda). Consistent hashing resolve isso elegantemente: só ~1/N das chaves migra quando N muda em 1.

# Sharding NAIVE com hash modulo:
# servers = [s0, s1, s2]
# shard = hash(key) % len(servers)
# Problema: adicionar s3 → shard = hash(key) % 4
#   75% das chaves agora estão no shard "errado" e precisam migrar

# Sharding por RANGE:
# servers = [s0: keys "a-h", s1: "i-p", s2: "q-z"]
# Problema: distribuição desigual (mais usuários começam com "j-m" que "x-z")
# Hot range: bursts de tráfego em chaves próximas saturam um único shard

# CONSISTENT HASHING:
# 1. Mapear todos os servidores e todas as chaves em um anel (hash circular [0, 2^32))
# 2. Para encontrar o servidor de uma chave: hash(chave), depois andar no sentido horário
#    até encontrar o primeiro servidor no anel
# 3. Adicionar/remover servidor: só as chaves entre o predecessor e o novo servidor migram

# Pseudocódigo:
class ConsistentHashRing:
    def __init__(self, servers):
        self.ring = {}  # hash_value → server
        for s in servers:
            for vnode in range(VIRTUAL_NODES):  # ex: 256 virtual nodes por servidor
                h = hash(f"{s}:{vnode}")
                self.ring[h] = s

    def get_server(self, key):
        h = hash(key)
        # Encontrar o menor hash >= h no anel (binary search no sorted ring)
        sorted_hashes = sorted(self.ring.keys())
        idx = bisect.bisect_right(sorted_hashes, h) % len(sorted_hashes)
        return self.ring[sorted_hashes[idx]]

    def add_server(self, s):
        for vnode in range(VIRTUAL_NODES):
            h = hash(f"{s}:{vnode}")
            self.ring[h] = s
        # Apenas as chaves nos "slots" novos precisam migrar

# Por que VIRTUAL NODES (vnodes)?
# Sem vnodes, com 3 servidores, cada um pega ~1/3 do anel — mas a distribuição
# real depende dos hashes específicos e tende a ser desigual (load skew)
# Com 256 vnodes por servidor (3 × 256 = 768 pontos no anel), a distribuição
# se aproxima muito da uniforme (lei dos grandes números)
# Vantagem adicional: ao adicionar servidor S4, as 256 vnodes de S4 estão
# espalhadas pelo anel → migração vem proporcionalmente de S1, S2, S3
# (não apenas do "vizinho" de S4)

# REPLICAÇÃO em consistent hashing (Dynamo-style):
# Para cada chave, replicar nos próximos N servidores do anel
# Replication factor RF=3: chave vai para o servidor "primary" + 2 vizinhos
# Leitura: contactar R servidores; quorum read W + R > N para consistência
# Escrita: enviar para W servidores; sucesso quando W ACKs recebidos
# Configurações comuns:
#   N=3, W=1, R=1: máxima disponibilidade, eventual consistency (default DynamoDB)
#   N=3, W=2, R=2: quorum, consistency em leitura
#   N=3, W=3, R=1: tudo escrito antes de ack, leitura local

# Quem usa consistent hashing:
# - Cassandra (com tweaks: tokens em vez de vnodes nativos pré-3.0)
# - DynamoDB (interno)
# - Memcached (clients usam libketama)
# - Riak, Voldemort
# - Redis Cluster (com tweak: hash slots, mas mesma ideia)
# - Maglev (Google load balancer)
# - Sistemas de WebSocket sticky session

Replicação: leader-follower, multi-leader e leaderless

# Três modelos fundamentais de replicação:

# 1. LEADER-FOLLOWER (single-leader, master-slave):
# Todos os writes vão para o leader, que replica para followers
# Reads podem ir para leader ou followers (com possível stale data)
# Usado por: Postgres (streaming replication), MySQL, MongoDB, Redis, Kafka (per-partition)

# Replicação síncrona vs assíncrona:
# - Síncrona: o leader espera ACK do follower antes de commitar
#   + RPO = 0 (zero data loss em failover)
#   - Latência inclui RTT até o follower
#   - Se follower está down/lento, writes do leader são bloqueados
# - Assíncrona: leader commit ANTES do follower receber
#   + Latência baixa, leader independente do follower
#   - RPO > 0 (writes não replicados perdem-se se leader cair)
#   - Replication lag visível para reads no follower

# Semi-sync (MySQL): o leader espera ACK de PELO MENOS UM follower
# Postgres: synchronous_commit pode ser local, on, remote_write, remote_apply
#   - remote_write: follower escreveu no buffer (ainda em RAM)
#   - remote_apply: follower aplicou WAL (commit completo)

# Failover:
# - Detecção de falha do leader (heartbeats, geralmente 5-30s)
# - Eleição de novo leader entre os followers
# - Redirecionar writes; aceitar que alguns writes recentes podem ter sido perdidos
# - Replicação reverse: ex-leader (quando voltar) precisa virar follower
# - SPLIT-BRAIN: dois leaders simultâneos pensando que são o leader
#   → resolvido com fencing (STONITH) ou consenso (Raft)

# 2. MULTI-LEADER (multi-master):
# Múltiplos nós aceitam writes, replicam entre si
# Usado em: multi-datacenter (cada DC tem seu leader local)
# Tendências modernas: descontinuado em muitos bancos por complexidade
# Exemplos: MySQL com tools como pt-table-sync; CouchDB; Google Spanner (parcialmente)

# Problema central: CONFLITOS
# Se dois leaders aceitam writes na mesma chave simultaneamente, qual vence?
# Resoluções:
# - Last write wins (LWW): timestamp mais recente vence (perde dados!)
# - Conflito reportado à aplicação: aplicação resolve (complexo)
# - CRDTs: estruturas que convergem matematicamente (G-counter, OR-Set)

# 3. LEADERLESS (peer-to-peer):
# Sem leader; client envia write para múltiplos nós (W) e lê de múltiplos (R)
# Quorum: W + R > N garante read-your-writes consistency
# Usado por: Cassandra, DynamoDB, Riak

# Vantagens:
# + Alta disponibilidade: nenhum nó é especial; qualquer um pode servir qualquer request
# + Failure handling natural: se um nó está down, escreve para os outros que ainda
#   estão no quorum
# + Sem failover: não há leader para falhar

# Desvantagens:
# - Sem ordering global: dois clients podem ver writes em ordens diferentes
# - Resolução de conflito é responsabilidade da aplicação (geralmente LWW)
# - Read repair / hinted handoff: complexidades adicionais para garantir convergência

# Read repair (Cassandra):
# Client lê de R nós; se respondem valores diferentes, escreve o "mais recente" para
# os outros nós para reconciliar — repair on read
# Anti-entropy: processo background que compara hashes de ranges entre nós

# Hinted handoff:
# Se um nó está down quando o write chega, o coordenador armazena um "hint" temporário
# Quando o nó volta, recebe os hints e aplica os writes perdidos

Consensus: Raft em termos práticos (e por que não Paxos)

Quando vários nós precisam concordar em algo (quem é o leader, qual é o próximo entry no log replicado), eles precisam de um protocolo de consenso. Paxos (Leslie Lamport, 1989) é o protocolo clássico mas é notoriamente difícil de entender e implementar correto. Raft (Ongaro & Ousterhout, 2014) foi explicitamente desenhado para ser compreensível — e por isso virou o padrão para sistemas novos.

# RAFT: três estados e três regras

# Estados de cada nó:
# - FOLLOWER: estado default; recebe AppendEntries do leader
# - CANDIDATE: tentando virar leader (após timeout sem heartbeat)
# - LEADER: aceita writes, replica para followers

# Term: número monotonicamente crescente; cada eleição incrementa
# Cada nó conhece o currentTerm; mensagens com term menor são rejeitadas

# Eleição:
# 1. Follower não recebe heartbeat por electionTimeout (150-300ms aleatório)
# 2. Vira CANDIDATE, incrementa currentTerm, vota em si mesmo
# 3. Envia RequestVote para todos os outros
# 4. Cada nó vota em até um candidato por term (regra fundamental)
# 5. Se receber votos da maioria → vira LEADER, envia heartbeats
# 6. Se outro nó for eleito (heartbeat com term ≥ atual) → volta para FOLLOWER
# 7. Se timeout sem ganhar → incrementa term, tenta de novo

# Por que electionTimeout RANDOMIZADO?
# Se todos votassem simultaneamente, vários candidatos empatariam (split vote)
# Randomização garante que UM candidato dispara o timeout primeiro

# Replicação de log:
# Leader recebe write do client
# Adiciona ao próprio log com (term, index, command)
# Envia AppendEntries para followers (com o new entry e o (term, index) do anterior)
# Cada follower:
#   - Verifica que o entry anterior bate (consistência do log)
#   - Se bate: append, retorna sucesso
#   - Se não bate: rejeita; leader manda entries mais antigas até alinhar
# Quando MAIORIA dos followers respondeu sucesso: leader COMMITA o entry
# Próximos heartbeats informam aos followers que esse índice está commited
# Followers commitam → aplicam à state machine

# COMMIT é a chave: somente após a maioria persistir, o entry é considerado durável
# Em caso de partição/falha:
#   - Se o leader cair antes do commit, novos leader pode descartar o entry
#   - Se o leader cair APÓS o commit, novo leader (que tem o entry) replica para os outros

# Garantias do Raft:
# - Leader Completeness: se um entry foi committed no term T, todos os leaders
#   subsequentes (terms > T) terão esse entry no log
# - Safety: dois leaders nunca commitam diferentes valores para o mesmo log index
# - Availability: enquanto maioria dos nós está online, o sistema progride

# Quórum: maioria SIMPLES (N/2 + 1)
# - 3 nós: quorum = 2 (tolera 1 falha)
# - 5 nós: quorum = 3 (tolera 2 falhas)
# - 7 nós: quorum = 4 (tolera 3 falhas)
# Diminishing returns: 5 nós é o sweet spot para a maioria dos sistemas
# Mais nós = mais resiliência, mas mais latência (precisa esperar ACKs de mais nós)

# Quem usa Raft:
# - etcd (Kubernetes config store)
# - Consul (HashiCorp service discovery)
# - TiKV (storage layer do TiDB)
# - CockroachDB (Raft por range de chaves)
# - InfluxDB
# - RethinkDB (descontinuado)
# - Centenas de novos sistemas distribuídos

# PAXOS (resumo):
# Mesmo problema, abordagem diferente. Conceitos:
# - Proposers propõem valores
# - Acceptors votam em valores propostos
# - Learners aprendem o valor decidido
# Two-phase: PREPARE (proposer pede aos acceptors um "ballot number"),
# ACCEPT (proposer propõe valor com ballot number)
# Por que Paxos é difícil:
# - O paper original ("The Part-Time Parliament") é uma metáfora obscura
# - Múltiplas variantes: Multi-Paxos, Cheap Paxos, Fast Paxos, Generalized Paxos
# - Detalhes sutis levam a implementações incorretas (e bugs sutis em produção)
# Quem usa Paxos:
# - Google Chubby (lock service) - original
# - Google Spanner (Multi-Paxos)
# - Apache ZooKeeper (Zab — variante de Paxos)
# - Sistemas legados, principalmente na Google

# Regra prática: para um sistema novo em 2026, escolher Raft, não Paxos

CAP e PACELC: o mapa de decisão

# CAP (Eric Brewer, 2000; provado por Gilbert & Lynch, 2002):
# Num sistema distribuído sujeito a PARTIÇÕES de rede, você escolhe entre:
# - Consistency (C): todos os nós veem o mesmo dado
# - Availability (A): toda request recebe resposta (não-erro)

# Importante: CAP é DURANTE A PARTIÇÃO. Sem partição, todos os sistemas podem ser CA.
# E partição é INEVITÁVEL em sistemas distribuídos suficientemente grandes.
# (network blips, switch failure, cable cut, GC pause longo simulando partição...)

# PACELC (Daniel Abadi, 2010): a extensão prática
# - Se Particionado: escolher entre A e C (CAP)
# - Else (sem partição): escolher entre Latência (L) e Consistency (C)

# Quase todos os sistemas reais têm tradeoff de latência mesmo SEM partição:
# Replicação síncrona = consistência forte mas latência alta
# Replicação assíncrona = baixa latência mas consistência eventual

# Classificação PACELC de bancos comuns:

# PA/EL (disponibilidade + latência; prioriza ambos sobre consistência):
# - DynamoDB (default), Cassandra, Riak, Voldemort
# - Comportamento: sempre responde (mesmo com dado stale); latência consistentemente baixa
# - Use case: shopping cart, sessões, leaderboards onde "alguns segundos atrasado" é OK

# PC/EC (consistência sempre; sacrifica disponibilidade durante partição):
# - HBase, BigTable, Zookeeper, etcd, Consul
# - Comportamento: em caso de partição, minoria fica indisponível; maioria continua
# - Use case: configuração crítica, service discovery, locks distribuídos

# PA/EC (disponibilidade durante partição; consistência sem partição):
# - MongoDB (com majority writeconcern e linearizable read concern)
# - Comportamento híbrido: rotina consistente, mas pode degradar disponibilidade

# PC/EL (consistência durante partição; latência sem partição):
# - PNUTS (Yahoo), original PNUTS-like systems

# Postgres é interessante:
# - Single-instance: ACID, sem partição interna (não distribuído)
# - Streaming replication assíncrona: PA/EL (replicas podem ter stale data)
# - Synchronous replication: PA/EC (espera replica, mas se replica cair pode quebrar)
# - PostgreSQL não é primariamente um sistema distribuído — para multi-master usa
#   ferramentas externas (BDR, Citus) que mudam a classificação

# Em system design:
# A pergunta NÃO é "este banco é AP ou CP" abstratamente
# A pergunta É: "para a operação X no meu produto, o que é pior:
#   receber dado stale, ou não receber resposta?"
# A resposta determina qual banco escolher para qual sub-sistema

# Exemplos práticos:
# - Carrinho de compras Amazon: receber dado stale é OK (resolvemos depois)
#   → AP system (DynamoDB original)
# - Saldo bancário: dado stale é catastrófico (cliente saca dinheiro que não existe)
#   → CP system (RDBMS tradicional ou Spanner)
# - Like contador: dado stale é totalmente OK
#   → AP system, eventual consistency
# - Inventory de e-commerce: cinco pessoas comprando o último item é problema
#   → CP system (ou AP com compensação business-level: cancelar pedidos depois)

Casos práticos: por que cada banco existe

# PostgreSQL — o "general purpose database"
# Strengths:
#   - ACID completo, snapshot isolation via MVCC, transações multi-table
#   - SQL completo, JOINs eficientes, queries ad-hoc
#   - Extensível: JSON, geographic (PostGIS), full-text, time-series (TimescaleDB)
#   - Comunidade enorme, ferramental maduro
# Weaknesses:
#   - Single-writer (master-slave); escala write só com sharding manual
#   - VACUUM como overhead; bloat em workloads write-heavy
# Use cases:
#   - 90% dos sistemas OLTP novos (e-commerce, SaaS, dashboards)
#   - Workloads onde consistência transacional importa
# Sweet spot: até 10k-50k writes/s, até 5TB single-instance

# MySQL (InnoDB) — irmão do Postgres, com tradeoffs diferentes
# Strengths:
#   - Mais simples operacionalmente, replicação master-slave nativa
#   - Foreign keys e transações, mas com isolamento weaker default (READ COMMITTED)
#   - Ecosistema gigante (WordPress, etc)
# Weaknesses:
#   - Menos features avançadas (full-text, geographic são fracos)
#   - Query optimizer historicamente atrás do Postgres
# Use cases:
#   - Aplicações tradicionais; legacy
#   - Casos onde simplicidade operacional importa mais que features

# Cassandra — write-heavy, distribuído, AP
# Strengths:
#   - Linear scalability: adicionar nó = throughput proporcional
#   - Multi-datacenter nativo
#   - Excelente para time-series e workloads append-only
# Weaknesses:
#   - Sem JOINs; queries só por partition key
#   - Tunable consistency é poderoso mas confunde devs
#   - Operação tem learning curve íngreme
# Use cases:
#   - Time-series (métricas, logs)
#   - Messaging history (WhatsApp, Discord, Instagram DMs)
#   - Feeds de atividades
# Sweet spot: 100k+ writes/s, billions de rows

# DynamoDB — serverless AP, gerenciado pela AWS
# Strengths:
#   - Zero ops (autoscaling, backup, replicação automáticos)
#   - Latência consistente (single-digit ms)
#   - Strongly consistent reads opt-in
#   - Global tables (multi-region active-active)
# Weaknesses:
#   - Caro em escala (RCU/WCU billing)
#   - Modelo de dados restrito (sem JOINs, queries limitadas)
#   - Lock-in à AWS
# Use cases:
#   - Workloads serverless (Lambda + DynamoDB é stack natural)
#   - Casos com throughput muito variável (autoscaling vence)
# Sweet spot: até 100k req/s, single-digit ms P99

# CockroachDB — distributed SQL, CP, geo-distribuído
# Strengths:
#   - SQL completo (drop-in para Postgres em muitos casos)
#   - Distribuído nativamente: shard automático com consistent hashing
#   - Multi-region com latência otimizada
#   - Serializable isolation
# Weaknesses:
#   - Latência maior que Postgres single-instance (consensus overhead)
#   - Custo (licença enterprise para algumas features)
#   - Ecosistema menor que Postgres
# Use cases:
#   - Aplicações que precisam de SQL + escala global
#   - Quando Postgres single-instance vai começar a apertar mas ainda preciso de SQL

# MongoDB — document store, foi AP, agora ambíguo
# Strengths:
#   - Schema flexível (bom para iteração rápida)
#   - JSON nativo (boa fit para JavaScript stacks)
#   - Aggregation pipeline poderoso
# Weaknesses:
#   - Historicamente teve problemas de durabilidade (defaults perigosos)
#   - JOINs ($lookup) são caros e tarde
#   - Sharding tem armadilhas operacionais
# Use cases:
#   - Document storage natural (catálogos com schemas variados)
#   - Stack JavaScript end-to-end
# Sweet spot: quando o modelo de dados é genuinamente document-oriented

# Redis — in-memory, key-value, single-thread
# Strengths:
#   - Latência sub-milissegundo (in-memory)
#   - Estruturas de dados ricas (sorted sets, hyperloglog, geo, streams)
#   - Pub/Sub nativo
# Weaknesses:
#   - Persistência opcional (snapshots ou AOF — tradeoffs)
#   - Single-threaded por shard
#   - Cluster mode tem limitações (multi-key ops restritas)
# Use cases:
#   - Cache (uso #1)
#   - Sessions, rate limiting, leaderboards
#   - Filas de jobs (com cuidado — RabbitMQ/Kafka melhor para mensagens persistentes)

Arquitetura comparativa: por que cada banco se parece com o que se parece

POSTGRES (single-instance, traditional)
┌──────────────────────────────────┐
│  Clients                          │
└─────────────┬────────────────────┘
              │ TCP / SQL protocol
              ▼
┌──────────────────────────────────┐
│  postmaster (parent process)     │
│    └── postgres backend (per conn)│
│         ├── Query parser          │
│         ├── Planner / optimizer   │
│         ├── Executor              │
│         └── Buffer cache (RAM)    │
└─────────────┬────────────────────┘
              │
              ▼
┌──────────────────────────────────┐
│  WAL (write-ahead log)            │
│  Heap files (B-tree storage)      │
│  Indexes (B-tree, GiST, BRIN, ...)│
└──────────────────────────────────┘
              │ async streaming
              ▼
       Read replicas (followers)

CASSANDRA (peer-to-peer, no leader)
        Client
          │ chooses any coordinator
          ▼
┌──────────────────────────────────┐
│  Coordinator (any node, rotating)│
│  - Decide replicas via ring      │
│  - Send to N nodes (RF=3 typical)│
│  - Wait for W ACKs (quorum)      │
└─────────────┬────────────────────┘
              │ gossip + native protocol
              ▼
   ┌──────────┼──────────┐
   ▼          ▼          ▼
 Node A    Node B    Node C    Node D    ...
 (LSM:     (LSM)     (LSM)     (LSM)
  memtable
  + sstables
  + bloom
  + WAL)

Cada nó tem o anel completo em memória → routing local
Replication factor configurável por keyspace
Read e Write consistency tunáveis (ONE, QUORUM, ALL)

COCKROACHDB (distributed SQL, Raft per range)
        SQL Client
          │
          ▼
   Gateway node (any node)
          │ SQL parser, planner
          ▼
   Distributed execution
          │
   ┌──────┼──────┐
   ▼      ▼      ▼
 Range1  Range2  Range3  (key-space dividido em ranges de ~512MB)
   │      │      │
 Raft   Raft   Raft     cada range é um grupo Raft separado
 group  group  group
   │      │      │
 ┌─┴─┐  ┌─┴─┐  ┌─┴─┐
 │N1N2│  │N2N3│  │N1N3│  réplicas em 3 nós diferentes (RF=3)
 │N3 │  │N1 │  │N2 │   leader rotacional para load balancing
 └───┘  └───┘  └───┘

Quando uma transação toca múltiplas ranges: 2PC sobre os Raft groups envolvidos

REDIS CLUSTER (single-thread shards)
   Client (cluster-aware)
       │ knows hash slot map
       ▼
   ┌───┴───┐
   ▼   ▼   ▼
  M1  M2  M3   masters (cada um dono de ~5461 hash slots de 16384)
   │   │   │
  R1  R2  R3   replicas (async replication)

Hash slot = CRC16(key) % 16384
MOVED redirect: se client manda para shard errado, recebe MOVED e refaz
Resharding: mover slots entre masters em batch (sem downtime)

Decisões de engenharia

Perguntas de entrevista

Exercícios práticos