CS Fundamentals Trainer · Guias

Replicação, particionamento e sharding

O que cada uma das três ferramentas escala, lag de replicação e read-your-writes, o que um failover assíncrono perde, partition pruning, escolha da shard key, shards quentes e resharding, executados no PostgreSQL e em Python.

27 min de leitura

Um servidor de banco de dados tem limites: só consegue atender tantas leituras, armazenar tantos dados e sobreviver apenas enquanto a máquina sobreviver. Três técnicas ultrapassam esses limites, e são fáceis de confundir porque todas "dividem ou copiam dados". A replicação mantém cópias dos mesmos dados em vários servidores, para atender mais leituras e sobreviver a uma falha. O particionamento divide uma tabela grande em pedaços dentro de um banco de dados. O sharding divide os dados entre vários servidores de banco de dados independentes, de modo que cada um guarda apenas uma parte. Cada uma resolve um problema particular e traz um novo problema particular: leituras obsoletas e escritas perdidas na replicação, consultas que ignoram a chave de partição no particionamento, shards quentes e trabalho entre shards no sharding. Executei o comportamento de replicação e de particionamento no PostgreSQL 16 (um primário com um standby de streaming em uma máquina) e simulei os efeitos do sharding em Python. Os scripts estão no apêndice; cada número é uma execução em uma máquina pequena, então confie no comportamento e não nos valores exatos.

1. Três ferramentas para três problemas

ReplicaçãoParticionamentoSharding
O que fazcopia os mesmos dados para outros servidoresdivide uma tabela em partes em um servidordivide os dados entre servidores
Ajuda commais capacidade de leitura, disponibilidade, uma cópia para fazer failovertabelas muito grandes, apagar dados antigos, índices menorescapacidade de escrita e dados maiores que uma máquina (dentro dos limites da seção 4)
Não ajuda comcapacidade de escrita (cada cópia repete cada escrita)um servidor sem CPU ou discoconsultas que precisam de todos os dados
Novo problemaas réplicas ficam atrasadas; um failover pode perder escritasuma consulta sem a chave de partição toca todas as partesshards quentes, consultas e transações entre shards, resharding

Recorra a elas nesta ordem, da mais barata à mais cara: corrija as consultas lentas e adicione os índices certos, adicione um cache, compre um servidor maior, adicione réplicas de leitura, particione as tabelas grandes e faça sharding por último. Cada passo acrescenta complexidade permanente.

2. Replicação

Na replicação líder-seguidor (primário-standby), um servidor, o líder, aceita todas as escritas e envia um fluxo de suas mudanças (no PostgreSQL, o write-ahead log) aos seguidores, que as aplicam na mesma ordem e podem atender leituras.

Diagram: Leader-follower replication

Replicação assíncrona significa leituras obsoletas

Com a replicação assíncrona, o líder diz ao cliente "confirmado" assim que salvou a escrita por conta própria, e a envia aos seguidores depois. Um seguidor está portanto sempre a alguma distância atrás, o que se chama lag de replicação. Normalmente são milissegundos. Quando um seguidor está ocupado, distante ou se atualizando, pode ser segundos ou minutos, e então um usuário pode escrever algo e não vê-lo.

Para tornar isso repetível, configurei o standby para aplicar as mudanças com dois segundos de atraso (recovery_min_apply_delay = '2s'), escrevi um pedido no primário e li do standby imediatamente: 0 linhas. A escrita tinha sido confirmada; o seguidor ainda não a tinha aplicado. A anomalia se chama violação da consistência read-your-writes. Parentes dela: monotonic reads (um usuário atualiza a página e vê um estado mais antigo que antes porque a segunda leitura caiu em um seguidor mais atrasado) e consistent prefix (ver uma resposta antes da pergunta).

Formas de lidar com isso, da mais simples:

A replicação síncrona compra segurança com latência

Com a replicação síncrona, o líder espera por um seguidor antes de confirmar o commit. O PostgreSQL deixa você escolher até onde o seguidor precisa chegar:

