Un GUID è unico il 100% delle volte?

https://stackoverflow.com/questions/39771

09-06-2019
|

Domanda

Rimarrà unico su più thread?

Soluzione

Mentre ogni GUID generato non è garantito per essere unico, il numero totale di chiavi univoci (2¹²⁸ o 3,4 × 10³⁸) è così grande che la probabilità dello stesso numero generato due volte è molto piccola.Ad esempio, considera l'universo osservabile, che contiene circa 5 × 10²²stelle;Ogni stella potrebbe quindi avere 6,8 × 10¹⁵ GUID universalmente univoci.

Da Wikipedia.

Questi sono alcuni articoli utili su come viene creato un GUID (per .NET) e su come ottenere lo stesso GUID nella situazione giusta.

https://ericlippert.com/2012/04/24/guida-guida-parte-uno/

https://ericlippert.com/2012/04/30/guida-guida-parte-due/

https://ericlippert.com/2012/05/07/guida-guida-parte-tre/

Altri suggerimenti

La risposta semplice è sì.

Raymond Chen ha scritto a ottimo articolo sui GUID e perché le sottostringhe di GUID lo sono non unico garantito.L'articolo approfondisce il modo in cui vengono generati i GUID e i dati che utilizzano per garantire l'unicità, il che dovrebbe essere abbastanza approfondito nella spiegazione Perché sono :-)

Se hai paura degli stessi valori GUID, mettine due uno accanto all'altro.

Guid.NewGuid().ToString() + Guid.NewGuid().ToString();

Se sei troppo paranoico, mettine tre.

Come nota a margine, stavo giocando con i GUID del volume in Windows XP.Questo è un layout di partizione molto oscuro con tre dischi e quattordici volumi.

\\?\Volume{23005604-eb1b-11de-85ba-806d6172696f}\ (F:)
\\?\Volume{23005605-eb1b-11de-85ba-806d6172696f}\ (G:)
\\?\Volume{23005606-eb1b-11de-85ba-806d6172696f}\ (H:)
\\?\Volume{23005607-eb1b-11de-85ba-806d6172696f}\ (J:)
\\?\Volume{23005608-eb1b-11de-85ba-806d6172696f}\ (D:)
\\?\Volume{23005609-eb1b-11de-85ba-806d6172696f}\ (P:)
\\?\Volume{2300560b-eb1b-11de-85ba-806d6172696f}\ (K:)
\\?\Volume{2300560c-eb1b-11de-85ba-806d6172696f}\ (L:)
\\?\Volume{2300560d-eb1b-11de-85ba-806d6172696f}\ (M:)
\\?\Volume{2300560e-eb1b-11de-85ba-806d6172696f}\ (N:)
\\?\Volume{2300560f-eb1b-11de-85ba-806d6172696f}\ (O:)
\\?\Volume{23005610-eb1b-11de-85ba-806d6172696f}\ (E:)
\\?\Volume{23005611-eb1b-11de-85ba-806d6172696f}\ (R:)
                                     | | | | |
                                     | | | | +-- 6f = o
                                     | | | +---- 69 = i
                                     | | +------ 72 = r
                                     | +-------- 61 = a
                                     +---------- 6d = m

Non è che i GUID siano molto simili ma il fatto che tutti i GUID contengano la stringa "mario".È una coincidenza o c'è una spiegazione dietro a tutto ciò?

Ora, quando cercando su Google la parte 4 nel GUID ho trovato circa 125.000 accessi con GUID di volume.

Conclusione: Quando si tratta di GUID di volume, non sono univoci come gli altri GUID.

Sì, un GUID deve essere sempre univoco.Si basa sia sull'hardware che sul tempo, oltre ad alcuni bit extra per garantire che sia unico.Sono sicuro che teoricamente sia possibile ritrovarsi con due identici, ma estremamente improbabile in uno scenario reale.

Ecco un ottimo articolo di Raymond Chen su Guids:

https://blogs.msdn.com/oldnewthing/archive/2008/06/27/8659071.aspx

Non dovrebbe succedere.Tuttavia, quando .NET è sottoposto a un carico pesante, è possibile ottenere guide duplicate.Ho due server Web diversi che utilizzano due server SQL diversi.Sono andato a unire i dati e ho scoperto di avere 15 milioni di guide e 7 duplicati.

Le guide sono statisticamente uniche.Le probabilità che due client diversi generino lo stesso Guid sono infinitesimamente piccole (supponendo che non vi siano bug nel codice di generazione del Guid).Potresti anche preoccuparti che il tuo processore abbia problemi a causa di un raggio cosmico e decidere che 2+2=5 oggi.

Più thread che allocano nuove guide otterranno valori univoci, ma dovresti verificare che la funzione che stai chiamando sia thread-safe.In quale ambiente si trova?

Eric Lippert ha scritto una serie di articoli molto interessanti sui GUID.

Ci sono nell'ordine 2³⁰ Personal Computers nel mondo (e ovviamente molti dispositivi portatili o dispositivi di elaborazione non PC che hanno più o meno gli stessi livelli di potenza di calcolo, ma lasciamo ignorarli).Supponiamo che abbiamo messo tutti quei PC nel mondo al compito di generare GUID;se ciascuno può generarne, diciamo, 2²⁰ Guids al secondo poi dopo solo circa 2⁷² secondi -- centocinquanta trilioni di anni -- avrai un molto alto possibilità di generare una collisione con il tuo GUID specifico.E le probabilità di collisione diventano abbastanza bene dopo solo trenta trilioni di anni.

Teoricamente no, non sono unici.È possibile generare una guida identica più e più volte.Tuttavia, le probabilità che ciò accada sono così basse che si può presumere che siano uniche.

Ho letto in precedenza che le probabilità sono così basse che dovresti davvero preoccuparti di qualcos'altro, come la combustione spontanea del tuo server o altri bug nel tuo codice.Cioè, presumi che sia unico e non creare alcun codice per "catturare" i duplicati: dedica il tuo tempo a qualcosa che è più probabile che accada (ad es. nulla altro).

IO fatto un tentativo per descrivere l'utilità dei GUID al pubblico del mio blog (membri della famiglia non tecnici).Da lì (tramite Wikipedia), le probabilità di generare un GUID duplicato:

1 su 2^128
1 su 340 UNDECILLION (Non preoccuparti, non è nel quiz)
1 su 3,4 × 10^38
1 su 340.000.000.000.000.000.000.000.000.000.000.000.000

Nessuno sembra menzionare la matematica effettiva della probabilità che ciò accada.

Innanzitutto, supponiamo di poter utilizzare l'intero spazio a 128 bit (Guid v4 utilizza solo 122 bit).

Sappiamo che la probabilità generale di NON ottenere un duplicato n scelte è:

(1-1/2¹²⁸)(1-2/2¹²⁸)...(1-(n-1)/2¹²⁸)

Poiché 2¹²⁸ è molto molto più grande di n, possiamo approssimarlo a:

(1-1/2¹²⁸)^n(n-1)/2

E perché possiamo supporre n è molto molto più grande di 0, possiamo approssimarlo a:

(1-1/2¹²⁸)^{n^2/2}

Ora possiamo equiparare questo alla probabilità "accettabile", diciamo l'1%:

(1-1/2¹²⁸)^{n^2/2} = 0.01

Per il quale risolviamo n e prendi:

n = sqrt(2* log 0,01 / log (1-1/2¹²⁸))

Quale sarà Wolfram Alpha 5.598318 × 10¹⁹

Per mettere quel numero in prospettiva, prendiamo 10000 macchine, ciascuna con una CPU a 4 core, che eseguono 4 Ghz e impiegano 10000 cicli per generare un Guid e non fanno nient'altro.Ci vorrebbero quindi circa 111 anni prima che generino un duplicato.

Da http://www.guidgenerator.com/online-guid-generator.aspx

Cos'è un GUID?

GUID (o UUID) è l'acronimo di "Globally Unique Identifier" (o "Universally Unique Identifier").È un numero intero a 128 bit utilizzato per identificare le risorse.Il termine GUID viene generalmente utilizzato dagli sviluppatori che lavorano con le tecnologie Microsoft, mentre UUID viene utilizzato ovunque.

Quanto è univoco un GUID?

128 bit è abbastanza grande e l'algoritmo di generazione è sufficientemente unico che se venissero generati 1.000.000.000 di GUID al secondo per 1 anno, la probabilità di un duplicato sarebbe solo del 50%.Oppure, se ogni essere umano sulla Terra generasse 600.000.000 di GUID, ci sarebbe solo il 50% di probabilità di un duplicato.

MSDN:

Esiste una probabilità molto bassa che il valore del nuovo Guid sia tutto zero o uguale a qualsiasi altro Guid.

Se l'orologio di sistema è impostato correttamente e non si è bloccato e se la scheda NIC ha il proprio MAC (ad es.non hai impostato un MAC personalizzato) e il fornitore della scheda NIC non ha riciclato i MAC (cosa che non dovrebbero fare ma che è noto che si verifica) e se la funzione di generazione del GUID del sistema è implementata correttamente, il sistema lo farà non generare mai GUID duplicati.

Se tutti coloro che generano GUID sulla terra seguono queste regole, i tuoi GUID saranno unici a livello globale.

In pratica, il numero di persone che infrangono le regole è basso ed è improbabile che i loro GUID "sfuggano".I conflitti sono statisticamente improbabili.

Ho riscontrato un GUID duplicato.

Utilizzo lo scanner desktop Neat Receipts e viene fornito con un software di database proprietario.Il software dispone di una funzionalità di sincronizzazione con il cloud e continuavo a ricevere un errore durante la sincronizzazione.Uno sguardo ai registri ha rivelato la frase fantastica:

"errori":[{"codice":1,"messaggio":"creator_guid:è già preso "," guida ":" C83E5734-D77A-4B09-B8C1-9623CAC7B167 "}]}

Ero un po' incredulo, ma sicuramente, quando ho trovato un modo per accedere al mio database locale di Neakworks e ho cancellato il record contenente quel GUID, l'errore ha smesso di verificarsi.

Quindi, per rispondere alla tua domanda con prove aneddotiche, no.È possibile un duplicato.Ma è probabile che il motivo per cui ciò è accaduto non sia dovuto al caso, ma al mancato rispetto in qualche modo della pratica standard.(Non sono così fortunato) Tuttavia, non posso dirlo con certezza.Non è il mio software.

Il loro supporto clienti è stato ESTREMAMENTE cortese e disponibile, ma non devono aver mai riscontrato questo problema prima perché dopo più di 3 ore al telefono con loro, non hanno trovato la soluzione.(Per inciso, sono molto colpito da Neat e questo problema tecnico, per quanto frustrante, non ha cambiato la mia opinione sul loro prodotto.)

Un GUID è unico il 100% delle volte?

Non è garantito, poiché esistono diversi modi per generarne uno.Tuttavia, puoi provare a calcolare la possibilità di creare due GUID identici e avrai un'idea:un GUID ha 128 bit, quindi ce ne sono 2¹²⁸ GUID distinti – tanto più di quante siano le stelle nell'universo conosciuto.Leggi il articolo di Wikipedia per ulteriori dettagli.

Gli algoritmi GUID vengono generalmente implementati in base alla specifica GUID v4, che è essenzialmente una stringa pseudo-casuale.Purtroppo, questi rientrano nella categoria di "probabilmente non unico", da Wikipedia (non so perché così tante persone ignorano questa parte):"...altre versioni GUID hanno proprietà e probabilità di unicità diverse, che vanno dall'unicità garantita alla probabile non unicità."

Le proprietà pseudo-casuali del JavaScript di V8 Math.random() sono TERRIBILI in termini di unicità, con collisioni che spesso arrivano dopo solo poche migliaia di iterazioni, ma V8 non è l'unico colpevole.Ho visto collisioni GUID nel mondo reale utilizzando implementazioni PHP e Ruby dei GUID v4.

Poiché sta diventando sempre più comune scalare la generazione di ID su più client e cluster di server, l'entropia subisce un grosso colpo: le possibilità che lo stesso seme casuale venga utilizzato per generare un ID aumentano (il tempo viene spesso utilizzato come seme casuale in generatori pseudo-casuali) e le collisioni GUID passano da "probabilmente non univoche" a "molto probabile che causino molti problemi".

Per risolvere questo problema, ho deciso di creare un algoritmo ID che potesse scalare in modo sicuro e fornire migliori garanzie contro le collisioni.Lo fa utilizzando il timestamp, un contatore client in memoria, l'impronta digitale del client e caratteri casuali.La combinazione di fattori crea una complessità additiva particolarmente resistente alle collisioni, anche se la si ridimensiona su un numero di host:

http://usecuid.org/

Ho riscontrato che i GUID non erano univoci durante i test unitari multi-thread/multi-processo (anche?).Immagino che ciò abbia a che fare, a parità di tutte le altre cose, con l'identico seeding (o mancanza di seeding) di generatori pseudo casuali.Lo stavo usando per generare nomi di file univoci.Ho scoperto che il sistema operativo è molto più bravo a farlo :)

Avviso di pesca alla traina

Chiedi se i GUID sono unici al 100%.Dipende dal numero di GUID tra cui deve essere univoco.Poiché il numero di GUID si avvicina all'infinito, la probabilità di GUID duplicati si avvicina al 100%.

In un senso più generale, questo è noto come "problema del compleanno" o "paradosso del compleanno".Wikipedia ha una panoramica abbastanza buona su:Wikipedia - Problema del compleanno

In termini molto approssimativi, la radice quadrata della dimensione del pool è un'approssimazione approssimativa di quando ci si può aspettare una probabilità del 50% di un duplicato.L'articolo include una tabella delle probabilità relativa alla dimensione del pool e varie probabilità, inclusa una riga per 2^128.Quindi, per una probabilità di collisione dell'1% ti aspetteresti di scegliere casualmente 2,6 * 10 ^ 18 numeri a 128 bit.Una probabilità del 50% richiede 2,2*10^19 scelte, mentre SQRT(2^128) è 1,8*10^19.

Naturalmente, questo è solo il caso ideale di un processo veramente casuale.Come altri hanno già detto, molto dipende da questo casuale aspetto: quanto sono buoni il generatore e il seme?Sarebbe bello se ci fosse un supporto hardware per assistere in questo processo che sarebbe più a prova di proiettile, tranne per il fatto che qualsiasi cosa può essere falsificata o virtualizzata.Ho il sospetto che questo potrebbe essere il motivo per cui gli indirizzi MAC/timestamp non sono più incorporati.

La risposta di "Un GUID è unico al 100%?" è semplicemente "NO" .

Se desideri l'unicità del GUID al 100%, procedi come segue.
1. generare GUID
2. controlla se quel GUID è Esiste nella colonna della tabella in cui stai cercando l'unicità
3. se esiste, vai al passaggio 1 altrimenti al passaggio 4
4. utilizzare questo GUID come univoco.

La parte più difficile non riguarda la generazione di una Guid duplicata.

La parte più difficile è progettare un database in cui archiviare tutti quelli generati per verificare se sono effettivamente duplicati.

Dal WIKI:

Ad esempio, il numero di UUID casuali della versione 4 che devono essere generati per avere una probabilità del 50% di almeno una collisione è 2,71 quintilioni, calcolato come segue:

inserisci qui la descrizione dell'immagine

Questo numero equivale a generare 1 miliardo di UUID al secondo per circa 85 anni, e un file contenente così tanti UUID, a 16 byte per UUID, sarebbe circa 45 exabyte, molte volte più grande dei più grandi database attualmente esistenti, che sono su dell'ordine di centinaia di petabyte

GUID sta per Global Unique Identifier

In breve:(l'indizio è nel nome)

In dettaglio:I GUID sono progettati per essere univoci;vengono calcolati utilizzando un metodo casuale basato sull'orologio del computer e sul computer stesso, se si creano molti GUID nello stesso millisecondo sulla stessa macchina è possibile che corrispondano ma per quasi tutte le normali operazioni dovrebbero essere considerati unici.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow