Teu progresso
0 / 83 módulos0%
Estágio 04 · 04-01
BloqueadoA maioria dos engenheiros que se diz "distributed systems engineer" sabe usar Kafka e Postgres replicado, não entende os teoremas que governam o comportamento desses sistemas. Quando o sistema falha de forma sutil (split brain, replication lag aparecendo como bug, message loss aparente), a falta de modelo mental cobra preço. O engenheiro chuta, troca tecnologia, ou aceita "é bug do Postgres". Não.
Este módulo é teoria pra engenharia distribuída. Não é PhD; é o subset que você precisa pra projetar e debugar sistemas distribuídos sem se enganar: CAP/PACELC, modelos de consistência, time e ordering (Lamport, vector clocks, hybrid logical clocks), quorum, consensus (Paxos/Raft em alto nível), failure detectors, replication models, e como tudo isso aparece no Postgres, Kafka, Redis, 04-03 que você já usa.
Em sistema único (1 process, 1 host), você assume:
Em sistema distribuído:
Isso não é detalhe, é a fonte de toda complexidade.
Em sistemas internos, você assume "fail-stop com recovery". Em sistemas adversariais (blockchain), Byzantine.
Em network real, partitions acontecem (cabo cortado, switch cai). Tempo, sempre.
"Servidor lento" é mais perigoso que "servidor morto". Cliente espera, timeout, retry. Recursos consumidos. Cascade.
Detector de falha:
Brewer, 2000. Em sistema distribuído com partição de rede (P), você escolhe entre:
Não pode ter ambos durante partition. CAP não é "escolha 2 de 3", partições acontecem; você escolha CP ou AP no momento de partition.
Exemplos:
Daniel Abadi extendeu: PACELC:
Mais útil que CAP. Postgres sync rep: PC + EC (sempre consistente, paga latência). DynamoDB: PA + EL (sempre disponível, latência baixa, paga consistency).
Spectrum (do mais forte ao mais fraco):
Postgres (single-leader): linearizable em writes; reads de réplica podem ser stale. DynamoDB strong read: linearizable. DynamoDB eventual read: eventual. Cassandra: tunable (QUORUM, ONE, ALL).
Wall clock (NTP): drift entre nodes, pode ir pra trás. Não use pra ordering.
Lamport clock: counter monotônico por node; em qualquer mensagem recebida, atualiza pra max(local, received) + 1. Garante: se A causally precede B, então L(A) < L(B). Não vice-versa.
Vector clock: array com counter por node. Captura concurrency: V(A) < V(B) se cada coord ≤. Ordena causally; detecta concurrents.
Hybrid Logical Clock (HLC): combina wall clock + logical counter. Dá ordem total ≈ tempo real, robusto a clock skew. Usado em CockroachDB, Citus.
TrueTime (Google Spanner): clocks com bound de uncertainty (now() retorna [earliest, latest]). Permite linearizable global usando hardware (GPS + atomic). Comum em datacenter Google; pra resto, HLC ou consensus pra ordering.
Single-leader: 1 primary aceita writes, replicas seguem. Postgres, MySQL, MongoDB.
Multi-leader: múltiplos nodes aceitam writes; mergiam. Conflict resolution problemático. Casos: multi-region active-active, offline-capable.
Leaderless: qualquer node aceita; client lê de N nodes, escreve em M. Quorum: R + W > N garante read sees most recent write. Cassandra, DynamoDB.
R + W > N: read quorum + write quorum > replicas total → reads see most recent writes (eventual converge depende de implementação).
N=3, W=2, R=2: comum, tolera 1 falha em cada operação.
Quorum em consensus: N/2 + 1 ("majority"). 5 nodes → 3 forma majority. Tolera até 2 falhas.
Problema: N nodes concordam num valor, tolerando minority de falhas.
Paxos (Lamport, 1989): hard, mas referência.
Raft (Ongaro, Stanford 2014): didaticamente acessível.
Raft é base de etcd, Consul, CockroachDB, MongoDB (com variações). Em apps você usa via essas tools, não implementa.
Fischer, Lynch, Paterson (1985): em rede async com 1 falha, não há algoritmo determinístico de consensus garantido a terminar.
Isso não bloqueia consensus, Paxos/Raft conseguem liveness sob suposições parciais (eventually synchronous network, leader stable). Mas explica por que consensus sempre tem riscos em casos extremos (pode entrar em loop de election).
Dois generais querem coordenar ataque mandando mensageiros. Cada mensagem pode perder. Não há protocolo finito que garanta acordo perfeito.
Implicação: at-most-once delivery + ack não basta pra acordo perfeito; sempre há janela onde sender não sabe se receiver tem mensagem.
Solução prática: idempotência. Receiver dedupa; sender pode retry sem efeito colateral.
Coordenador + N participants. Phase 1: coordenador pergunta "prepare". Cada participant escreve em log (durable) e responde. Phase 2: se todos OK, "commit"; senão "abort".
Falha: se coordenador morre depois de "prepare" e antes de "commit", participants ficam blocked.
3PC tenta resolver mas adiciona round trip e tem outras falhas.
Em prática: 2PC raramente é certo. Use sagas, outbox pattern (04-03).
Transação distribuída como sequência de local transactions, cada uma com compensation. Se step N falha, rollback executa compensations dos steps 1..N-1.
Exemplos:
Patterns:
Operação que pode ser repetida sem efeito adicional. Crucial em sistemas distribuídos com retry.
Em rede async, "exactly-once delivery" não existe. O que existe:
Kafka claims "exactly-once" via transações across producer + consumer + offset commit. Mesmo assim, é "exactly-once processing".
CRDTs são estruturas de dados onde merge é automatic e determinístico: independente de ordem ou duplicação de mensagens, todas as réplicas convergem pro mesmo state. Strong eventual consistency sem coordination.
Por que importam em 2026:
Famílias:
State-based (CvRDT): replicas trocam state inteiro; merge é função associativa, comutativa, idempotente (ACI).
Operation-based (CmRDT): replicas propagam operações. Exige causal delivery (geralmente via vector clock).
Delta-state CRDTs (modernas), estado mas só delta desde último sync. Mistura vantagens.
Sequence/Text CRDTs: gerenciam ordering em streams editáveis.
Yjs em particular dominou, biblioteca JS que serializa CRDT pra binary compact, integra com WebRTC/WebSocket pra sync, e tem bindings pra ProseMirror, Quill, Slate, etc. Linear e várias ferramentas SaaS usam.
Exemplo real Logística (notas colaborativas em pedido editadas por lojista + suporte simultaneamente):
// Server (Node + y-websocket)
import { setupWSConnection } from 'y-websocket/bin/utils';
import { WebSocketServer } from 'ws';
import { LeveldbPersistence } from 'y-leveldb';
const persistence = new LeveldbPersistence('./yjs-storage');
const wss = new WebSocketServer({ port: 1234 });
wss.on('connection', (ws, req) => {
const docName = new URL(req.url, 'http://x').pathname.slice(1); // ex: order-abc123
setupWSConnection(ws, req, { docName, gc: true });
// persistence carrega/salva doc automaticamente
});
// Client (lojista dashboard)
import * as Y from 'yjs';
import { WebsocketProvider } from 'y-websocket';
import { yCollab } from 'y-codemirror.next';
const ydoc = new Y.Doc();
const provider = new WebsocketProvider(
'wss://rt.logistica.com', `order-${orderId}`, ydoc,
{ params: { token: jwt } } // auth no upgrade (02-13)
);
const ynotes = ydoc.getText('notes'); // CRDT text type
// awareness = presença + cursor (não persiste, só p2p ephemeral)
provider.awareness.setLocalStateField('user', {
name: currentUser.name, color: '#3b82f6', role: 'lojista'
});
// Liga ao editor (CodeMirror, ProseMirror, plain textarea via y-textarea)
const view = new EditorView({
state: EditorState.create({
extensions: [yCollab(ynotes, provider.awareness)]
}),
parent: document.querySelector('#notes')
});
Resultado em produção: lojista edita "Cliente solicita troco de R$ 50" enquanto suporte adiciona "Tentou contato 14h, sem resposta" simultaneamente. Ambos veem updates em tempo real, sem conflict, sem locking, com cursor presence.
Pegadinhas em produção:
gc: true no provider; tombstones senão crescem indefinidamente. Mas GC pode quebrar undo distante; trade-off por feature.Authorization; passe via query param, valide no setupWSConnection antes de aceitar.y-protocols custom message types, não trivial.bytea por doc, ou Redis com TTL pra docs cold.Limitações reais:
Calm Theorem (relacionado): programa é monotônico (set-only-grows) → pode ser implementado sem coordination. CRDTs são corollary prático.
Quando usar CRDT vs alternatives:
Refs canônicas:
Em sistema distribuído, fast producer + slow consumer = queue cresce. Memory blowup ou drops.
Padrões:
Ao desenhar sistema distribuído, perguntar:
Wall-clock time (NTP) é mentira em sistemas distribuídos: clock skew de centenas de ms entre nodes, leap second drama, virtualização com VMs cujo clock pula minutos após migration. "Quem aconteceu primeiro?" não pode usar Date.now(). Logical clocks resolvem o problema com 3 técnicas progressivas: Lamport timestamps (ordering total mas perde causalidade), vector clocks (causalidade exata mas O(N) bytes), hybrid logical clocks (HLC, melhor dos dois, 2014). CockroachDB, Spanner-like systems e CRDTs todos usam variantes.
Foundation: o problema de "happened-before":
Lamport (1978) define: evento A → B se A precede B na mesma máquina, OU A é send de mensagem que B recebe, OU transitividade via cadeia. Sem ordering causal: cliente A escreve saldo = 100, cliente B escreve saldo = 50. Qual venceu? NTP timestamp pode dizer A vence quando na verdade B foi causado por A (leu 100, descontou 50). Resultado errado: 100 sobrescreve a operação derivada.
Lamport timestamp — total ordering, simples:
class LamportClock {
private counter = 0;
// Antes de evento local
now(): number {
return ++this.counter;
}
// Ao receber evento de outro node com timestamp T
receive(T: number): number {
this.counter = Math.max(this.counter, T) + 1;
return this.counter;
}
}
// Uso:
const clock = new LamportClock();
const event1 = clock.now(); // 1
sendMessage({ data: 'foo', ts: clock.now() }); // 2
// Outro node:
const ts = clock.receive(2); // max(0, 2) + 1 = 3
Garantia: se A → B causally, então lamport(A) < lamport(B). Limite: lamport(A) < lamport(B) NÃO implica A → B (eventos concorrentes podem ter ordem arbitrária). Usado em Cassandra (timestamps de write), Kafka (offsets dentro de partition), Riak.
Vector clocks — causalidade exata:
type VectorClock = Record<string, number>; // nodeId → counter
class VClock {
private vc: VectorClock;
constructor(private nodeId: string, initial: VectorClock = {}) {
this.vc = { ...initial, [nodeId]: initial[nodeId] ?? 0 };
}
tick(): VectorClock {
this.vc[this.nodeId]++;
return { ...this.vc };
}
receive(remote: VectorClock): VectorClock {
for (const [node, count] of Object.entries(remote)) {
this.vc[node] = Math.max(this.vc[node] ?? 0, count);
}
this.vc[this.nodeId]++;
return { ...this.vc };
}
// Compare two VCs
static compare(a: VectorClock, b: VectorClock): 'before' | 'after' | 'concurrent' | 'equal' {
const keys = new Set([...Object.keys(a), ...Object.keys(b)]);
let aLessOrEq = true, bLessOrEq = true;
for (const k of keys) {
const av = a[k] ?? 0, bv = b[k] ?? 0;
if (av > bv) bLessOrEq = false;
if (av < bv) aLessOrEq = false;
}
if (aLessOrEq && bLessOrEq) return 'equal';
if (aLessOrEq) return 'before';
if (bLessOrEq) return 'after';
return 'concurrent';
}
}
compare(a, b) === 'concurrent' = eventos genuinamente paralelos sem causalidade entre. Custo: O(N) bytes por timestamp; N = number of nodes que já tocaram o dado. Em sistema com 1000 clients, VC vira 8KB+ por write. Usado em Riak (sibling resolution), Voldemort, classic CRDTs.
Vector clock pruning — o trick em produção:
Estratégia: keep só top-K most recent nodes; TTL para nodes inativos.
function prune(vc: VectorClock, lastSeenAt: Record<string, number>, maxAgeMs = 7 * 86400_000) {
const now = Date.now();
const pruned: VectorClock = {};
for (const [node, count] of Object.entries(vc)) {
if (now - (lastSeenAt[node] ?? 0) < maxAgeMs) {
pruned[node] = count;
}
}
return pruned;
}
Trade-off: pruning agressivo causa false-concurrent (loss of causality info); conservador cresce indefinidamente.
Hybrid Logical Clocks (HLC) — best of both worlds:
Kulkarni & Demirbas, 2014. Combina wall-clock + logical counter em 64-bit.
type HLC = { wallTime: number; logical: number };
class HybridLogicalClock {
private last: HLC = { wallTime: 0, logical: 0 };
now(): HLC {
const wall = Date.now();
if (wall > this.last.wallTime) {
this.last = { wallTime: wall, logical: 0 };
} else {
this.last = { ...this.last, logical: this.last.logical + 1 };
}
return { ...this.last };
}
receive(remote: HLC): HLC {
const wall = Date.now();
const newWall = Math.max(wall, this.last.wallTime, remote.wallTime);
let logical: number;
if (newWall === this.last.wallTime && newWall === remote.wallTime) {
logical = Math.max(this.last.logical, remote.logical) + 1;
} else if (newWall === this.last.wallTime) {
logical = this.last.logical + 1;
} else if (newWall === remote.wallTime) {
logical = remote.logical + 1;
} else {
logical = 0;
}
this.last = { wallTime: newWall, logical };
return { ...this.last };
}
static compare(a: HLC, b: HLC): -1 | 0 | 1 {
if (a.wallTime !== b.wallTime) return a.wallTime < b.wallTime ? -1 : 1;
if (a.logical !== b.logical) return a.logical < b.logical ? -1 : 1;
return 0;
}
}
Garantia: monotônico mesmo com clock skew; close to wall-clock (good pra debugging); 64-bit fits. Limite: não detecta concurrency (Lamport-like, não vetor). Pra concurrency precisa MVCC + version vectors. Usado em CockroachDB (default), MongoDB (clusterTime), YugabyteDB.
Logística — escolha por uso:
| Cenário | Clock |
|---|---|
| Order status updates (LWW); ordering total OK | HLC ou Lamport |
| Multi-master replication com sibling resolution | Vector clock |
| Audit log; precisa wall-clock próximo (humans readable) | HLC |
| Operational counter sob race | Lamport sufficient |
| CRDT (Yjs, Automerge) com causality | Vector clock interno |
Production gotchas:
chronyd ou alike monitoring.last + 1.Code: integração com message broker:
// Cada message envia HLC
const hlc = new HybridLogicalClock();
producer.send({
topic: 'orders',
messages: [{
value: JSON.stringify(order),
headers: { hlc: JSON.stringify(hlc.now()) },
}],
});
consumer.run({
eachMessage: async ({ message }) => {
const remoteHlc: HLC = JSON.parse(message.headers!.hlc!.toString());
const newHlc = hlc.receive(remoteHlc);
// Process com newHlc atribuído ao evento downstream
},
});
Anti-patterns observados:
Date.now() pra ordering em distributed system: clock skew NTP entre nodes destroi correctness.now() chamado N vezes em mesmo handler: micro-incrementos sem semantic; gera "timestamps" sequenciais sem causality real.Cruza com 04-01 §2.16 (idempotência precisa ordering), 04-01 §2.18 (CRDT usa vector internally), 04-02 §2.18 (idempotent consumer + HLC pra ordering), 04-13 §2.16 (exactly-once delivery semântica), 02-09 §2.13 (Postgres logical replication usa LSN, conceito relacionado).
§2.11 estabelece Raft/Paxos no whiteboard: leader election, log replication, safety. Produção é outra coisa. Raft em etcd 3.5+ rodando control plane do Kubernetes não é o mesmo Raft do paper Ongaro 2014 — tem prevote, learner role, joint consensus pra membership change, snapshot incremental, batched AppendEntries. Falhar em entender o gap entre teoria e implementação leva a clusters que perdem quorum durante upgrade rolling, leader election flapping em rede cross-region, ou pior: split-brain mascarado por timeouts mal configurados. §2.22 é o deep operacional: como Raft vive em etcd/CockroachDB/Consul/TiKV, por que Multi-Paxos sobrevive em Spanner/Chubby, quando Byzantine variants importam, e qual escolher pra qual problema.
Raft mechanics deep — state machine real.
timeout, start election
┌─────────┐ ─────────────────────────► ┌──────────┐
│Follower │ │Candidate │
└─────────┘ ◄───────────────────────── └──────────┘
▲ receives AppendEntries from │
│ leader with term >= currentTerm │ wins majority
│ ▼
│ discovers higher term ┌──────────┐
└────────────────────────────────── │ Leader │
└──────────┘
Cada node mantém currentTerm (monotonic), votedFor (per term), log[] (replicated entries). Eleição: follower sem heartbeat por electionTimeout (típico 150-300ms randomizado pra evitar split votes simultâneos) vira candidate, incrementa term, vota em si, manda RequestVote pro cluster. Maioria → leader. Leader manda AppendEntries periódico (heartbeat ~50ms) pra suprimir nova eleição.
Prevote (etcd 3.5+, Raft thesis §9.6) — antes de incrementar term de verdade, candidate manda RequestVote especulativo. Se não ganhar maioria, NÃO incrementa term. Evita disruption: node particionado que volta com term inflacionado força leader saudável a step down. Sem prevote: cluster em rede flaky sofre election storm.
Quorum math, 2026 reality:
| Cluster size | Quorum | Failures tolerated | Custo write |
|---|---|---|---|
| 3 | 2 | 1 | 2 fsync round-trips |
| 5 | 3 | 2 | 3 fsync round-trips |
| 7 | 4 | 3 | 4 fsync round-trips (raro fora de regulado) |
Even number é anti-pattern: 4 nodes tolera 1 failure (igual a 3) e custa 1 write a mais. Sempre odd.
Latency napkin math (cross-AZ, mesma region, 2026):
Production systems — quem usa o quê.
# etcd 3.5+ — Kubernetes control plane backend
# Cluster típico: 3 ou 5 nodes, single region, dedicated SSD
etcdctl --endpoints=https://etcd-0:2379,https://etcd-1:2379,https://etcd-2:2379 \
endpoint status --write-out=table
# Mostra: leader, raft term, raft index, db size
# Inspeção de health do Raft
etcdctl endpoint health --cluster
etcdctl member list # Voters + learners
# Adicionar learner (não conta pra quorum, faz catch-up)
etcdctl member add etcd-3 --peer-urls=https://etcd-3:2380 --learner
# Promover learner pra voter SOMENTE após log catch-up completo
etcdctl member promote <member-id>
-- CockroachDB 24.x — Raft per range (não per cluster)
-- Cada range (~512MB) tem seu próprio Raft group de 3 ou 5 replicas
SHOW RANGES FROM TABLE orders;
-- range_id | start_key | end_key | replicas | lease_holder | ...
-- Inspecionar Raft status de range específico
SELECT * FROM crdb_internal.ranges WHERE range_id = 42;
-- Zone config: força replicação cross-region
ALTER TABLE orders CONFIGURE ZONE USING
num_replicas = 5,
constraints = '{"+region=us-east": 2, "+region=us-west": 2, "+region=eu-west": 1}',
lease_preferences = '[[+region=us-east]]';
# Consul 1.18+ — service registry + KV, Raft pra consistency
# server count: 3 ou 5; clients são gossip-only (não participam Raft)
consul operator raft list-peers
# Node ID Address State Voter RaftProtocol
# server1 ... 10.0.1.1:8300 leader true 3
# server2 ... 10.0.1.2:8300 follower true 3
# server3 ... 10.0.1.3:8300 follower true 3
# Autopilot: cleanup de dead servers automático
consul operator autopilot get-config
Mapping pragmático:
Multi-Paxos legado — onde Raft não chegou.
Spanner (Google), Chubby (Google), MegaStore — todos Multi-Paxos. Não migraram pra Raft porque infra interna foi escrita pre-Raft (paper Ongaro 2014, Spanner 2012, Multi-Paxos Lamport 2001). Multi-Paxos é mais complexo de provar correto mas roda igual em produção. Phases:
Raft = Multi-Paxos com restrições (log contíguo, leader-only writes). Trade-off: Raft é mais didático e implementável; Paxos é mais flexível (Generalized Paxos, EPaxos pra leaderless). EPaxos (CMU 2013) tem traction limitado: TiKV experimentou, abandonou; CockroachDB descartou. Leaderless soa bom no paper, em produção introduz dependency tracking complexo.
Byzantine variants — quando importa.
Raft/Paxos assumem crash failure (node morre ou silencia). Não toleram byzantine failure (node mente, manda dados corrompidos, age maliciosamente). Em datacenter próprio confiança alta + checksums TCP/aplicação = crash model basta.
Quando byzantine importa:
Custo: PBFT precisa 3f+1 nodes pra tolerar f byzantine failures (vs 2f+1 do crash model). 7 nodes pra tolerar 2 maliciosos. Comunicação O(n²) por round → não escala além de ~20 nodes sem otimização (HotStuff reduz pra O(n) com pipelining).
Operational reality — onde acordam às 3am.
Stack Logística aplicada.
coordination.k8s.io/v1, ou Consul session com TTL. NÃO escrever lock primitivo do zero.10 anti-patterns.
match_index antes de promover.Cruza com: 04-01 §2.11 (Raft/Paxos foundation no whiteboard, base teórica), 04-01 §2.5 (CAP — Raft é CP, perde availability em partição minoritária), 04-01 §2.10 (quorum math + sloppy quorum em Dynamo-style; Raft é strict quorum), 03-03 (Kubernetes usa etcd como control plane, K8s Lease pra leader election), 02-12 (MongoDB replica set election é Raft-like com priorities + arbiters), 04-08 (Consul como service mesh control plane, Raft pro registry), 03-09 (resilience patterns aplicados a coordinators — circuit breaker em client de etcd, retry com jitter), 04-04 §2.25 (failover patterns + leader election cost), 04-13 (transactional outbox em system com Raft backend pra durability).
Você precisa, sem consultar:
Construir uma simulação de sistema distribuído explorando os conceitos.
PUT, GET, DELETE.Threshold de Maestria
Acerte todas as 5 pra marcar o módulo como concluído. Sem pressa, sem timer. Tudo fica salvo no teu navegador.
Q1Qual é a diferença essencial entre o teorema CAP e PACELC?
Q2Por que vector clocks capturam causalidade que Lamport timestamps perdem?
Q3Em um cluster Raft de 5 nós, quantas falhas simultâneas o sistema tolera?
Q4Por que 'exactly-once delivery' é considerado mito em sistemas distribuídos?
Q5Em quórum com R+W>N, qual é o efeito quando R+W=N exatamente?
Destrava
04-01 é prereq dos seguintes módulos: