IDs únicos em escala cósmica

 (jasonfantl.com)
25 pontos por GN⁺ 2026-02-20 | 4 comentários | Compartilhar no WhatsApp
  • Explora como atribuir IDs absolutamente não duplicados a dispositivos ou objetos, comparando abordagens aleatórias (random) e determinísticas (deterministic)
  • A abordagem aleatória pode tornar a probabilidade de colisão praticamente zero com um número de bits suficientemente grande, com vários níveis possíveis, de UUID (122 bits) até o limite computacional de todo o universo (798 bits)
  • Na abordagem determinística, propõe vários esquemas, como contador central, hierarquia delegada (Dewey), árvore binária (Binary) e token (Token), e analisa por simulação as características de crescimento do comprimento dos IDs em cada método
  • Também apresenta uma prova matemática de que todos os esquemas determinísticos não conseguem evitar crescimento linear no pior caso
  • Como resultado, conclui que o método prático e eficiente mesmo em expansão cósmica é a geração aleatória de IDs, enquanto abordagens determinísticas são ineficientes

Necessidade de IDs únicos e definição do problema

  • A identificação de objetos é a base de todos os sistemas, como manufatura, logística, comunicações e segurança, e atribuir IDs sem duplicação é um desafio central em expansão em larga escala
  • Mesmo que a humanidade se expanda em escala galáctica, será necessário um sistema de IDs sem duplicação
  • O problema é formulado como: “como criar IDs que nunca se repitam?”

Abordagem aleatória (Random)

  • O método mais simples é escolher um número aleatório
    • Pode ser gerado em qualquer lugar sem administração central ou sincronização
  • A probabilidade de colisão pode ser controlada aumentando o número de bits, podendo ser ajustada para ficar efetivamente próxima de zero
  • Um UUID (122 bits) deve começar a ter colisões esperadas ao gerar cerca de $2^{61}$ IDs
  • Considerando o limite computacional de todo o universo (10¹²⁰ operações), seriam necessários 798 bits
    • Na escala atômica (10⁸⁰ itens), seriam 532 bits; para 1g de nanorrobôs (10⁵⁶), 372 bits
  • Garantir verdadeira aleatoriedade é importante, com recomendação de usar CSPRNG ou fontes quânticas de aleatoriedade
    • Seeds comuns ou IDs constantes (ex.: all-zero) devem ser proibidos

Abordagem determinística (Deterministic)

  • O método de contador central faz um único servidor emitir IDs em sequência
    • Por problemas de acessibilidade, propõe-se uma estrutura de delegação entre satélites e dispositivos (Dewey)
  • Esquema Dewey: ID hierárquico no formato A.B.C, representado com codificação Elias omega
    • Dependendo da estrutura da árvore, o crescimento pode ser logarítmico ou linear
  • O esquema Binary divide o espaço de IDs em uma árvore binária, sendo mais eficiente que o Dewey em alguns casos
  • 2-Adic Valuation garante unicidade matematicamente e é uma forma variante do Binary
  • O esquema Token mostra crescimento logarítmico em estruturas em cadeia, mas muda para linear quando a largura aumenta

Prova da inevitabilidade do crescimento linear

  • Partindo da premissa de que todos os caminhos de atribuição de IDs devem ser únicos, calcula-se o número de caminhos possíveis
  • Quando o número de nós é n, a quantidade de IDs necessária cresce para $2^{n-1}$
  • Portanto, o comprimento do ID precisa ser no mínimo O(n), ou seja, o crescimento linear é inevitável no pior caso
  • Nenhum algoritmo consegue manter crescimento logarítmico em todos os casos

Simulação de modelos de expansão

  • Foram testados vários modelos de crescimento, como Random Recursive Tree, Preferential Attachment e Fitness Model
    • Em pequena escala (2.048 nós), o Binary se sai melhor, enquanto Dewey e Token variam conforme o cenário
    • No modelo Preferential, o Dewey é o mais eficiente
    • No modelo Fitness, Dewey e Binary têm desempenho semelhante
  • Mesmo em experimentos com um milhão de nós, Dewey e Token mantêm crescimento logarítmico
    • O comprimento do ID pode ser aproximado por algo como ≈ 6.55 × ln(n)

Modelo de expansão em escala galáctica e cósmica

  • A dispersão entre planetas é modelada como uma frente de onda com velocidade constante
    • Cada planeta gera cerca de 10⁹ IDs antes de se espalhar para o próximo planeta
  • Com raio galáctico de cerca de 2.121 planetas, o comprimento do ID chega a aproximadamente 288.048 bits
  • Considerando também a dispersão entre galáxias (cerca de 7.816 etapas), seriam necessários cerca de 2,2 bilhões de bits (281MB)
  • Abordagens determinísticas são ineficientes, e a abordagem aleatória (798 bits ou menos) é esmagadoramente mais eficiente

