Aceitável confiar em ints aleatórios sendo únicos?

Estou implementando um protocolo de rede e exijo que os pacotes tenham identificadores exclusivos. Até agora, acabei de gerar números inteiros aleatórios de 32 bits e assumindo que é astronomicamente improvável que ocorra uma colisão durante a vida útil de um programa / conexão. Isso geralmente é considerado uma prática aceitável no código de produção ou deve-se criar um sistema mais complexo para evitar colisões?

Cuidado com o paradoxo do aniversário .

Suponha que você esteja gerando uma sequência de valores aleatórios (uniformemente, independentemente) a partir de um conjunto de tamanho N (N = 2 ^ 32 no seu caso).

Em seguida, a regra geral para o paradoxo do aniversário indica que, depois de gerar sobre os valores sqrt (N), há pelo menos 50% de chance de uma colisão, ou seja, de que haja pelo menos dois valores idênticos no sequência gerada.

Para N = 2 ^ 32, sqrt (N) = 2 ^ 16 = 65536. Portanto, depois de gerar cerca de 65k identificadores, é mais provável que dois deles colidam do que não! Se você gerar um identificador por segundo, isso aconteceria em menos de um dia; escusado será dizer que muitos protocolos de rede operam muito mais rápido que isso.

É amplamente considerado aceitável contar com números aleatórios únicos, se esses números tiverem bits suficientes. Existem protocolos criptográficos nos quais a repetição de um número aleatório interrompe toda a segurança. E desde que não haja vulnerabilidades sérias no gerador de números aleatórios em uso, isso não foi um problema.

Um dos algoritmos para gerar UUIDs gerará efetivamente um ID que consiste em 122 bits aleatórios e assume que ele será único. E dois dos outros algoritmos contam com um valor de hash truncado para 122 bits, sendo único, o que tem aproximadamente o mesmo risco de colisões.

Portanto, existem padrões que dependem de 122 bits para tornar um ID aleatório único, mas 32 bits definitivamente não são suficientes. Com IDs de 32 bits, são necessários apenas dois IDs antes que o risco de uma colisão atinja 50%, porque com IDs de 2 bits haverá perto de 2 ³ pares cada um dos quais pode ser uma colisão.

Até 122 bits é menor do que eu recomendaria em qualquer novo design. Se seguir alguma padronização for importante para você, use UUIDs. Caso contrário, use algo maior que 122 bits.

A função hash SHA1 com uma saída de 160 bits não é mais considerada segura, o que é parcialmente porque 160 bits não são suficientes para garantir a exclusividade das saídas. Funções hash modernas têm saídas de 224 a 512 bits. Os IDs gerados aleatoriamente devem ter o mesmo tamanho para garantir exclusividade com uma boa margem de segurança.

Eu chamaria isso de má prática. O número aleatório gerado simplesmente não cria números únicos, apenas cria números aleatórios. É provável que uma distribuição aleatória inclua algumas duplicatas. Você pode tornar essa circunstância aceitável improvável adicionando um elemento de tempo. Se você obtiver a hora atual do relógio do sistema em milissegundos. Algo assim:

parseToInt(toString(System.currentTimeMillis()) + toString(Random.makeInt()))

Irá um longo caminho. Obviamente, para realmente garantir a exclusividade, você precisa usar o UUID / GUID. Mas eles podem ser caros de gerar, o acima exposto provavelmente é suficiente, pois a única possibilidade de sobreposição é se a geração aleatória tiver uma duplicata no mesmo milissegundo.

Depende da probabilidade de falha e das consequências da falha.

Lembro-me de um debate entre as pessoas de software e hardware, nas quais as pessoas consideravam aceitável um algoritmo com uma pequena probabilidade de resultados errados (algo como 1 falha em 100 anos), e as pessoas de software pensavam que isso era um anátema. Verificou-se que o pessoal do hardware calculava rotineiramente as taxas de falhas esperadas e estava muito acostumado à idéia de que tudo daria respostas erradas ocasionalmente, por exemplo, devido a distúrbios causados ​​por raios cósmicos; eles acharam estranho que o pessoal do software esperasse 100% de confiabilidade.

Claro, você tem probabilidades muito baixas de dois inteiros aleatórios de 32 bits serem sequenciais, mas não é completamente impossível. A decisão de engenharia apropriada é baseada em quais seriam as consequências de colisões, uma estimativa do volume de números que você está gerando, a vida útil em que a exclusividade é necessária e o que acontece se um usuário mal-intencionado começar a tentar causar colisões.

Pode ser aceitável assumir que os números aleatórios serão únicos, mas você deve ter cuidado.

