Particionamento e NewSQL

Três anos depois do lançamento, a BoxOffice vende em 30 países. As tabelas orders e tickets crescem centenas de milhões de linhas por ano, o disco do primário é medido em terabytes e a taxa de escrita durante as grandes aberturas de vendas chega perto do que uma máquina consegue absorver. As réplicas não ajudam mais: elas escalam leituras, e toda réplica continua tendo de aplicar todas as escritas. O próximo degrau da escada de escalabilidade é dividir os próprios dados entre máquinas.

O particionamento — também chamado de sharding — divide um conjunto de dados de forma que cada registro pertença a exatamente uma partição (shard), e partições diferentes vivam em nós diferentes. Cada nó cuida apenas da sua parte das leituras, das escritas e do armazenamento. Os nomes variam conforme o produto — shard no MongoDB e no Elasticsearch, region no HBase, tablet no Bigtable, range no CockroachDB, vnode no Cassandra —, mas as perguntas são sempre as mesmas: por qual chave, como distribuir por igual, como encontrar e como mover quando os nós mudam¹.

flowchart LR
    R["roteador<br/>partição = f(chave)"] -->|"cliente 7"| S1[("shard 1<br/>+ réplicas")]
    R -->|"cliente 1042"| S2[("shard 2<br/>+ réplicas")]
    R -->|"cliente 98311"| S3[("shard 3<br/>+ réplicas")]

O particionamento normalmente é combinado com replicação: cada partição tem seu próprio líder e seus seguidores, então um nó pode ser líder de algumas partições e seguidor de outras.

Particionamento por intervalo de chaves

Atribua a cada partição um intervalo contínuo de chaves, como os volumes de uma enciclopédia: A–F, G–M, N–S, T–Z. Dentro de uma partição, as chaves ficam ordenadas.

• Consultas por intervalo são baratas: "pedidos de 2027-03-01 a 2027-03-07" lê uma ou duas partições.
• Os limites se adaptam aos dados: quando um intervalo fica grande demais, ele é dividido em dois (tablets do Bigtable, regions do HBase e ranges do CockroachDB e do TiDB fazem isso automaticamente).
• Perigo — chaves sequenciais. Se a chave é um timestamp ou um id autoincremental, todas as novas escritas vão para o último intervalo. O clickstream de hoje cai num único nó enquanto os outros ficam ociosos. Corrija prefixando a chave com outra coisa: (event_id, timestamp) em vez de timestamp.

Particionamento por hash

Aplique uma função de hash à chave e use o hash para escolher a partição. Um bom hash espalha uniformemente até chaves sequenciais.

• Carga equilibrada para escritas e leituras pontuais.
• Consultas por intervalo se espalham: chaves vizinhas caem em partições sem relação entre si, então "pedidos desta semana" precisa consultar todas as partições.
• Chaves compostas recuperam alguma localidade: o Cassandra faz hash apenas da partition key e mantém as linhas ordenadas pelas clustering columns dentro dela — PRIMARY KEY ((event_id), scanned_at) dá uma distribuição equilibrada entre eventos e intervalos de tempo baratos dentro de um evento.

A implementação ingênua, partition = hash(key) mod N, tem uma falha fatal: quando N muda, quase todas as chaves mudam de partição.

Hashing consistente

O hashing consistente (consistent hashing)² coloca nós e chaves no mesmo espaço circular de hash (um anel, por exemplo de 0 a 2^64 − 1). Cada chave pertence ao primeiro nó encontrado andando no sentido horário a partir da posição da chave.

Quando um nó entra, ele assume apenas as chaves entre ele e seu antecessor; quando um nó sai, só as chaves dele vão para o sucessor. Em média, 1/N das chaves se move, o mínimo possível — contra quase todas com mod N.

Com uma única posição por nó, os arcos ficam desiguais e um nó pode ficar com muito mais do que sua parte. Os nós virtuais (vnodes) resolvem isso: cada nó físico ocupa muitas posições no anel (100–256 é comum), então sua fatia total se equilibra na média, e um nó com o dobro da capacidade pode simplesmente ficar com o dobro de vnodes.

A simulação abaixo faz hash de 20.000 chaves com MD5. À esquerda, a porcentagem de chaves que mudam de nó quando o cluster cresce de N − 1 para N nós; à direita, quão desbalanceados ficam 10 nós (nó mais carregado ÷ média) conforme cresce o número de nós virtuais:

Ir de 9 para 10 nós com mod N move cerca de 90% das chaves — num cache distribuído, é o mesmo que despejar o cache inteiro sobre o banco de uma vez. Com hashing consistente, cerca de 10% se move. E com uma única posição por nó, o nó mais carregado leva várias vezes a sua parte justa; algumas centenas de vnodes o aproximam de 1.

O hashing consistente é usado pelo Dynamo e pelo DynamoDB, Cassandra e ScyllaDB, Riak, sharding do Memcached no lado do cliente (o algoritmo ketama), upstreams hash … consistent do Nginx e muitos balanceadores de carga. Vale reconhecer dois parentes: o rendezvous hashing (highest random weight: cada chave escolhe o nó com o maior hash(key, node))³ e o jump consistent hash (sem anel, balanceamento quase perfeito, mas nós só podem ser adicionados ou removidos no final)⁴.

Número fixo de partições

Uma alternativa mais simples que muitos sistemas usam: crie de antemão muito mais partições do que nós e atribua partições inteiras aos nós. Adicionar um nó significa mover para ele algumas partições inteiras; o mapeamento chave → partição nunca muda.

• Redis Cluster: 16.384 hash slots, slot = CRC16(key) mod 16384; os slots são movidos entre os nós (veja Redis).
• Elasticsearch / OpenSearch: o número de shards primários é fixado na criação do índice.
• Kafka: as partições de um tópico (veja Kafka).

O porém: escolha bem a quantidade. Partições de menos limitam até onde você consegue escalar; partições demais acrescentam overhead por partição.

Escolhendo a chave de partição

A chave de partição é a decisão de maior consequência e a menos reversível de um design com sharding. Uma boa chave tem:

1. Alta cardinalidade — muitos valores distintos, para que os dados possam ser cortados em muitos pedaços.
2. Distribuição equilibrada tanto dos dados quanto do tráfego entre os valores.
3. Localidade das consultas — as consultas mais frequentes e todas as transações tocam uma partição.

Partições quentes

Mesmo com um hash perfeito, o tráfego raramente é uniforme. Uma partição quente (hot partition, ou chave quente) recebe muito mais carga do que as outras: a celebridade cujos posts todo mundo lê, o produto em promoção na Black Friday, o show no estádio às 10:00. O hash não consegue espalhar uma carga que mira uma única chave.

Experimente. O cenário sharding espalha uma tabela NoSQL por várias partições. Execute-o com tráfego uniforme e anote a carga por partição; depois deixe a distribuição de chaves desequilibrada (uma chave quente) e veja uma única partição saturar e sua latência subir enquanto as outras ficam ociosas — adicionar partições não ajuda.

Mitigações, da menos à mais invasiva:

Índices secundários em dados particionados

Particionar por customer_id deixa "pedidos do cliente 7" rápido. E "pedidos do evento 42"? É preciso um índice secundário, e em dados particionados ele vem em dois sabores:

flowchart TB
    subgraph local ["Índice local (particionado por documento)"]
        Q1["consulta: event_id = 42"] --> P1["shard 1<br/>+ seu próprio índice"]
        Q1 --> P2["shard 2<br/>+ seu próprio índice"]
        Q1 --> P3["shard 3<br/>+ seu próprio índice"]
    end
    subgraph global ["Índice global (particionado por termo)"]
        Q2["consulta: event_id = 42"] --> IX["partição do índice<br/>para event_id 42"]
        IX --> D1["shard 1"]
        IX --> D3["shard 3"]
    end

O scatter/gather é mais perigoso do que parece: uma consulta a 20 shards é tão lenta quanto o mais lento dos 20. A chance de os 20 responderem dentro do próprio p99 é 0,99²⁰ ≈ 82 %, então o p99 de um shard é só cerca do p82 da consulta — 18 % das consultas são mais lentas. Para o p99 da consulta ficar abaixo de uma meta, cada shard precisa cumpri-la no seu p99,95 (0,99^(1/20) ≈ 0,9995) (veja Percentis).

Rebalanceamento e resharding

Nós são adicionados, removidos e falham; os dados crescem de forma desigual. O rebalanceamento move partições para manter a carga equilibrada, de preferência enquanto o banco continua atendendo tráfego e movendo apenas os dados que precisam se mover.

• Prefira esquemas em que o mapeamento chave → partição é estável (partições fixas, hashing consistente, divisão de intervalos), para que o rebalanceamento mova partições, não chaves individuais.
• O rebalanceamento disputa rede e disco com o tráfego real; limite sua velocidade e evite rebalanceamento totalmente automático disparado por um nó que está apenas lento (isso pode virar uma cascata).
• Trocar a chave de partição (resharding) é um projeto de migração. A receita comum é online:

flowchart LR
    A["1. crie os novos shards<br/>com a nova chave"] --> B["2. escrita dupla:<br/>antigo + novo"]
    B --> C["3. backfill do histórico<br/>(cópia + CDC para alcançar)"]
    C --> D["4. verifique:<br/>compare as leituras"]
    D --> E["5. mude as leituras<br/>para os novos shards"]
    E --> F["6. pare as escritas antigas,<br/>apague os shards antigos"]

