Colisões UUID [fechadas]

33

Alguém já fez alguma pesquisa real sobre a probabilidade de colisões de UUID, especialmente com os UUIDs da versão 4 (aleatórios), considerando que os geradores de números aleatórios que usamos não são realmente aleatórios e que podemos ter dezenas ou centenas de máquinas idênticas executando o mesmo código gerando UUIDs?

Meus colegas de trabalho consideram que o teste de colisão de UUID é um completo desperdício de tempo, mas eu sempre escrevo um código para capturar uma exceção de chave duplicada do banco de dados e tentar novamente com um novo UUID. Mas isso não resolverá o problema se o UUID vier de outro processo e se referir a um objeto real.

Paul Tomblin
fonte
4
A questão já foi respondida no Stack Overflow: stackoverflow.com/questions/3038023/... , como mostra a pesquisa básica do Google: google.com/search?q=uuid+collision
Arseni Mourzenko
3
Essa pergunta é sobre os algoritmos específicos usados ​​no SQL * Server, que definitivamente NÃO é uma versão 4 (aleatória). Estou perguntando sobre a versão 4 especificamente.
Paul Tomblin
Você está dizendo que a implementação da NEWID()função do SQL Server não é aleatória? Em caso afirmativo, você tem alguma fonte para fazer backup dessa reivindicação? Sua saída claramente se parece com UUIDs v4 para mim. NEWSEQUENTIALID()decididamente não é completamente aleatório, mas esse é o seu objetivo : gerar UUIDs que funcionam bem (assim como UUIDs podem, pelo menos) como chaves de índice.
um CVn
1
Vou responder a pergunta vinculada, que afirma que NEWID () contém alguns bits do endereço mac, o que o torna um UUID V1 ou V2, não um V4.
Paul Tomblin
2
Esta questão parece ser off-topic porque se trata de algo já discutido ad nauseum-na internet, em livros e especialmente sobre StackOverflow

Respostas:

18

A Wikipedia tem alguns detalhes:

http://en.wikipedia.org/wiki/Universally_unique_identifier

http://en.wikipedia.org/wiki/Universally_unique_identifier#Random_UUID_probability_of_duplicates

Mas a probabilidade só vale se os bits forem perfeitamente aleatórios. No entanto, o RFC http://tools.ietf.org/html/rfc4122#page-14 vinculado na outra resposta define isso para a versão 4:

"4.4. [...] O UUID da versão 4 destina-se a gerar UUIDs a partir de números verdadeiramente aleatórios ou pseudo-aleatórios. [...] Defina todos os outros bits para valores escolhidos aleatoriamente (ou pseudo-aleatoriamente)."

Isso praticamente permite qualquer coisa, desde o gerador aleatório xkcd http://xkcd.com/221/ até um dispositivo de hardware usando ruído quântico. As considerações de segurança no RFC:

"6. Os aplicativos distribuídos que geram UUIDs em uma variedade de hosts devem estar dispostos a confiar na fonte de números aleatórios em todos os hosts. Se isso não for possível, a variante de namespace deve ser usada."

Eu li isso como: Você está por sua conta. Você é responsável por seu gerador aleatório em seu próprio aplicativo, mas isso e qualquer outra coisa se baseia na confiança. Se você não confia em sua capacidade de entender e usar corretamente o gerador aleatório de sua escolha, é uma boa ideia verificar se há colisões. Se você não confia no programador dos outros processos, verifique colisões ou use uma versão UUID diferente.

Seguro
fonte
11

Você certamente deve detectar se uma colisão ocorre e seu aplicativo deve lançar uma exceção, se isso acontecer. Por exemplo, se o UUID é usado como chave primária no banco de dados, o banco de dados deve gerar um erro ao inserir um ID em colisão.

No entanto, eu acreditaria que escrever código para gerar um novo UUID no caso de uma colisão e tentar novamente ser uma perda de tempo. A chance de uma colisão ocorrer é tão pequena que lançar uma exceção seria uma maneira perfeitamente razoável de lidar com ela.

Lembre-se de que não é apenas uma perda de tempo escrevendo o código, mas também o torna mais complexo, dificultando a leitura da próxima pessoa, quase sem nenhum ganho.

Pete
fonte
2
seu UUID é tão bom quanto seu gerador aleatório. Com um muito ( muito ) pobre, colisões não apenas ocorrerão como são inevitáveis. Dito isso, talvez a verificação de duplicatas no tempo de geração seja realmente um exagero, mas esperando que a situação possa ocorrer e, na minha opinião, não é pedir muito. Em algum domínio (assistência médica, por exemplo), acho necessário ter um código que capte essas situações (talvez como detecção de colisão no banco de dados). você ficaria surpreso com o tempo que passei depurando situações que nunca acontecem.
Newtopian
1
Eu acho que não me deixei claro. Atualizei a resposta para ser mais explícita.
Pete
7

Esta é uma pergunta muito boa. Não acredito que tenha sido considerado adequadamente na pressa de usar UUIDs em todos os lugares. Não encontrei nenhuma pesquisa sólida.

Uma sugestão: pise com muito cuidado aqui e conheça bem sua criptografia. Se você usar um UUID de 128 bits, o 'efeito de aniversário' nos informa que é provável que ocorra uma colisão após a geração de cerca de 2 ^ 64 chaves, desde que você tenha 128 bits de entropia em cada chave .

Na verdade, é bastante difícil garantir que esse seja o caso. A verdadeira aleatoriedade pode ser gerada a partir de (a) decaimento radioativo (b) ruído aleatório do rádio de fundo, muitas vezes contaminado, a menos que você tenha cuidado (c) ruído eletrônico adequadamente escolhido, por exemplo, retirado de um diodo Zener com polaridade inversa. (Eu joguei com o último, e funciona como um encanto, BTW).

Eu não confiava em pronunciamentos como "eu não vejo isso há um ano de uso", a menos que o usuário tenha gerado algo parecido com 2 ^ 64 (ou seja, cerca de 10 ^ 19) chaves e verificado todos eles um contra o outro, um exercício não trivial.

O problema é esse. Digamos que você tenha apenas 100 bits de entropia, ao comparar suas chaves com todas as outras chaves que todos os outros estão gerando em um espaço de chaves comum. Você começará a ver colisões em cerca de 2 ^ 50 ou seja. cerca de 10 ^ 15 chaves. Suas chances de encontrar uma colisão se você tiver preenchido seu banco de dados com apenas 1000 bilhões de chaves ainda são desprezíveis. E se você não verificar, mais tarde você receberá erros inesperados que se infiltram no banco de dados do tamanho de uma linhaeta. Isso pode morder muito.

O próprio fato de haver várias abordagens para gerar esses UUIDs deve causar um espasmo momentâneo de preocupação. Quando você perceber que poucos geradores usam processos 'verdadeiramente aleatórios' com entropia suficiente para um UUID do tipo 4, você deve estar excessivamente preocupado, a menos que tenha examinado cuidadosamente o conteúdo de entropia do gerador. (A maioria das pessoas não faz isso, ou mesmo sabe como fazer; você pode começar com o pacote DieHarder). NÃO confunda geração de números aleatórios pseudo-aleatórios com geração de números aleatórios verdadeira.

É fundamental que você perceba que a entropia inserida é a entropia que possui e simplesmente perturbar a chave aplicando uma função criptográfica não altera a entropia. Pode não ser intuitivamente óbvio que, se todo o meu espaço compreender os dígitos 0 e 1, o conteúdo da entropia será o mesmo das duas seqüências a seguir, desde que sejam as únicas duas opções: "Essa é uma sequência realmente muito complexa 293290729382832 * ! @@ # & ^% $$), m} "e" E AGORA PARA ALGO COMPLETAMENTE DIFERENTE ". Ainda existem apenas duas opções.

A aleatoriedade é complicada de acertar, e simplesmente acreditar que "os especialistas analisaram, portanto está tudo bem" pode não ser suficiente. Criptografistas especialistas (e alguns deles são realmente proficientes) são os primeiros a admitir que muitas vezes entendem errado. Confiamos em heartbleed, DigiNotar, etc.

Eu acho que Paul Tomblin está exercendo a devida cautela. Meu 2c.

user199506
fonte
6

O problema é que, se você usa um "gerador de números aleatórios" e não sabe o quão aleatório é esse gerador, a probabilidade de colisão é realmente desconhecida. Se os geradores de números aleatórios estiverem correlacionados de alguma forma, a probabilidade de colisão pode aumentar drasticamente - possivelmente muitas, muitas ordens ou magnitude.

Mesmo que você tenha uma probabilidade muito pequena de colisão, você tem um problema fundamental: a probabilidade NÃO é 0. Isso significa que uma colisão eventualmente ocorrerá, elas simplesmente não ocorrerão com muita frequência.

Quanto mais frequentemente você gera e usa os UUIDs, mais cedo é provável que a colisão seja vista. (gerar 1 por ano significa um tempo de espera maior do que gerar um milhão por segundo, todas as outras coisas sendo iguais).

Se essa probabilidade for finita, desconhecida e você usar muitos UUIDs, precisará considerar as consequências de uma colisão. Se não for aceitável lançar uma exceção e encerrar um aplicativo de negócios, não faça isso! (Exemplos em primeiro lugar: "Não há problema em desligar o servidor da Web no meio da atualização de um check-in de biblioteca ... isso não acontece com frequência" e "Não há problema em desligar o sistema de folha de pagamento no meio de execução salarial ". Essas decisões podem ser movimentos limitadores da carreira.)

Você pode ter um caso pior, novamente, dependendo da sua aplicação. Se você testar a presença de um UUID (ou seja, fazer uma pesquisa) e criar um novo se ainda não estiver lá - o que é um tipo de coisa bastante comum a ser feito -, você poderá descobrir que está vinculando registros ou fazendo relacionamentos , quando você estiver conectando duas coisas por meio de um UUID que não deve ser conectado. Isso é algo em que lançar uma exceção não resolve nada e você tem uma bagunça indetectável criada em algum lugar. Esse é o tipo de coisa que leva ao vazamento de informações e pode ser muito embaraçoso. (ex: faça login no seu banco e descubra que você pode ver o saldo da conta de outra pessoa! Ruim!)