Supondo que seus números aleatórios sejam igualmente distribuídos, a probabilidade de uma colisão é aproximadamente (n ^2/2 ) / k, em que n é o número de números aleatórios que você gera e k é o número de valores possíveis que um número "aleatório" pode assumir.

Você não coloca um número improvável em termos astronômicos, então vamos considerá-lo como 1 em 2 ³⁰ (aproximadamente um bilhão). Vamos dizer ainda que você gera 2 ³⁰ pacotes (se cada pacote representa cerca de um kilobyte de dados, isso significa cerca de um terabyte de dados totais, grande, mas não inimaginavelmente). Achamos que precisamos de um número aleatório com pelo menos 2 ⁸⁹ valores possíveis.

Em primeiro lugar, seus números aleatórios precisam ser grandes o suficiente. Um número aleatório de 32 bits pode ter no máximo 2 ³² valores possíveis. Para um servidor ocupado que não chega nem perto do ponto alto.

Em segundo lugar, seu gerador de números aleatórios precisa ter um estado interno suficientemente grande. Se o seu gerador de números aleatórios tiver apenas um estado interno de 32 bits, não importa o tamanho do valor que você gerar, você ainda obterá no máximo 2 ³² valores possíveis.

Em terceiro lugar, se você precisar que os números aleatórios sejam únicos nas conexões, e não apenas dentro de uma conexão, seu gerador de números aleatórios precisará ser bem distribuído. Isto é especialmente verdade se o seu programa for reiniciado com freqüência.

Em geral, os geradores de números aleatórios "regulares" nas linguagens de programação não são adequados para esse uso. Os geradores de números aleatórios fornecidos pelas bibliotecas de criptografia geralmente são.

Embutido em algumas das respostas acima está a suposição de que o gerador de números aleatórios é realmente 'plano' - que a probabilidade de dois números serem o próximo gerado é a mesma.

Provavelmente isso não é verdade para a maioria dos geradores de números aleatórios. A maioria usa polinômio de alta ordem, aplicado repetidamente a uma semente.

Dito isto, existem muitos sistemas por aí que dependem desse esquema, geralmente com UUIDs. Por exemplo, todos os objetos e ativos no Second Life têm um UUID de 128 bits, gerado aleatoriamente e raramente colidem.

Muitas pessoas já deram respostas de alta qualidade, mas eu gostaria de acrescentar alguns pontos menores: primeiro, o ponto de @nomadictype sobre o paradoxo do aniversário é excelente .

Outro ponto: a aleatoriedade não é tão simples de gerar e definir quanto as pessoas podem assumir. (Na verdade, existem na realidade os testes estatísticos para aleatoriedade disponível).

Dito isso, é importante estar ciente da falácia do jogador , que é uma falácia estatística em que as pessoas assumem que eventos independentes de alguma forma se influenciam. Eventos aleatórios geralmente são estatisticamente independentes um do outro - ou seja, se você gerar um "10" aleatoriamente, isso não altera sua probabilidade futura de gerar mais "10" s no mínimo. (Talvez alguém possa apresentar uma exceção a essa regra, mas eu esperaria que esse fosse o caso de praticamente todos os geradores de números aleatórios).

Portanto, minha resposta é que, se você pudesse supor que uma sequência suficientemente longa de números aleatórios fosse única, eles não seriam realmente números aleatórios porque esse seria um padrão estatístico claro. Além disso, isso implicaria que cada novo número não é um evento independente, porque se você gerar, por exemplo, um 10, significaria que a probabilidade de gerar qualquer 10s futuro seria 0% (isso não poderia acontecer), mais isso significaria que você aumentaria as chances de obter um número diferente de 10 (ou seja, quanto mais números você gerar, maior será a probabilidade de cada um dos números restantes).

Mais uma coisa a considerar: a chance de ganhar a Powerball de jogar um único jogo é, pelo que entendi, aproximadamente 1 em 175 milhões. No entanto, as chances de alguém ganhar são consideravelmente maiores que isso. Você está mais interessado nas chances de alguém "ganhar" (ou seja, ser uma duplicata) do que nas chances de qualquer número específico "vencer" / ser uma duplicata.

Não importa quantos bits você use - você NÃO PODE garantir que dois números "aleatórios" serão diferentes. Em vez disso, sugiro que você use algo como o endereço IP ou outro endereço de rede do computador e um número seqüencial, de preferência um número seqüencial HONKIN 'BIG - 128 bits (obviamente sem sinal) parece um bom começo, mas 256 seria melhor.

Não, claro que não. A menos que a rng esteja usando amostras sem substituição, há uma chance - embora pequena - de duplicação.