Camadas de sharding automatizam boa parte disso para bancos relacionais existentes: o Vitess para MySQL (criado no YouTube) e o Citus para PostgreSQL cuidam de roteamento, resharding e consultas distribuídas.

Roteamento de requisições

Algum componente precisa saber qual nó guarda qual partição:

O próprio mapa é um metadado pequeno e crítico — guardado num armazenamento de consenso como etcd ou ZooKeeper, ou propagado por gossip entre os nós (veja Consenso).

Consultas e transações entre partições

O particionamento funciona lindamente até uma operação precisar de várias partições ao mesmo tempo:

• Joins e agregações entre shards viram scatter/gather, feitos por um coordenador — mais lentos e limitados pelo shard mais lento.
• Transações entre shards precisam de um protocolo de coordenação — commit em duas fases ou commit baseado em consenso — com idas e voltas extras e novos modos de falha (veja Transações).
• Constraints de unicidade em colunas que não são a chave (e-mail único quando o sharding é por customer_id) precisam de um índice global ou de uma tabela de consulta separada.

Então o objetivo do design é: escolher as chaves para que o caminho quente seja de uma única partição e mandar o resto para sistemas feitos para isso (um data warehouse para analytics, um índice de busca para consultas transversais).

NewSQL: bancos SQL distribuídos

E se você quiser particionamento e transações SQL entre partições, sem escrever uma camada de sharding? Os bancos NewSQL, ou SQL distribuído, fazem isso⁵:

• O Google Spanner⁶ divide as tabelas em intervalos, replica cada intervalo com Paxos entre zonas ou regiões e executa transações distribuídas com commit em duas fases sobre esses grupos. Sua API TrueTime expõe a incerteza do relógio (alguns milissegundos, limitada por GPS e relógios atômicos); um commit espera essa incerteza passar, o que dá consistência externa (transações linearizáveis) no mundo todo.
• O CockroachDB⁷ (protocolo de rede do PostgreSQL) divide os dados em intervalos de algumas centenas de megabytes, replica cada um com Raft e usa relógios lógicos híbridos em vez de hardware especial; o isolamento serializable é o padrão.
• O YugabyteDB (compatível com PostgreSQL) e o TiDB (compatível com MySQL) seguem designs parecidos; os provedores de nuvem também oferecem SQL distribuído gerenciado e serverless.

sequenceDiagram
    participant C as Cliente
    participant G as Nó gateway
    participant R1 as Líder do intervalo 1 (orders)
    participant R2 as Líder do intervalo 2 (tickets)
    C->>G: BEGIN, INSERT order, INSERT tickets, COMMIT
    G->>R1: intenção de escrita (replicada por Raft)
    G->>R2: intenção de escrita (replicada por Raft)
    R1-->>G: ok (maioria confirmou)
    R2-->>G: ok (maioria confirmou)
    G->>G: registro de commit (atômico)
    G-->>C: COMMIT ok

SQL distribuído não sai de graça: toda escrita é replicada por consenso, então a latência é maior do que num único nó, e uma transação que abrange regiões paga idas e voltas entre regiões. É a resposta certa quando você precisa ao mesmo tempo de transações SQL e de mais capacidade de escrita ou resiliência geográfica do que um primário consegue dar — não como padrão.

Como se conecta

flowchart LR
    RANGE["por faixa de chave"] --> KEY["escolher a chave de partição<br/>cardinalidade, distribuição, localidade"]
    HASH["por hash"] --> KEY
    CH["hashing consistente<br/>nós virtuais"] --> HASH
    KEY --> HOT["partições quentes<br/>o evento em venda"]
    HOT --> MIT["cache, chave mais fina, salting,<br/>fila → Caching, Mensageria"]
    KEY --> SEC["índices secundários<br/>locais vs globais"]
    KEY --> RESH["rebalanceamento,<br/>roteamento de requisições"]
    KEY --> XP["consultas entre partições<br/>relatórios → warehouse"]
    XP --> NEW["NewSQL: Spanner, CockroachDB<br/>consenso por faixa → Distribuídos"]
    CH -.-> LB["o mesmo anel nos balanceadores<br/>→ Borda"]

Componentes da paleta: nosql (Cassandra, DynamoDB, MongoDB particionam por chave) · sql (PostgreSQL fragmentado, ou SQL distribuído) · cache (hash slots do Redis Cluster; serve a página do evento quente no lugar do shard) · search (shards do Elasticsearch) · kafka (partições por chave) · queue (a sala de espera na frente de uma partição quente) · lb (hashing consistente para afinidade) · dwh (onde ficam os relatórios scatter-gather). Cenários: sharding, flash-sale. Continua em: Armazenamentos Especializados, Distribuídos — consenso, Borda — balanceamento de carga, Caching — Redis Cluster, Estudo de caso: cache distribuído.