Resumo: você precisa considerar a maneira como seus UUIDs são usados ​​e as consequências de uma colisão. Isso determina se você deve tomar cuidado para detectar e evitar colisões, executar alguma ação simples no caso de uma colisão ou não fazer nada. Uma solução simples, única e adequada para todos é provavelmente inadequada em algumas circunstâncias.

rapid_now
fonte
2
"A probabilidade (de colisão) NÃO é 0" Qualquer sequência de comprimento finito possui essa propriedade. Mesmo com um UUID v4 perfeitamente aleatório, depois de gerar 2 ^ 122 UUIDs únicos (versão de 128 bits menos 4 bits menos 2 bits reservados), o próximo que você gerar será garantido como uma colisão. Provavelmente, você atingirá uma colisão mais cedo do que isso. A questão maior é se uma colisão após algo como repetições 5e36 é um problema, e isso não pode ser respondido em geral (embora seja obviamente possível responder em cada caso específico), como você diz no resumo.
um CVn
Claro. Esta foi uma afirmação do óbvio (mas ainda vale a pena repetir). A questão é a quantidade de correlação com os geradores de números aleatórios. Isso pode aumentar significativamente a probabilidade de colisão (2 ^ grandes), mas quanto é algo que você não saberá, a menos que faça muitas escavações, pesquisas ou cálculos. Assumir que a probabilidade de colisão é significativamente pior do que provavelmente o melhor valor é prudente. Depois disso ... você precisa considerar as consequências.
precisa saber é o seguinte
0

Há dois problemas envolvidos:

  1. Qualidade dos geradores de números aleatórios usados.

  2. Quantidade de UUIDs que podem ser gerados.

Um UUID "aleatório" possui 122 bits aleatórios. Supondo uma aleatoriedade perfeita, você pode esperar a primeira colisão em cerca de 2 ^ 61 UUIDs gerados (essa é a raiz quadrada de 2 ^ 122). Se todos nesta terra gerassem um UUID por segundo, seriam 10.000.000.000 * 365 * 24 * 60 * 60 = 315360000000000000 UUIDs por ano, o que é bem próximo de 2 ^ 58. Ou seja, depois de alguns anos você obteria as primeiras colisões. A menos que seu aplicativo chegue perto desses números, você pode ter certeza de que não terá uma colisão se o seu gerador aleatório for de qualidade decente.

Falando sobre o gerador de números aleatórios: Se você usar os geradores de bibliotecas C padrão (geradores diretos, indiretos ou similares), provavelmente semeando-os com o tempo, você será dispensado. Eles não podem usar entropia suficiente para evitar colisões. No entanto, se você estiver no Linux, basta ler 16 bytes de dados de /dev/urandom: Isso atrai um pool de entropia que é agitado pelo kernel, que tem acesso a alguns eventos aleatórios reais. A menos que você gere UUIDs normalmente, bem no início da sequência de inicialização, /dev/urandomdeve se comportar como uma verdadeira fonte aleatória.

cmaster
fonte
-1

Eu testei uma vez usando um programa bastante simples (força bruta) que gerou 10 milhões de UUID-s e não tive colisão.

O UUID RFC diz que o UUID não é apenas um monte de (pseudo) números aleatórios.

xea
fonte
1
A versão 4, sobre a qual estou perguntando, é basicamente um monte de números aleatórios, exceto os 6 bits, que serão exatamente iguais em todos eles.
Paul Tomblin
8
10 milhões nem é uma gota no balde. Há apenas uma chance de 1 em 3E30 de colisão. Se você encontrou um, eu o aconselharia a sair correndo e comprar um bilhete em todas as loterias que puder!
Ross Patterson
@ RossPatterson, o que eu estava pensando especificamente é se você tem várias centenas de computadores usando exatamente o mesmo algoritmo aleatório psuedo no mesmo hardware, aumenta drasticamente as chances de colisão. Eu suspeito que sim.
Paul Tomblin
1
@ Paul - eu teria pensado apenas se houver entropia insuficiente no processo inicial de semeadura - por exemplo, se a semente for gerada apenas a partir da hora do dia, e todas as suas máquinas iniciarem muito perto do mesmo instante. Duvido muito que a propagação seja tão fraca - é possível que sejam usados ​​números de série de hardware, o que, obviamente, seria exclusivo para cada máquina.
precisa saber é o seguinte
1
Infelizmente, a semeadura pode ser muito fraca. Os sistemas Linux gostam de propagar o PRNG a partir de fontes altamente aleatórias (atividade do driver de dispositivo, etc. ), mas em outros ambientes, o padrão é usar o registro de data e hora atual, que com máquinas suficientes em sincronização horária próxima, pode ser um problema.
Ross Patterson