Gerador de IDs únicos

01 · CONTEXTO

Por que gerar IDs únicos deixa de ser trivial

Num banco único, o auto-incremento resolve: cada linha nova recebe o próximo número. O problema aparece quando os dados se espalham por várias máquinas e cada uma precisa criar identificadores sem esperar as outras. Como em qualquer entrevista, comece por levantar requisitos: o ID precisa ser numérico? Precisa caber em poucos bytes? Precisa seguir a ordem de criação? Qual a vazão esperada por segundo?

O caso do Twitter mostra o motivo prático. Ao sair do MySQL em direção ao Cassandra, a equipe perdeu o gerador sequencial que vinha de graça: o próprio projeto dizia que não há facilidade de geração sequencial de IDs nesse tipo de armazenamento. A escolha do banco de dados mudou o que a camada de IDs precisava oferecer, e foi daí que nasceu o Snowflake.

Os requisitos do Snowflake são um bom roteiro de perguntas. As máquinas que geram IDs não devem precisar se coordenar entre si, para manter a alta disponibilidade. Os IDs devem ser aproximadamente ordenados no tempo, ou seja, k-ordenáveis dentro de um limite razoável, e não estritamente em ordem. E devem ser compactos: a equipe descartou soluções que exigiam números de 128 bits e quis manter os IDs abaixo de 64 bits.

02 · TICKET SERVERS

O caminho do Flickr: bancos dedicados a emitir IDs

O Flickr descartou GUIDs principalmente porque eles são grandes e indexam mal no MySQL, e a equipe depende de índices para manter as consultas rápidas. A alternativa foi o ticket server: um servidor de banco de dados dedicado, com uma única base, em que cada novo ID sai de um comando REPLACE INTO seguido da leitura do último ID inserido, aproveitando o auto-incremento.

1. Antes de gravar um objeto novo, o serviço de aplicação pede um ID em vez de deixar cada banco inventar o seu.

2. Os pedidos se alternam entre os dois ticket servers, o que divide a carga e tolera a queda de um deles.

3. O espaço de IDs é dividido ao meio: um servidor emite só números ímpares e o outro só pares, sem precisar replicar nem travar entre si.

4. Se um ticket server cai, o outro segue emitindo, mas só do seu lado do espaço; por isso um único servidor seria um ponto único de falha.

Esse desenho resolve a unicidade e a compactação, mas mantém um serviço central a mais para operar. O Flickr observou que provisionar IDs como ponto único de falha é inaceitável e por isso roda dois ticket servers, e que replicar entre eles seria problemático e travar derrubaria o desempenho.

03 · SNOWFLAKE

IDs que carregam o tempo dentro

O Snowflake monta o ID de 64 bits em três partes: 41 bits de tempo em milissegundos a partir de uma época própria, o que dá 69 anos; 10 bits de identificador da máquina, até 1024 máquinas; e 12 bits de número de sequência, que reinicia a cada 4096 IDs por máquina, com proteção para não reiniciar dentro do mesmo milissegundo. Como o tempo ocupa os bits mais altos, ordenar por ID equivale, aproximadamente, a ordenar por criação.

1. Cada gerador atende sozinho as suas aplicações: nenhum pergunta ao outro antes de emitir, e isso preserva a disponibilidade.

2. Cada ID emitido combina o instante atual, a identidade configurada da máquina e um contador local; máquinas distintas nunca produzem o mesmo valor.

3. As aplicações gravam no armazenamento particionado usando esses IDs, que ordenam aproximadamente por criação sem consultar os objetos.

Note o efeito sobre o particionamento dos dados: como o ID já nasce único em qualquer gerador, qualquer partição pode recebê-lo sem consultar um coordenador central. O custo é a ordem apenas aproximada, não total.

04 · RELÓGIO

A dependência do relógio

Como o tempo é parte do ID, o relógio vira dependência crítica. A documentação do Snowflake recomenda usar NTP para manter o relógio preciso e diz que o serviço se protege de relógios não monotônicos, isto é, que andam para trás. Se o NTP mandar o relógio repetir alguns milissegundos, o serviço se recusa a gerar IDs até chegar a um instante posterior ao do último ID emitido.

1. O relógio de um gerador recua depois de um ajuste de sincronização; emitir agora poderia repetir um instante já usado.

2. O gerador recusa emitir até o tempo ultrapassar o do último ID; a aplicação ligada a ele espera, enquanto o outro gerador continua normal.

05 · COMPARAÇÃO

Qual abordagem escolher