È sicuro assumere un GUID sarà sempre unico?

So che c’è una possibilità minima di uno scontro, ma se ho generato un lotto di 1000 GUID (ad esempio), sarebbe sicuro assumere che sono tutti unici per salvare testare ciascuno di essi?

Domanda bonus

Un modo ottimale per testare un GUID per l’unicità? Forse il filtro Bloom?

Si, puoi. Poiché i GUID hanno una lunghezza di 128 bit, è evidente che esiste una possibilità minima di uno scontro, ma la parola “minuto” non è affatto abbastanza forte. Ci sono così tanti GUID che se ne generi diversi trilioni in modo casuale, sei ancora più probabilità di essere colpito da un meteorite piuttosto che avere una collisione (da Wikipedia ). E se non li stai generando casualmente, ma stai usando ad esempio l’algoritmo MAC-address-and-time-stamp, allora saranno anche unici, dato che gli indirizzi MAC sono unici tra i computer e i timestamp sono unici sul tuo computer.

Modifica 1: per rispondere alla tua domanda bonus, il modo ottimale per testare un set di GUID per l’unicità è semplicemente supporre che siano tutti unici. Perché? Perché, dato il numero di GUID che stai generando, le probabilità di una collisione GUID sono più piccole delle probabilità di un raggio cosmico di girare un po ‘nella memoria del tuo computer e di rovinare la risposta fornita da un algoritmo “accurato” di cui ti occuperesti correre. (Vedi questa risposta StackOverflow per la matematica.)

C’è un numero enorme di GUID là fuori. Per citare la Guida galattica di Hitchhiker di Douglas Adams:

“Lo spazio”, dice, “è grande, davvero grande, non crederai a quanto enormemente incredibilmente grande è, voglio dire, potresti pensare che è molto lontano lungo la strada per il farmacista, ma è solo noccioline nello spazio , ascolta…”

E poiché nell’universo ci sono circa 7 × 10 22 stelle , e poco meno di 2 128 GUID, ci sono approssimativamente 4.86 × 10 15 -almeno cinque quadrilioni -GUID per ogni singola stella. Se ognuna di quelle stelle avesse un mondo con una popolazione fiorente come la nostra, allora attorno a ogni stella, ogni umano o alieno che fosse mai vissuto avrebbe avuto diritto a oltre quarantacinquemila GUID. Per ogni persona nella storia in ogni stella nell’universo. Lo spazio GUID è allo stesso livello di ampiezza delle dimensioni dell’intero universo. Non devi preoccuparti.

( Modifica 2: Riflettendo su questo: wow, non mi ero reso conto di cosa significasse: lo spazio GUID è incomprensibilmente massiccio.

Risposta breve: a fini pratici, sì.

Tuttavia, devi considerare il paradosso del compleanno!

Ho calcolato alcune probabilità di collisione rappresentative. Con UUID a 122 bit come specificato nell’articolo di Wikipedia , la probabilità di collisione è 1/2 se si generano almeno 2.71492e18 UUID. Con 10 ^ 19 UUID, la probabilità è 0.999918. Con 10 ^ 17 UUID, 0.000939953.

Alcuni numeri per il confronto possono essere trovati su Wikipedia. Quindi puoi tranquillamente assegnare un UUID per ogni essere umano che ha vissuto, ogni galassia nell’universo osservabile, ogni pesce nell’oceano e ogni singola formica sulla Terra. Tuttavia , le collisioni sono quasi certe se generi un UUID per ogni transistor che l’umanità produce in un anno, ogni insetto sulla Terra, ogni granello di sabbia sulla Terra, ogni stella nell’universo osservabile o qualcosa di più grande.

Se generi 1 miliardo di UUID al secondo, ci vorranno circa 36 anni per ottenere una probabilità di collisione del 10%.

Alla fine, ci sarà probabilmente una collisione tra l’insieme di UUID generati nel corso della storia umana. Tuttavia, la probabilità che UUID in collisione vengano utilizzati per lo stesso scopo è estremamente piccola, quindi nella pratica non ci sono problemi.

In generale, sì, è sicuro assumere.

Se il tuo generatore GUID è veramente casuale, le possibilità di uno scontro all’interno di 1000 GUID sono straordinariamente piccole.

Ovviamente, questo presuppone un buon generatore GUID. Quindi la domanda è davvero su quanto ti fidi dello strumento che stai usando per generare GUID e ha i suoi test?

Un’analisi della possibilità di collisione è disponibile su Wikipedia: http://en.wikipedia.org/wiki/Uuid#Random_UUID_probability_of_duplicates

Come menzionato nel link, questo sarà influenzato dalle proprietà del generatore di numeri casuali.

C’è anche la possibilità di un bug nel codice del generatore GUID; mentre le probabilità sono basse, probabilmente sono più alte delle probabilità di una collisione basata sulla matematica.

Un filtro Bloom potrebbe essere appropriato; può rapidamente dirti se un GUID è unico, ma c’è una possibilità per una falsa indicazione di una collisione. Un metodo alternativo se stai testando un batch alla volta è quello di ordinare il batch e confrontare ogni elemento successivo.

Mentre una collisione è ansible, è ALTAMENTE improbabile. (Matematica qui .) È lecito ritenere che siano in realtà distinti.

Di solito è un’ipotesi abbastanza sicura.

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

Un GUID è unico al 100% delle volte?