Padrões de geração de IDs distribuídos sem ponto único de falha

1. Fundamentos e Desafios da Geração de IDs em Sistemas Distribuídos

1.1. Requisitos de unicidade, ordenação e escalabilidade horizontal

Em sistemas distribuídos modernos, a geração de identificadores únicos enfrenta três requisitos fundamentais: unicidade global, ordenação temporal aproximada e capacidade de escalar horizontalmente sem degradação. IDs sequenciais tradicionais, como auto-incremento em bancos relacionais, falham nesses requisitos por dependerem de um único nó mestre.

1.2. Problemas de pontos únicos de falha (SPOF) em abordagens centralizadas

Uma tabela com SERIAL ou AUTO_INCREMENT em um banco centralizado cria um ponto único de falha. Se o banco cair, todo o sistema de geração de IDs para. Além disso, o gargalo de escrita limita a vazão máxima do sistema.

-- Abordagem com SPOF (evitar em produção distribuída)
CREATE TABLE id_generator (
    id BIGSERIAL PRIMARY KEY,
    created_at TIMESTAMP DEFAULT NOW()
);

1.3. Trade-offs entre consistência, disponibilidade e tolerância a partições (CAP)

Sistemas de IDs distribuídos geralmente sacrificam consistência forte em favor de disponibilidade e tolerância a partições. IDs baseados em tempo aceitam pequenas janelas de duplicidade potencial em troca de operação contínua mesmo durante falhas de rede.

2. Padrão UUID e suas Variantes para Ambientes Distribuídos

2.1. UUID v4 (aleatório) vs UUID v7 (ordenado por tempo)

UUID v4 gera 122 bits aleatórios, oferecendo 5.3×10³⁶ valores possíveis — colisões são virtualmente impossíveis em qualquer escala prática. Porém, sua natureza aleatória causa fragmentação severa em índices B-tree de bancos relacionais.

UUID v7 combina timestamp de 48 bits com 74 bits aleatórios, garantindo ordenação cronológica aproximada. Isso reduz drasticamente a fragmentação de índices.

// Exemplo de estrutura UUID v7 (128 bits)
// Timestamp Unix ms (48 bits) | Versão (4 bits) | Aleatório (74 bits) | Variante (2 bits)
// 0x01EC9A3B7F008000 | 7 | 8A3B7F0080008A3B7F00 | 10

2.2. Estratégias para evitar colisões em larga escala sem coordenação central

Com 122 bits aleatórios no UUID v4, a probabilidade de colisão após 1 bilhão de IDs é inferior a 10⁻¹⁵. Para UUID v7, a chance de dois nós gerarem o mesmo timestamp+aleatório é de 1 em 2⁷⁴ (~1.9×10²²). Nenhuma coordenação central é necessária.

2.3. Impacto no desempenho de índices de banco de dados e armazenamento

UUIDs ocupam 16 bytes (vs 8 bytes de um BIGINT). Em índices clusterizados, UUID v4 causa 50-80% de fragmentação e degradação de desempenho em inserções. UUID v7 melhora isso para 10-20% de fragmentação.

3. Snowflake ID: Geração Descentralizada Baseada em Timestamps

3.1. Estrutura do ID Snowflake

O formato clássico do Twitter Snowflake usa 64 bits:

// Snowflake ID de 64 bits
// 1 bit reservado | 41 bits timestamp (69 anos) | 10 bits ID do nó (1024 nós) | 12 bits sequência (4096/s)
// Exemplo: 0 | 0x1EC9A3B7F00 | 0x3FF | 0xFFF
// ID gerado: 1453298574298128384

3.2. Implementação de identificação de nós sem coordenador central

Cada nó recebe um ID único via configuração estática (arquivo, variável de ambiente) ou descoberta via Zookeeper. A sequência local garante unicidade dentro do mesmo milissegundo.

// Pseudo-código para geração de Snowflake ID
timestamp = getCurrentUnixMs()
if timestamp < lastTimestamp:
    handleClockSkew()
if timestamp == lastTimestamp:
    sequence = (sequence + 1) & 0xFFF
    if sequence == 0:
        waitNextMs()
else:
    sequence = 0
lastTimestamp = timestamp
id = (timestamp << 22) | (nodeId << 12) | sequence

3.3. Tratamento de reversão de relógio (clock skew)

Quando o relógio do sistema volta no tempo (ex: correção NTP), IDs duplicados podem ocorrer. Estratégias comuns incluem:

  • Esperar até que o timestamp alcance o último valor registrado
  • Usar sequência negativa como fallback
  • Rejeitar geração até sincronização correta