synchronous_commitO commit espera atéTempo por commit (500 inserts, mesma máquina)
localo líder ter gravado o seu próprio log em disco0,35 ms
remote_writeo seguidor ter recebido e escrito o log0,46 ms
ono seguidor tê-lo gravado em disco0,53 ms
remote_applyo seguidor tê-lo aplicado, de modo que as leituras lá o veem0,65 ms

Em uma máquina sem rede o custo é pequeno e mesmo assim cresce com cada garantia mais forte (+30%, +50%, +84% sobre local); entre data centers cada commit pagaria também a ida e volta, que costuma ser de milissegundos. remote_apply é a configuração que elimina leituras obsoletas nesse seguidor.

O teste de failover: o que a replicação assíncrona perde

Cortei a conexão do standby com o primário (o standby continuou rodando, mas não conseguia mais receber mudanças) e deixei o primário confirmar mais dez pedidos. Os dez clientes foram informados de "confirmado". Depois derrubei o primário e promovi o standby a novo líder. Ele tinha 5 linhas, não 15: os dez pedidos confirmados existiam apenas na máquina que tinha morrido. Esse é o risco da replicação assíncrona: os dados ainda não enviados quando o líder falha são perdidos (ou precisam ser reconciliados à mão quando o antigo líder volta).

A alternativa síncrona custa disponibilidade. Com synchronous_standby_names = '*' e o único standby parado, as leituras no primário ainda funcionaram, mas uma escrita travou: meu INSERT ainda esperava depois de cinco segundos (eu mesmo o interrompi). O líder prefere esperar a confirmar uma escrita que existe em um só lugar. É a troca entre consistência e disponibilidade do teorema CAP em uma única configuração. O compromisso usual é um quórum: esperar por qualquer um entre vários seguidores (ANY 1 (a, b, c) no PostgreSQL), de modo que um único seguidor lento ou com falha não pare as escritas, mas uma escrita confirmada ainda vive em pelo menos duas máquinas.

O que um standby síncrono garante e o que não garante

Esperar por um seguidor melhora a durabilidade ou a visibilidade, mas apenas contra as falhas que você supôs. Leia cada configuração com o seu modelo de falhas:

Então enuncie o objetivo com precisão: "nenhuma escrita confirmada é perdida se qualquer uma máquina falhar", ou "qualquer uma zona de disponibilidade", e confira se a configuração, o procedimento de promoção e o monitoramento sustentam exatamente essa afirmação.

Replication slots e lag operacional

Um replication slot faz o primário guardar todo segmento de log (WAL) que um seguidor ainda não recebeu, para que um seguidor que fica para trás ou se desconecta possa se atualizar. O preço é disco. Criei um slot sem consumidor e escrevi cerca de 100 MB de dados por rodada: o diretório pg_wal do primário cresceu de 33 MB para 337 MB em três rodadas, e o slot informava 322 MB retidos. Um slot esquecido ou parado continua crescendo até o disco encher, e um disco cheio para o primário. Depois que o slot foi removido e os checkpoints rodaram, o pg_wal começou a encolher (241 MB depois de dois checkpoints, já que os segmentos antigos são reciclados aos poucos).

Opere isso de propósito: monitore pg_replication_slots (restart_lsn, wal_status) e as colunas de lag de pg_stat_replication (write_lag, flush_lag, replay_lag), alerte sobre o WAL retido e sobre o lag, remova os slots que ninguém usa e limite a retenção com max_slot_wal_keep_size, para que um consumidor parado seja cortado antes de derrubar o primário (ao custo de esse seguidor precisar ser reconstruído). Consultas longas em um hot standby também podem entrar em conflito com a reprodução e ou são canceladas ou a atrasam (max_standby_streaming_delay), e o hot_standby_feedback evita os cancelamentos fazendo o primário manter versões antigas de linhas, o que o incha.

Outras coisas a saber

3. Particionamento

O particionamento divide uma tabela lógica em partes físicas por uma chave de partição, dentro de um único banco de dados. As aplicações continuam consultando events; o banco de dados encaminha cada linha à parte certa.

