Papers
Snowflake (Twitter, 2010) e Ticket Servers: Distributed Unique Primary Keys on the Cheap (Flickr, 2010)
Twitter (repositório snowflake), Flickr Engineering · Repositório twitter/snowflake (tag snowflake-2010; anúncio no blog não verificado) e code.flickr.com, 2010
O problema: IDs únicos quando um contador de banco único não basta
Quando os dados são espalhados por muitos bancos, a coluna auto-increment de cada tabela deixa de bastar, porque dois bancos distintos entregam o mesmo número sem perceber. O post do Flickr descreve exatamente isso: o Flickr faz sharding do MySQL (vários bancos, cada um com parte dos dados) e, às vezes, precisa migrar dados entre eles; por isso as chaves primárias precisam ser únicas no site inteiro. Além disso, cada shard é um par master-master, então é preciso garantir unicidade também dentro do shard para evitar colisão de chaves. O autor diz que gostaria de continuar com auto-increment como todo mundo, mas o MySQL não garante unicidade entre bancos físicos e lógicos. Surge então a pergunta óbvia: por que não usar GUIDs? Segundo o post, GUIDs são grandes e indexam mal no MySQL; o Flickr indexa tudo que consulta e só consulta por índices, então o tamanho do índice importa, e um índice que não cabe em memória deixa o banco lento. O post também aprecia que IDs sequenciais facilitam relatórios e depuração. O problema, portanto, tem três exigências em tensão: unicidade global, chaves pequenas e bem comportadas em índices, e não depender de um único banco para cada inserção. O código do Snowflake, publicado em 2010 pelo Twitter, ataca a mesma necessidade por outro caminho, que veremos a seguir.
A ideia do Snowflake: o próprio ID carrega o que garante sua unicidade
No Snowflake cada gerador cria IDs localmente, sem consultar outros geradores, porque o ID é montado a partir de campos que o distinguem. Pela leitura do código IdWorker.scala da versão de 2010 (a fonte usada aqui; o texto do anúncio original não foi lido), o ID de 64 bits é composto, do bit mais alto ao mais baixo, por: timestamp em milissegundos contado a partir de uma época própria (o código fixa essa época em 1288834974657 ms), um datacenter ID de 5 bits, um worker ID de 5 bits e um número de sequência de 12 bits. O timestamp fica nos bits altos, e por isso IDs gerados mais tarde tendem a ser numericamente maiores. A sequência de 12 bits diferencia IDs criados pelo mesmo worker dentro do mesmo milissegundo; se ela estoura (volta a zero), o código espera o próximo milissegundo antes de continuar. Desde que cada gerador receba um par datacenter/worker distinto (o código só valida que cada campo está entre 0 e 31), duas máquinas diferentes não produzem o mesmo ID. Enquanto o mesmo gerador está em execução, ele também não repete: o tempo avança ou a sequência muda, e se o relógio recua o gerador se recusa a emitir (o último timestamp fica só em memória, então essa proteção não cobre reinícios do processo). Assim não há coordenação entre geradores no momento de gerar. A divisão do campo de máquina em datacenter e worker é a do código de 2010; o repositório arquivado informa que a versão inicial usava Apache Thrift e que foi substituída por uma reescrita interna do Twitter.
O trade-off: a unicidade depende do relógio e da configuração
Gerar IDs sem coordenação tem um preço: o esquema se apoia no relógio da máquina. O código de 2010 guarda o último timestamp usado e, se o relógio atual aparece menor que ele (o relógio andou para trás), o gerador registra um erro e se recusa a emitir IDs, lançando uma exceção que informa por quantos milissegundos se recusa; só volta a funcionar quando o relógio alcança de novo o último valor usado. Em outras palavras, o sistema prefere ficar indisponível naquela máquina a arriscar um ID repetido. Dentro do mesmo milissegundo, a unicidade vem do contador de sequência; ao estourar, o gerador espera ativamente o próximo milissegundo. O segundo ponto de risco é a configuração: workerId e datacenterId são parâmetros do gerador, e o código só valida que estão na faixa de 0 a 31. Nada no código lido impede que duas instâncias recebam o mesmo par, o que quebraria o argumento de unicidade; garantir que cada par seja distinto é responsabilidade de quem opera o sistema. Garantias de ordem mais finas (como a precisão da ordenação entre máquinas diferentes) não constam do código lido e, por isso, não são afirmadas aqui; o que o código mostra é que a ordem numérica segue o timestamp, e o timestamp vem do relógio local de cada máquina.
O contraste: os ticket servers do Flickr
O Flickr escolheu um caminho oposto, deliberadamente simples e centralizado. Um ticket server é um servidor de banco dedicado, com um único banco contendo tabelas como Tickets32 e Tickets64. A Tickets64 tem uma coluna id auto-increment e uma coluna stub de um caractere com chave única; a tabela guarda uma só linha. Para obter um ID global de 64 bits, o cliente executa um REPLACE INTO nessa tabela e depois lê LAST_INSERT_ID(). O REPLACE funciona como INSERT, mas apaga a linha antiga quando há conflito de chave primária ou única, o que permite atualizar uma única linha no lugar e ainda receber um novo valor auto-incrementado. Para não ter um ponto único de falha, o Flickr roda dois ticket servers que dividem o espaço de IDs em pares e ímpares (auto-increment-increment igual a 2, com offset 1 em um servidor e 2 no outro), e os clientes se alternam entre eles em round robin, o que balanceia carga e tolera um servidor fora. O autor diz que replicar entre os dois seria problemático nesse volume e que travas prejudicariam o desempenho. Os dois lados ficam um pouco dessincronizados (o autor estimava, na época, algumas centenas de milhares de objetos ímpares a mais), e isso não faz mal. Também há sequências separadas para Photos, Accounts, OfflineTasks e Groups. O post chama o desenho de pouco elegante, em produção desde janeiro de 2006. Comparado ao Snowflake, cada ID custa uma escrita num banco central (REPLACE INTO), em troca de números sequenciais e compactos; no Snowflake de 2010 o cliente também chamava um serviço (Thrift), mas os geradores não coordenavam entre si para gerar o ID.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.