// Estratégia de clock skew por espera
if currentMs < lastTimestamp:
    wait(lastTimestamp - currentMs)
    return generateId()

4. Uso de Sequências com Zookeeper ou Etcd sem SPOF

4.1. Algoritmo de sequência incremental com líder eleito (consenso)

Zookeeper e Etcd implementam consenso Raft/Zab para eleger um líder que gerencia a sequência. Se o líder falha, um novo é eleito automaticamente.

// Algoritmo simplificado com Etcd
// 1. Conectar ao cluster Etcd (3+ nós)
// 2. Tentar adquirir lock: etcdctl lock id-lock
// 3. Incrementar contador: etcdctl put counter $(($(etcdctl get counter) + 1))
// 4. Liberar lock
// 5. Retornar valor do contador

4.2. Configuração de quorum e failover para disponibilidade contínua

Um cluster com 3 nós tolera falha de 1 nó; com 5 nós, tolera 2 falhas. O failover ocorre em 200-500ms, durante os quais a geração de IDs pode pausar.

4.3. Limitações de latência e gargalos de rede

Cada requisição ao Zookeeper adiciona 2-5ms de latência. Em clusters com 100+ nós gerando IDs, o throughput máximo é limitado a ~500 IDs/s por líder. Para maior escala, combine com alocação em lote.

5. Abordagem Híbrida: IDs Baseados em Intervalos e Segmentos

5.1. Alocação de blocos de IDs (range-based)

Cada microsserviço solicita um intervalo de IDs ao serviço central e os consome localmente sem coordenação adicional.

// Serviço de alocação concede bloco [10000, 19999] ao microsserviço A
// Microsserviço A gera IDs incrementalmente: 10000, 10001, 10002...
// Quando esgota o bloco, solicita novo intervalo

5.2. Reserva de segmentos por microsserviço com cache local

O serviço central aloca segmentos de 1000 IDs por vez. O microsserviço armazena o segmento em cache e gera IDs sem latência de rede até esgotá-lo. A renovação ocorre em background.

// Cache local de segmento
segmentStart = 50000
segmentEnd = 50999
currentId = segmentStart

function getNextId():
    if currentId > segmentEnd:
        segment = requestSegmentFromCentral(1000)
        segmentStart = segment.start
        segmentEnd = segment.end
        currentId = segmentStart
    return currentId++

5.3. Estratégias de recuperação em caso de perda de segmento não utilizado

Se um microsserviço falha após receber um segmento, os IDs não utilizados são perdidos. Estratégias incluem:

  • Aceitar lacunas (IDs não consecutivos)
  • Recuperar segmentos via heartbeat com timeout
  • Usar IDs como segmento + contador para detecção de lacunas

6. Geração de IDs com Base em Redes Sociais (Grafos) e Hash Consistente

6.1. Uso de hashes consistentes para mapear IDs a nós

Hash consistente permite que cada nó seja responsável por um intervalo do espaço de hash. Ao gerar um ID, o hash do nome do recurso determina qual nó o processa.

// Hash consistente com 256 partições virtuais
resourceKey = "user:12345"
partition = hash(resourceKey) % 256
node = virtualToPhysical[partition]
id = generateOnNode(node, partition, timestamp)

6.2. Combinação de identificadores de partição com contadores locais

O ID final combina partição + timestamp + contador local, garantindo unicidade global sem coordenação.

// ID composto: 8 bits partição | 41 bits timestamp | 15 bits contador
// 0x1A | 0x1EC9A3B7F00 | 0x7FFF
// ID: 0x1A1EC9A3B7F007FFF (64 bits)

7. Considerações Operacionais e Monitoramento

7.1. Métricas de desempenho

  • Latência de geração: <1ms para Snowflake local, 2-5ms para Zookeeper
  • Taxa de colisão: Zero em condições normais, monitorar durante clock skew
  • Uso de armazenamento: 8 bytes (Snowflake) vs 16 bytes (UUID) vs 4-8 bytes (sequencial)

7.2. Testes de resiliência

Simule cenários de falha:

# Teste de clock skew (Linux)
date -s "2 minutes ago"
# Verificar se IDs gerados são únicos

# Teste de falha de nó (Docker)
docker stop etcd-node-1
# Verificar failover e continuidade

7.3. Boas práticas para versionamento e migração

  • Prefixar IDs com versão (ex: 2 bytes de versão)
  • Suportar múltiplos formatos simultaneamente durante migração
  • Usar campo id_type em tabelas para distinguir padrões

Referências