Criei uma tabela events com 1 200 000 linhas, particionada por mês em created_at:

ConsultaPartições varridas
WHERE created_at em março1 de 12 (o planejador ignora o resto: partition pruning)
WHERE user_id = 42 (não é a chave)12 de 12

A primeira consulta se beneficia do particionamento; a segunda paga por ele, porque o banco de dados não pode saber qual partição guarda o usuário 42, então confere as doze (cada uma com o seu índice). O planejamento também é trabalho por partição: a consulta que precisou considerar as doze levou cerca de 1,2 ms para planejar, contra cerca de 0,5 ms para a podada. Então escolha a chave pela qual a maioria das consultas filtra e mantenha o número de partições na casa das dezenas ou de poucas centenas, não de dezenas de milhares.

O uso mais forte é remover dados antigos. Apagar o mês mais antigo (cerca de 100 000 linhas) de uma cópia não particionada com DELETE levou 85,7 ms e deixou linhas mortas para o vacuum limpar. Na tabela particionada, DETACH PARTITION levou 2,6 ms e DROP TABLE 7,1 ms: o mês inteiro desapareceu como um arquivo, sem linhas mortas. Em tamanhos maiores a diferença é muito maior, e a retenção vira um job agendado que cria a partição do mês seguinte e remove a mais antiga.

Limites a lembrar: no PostgreSQL, uma chave primária ou restrição de unicidade em uma tabela particionada precisa incluir a chave de partição, então "único em todo o tempo" exige outro projeto; e o particionamento não faz nada por um servidor cuja CPU ou disco está cheio, porque tudo ainda está em uma máquina. É o passo certo antes do sharding para uma grande tabela de séries temporais ou de logs.

4. Sharding

O sharding (particionamento horizontal entre servidores) coloca cada linha em um de vários servidores de banco de dados independentes, os shards, escolhido pela shard key. Cada shard guarda uma fração dos dados e trata uma fração das escritas, o que faz dele a única das três ferramentas capaz de crescer a capacidade de escrita e o tamanho total além de uma única máquina. Ele não faz isso sem limite: a capacidade agregada é limitada pela sobrecarga de coordenação, por chaves quentes que um shard precisa absorver, pela largura de banda de rede entre a aplicação e os shards, pelo tamanho da camada de metadados e de roteamento e pelo custo de toda operação que atravessa shards (descrito abaixo). A aplicação, um roteador ou uma camada de proxy precisa saber qual shard é dono de uma linha.

Diagram: Sharding by key

Escolher a shard key é o projeto inteiro

Uma boa shard key tem alta cardinalidade, espalha a carga uniformemente e está presente na maioria das consultas, de modo que a maioria das requisições vá a um shard. Escolhas típicas: o id do usuário, o id do tenant (veja projetando um sistema multi-tenant) ou o id do pedido. Três formas comuns de mapear uma chave a um shard:

Problemas que aparecem

Adicionar um shard move dados. Com hash(key) mod N, mudar N muda a casa da maioria das chaves. Na simulação (uma ilustração do movimento de chaves, não uma previsão), ir de 4 para 5 shards moveu 79,7% de 100 000 chaves, e de 10 para 11 shards 91,1%. Um anel de consistent hashing moveu apenas 20,2% e 8,1%, perto do ideal 1/(N+1) (veja consistent hashing). O rebalanceamento real também depende de quantos dados precisam ser copiados, de onde caem os nós virtuais, de shards de capacidades desiguais e de como a cópia é mantida consistente enquanto as escritas continuam. Ele é feito em etapas: copiar os dados para o novo shard, manter os dois sincronizados (escritas duplas ou captura de mudanças), verificar, trocar as leituras e depois apagar a cópia antiga.

A carga não é tão uniforme quanto o espaço de chaves. Mesmo com um hash perfeito, a popularidade é assimétrica. Com 1 000 000 de requisições sobre 100 000 chaves e uma popularidade do tipo Zipf (poucas chaves são muito populares), o mais ocupado de oito shards recebeu 1,89 vez a carga média, e a chave mais quente sozinha recebeu 13,5% de todas as requisições, todas em um shard. O hash não consegue dividir uma única chave. Mitigações: pôr a chave quente em cache, dividi-la em subchaves (celebrity#1 a celebrity#16) com uma junção na leitura, ou isolá-la em um shard próprio.

Consultas sem a shard key precisam perguntar a todos os shards (scatter-gather). A latência da resposta combinada é a do shard mais lento, então a cauda cresce com o número de shards: se cada shard é lento 1% das vezes, a chance de pelo menos um deles ser lento é 1,0% com um shard, 7,7% com oito, 27,5% com trinta e dois e 72,4% com 128. A mesma aritmética de observabilidade. Projete o modelo de dados de modo que as consultas comuns carreguem a shard key e use um índice de busca separado ou uma cópia replicada para as demais.

Joins, transações e restrições de unicidade atravessam shards. Um join entre linhas em shards diferentes precisa ser feito na aplicação ou movido para outro lugar. Uma transação que toca dois shards precisa de two-phase commit ou de uma saga (transações distribuídas). Uma restrição de unicidade (um endereço de e-mail) só é aplicada dentro de um shard. Ids de auto-incremento globais precisam de um esquema (faixas entregues a cada shard, ou ids ordenados por tempo), e os índices secundários passam a ser locais (consultados por scatter-gather) ou globais (mantidos em outro shard).

Por isso, muitas equipes usam um sistema que faz o roteamento, o rebalanceamento e às vezes as transações distribuídas por elas: Vitess (MySQL), Citus (PostgreSQL) ou um banco de dados SQL distribuído como CockroachDB, YugabyteDB ou Spanner. Eles removem a maior parte da encanação e nenhuma das decisões de projeto: a shard key ainda precisa servir às suas consultas.

5. Escolhendo, em ordem

SintomaPrimeira coisa a tentar
Consultas lentasíndices, planos de consulta
As mesmas leituras repetidamenteum cache
As leituras excedem um servidorréplicas de leitura (decida quais leituras podem estar obsoletas)
Uma tabela é enorme, dados antigos se acumulamparticionamento por tempo, com um job de retenção
Precisa de uma cópia pronta depois de uma falhareplicação com um processo de failover e uma restauração testada a partir de backup
Escritas ou dados totais excedem o maior servidorsharding, com uma shard key bem escolhida
Clientes precisam ser isolados ou colocados em regiõessharding por tenant (células)

6. Erros comuns

  1. Ler de um seguidor logo depois de uma escrita e esperar vê-la.
  2. Tratar a replicação como um backup.
  3. Promover um seguidor sem conferir o quanto estava atrasado, ou sem fazer fencing do antigo líder.
  4. Usar replicação síncrona para um seguidor e não ter plano para quando ele estiver fora do ar.
  5. Particionar por uma chave pela qual a maioria das consultas não filtra.
  6. Milhares de partições, ou nenhum job que crie a próxima partição a tempo.
  7. Fazer sharding cedo demais, quando um índice, um cache ou uma réplica teriam bastado.
  8. Uma shard key que cresce (timestamp, auto-incremento) com sharding por faixa, de modo que um shard recebe todas as escritas.
  9. hash(key) mod N sem plano para adicionar shards.
  10. Consultas e transações que precisam de todos os shards no caminho crítico.

7. Coisas a mencionar em uma entrevista

Perguntas que os entrevistadores gostam de acrescentar:

Resumo rápido

  1. A replicação copia dados (leituras e disponibilidade), o particionamento divide uma tabela dentro de um servidor (gerenciabilidade), o sharding divide entre servidores (escritas e tamanho). Siga nessa ordem, da mais barata.
  2. Seguidores assíncronos ficam atrás: uma escrita ficou invisível em um standby por 2 s no teste, e a correção é ler suas escritas do líder, fixar a sessão ou esperar pela posição no log.
  3. Configurações síncronas mais fortes custam latência (0,35, 0,46, 0,53 e 0,65 ms por commit nas quatro configurações) e um seguidor fora do ar bloqueia as escritas.
  4. Um failover assíncrono perdeu 10 pedidos confirmados. A replicação por quórum os protege sem esperar por todos os seguidores.
  5. Uma consulta filtrada pela chave de partição varreu 1 de 12 partições; uma que não era varreu as 12. Remover um mês levou cerca de 10 ms contra 86 ms para apagar as mesmas linhas.
  6. A shard key é o projeto: uma chave crescente empilhou todo pedido novo em um shard ([0, ..., 12500]), um hash os espalhou uniformemente.
  7. Nas simulações, hash mod N moveu de 80% a 91% das chaves quando um shard foi adicionado e um anel de consistent hashing moveu cerca de 1/(N+1); o rebalanceamento real depende do volume de dados, da posição dos nós e do procedimento de cópia. A assimetria ainda deixou um shard em 1,89 vez a média, e as consultas scatter-gather pioram a cauda a cada shard.

Apêndice: o código dos experimentos

Os scripts de replicação precisam dos binários do PostgreSQL 16 e rodam como um usuário não root; os caminhos são os que usei, então altere B e R. Execute setup.sh primeiro e, para cada experimento, execute-o de novo para começar de um primário e um standby limpos.

Primário e standby em uma máquina (setup.sh)

B=/usr/lib/postgresql/16/bin; R=/var/tmp/repl
$B/pg_ctl -D $R/primary -m immediate stop >/dev/null 2>&1; $B/pg_ctl -D $R/standby -m immediate stop >/dev/null 2>&1
rm -rf $R/primary $R/standby
$B/initdb -D $R/primary -A trust >/dev/null
echo "host replication all 127.0.0.1/32 trust" >> $R/primary/pg_hba.conf
$B/pg_ctl -D $R/primary -o "-p 55433 -k $R -c listen_addresses=127.0.0.1" -l $R/primary.log -w start | tail -1
$B/pg_basebackup -h 127.0.0.1 -p 55433 -D $R/standby -R -X stream >/dev/null
chmod 700 $R/standby
$B/pg_ctl -D $R/standby -o "-p 55434 -k $R -c listen_addresses=127.0.0.1" -l $R/standby.log -w start | tail -1
psql -h $R -p 55433 -d postgres -At -c "select client_addr, state, sync_state from pg_stat_replication"
psql -h $R -p 55434 -d postgres -At -c "select pg_is_in_recovery()"

Leituras obsoletas e espera pela posição no log (r1.sh)

R=/var/tmp/repl; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table orders(id int primary key, note text)"
echo "== 1. a standby that is 2 seconds behind (recovery_min_apply_delay = 2s)"
$S -c "alter system set recovery_min_apply_delay = '2s'" -c "select pg_reload_conf()" >/dev/null; sleep 1
t0=$(date +%s.%N)
$P -c "insert into orders values (1, 'first')"
LSN=$($P -c "select pg_current_wal_lsn()")
echo "primary wrote order 1; read from the standby right away: [$($S -c 'select count(*) from orders where id=1')] rows"
echo "== 2. read-your-writes: wait until the standby has replayed the write's WAL position, then read"
until [ "$($S -c "select pg_last_wal_replay_lsn() >= '$LSN'::pg_lsn")" = "t" ]; do sleep 0.05; done
t1=$(date +%s.%N)
echo "waited $(echo "$t1 - $t0" | bc -l | cut -c1-4) s, then standby has: [$($S -c 'select count(*) from orders where id=1')] row"
$S -c "alter system reset recovery_min_apply_delay" -c "select pg_reload_conf()" >/dev/null
R=/var/tmp/repl; B=/usr/lib/postgresql/16/bin; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table orders(id int primary key, note text)" -c "insert into orders select g, 'ok' from generate_series(1,5) g"
sleep 1
echo "== 3. asynchronous replication and a failover"
echo "standby has $($S -c 'select count(*) from orders') rows, primary has $($P -c 'select count(*) from orders')"
echo "the link between them breaks (standby loses its connection to the primary)"
$S -c "alter system set primary_conninfo = ''" -c "select pg_reload_conf()" >/dev/null; sleep 1.5
echo "streaming clients seen by the primary: $($P -c 'select count(*) from pg_stat_replication')"
$P -c "insert into orders select g, 'written after the link broke' from generate_series(6,15) g"
echo "10 more orders committed on the primary; the clients were told OK. Primary now has $($P -c 'select count(*) from orders') rows"
echo "the primary crashes"; $B/pg_ctl -D $R/primary -m immediate stop >/dev/null 2>&1
$B/pg_ctl -D $R/standby promote -w >/dev/null
echo "standby promoted to primary: it has $($S -c 'select count(*) from orders') rows, so 10 acknowledged orders are gone"

Níveis de commit síncrono e um standby ausente (r4.sh)

R=/var/tmp/repl; B=/usr/lib/postgresql/16/bin; P="psql -h $R -p 55433 -d postgres -X -q -At"; S="psql -h $R -p 55434 -d postgres -X -q -At"
$P -c "create table t(n int)" -c "alter system set synchronous_standby_names = '*'" -c "select pg_reload_conf()" >/dev/null; sleep 1
echo "sync_state seen by the primary: $($P -c 'select sync_state from pg_stat_replication')"
echo "== 4. cost of waiting for the standby: 500 single-row commits per setting (one connection, same machine)"
for lvl in local remote_write on remote_apply; do
  { echo "set synchronous_commit = $lvl;"; for i in $(seq 1 500); do echo "insert into t values ($i);"; done; } > /var/tmp/repl/c.sql
  t0=$(date +%s.%N); $P -f /var/tmp/repl/c.sql >/dev/null; t1=$(date +%s.%N)
  echo "   synchronous_commit = $(printf '%-12s' $lvl) $(echo "($t1 - $t0) * 1000 / 500" | bc -l | cut -c1-5) ms per commit"
done
echo "== 5. the synchronous standby goes away"
$B/pg_ctl -D $R/standby -m fast stop >/dev/null 2>&1
echo "a plain read still works: $($P -c 'select count(*) from t') rows"
( time timeout 5 $P -c "insert into t values (-1)" ) 2>&1 | grep -E "real|ERROR|WARNING" ; echo "exit code of the insert (124 = still waiting after 5 s): ${PIPESTATUS[0]}"

Particionamento: pruning e remoção de dados antigos (part.sh)

Isto roda contra um único servidor com um banco de dados chamado idem (altere as opções -h, -p e -d).

P="psql -h /var/tmp/pgscratch -p 55432 -d idem -X -q -At"
$P <<'S' >/dev/null
drop table if exists events, events_plain cascade;
create table events (id bigserial, user_id int not null, created_at timestamptz not null, payload text) partition by range (created_at);
do $$ begin
  for m in 1..12 loop
    execute format('create table events_2026_%s partition of events for values from (%L) to (%L)', lpad(m::text,2,'0'), make_date(2026,m,1), make_date(2026,m,1) + interval '1 month');
  end loop; end $$;
insert into events (user_id, created_at, payload)
select (random()*100000)::int, timestamptz '2026-01-01' + (random()*364 || ' days')::interval, repeat('x', 50) from generate_series(1,1200000);
create index on events (user_id); create index on events (created_at);
create table events_plain as select * from events; create index on events_plain (created_at);
analyze events; analyze events_plain;
S
echo "rows per partition (first 3): $($P -c "select string_agg(tableoid::regclass::text || '=' || c, ' ') from (select tableoid, count(*) c from events group by 1 order by 1 limit 3) x")"
echo "== partition pruning"
echo "WHERE created_at in March:        scans $($P -c "explain select count(*) from events where created_at >= '2026-03-05' and created_at < '2026-03-10'" | grep -o 'events_2026_[0-9]*' | sort -u | tr '\n' ' ')"
echo "WHERE user_id = 42 (not the key): scans $($P -c "explain select * from events where user_id = 42" | grep -o 'events_2026_[0-9]*' | sort -u | wc -l) of 12 partitions"
for q in "select count(*) from events where created_at >= '2026-03-05' and created_at < '2026-03-10'" "select count(*) from events where user_id = 42"; do
  echo "   $q"; $P -c "explain analyze $q" | grep -E "Execution Time|Planning Time"
done
echo "== removing the oldest month (about 100,000 rows)"
$P -c "\timing on" -c "delete from events_plain where created_at < '2026-02-01'" | grep Time
$P -c "\timing on" -c "alter table events detach partition events_2026_01" -c "drop table events_2026_01" | grep Time
echo "rows left: plain $($P -c 'select count(*) from events_plain') partitioned $($P -c 'select count(*) from events')"

Simulações de sharding (shard.py)

Python 3, apenas a biblioteca padrão.

import bisect, collections, hashlib, random
random.seed(11)
h = lambda s: int.from_bytes(hashlib.sha256(str(s).encode()).digest()[:8], "big")

print("1. adding a shard: how many of 100,000 keys change shard?")
keys = range(100_000)
def ring(n, vnodes=100):
    pts = sorted((h(f"shard-{i}-{v}"), i) for i in range(n) for v in range(vnodes))
    hs = [p[0] for p in pts]
    return lambda k: pts[bisect.bisect(hs, h(k)) % len(pts)][1]
for n in (4, 10):
    a, b = (lambda k, n=n: h(k) % n), (lambda k, n=n: h(k) % (n + 1))
    moved_mod = sum(a(k) != b(k) for k in keys) / len(keys)
    ra, rb = ring(n), ring(n + 1)
    moved_ring = sum(ra(k) != rb(k) for k in keys) / len(keys)
    print(f"   {n} -> {n + 1} shards: hash(key) mod N moves {moved_mod:5.1%}; a consistent-hash ring moves {moved_ring:5.1%} (ideal {1 / (n + 1):5.1%})")

print("2. the shard key decides where the load lands: the newest 12,500 of 100,000 orders, with increasing ids, 8 shards")
ids = range(1, 100_001)
by_hash = [0] * 8
for i in range(87_501, 100_001): by_hash[h(i) % 8] += 1
by_range_new = [0] * 8
for i in range(87_501, 100_001): by_range_new[min(7, (i - 1) // 12_500)] += 1
print("   range sharding (ranges of 12,500 ids), orders 87,501 to 100,000 land on shards:", by_range_new)
print("   hash sharding, the same orders 87,501 to 100,000 land on shards:", by_hash)

print("3. skewed access: 1,000,000 requests over 100,000 keys, 8 shards, Zipf-like popularity")
weights = [1 / (r ** 1.1) for r in range(1, 100_001)]
reqs = random.choices(range(100_000), weights=weights, k=1_000_000)
load = [0] * 8
for k in reqs: load[h(k) % 8] += 1
print(f"   requests per shard {load}: busiest shard {max(load) / (sum(load) / 8):.2f}x the average")
top, topn = collections.Counter(reqs).most_common(1)[0]; print(f"   the single hottest key got {topn:,} requests ({topn / len(reqs):.1%}), all on shard {h(top) % 8}; hashing cannot spread one key across shards")

print("4. a query that does not include the shard key must ask every shard (scatter-gather)")
for n in (1, 8, 32, 128):
    print(f"   {n:>3} shards: chance that at least one answers slowly (1% slow each) = {1 - 0.99 ** n:5.1%}")

Fontes

  1. Documentação do PostgreSQL, High availability, load balancing and replication, incluindo servidores standby de log shipping e replicação síncrona.
  2. Documentação do PostgreSQL, Table partitioning. Particionamento por faixa, lista e hash, pruning e limitações.
  3. Martin Kleppmann, Designing Data-Intensive Applications, capítulos 5 (replicação) e 6 (particionamento). Anomalias do lag de replicação, failover e rebalanceamento.

Pratique este tema: Databases

Mais guias