Sono possibili collisioni GUID?

Question

Sto lavorando su un database in SQL Server 2000 che utilizza un GUID per ogni utente che utilizza l'app a cui è legato. In qualche modo, due utenti hanno finito con lo stesso GUID. So che microsoft utilizza un algoritmo per generare un GUID casuale che ha una probabilità estremamente bassa di causare collisioni, ma è ancora possibile una collisione?

Answer 1

In sostanza, no. Penso che qualcuno sia andato in rovina con il tuo database. A seconda della versione del GUID che stai utilizzando, il valore è unico (per cose come i GUID versione 1) o sia unico che imprevedibile (per cose come i GUID versione 4). L'implementazione di SQL Server per la funzione NEWID () sembra utilizzare un numero casuale a 128 bit, quindi non si otterrà una collisione.

Per una probabilità dell'1% di collisione, è necessario generare circa 2.600.000.000.000.000.000 GUID.

Answer 2

Fondamentalmente non sono possibili! , le probabilità sono astronomicamente basse .

Ma ... Sono l'unica persona al mondo che conosco, che ha avuto una colisione GUID una volta (sì!).

E ne sono sicuro, e che non è stato un errore.

Come è successo, in una piccola applicazione in esecuzione su Pocket PC, alla fine di un'operazione deve essere emesso un comando che ha un GUID generato. Il comando dopo che è stato eseguito sul server è stato archiviato in una tabella comandi sul server insieme alla data di esecuzione. Un giorno, durante il debug, ho emesso il comando module (con il GUID appena generato allegato) e non è successo nulla. L'ho fatto di nuovo (con lo stesso guid, perché il guid è stato generato solo una volta all'inizio dell'operazione), e ancora, e niente, finalmente cercando di scoprire perché il comando non viene eseguito, ho controllato la tabella dei comandi, e lo stesso GUID di quello attuale è stato inserito 3 settimane fa. Non credendo a ciò, ho ripristinato un database dal backup di 2 settimane e il guid era lì. Controllato il codice, il nuovo guid è stato appena generato senza alcun dubbio. La collisione di Pow guid, è avvenuta una sola volta, ma vorrei davvero che avrei vinto al lotto, la possibilità è maggiore :).

Modifica: ci sono alcuni fattori che potrebbero aver aumentato notevolmente le possibilità che ciò accada, l'applicazione era in esecuzione sull'emulatore PocketPC e l'emulatore ha una funzione di salvataggio dello stato, il che significa che ogni volta che lo stato viene ripristinato all'ora locale viene anche ripristinato e il guid si basa sul timer interno .... anche l'algoritmo di generazione guid per il framework compatto potrebbe essere meno completo rispetto ad esempio a quello COM ...

Answer 3

Sono teoricamente possibili, ma con 3.4E38 possibili numeri, se si creano decine di trilioni di GUID in un anno, la possibilità di avere un duplicato è 0,00000000006 ( Fonte ).

Se due utenti finissero con lo stesso GUID, scommetterei che c'è un bug nel programma che sta causando la copia o la condivisione dei dati.

Answer 4

Per prima cosa diamo un'occhiata alla possibilità di collisione di due GUID. Non è, come hanno affermato altre risposte, 1 su 2 ^ 128 (10 ^ 38) a causa del paradosso del compleanno di , il che significa che per una probabilità del 50% di due GUID che si scontrano la probabilità è in realtà 1 su 2 ^ 64 (10 ^ 19) che è molto più piccola. Tuttavia, si tratta ancora di un numero molto elevato e pertanto la probabilità di collisione supponendo che si stia utilizzando un numero ragionevole di GUID è bassa.

Nota anche che i GUID non contengono un timestamp o l'indirizzo MAC, come sembrano credere anche molte persone. Questo era vero per i GUID v1 ma ora vengono utilizzati i GUID v4, che sono semplicemente un numero pseudo-casuale il che significa che la possibilità di collisione è probabilmente maggiore perché non sono più univoci per un tempo e una macchina.

Quindi essenzialmente la risposta è sì, le collisioni sono possibili. Ma sono altamente improbabili.

Modifica: risolto per dire 2 ^ 64

Answer 5

Le possibilità che due GUID casuali si scontrino (~ 1 su 10 ^ 38) sono inferiori alla possibilità di non rilevare un pacchetto TCP / IP corrotto (~ 1 su 10 ^ 10). http: //wwwse.inf.tu-dresden .de / data / corsi / SE1 / SE1-2004-lec12.pdf , pagina 11. Questo vale anche per unità disco, unità cd, ecc ...

I GUID sono statisticamente univoci e i dati letti dal database sono statisticamente corretti.

Answer 6

Vorrei considerare il rasoio di Occam come una buona guida in questo caso. È incredibilmente improbabile che tu abbia una collisione GUID. È molto più probabile che tu abbia un bug o qualcuno che scherzi con i tuoi dati.

Answer 7

Vedi l'articolo Identificatore univoco globale di Wikipedia. Esistono diversi modi per generare GUID. Apparentemente il vecchio modo (?) Utilizzava l'indirizzo Mac, un timestamp fino a un'unità molto corta e un contatore univoco (per gestire generazioni veloci sullo stesso computer), quindi renderli duplicati è quasi impossibile. Ma questi GUID sono stati eliminati perché potevano essere utilizzati per rintracciare gli utenti ...

Non sono sicuro del nuovo algoritmo utilizzato da Microsoft (l'articolo dice che è possibile prevedere una sequenza di GUID, sembra che non utilizzino più il timestamp? L'articolo Microsoft collegato sopra dice qualcos'altro ...).

Ora, i GUID sono attentamente progettati per essere, per nome, globalmente unici, quindi rischierò che sia impossibile o con probabilità molto molto molto basse. Vorrei cercare altrove.

Answer 8

Due macchine Win95 che hanno schede Ethernet con indirizzi MAC duplicati emetteranno GUID duplicati in condizioni strettamente controllate, specialmente se, ad esempio, l'alimentazione si interrompe nell'edificio ed entrambi si avviano esattamente allo stesso tempo.

Answer 9

Conosco persone come la risposta positiva che i GUID sono magici e garantiti come unici, ma in realtà la maggior parte dei GUID sono solo numeri casuali a 121 bit (sette dei bit sono sprecati nella formattazione). Se non ti senti a tuo agio con un grande numero casuale, non dovresti sentirti a tuo agio con un GUID.

Answer 10

Il codice utilizzato per generare un GUID potrebbe contenere un bug? Sì, certo che potrebbe. Ma la risposta è la stessa di un bug del compilatore: il tuo codice è che gli ordini di grandezza hanno maggiori probabilità di essere difettosi, quindi guarda prima lì.

Answer 11

Certo che è possibile .... Probabile? Non è probabile, ma è possibile.

Ricorda, la stessa macchina sta generando ogni GUID (il server), quindi molta della "casualità" che si basa su informazioni specifiche della macchina viene perso.

Answer 12

Solo per grins, prova il seguente script ... (funziona su SQL 2005, non sono sicuro di 2000)

declare @table table
(
    column1 uniqueidentifier default (newid()),
    column2 int,
    column3 datetime default (getdate())
)

declare @counter int

set @counter = 1

while @counter <= 10000
begin
    insert into @table (column2) values (@counter)
    set @counter = @counter + 1
end

select * from @table

select * from @table t1 join @table t2 on t1.column1 = t2.column1 and t1.column2 != t2.column2

L'esecuzione ripetuta (richiede meno di un secondo) produce un intervallo abbastanza ampio dalla prima selezione, anche con un intervallo di tempo ESTREMAMENTE breve. Finora la seconda selezione non ha prodotto nulla.

Answer 13

Impossibile se gli utenti hanno macchine diverse con schede di rete, e anche se non è ancora un rischio quasi teorico estremamente marginale.

Personalmente guarderei altrove poiché è più probabile un bug piuttosto che uno scontro GUID ...

Fornendo ovviamente che non tagliare i bit dal GUID per renderlo più breve.

Answer 14

Certo che è possibile, e forse anche probabile. Non è come se ogni GUID fosse in una porzione casuale del possibile spazio numerico. Nel caso in cui due thread abbiano tentato di generarne uno contemporaneamente, escludendo una sorta di funzione GUID centralizzata con un semaforo attorno, potrebbero finire con lo stesso valore.

Answer 15

Premetto questo con " Non sono una persona in rete, quindi potrei fare frasi completamente incoerenti seguendo. " ;.

Quando lavoravo all'Illinois State University, avevamo due desktop Dell, ordinati in momenti diversi. Abbiamo messo il primo sulla rete, ma quando abbiamo provato a mettere il secondo sulla rete abbiamo iniziato a ricevere errori folli. Dopo una lunga risoluzione dei problemi, è stato stabilito che entrambe le macchine stavano producendo lo stesso GUID (non sono sicuro del perché, ma le ha rese entrambe inutilizzabili sulla rete). Dell ha effettivamente sostituito entrambe le macchine come difettose.

Answer 16

È altamente improbabile che ti imbatterai in collisioni GUID se le stai generando attraverso qualcosa come la funzione NEWID () in SQL Server (anche se ovviamente possibile, come sottolineato da altre risposte) . Una cosa che non hanno sottolineato è che in realtà è molto probabile che ti imbatterai in collisioni se stai generando GUID in JavaScript su browser in natura. A volte non solo ci sono problemi nell'RNG in diversi browser, ma ho anche incontrato problemi in cui gli spider di Google sembrano memorizzare nella cache i risultati di funzioni del genere e sono finiti ripetutamente passando lo stesso GUID ai nostri sistemi.

Vedi le varie risposte qui per maggiori dettagli:

Collisioni durante la generazione di UUID in JavaScript?