Quando hai veramente costretti ad usare UUID come parte del disegno?

https://stackoverflow.com/questions/703035

22-08-2019
|

Domanda

Io non vedo proprio il punto di UUID . So che la probabilità di una collisione è in modo efficace nil , ma in modo efficace nil è nemmeno vicino ad impossibile.

Qualcuno può dare un esempio in cui non hai scelta, ma di utilizzare UUID? Da tutti gli usi che ho visto, posso vedere un progetto alternativo senza UUID. Certo il design potrebbe essere un po 'più complicato, ma almeno non ha un non-zero probabilità di fallimento.

UUID odora di variabili globali per me. Ci sono molti modi variabili globali rendono design più semplice, ma il suo design solo pigro.

Soluzione

ho scritto l'UUID generatore / parser per Ruby, quindi mi ritengo di essere ragionevolmente ben informati sull'argomento. Ci sono quattro grandi versioni UUID:

Versione 4 UUIDs sono essenzialmente solo 16 byte di casualità tirati da un generatore di numeri casuali crittograficamente sicuro, con un certo bit-girarsi per identificare la versione UUID e variante. Queste sono estremamente improbabile che si scontrano, ma potrebbe succedere se si utilizza un PRNG o se semplicemente capita di avere davvero, davvero, davvero, davvero, davvero sfortuna.

Versione 5 e versione 3 UUID utilizzano lo SHA1 e le funzioni di hash MD5, rispettivamente, di combinare uno spazio dei nomi con un pezzo di dati già unici per generare un UUID. In questo modo, per esempio, permetterà di produrre un UUID da un URL. Le collisioni qui sono possibili solo se la funzione hash sottostante ha anche una collisione.

Versione 1 UUID sono i più comuni. Usano l'indirizzo della scheda di rete MAC (che a meno che spoofing, dovrebbe essere unico), oltre a un timestamp, più la solita bit-giocherellando per generare l'UUID. Nel caso di una macchina che non ha un indirizzo MAC, i nodi 6 byte sono generate con un generatore di numeri casuali crittograficamente sicuro. Se due UUID vengono generati in sequenza abbastanza veloce che il timestamp corrisponde alla UUID precedente, il timestamp viene incrementato di 1. collisioni non dovrebbe avvenire a meno che una delle condizioni seguenti: L'indirizzo MAC è falso; Una macchina che esegue due diverse applicazioni generatrici UUID UUID produce esattamente nello stesso momento; Due macchine senza una scheda di rete o senza accesso a livello utente all'indirizzo MAC hanno la stessa sequenza casuale nodo, e generare UUID esattamente nello stesso momento; Siamo a corto di byte per rappresentare il timestamp e rollover di nuovo a zero.

Realisticamente, nessuno di questi eventi si verificano per caso all'interno dello spazio ID delle singole applicazioni. A meno che non si sta accettando gli ID, diciamo, una scala di Internet a livello, o con un ambiente attendibile dove gli individui malintenzionati potrebbero essere in grado di fare qualcosa di male nel caso di una collisione ID, non è solo qualcosa che si dovrebbe preoccupare. E 'fondamentale capire che se vi capita di generare la stessa versione 4 UUID come io, nella maggior parte dei casi, non importa. Ho generato l'ID in uno spazio ID completamente diversa dalla vostra. La mia applicazione non saprà mai la collisione in modo che la collisione non ha importanza. Francamente, in un unico spazio di applicazione senza attori maligni, l'estinzione di ogni forma di vita sulla terra avverrà molto prima di avere una collisione, anche su una versione 4 UUID, anche se si sta generando un paio di UUID bel al secondo.

Inoltre, 2 ^ 64 * 16 è 256 exabyte. Come in, si avrebbe bisogno di memorizzare 256 exabyte valore di ID prima di avere una probabilità del 50% di una collisione ID in un unico spazio di applicazione.

Altri suggerimenti

La cosa che si acquista UUID che è molto difficile fare altrimenti è quello di ottenere un identificatore univoco senza dover consultare o coordinare con un'autorità centrale . Il problema generale di essere in grado di ottenere una cosa del genere senza una sorta di infrastrutture gestito è il problema gli UUID risolvere.