Segurança e outras considerações

  • Para evitar falsificação de IDs, é possível aplicar um sistema de verificação baseado em assinaturas
    • IDs aleatórios podem usar a chave pública como ID; em esquemas determinísticos, o pai assina a chave do filho
  • Também são necessários códigos de correção de erros e controle de versão
  • Para objetos que não podem armazenar ID (ex.: planetas), vários IDs podem ser mapeados para gerenciamento
  • Discute-se a persistência do ID quando componentes são substituídos, como no paradoxo do navio de Teseu
  • Conceitos relacionados: Decentralized Identifiers (DID), Ancestry Labeling Schemes

Conclusão

  • Esquemas determinísticos são teoricamente interessantes, mas pouco práticos
  • A geração aleatória de IDs é realista e eficiente mesmo em escala cósmica
  • Tornar a probabilidade de colisão de IDs “efetivamente zero” é a opção mais segura e prática

Leituras relacionadas

4 comentários

 
mammal 2026-02-20

Leiam o original sem falta. Foi muito divertido de ler porque explica e visualiza com fórmulas e simulações.
 
princox 2026-02-20

Acho que algo feito com base no tempo teria que ser visto como algo linear, certo..?
Acho que vou precisar ver o original. É uma história interessante.
 
hmmhmmhm 2026-02-20

Se houver colisão, é um azar em escala cósmica... (?)
 
GN⁺ 2026-02-20
Comentários no Hacker News

  • Esta análise não é totalmente justa. Ao projetar UUIDs, considera-se a localidade (locality), ou seja, a velocidade da luz, mas isso é ignorado no cálculo da probabilidade de colisão. Na prática, para uma colisão ter significado, os dois UUIDs precisam entrar em contato causal (causal contact) após serem gerados. Portanto, aplicar simplesmente o paradoxo do aniversário (birthday paradox) é uma abordagem equivocada. Se levarmos a localidade em conta, o tamanho necessário do UUID provavelmente será muito menor do que os 800 bits mencionados no artigo. Não fiz a conta matemática, mas duvido que passe de 256 bits. Gosto muito do HN porque é um dos poucos lugares onde esse tipo de discussão técnica minuciosa acontece a sério

    • Já li antes a hipótese da expansão do universo em que as galáxias se afastam e deixam de poder trocar informações entre si. Segundo essa hipótese, formas de vida inteligentes acabariam convergindo para os locais de maior densidade de massa para sobreviver. No fim, antes da morte térmica do universo, talvez haja uma “grande reunião” em que civilizações alienígenas se encontrem num só lugar. Talvez aí comecem a surgir colisões de UUID. Fico imaginando os Vogons colocando UUID em cada tag XML e arruinando completamente as estatísticas
    • Uma vez recebi uma caixa de NICs da Intel e todas tinham o mesmo endereço MAC. Lembro de ter passado dias sofrendo para descobrir a causa
    • Quando se fala de probabilidades extremamente baixas, talvez seja preciso considerar até a possibilidade de estarmos entendendo a cosmologia de forma errada. O cone de luz (light cone) pode não ser o limite causal real
    • É preciso considerar tanto o tempo quanto a localidade. Até os prótons decaírem e a matéria desaparecer, estamos falando de apenas cerca de 10^56 nanossegundos
    • Essa crítica está correta. O texto original é um experimento mental divertido, mas exagera o problema ao ignorar a causalidade. Na prática, colisões de UUID só importam dentro de sistemas que se comunicam entre si. Esses sistemas são limitados pelo cone de luz. 128 bits já bastam para os sistemas que a humanidade criará ao longo de mil anos, e 256 bits são exagero até para o universo inteiro

  • Ao calcular o número de objetos endereçáveis, é preciso considerar que o endereço de cada objeto precisa ser armazenado em algum lugar pelo menos uma vez. Se forem necessárias Npb partículas para armazenar um bit, então, à medida que o número de bits do endereço cresce, o número de objetos endereçáveis diminui. Assim, o máximo de objetos endereçáveis pode ser obtido por uma relação do tipo Nthg = Np / (Npb * f(Ntng))

  • Já precisei argumentar antes que um ID aleatório de 256 bits já era suficiente sem checagem de colisão. Os colegas queriam adicionar uma lógica complexa de verificação de colisão, mas expliquei que 2^256 está numa escala parecida com o número de átomos no universo observável. Convenci o pessoal de que a chance de o datacenter explodir milhões de vezes era maior do que a de acontecer uma colisão antes disso. No fim, chegamos à conclusão de que até 128 bits já bastavam

    • Mas, em ambientes distribuídos, se agentes não confiáveis estiverem gerando IDs, então é preciso verificar por causa da possibilidade de colisões maliciosas. Já num sistema único, um simples contador basta, e se houver vários servidores, dá para dividir os intervalos com um contador particionado (sharded counter)
    • Na verdade, a conta é ainda mais simples. O volume total de dados de toda a humanidade ainda não chega a 1 yottabyte. Pelo paradoxo do aniversário, uma chance de colisão de 50% aparece na faixa de 2^128 itens. Um ID de 256 bits ocupa 32 bytes, então 2^128 * 32 bytes = 10^16 yottabytes. Ou seja, a probabilidade de colisão é astronomicamente baixa

  • Há um cálculo segundo o qual seriam necessários cerca de 532 bits para atribuir um ID a cada átomo. Mas, na prática, provavelmente também quereríamos atribuir IDs a grupos de átomos, como microchips, carros etc., então isso pode crescer

    • Na verdade, em vez de um ID por partícula, bastaria um ID por tipo de partícula. Pela física, partículas idênticas são indistinguíveis
    • Mesmo considerando grupos de átomos, quase não seriam adicionados bits extras
    • O UUIDv∞ teria no mínimo algo em torno de 536 bits? Se incluir ID de grupo e timestamp, talvez chegue a 1024 bits
    • Será que precisaríamos atribuir um novo ID toda vez que um neutrino oscila? Felizmente, basta um para o elétron

  • Existe a ideia de representar IDs com um baralho de cartas. Se cada uma das 52 cartas for representada por um caractere Unicode, fica fácil de ler, difícil de editar manualmente e bom para reconhecimento de padrões. Se você embaralhar um baralho real e ler com uma câmera, isso também pode servir como seed aleatória. Há uma ideia parecida no DiceKeys

    • Mas o maior ponto fraco é justamente “embaralhar direito”

  • Ótima visualização e ótimo insight. Eu projetei bancos de dados em torno de identificadores aleatórios tão pequenos quanto possível. Acho que esse tipo de identificador universal é, na prática, o único verdadeiro “disco de ouro”. Nas áreas de gestão de dados científicos e biblioteconomia, esse conceito é subestimado. Muitos problemas em grandes organizações poderiam ter sido resolvidos com um projeto melhor de identificadores.
    Leitura relacionada: Identifiers Deep Dive, Trible Structure

    • A identidade de uma entidade também pode ser definida de forma intrínseca (intrinsic). Por que um contrato de consistência (consistency contract) não serviria?

  • Estou lendo Becky Chambers, The Galaxy, and the Ground Within, por volta da página 281.
    Exemplo de mensagem no livro:

    Received Message
Encryption: 0
From: GC Transit Authority --- Gora System (path: 487-45411-479-4)
To: Ooli Oht Ouloo (path: 5787-598-66)
Subject: URGENT UPDATE

    Amo muito essa série. Acho interessante a ideia de um universo multiespécies usar um sistema centralmente acordado de endereços por caminho

    • Como exemplo parecido, recomendo A Fire Upon The Deep, de Vernor Vinge. O esquema de rotulagem para comunicação intergaláctica é interessante
    • Fiquei especialmente impressionado com a cena em que têm medo do conceito de queijo. O segundo livro da série, A Closed and Common Orbit, foi o melhor

  • Recentemente conheci o Snowflake ID. Ele é usado por Twitter, Discord, Instagram, Mastodon etc. É um método de reduzir o tamanho do ID combinando timestamp + aleatoriedade, e achei uma pena que o artigo não tenha tratado disso.
    Veja a wiki do Snowflake ID e o vídeo do Tom Scott.
    Se alguns bits do timestamp do Snowflake fossem trocados por bits aleatórios, talvez desse para gerar 4 bilhões de IDs por segundo

    • Na verdade, o Snowflake tem praticamente a mesma estrutura do UUID v1. Só tem metade do tamanho
    • Há uma ideia parecida também no DRUUID
    • Mas é praticamente impossível que o universo inteiro concorde com um único relógio
    • Esse método também é semelhante ao BSON ID

  • Fico pensando se daria para criar IDs com base em fenômenos observáveis. Talvez a unicidade pudesse ser garantida por características distinguíveis no tempo e no espaço. Por exemplo, o padrão da luz das estrelas num dado momento só pode ser visto por uma única pessoa. É parecido com usar ruído como fonte de entropia, como numa lava lamp. Se fosse possível definir um sistema de coordenadas para o universo inteiro, talvez desse para criar um ID único com tempo local + x + y + z + salt

  • O método de UUID aleatório é muito melhor em termos de longevidade. O número de dispositivos que podem operar ao mesmo tempo é limitado e, ao contrário de UUIDs baseados em árvore, quando um dispositivo é descartado o ID pode ser reutilizado. Na prática, parece mais viável um algoritmo híbrido que misture uma raiz baseada em localização + bits aleatórios nas partes inferiores