Ho letto che secondo il paradosso di compleanno la possibilità di un verificano UUID collisione è del 50% una volta 2 ^ 64 UUID sono stati generati. Ora 2 ^ 64 è un bel numero grande, ma una probabilità del 50% di collisione appare troppo rischioso (per esempio, il numero di UUID bisogno di esistere prima che ci sia una probabilità del 5% di collisione - anche questo sembra troppo grande di una probabilità) .

Il problema di questa analisi è duplice:

UUID non sono del tutto casuale - ci sono componenti importanti del UUID che sono ora e / o location-based. Quindi, per avere una reale possibilità di una collisione, gli UUID collisione bisogno Tobe generato al tempo stesso esatto da diversi generatori UUID. Direi che, mentre v'è una ragionevole possibilità che diversi UUID di potrebbe essere generato, allo stesso tempo, non c'è abbastanza gunk altri (compresi luogo o bit casuali) per rendere il likeyhood di una collisione tra questo piccolo insieme di UUID quasi impossibile .
in senso stretto, UUID solo bisogno di essere unico tra i set di altri UUID che essi possano essere confrontati con. Se si sta generando un UUID da utilizzare come chiave di database, non importa se da qualche altra parte in un universo alternativo male che lo stesso UUID viene utilizzato per identificare un'interfaccia COM. Proprio come sarà causa nessuna confusione se c'è qualcuno (o qualcosa) altro nome "Michael Burr" su Alpha-Centauri.

Tutto ha un non-zero probabilità di fallimento. Vorrei concentrarmi su di gran lunga più probabile che si verifichi problemi (vale a dire quasi tutto si può pensare) che la collisione di UUID

L'accento sulla "ragionevolmente" o, come dici tu, "efficace": è abbastanza buono come funziona il mondo reale. La quantità di lavoro computazionale coinvolti nel coprire quel divario fra "pressoché unica" e "veramente unico" è enorme. L'unicità è una curva con rendimenti decrescenti. Ad un certo punto su quella curva, c'è una linea tra cui "abbastanza unico" è ancora accessibile, e poi abbiamo la curva molto ripida. Il costo di aggiunta più unicità diventa abbastanza grande. unicità Infinite ha un costo infinito.

UUID / GUID è, relativamente parlando, un modo computazionalmente semplice e veloce per generare un ID che può essere ragionevolmente presume di essere universalmente univoco. Questo è molto importante in molti sistemi che hanno bisogno di integrare dati da sistemi precedentemente non connessi. Per esempio: se si dispone di un Content Management System che gira su due piattaforme diverse, ma ad un certo punto c'è bisogno di importare il contenuto da un sistema nell'altro. Se non si desidera gli ID per cambiare, in modo che le riferimenti tra dati dal sistema A rimangono intatte, ma non si vuole collisioni con i dati creati nel sistema di B. Un UUID risolve questo.

Non è mai assolutamente necessario per creare un UUID. È comunque conveniente avere uno standard in cui non in linea gli utenti possono ciascuna generare una chiave per qualcosa con una bassissima probabilità di collisione.

Questo può aiutare nella risoluzione replica del database ecc ...

Sarebbe facile per in linea utenti di generare chiavi univoche per qualcosa senza il sovraccarico o la possibilità di collisione, ma questo non è ciò che sono per UUID.

In ogni modo, una parola sulla probabilità di collisione, tratta da Wikipedia:

Per mettere questi numeri in prospettiva, il proprio rischio annuale di essere colpiti da un meteorite è stimato una probabilità su 17 miliardi, equivalenti per le probabilità di creazione di alcune decine di bilioni di UUID in un anno e avere un duplicato. In altre parole, solo dopo la generazione 1 miliardo UUID ogni secondo per i prossimi 100 anni, la probabilità di creare solo un duplicato sarebbe di circa il 50%.

C'è anche una non-zero probabilità che ogni particella nel vostro corpo sarà contemporaneamente tunnel attraverso la sedia si sta seduto su e vi ritroverete improvvisamente seduto sul pavimento.

Ti preoccupi di questo?

Un esempio classico è quando si replicano tra i due database.

dB (A) inserisce un record con int ID 10 e al tempo stesso DB (B) crea un un record con ID di 10. Si tratta di una collisione.

Con UUID questo non accadrà in quanto non corrisponderanno. (Quasi certamente)

Ho un sistema per evitare UUID. Impostare un server da qualche parte e lo hanno in modo che ogni volta che qualche pezzo di software vuole un identificatore univoco universale, si mettono in contatto quel server e porge uno fuori. Semplice!

Se non fosse che ci sono alcuni problemi reali pratici con questo, anche se ignoriamo cattiveria a titolo definitivo. In particolare, il server può fallire o diventare irraggiungibile da parte di Internet. Si occupano di errore del server richiede la replica, e questo è molto difficile per ottenere destra (vedi la letteratura sul algoritmo Paxos del motivo per cui la costruzione del consenso è imbarazzante) ed è piuttosto lento troppo. Inoltre, se tutti i server sono irraggiungibili da una particolare parte della 'rete, non dei client connessi a quella sottorete sarà in grado di fare nulla perché saranno tutti in attesa di nuovi ID.

Quindi ... usare un semplice algoritmo probabilistico per generare loro che è improbabile che a fallire durante la vita della Terra, o (fondo e) costruzione di una grande infrastruttura che sta per essere una distribuzione valle di lacrime e hanno frequenti guasti. Io so quale mi piacerebbe andare per.

Se basta guardare le alternative per esempio per una semplice applicazione di database, di dover interrogare il database ogni volta prima di creare un nuovo oggetto, presto scoprire che usando UUID può efficacemente ridurre la complessità del sistema. Certo - se si utilizza chiavi int sono a 32 bit, che memorizza in un quarto del UUID 128bit. Concesso - algoritmi di generazione di UUID occupano più potenza di calcolo di un semplice incremento di un numero. Ma a chi importa? L'overhead di gestione di una "autorità" per assegnare i numeri altrimenti univoco facilmente supera quella di ordini di grandezza, a seconda del vostro spazio ID unicità previsto.

On UUID == disegno pigro

Non sono d'accordo i suoi circa prendere i tuoi combattimenti. Se un UUID duplicato è statisticamente impossibile e la matematica è provata allora perché preoccuparsi? Passare del tempo progettare intorno al vostro piccolo sistema N UUID di generazione è impraticabile, ci sono sempre una dozzina di altri modi per migliorare il sistema.

non ho ricevuto tutti i discorsi circa la probabilità di collisione. Non mi importa di collisione. Mi interessa prestazioni però.

https://dba.stackexchange.com/a/119129/33649

UUID sono un disastro prestazioni per tabelle molto grandi. (200K righe è   Non "molto grande".)

Il tuo # 3 è davvero male quando il SET charcter è utf8 - CHAR (36)   occupa 108 byte!

UUID (GUID) sono molto "random". Il loro utilizzo sia come unica o un   PRIMARY KEY su grandi tavoli è molto inefficiente. Questo è causa di   dover passare intorno al tavolo / indice ogni volta che si inserisce un nuovo UUID   o SELECT per UUID. Quando la tabella / indice è troppo grande per entrare nella cache   (Vedi innodb_buffer_pool_size, che deve essere più piccolo di RAM,   tipicamente 70%), l'UUID 'next' non può essere memorizzata nella cache, quindi un disco lento   colpire. Quando la tabella / indice è 20 volte più grande cache, solo 1 / 20th   (5%) di visite vengono memorizzati nella cache - sei I / O-bound
.
Quindi, non usare gli UUID a meno che una

si dispone di tabelle "piccoli", o si ha realmente bisogno di loro a causa della generazione   ID univoci da luoghi diversi (e non hanno capito un altro modo   per farlo). Maggiori info su UUID: http://mysql.rjweb.org/doc.php/uuid (E '   include funzioni per la conversione tra UUID 36-char standard e   BINARIO (16).)

Avendo sia un UNICO AUTO_INCREMENT e un esclusivo UUID nella stessa   tavolo è uno spreco.

Quando si verifica un INSERT, tutte le chiavi univoche / primarie devono essere controllati per   duplicati. O chiave unica è sufficiente per il requisito di InnoDB   di avere una chiave primaria. BINARIO (16) (16 byte) è piuttosto ingombrante (a   argomento contro diventando così il PK), ma non è così male. l'ingombro   che conta quando si hanno le chiavi secondarie. InnoDB vira in silenzio il PK   sull'estremità di ogni chiave secondaria. La lezione principale è quello di   ridurre al minimo il numero di tasti secondari, specialmente per molto grande   tabelle. Per il confronto: INT UNSIGNED è 4 byte con gamma di 0..4   miliardi. BIGINT è di 8 byte.

Al mio ultimo lavoro, ci stavano ottenendo oggetti da parte di terzi che sono stati identificati in modo univoco con UUID. Ho messo in un'UUID-> intero lungo tabella di ricerca e utilizzato lungo intero come le mie chiavi primarie perché era il modo più veloce in questo modo.

Usando l'algoritmo versione 1 sembra che sia impossibile collisione sotto il vincolo che meno di 10 UUID per millisecondo sono generati dallo stesso indirizzo MAC

Concettualmente, l'originale (versione 1) schema di generazione di UUID doveva concatenare la versione con l'UUID indirizzo MAC del computer che è generare l'UUID, e con la numero di intervalli di 100 nanosecondi dopo l'adozione della Gregoriana Calendario in Occidente. In pratica, il algoritmo reale è più complicato. Questo schema è stato criticato in che non è sufficientemente 'opachi'; si rivela sia l'identità del computer che ha generato l'UUID e il momento in cui lo ha fatto.

Qualcuno mi corregga se interpretato male come funziona

Per quelli dicendo che UUID sono cattiva progettazione perché potrebbe (ad un certo ridicolmente piccola probabilità) si scontrano, mentre il vostro DB generato tasti non ... sai la possibilità di errore umano causando un collisione sul vostro DB ha generato chiavi a causa di qualche necessità ONU-forseen è di gran lunga di gran lunga superiore la probabilità di collisione UUID4. We so che se il db è ricreato inizierà ids a 1 ancora una volta, e come molti di noi hanno dovuto ricreare un tavolo quando eravamo sicuri che non avremmo mai mai bisogno di? Avevo messo i miei soldi su sicurezza UUID quando roba comincia ad andare male con sconosciuti-incognite qualsiasi giorno.

A parte i casi in cui si deve usare qualcun altro API che richiede un UUID, naturalmente c'è sempre un'altra soluzione. Ma saranno queste alternative risolvere tutti i problemi che UUID fare? Will si finisce per l'aggiunta di più strati di hack, ciascuna per risolvere un problema diverso, quando si potrebbe avere risolto tutti in una volta?

Sì, è teoricamente possibile per UUID a scontrano. Come altri hanno notato, è ridicolmente improbabile al punto che semplicemente non vale la pena considerare. Non è mai successo fino ad oggi e molto probabilmente non lo farà mai. Non pensarci più.

Il modo più "ovvio" per evitare collisioni è di lasciare che un singolo server di generare ID univoco su ogni inserto, che ovviamente crea seri problemi di prestazioni e non risolve il problema connesso generazione a tutti. Oops.

L'altra soluzione "ovvia" è un'autorità centrale che distribuisce blocchi di numeri unici in anticipo, che è essenzialmente quello UUID V1 fa utilizzando l'indirizzo MAC della macchina generatrice (tramite l'IEEE OUI). Ma duplicato indirizzi MAC accadono perché ogni centrali viti di autorità fino alla fine, quindi, in pratica, questo è di gran lunga più probabile che una collisione UUID V4. Oops.

Il miglior argomento contro l'uso di UUID è che sono "troppo grande", ma uno schema (significativamente) più piccolo inevitabilmente non riescono a risolvere i problemi più interessanti; dimensioni UUID è un effetto collaterale intrinseco della loro utilità a risolvere questi stessi problemi.

E 'possibile che il vostro problema non è grande abbastanza per bisogno di quello che offrono UUID, e in tal caso, si sentono liberi di utilizzare qualcos'altro. Ma se il vostro problema aumenta in modo imprevisto (e la maggior parte fare), si finirà per passare in seguito - e calci te stesso per non usarle, in primo luogo. Perché il design per il fallimento, quando è altrettanto facile da progettare per il successo invece?

UUID incarnano tutte le pratiche di codifica cattivi associati a variabili globali, solo peggio, dal momento che sono variabili superglobali che possono essere distribuiti su diversi pezzi di corredo.

Recentemente ha colpito un tale problema con la sostituzione di una stampante con un modello di rimontaggio esatto, e ha scoperto che nessuno dei software client avrebbe funzionato.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow