Quanto sono probabili le collisioni degli identificatori basati su timestamp? [chiuso]

0

Ho ascoltato una discussione sull'uso dei timestamp come identificatori univoci durante l'archiviazione di alcuni dati in un database. La persona A ha sottolineato che c'è il rischio di collisioni. La persona B ha risposto che è molto improbabile che si verifichi con le tariffe di generazione degli identificatori in questione.

La mia domanda è: quanto è probabile? C'è un modo per stimare la probabilità di ottenere una collisione o la quantità di collisioni che si otterranno in un determinato intervallo di tempo?

Sono interessato a entrambe le risposte teoriche e pratiche.

    
posta Miikka 26.12.2015 - 18:31
fonte

3 risposte

13

In primo luogo, perché non stai usando un contatore? Di solito è tutto ciò di cui hai bisogno.

In secondo luogo, dovresti usare uuids anziché i timestamp. Hanno risolto questo problema, e non c'è davvero nessuna buona ragione per provare a risolverlo da solo, potenzialmente aprendo ai problemi.

In terzo luogo, il calcolo che dovresti fare è chiamato problema del compleanno. Il problema del compleanno originale si chiede quanto sia probabile che due persone in un gruppo condividano un compleanno. Dovrebbe essere chiaro che questo è più o meno lo stesso che chiedere quanto sia probabile che due timestamp siano generati allo stesso millisecondo (o qualunque granularità).

A quanto pare, hai solo bisogno di 23 persone per la probabilità che un compleanno condiviso superi il 50%. Questo è molto meno di quanto la maggior parte della gente si aspetti (quindi a volte viene chiamato il paradosso del compleanno). È anche il motivo per cui ci sono buone probabilità che le collisioni siano più probabili di quanto ti aspetti.

Puoi leggere come calcolarlo su Wikipedia o utilizzare il calcolatore online su WolfromAlpha :

Solo per fare un esempio, se generi 10 id al secondo con una granularità di millisecondi, la probabilità di una collisione è 1 su 23. In media, avrai una collisione ogni 23 secondi.

Ma è peggio di così. L'assunto in questa matematica è che ogni possibile compleanno è ugualmente probabile. Non è vero per i compleanni, più persone nascono in primavera. Inoltre non sarà vero per i tuoi timestamp. Stai per diventare molto più pesante in determinati momenti della giornata rispetto ad altri.

La cosa peggiore di tutte è che un improvviso aumento dell'utilizzo, con un conseguente notevole aumento delle probabilità di collisione, è esattamente il tempo in cui non vuoi che si verifichi un misterioso errore casuale.

Non utilizzare i timestamp. Non farlo. Usa uuids che sono stati progettati da persone intelligenti per evitare il problema di collisione.

    
risposta data 26.12.2015 - 19:10
fonte
4

Person A pointed out that there's a risk of collisions. Person B replied that it's very unlikely to happen with the identifier generation rates at question.

Entrambi possono essere corretti per adesso , ma non è giusto che ti importi così tanto. È ciò che succede più tardi che ti farà entrare. Cosa succede quando aumenta la velocità di generazione delle righe? Cosa farai quando qualcuno che ti ha fornito una serie di dati ritorna e dice che è necessario regolare i tempi perché i loro orologi erano sbagliati ei nuovi valori si sovrappongono a quelli di altre righe?

B ammette essenzialmente che è impossibile garantire che non si verifichi una collisione. Se non è in grado di fornire tale garanzia, non può garantire che il suo sistema funzioni correttamente e sarà rispedito al tavolo da disegno per elaborare uno schema per gestirli. Dopo averne trovato uno senza gli stessi rischi (molto probabile che coinvolga il contatore B che non vuole usare), il tasso che si verificano non conta più.

Is there a way to estimate the probability of getting a collision, or the amount of collisions you're going to get in some timespan?

Fornisci informazioni sufficienti, certo, ma ci sono molte cose che sarebbero molto difficili da quantificare in un modo che ti darà una risposta significativa.

Alan Kay ha detto che il modo migliore per predire il futuro è inventarlo. Ho intenzione di distorcerlo un po 'e dire che il modo migliore per stimare la probabilità di una collisione è costringerlo a zero. In questo caso, ciò significa utilizzare le chiavi primarie garantite univoche fornite da qualsiasi database che ne valga la pena. A meno che non si riesca a creare un caso tremendo contro lo spazio extra necessario per archiviarli, è meglio seguire questa strada anziché una soluzione troppo intelligente per metà che cerca di incorporare l'intelligenza in ciò che dovrebbe essere essenzialmente un numero casuale.

    
risposta data 26.12.2015 - 20:22
fonte
1

Considerare che per qualsiasi precisione di un ID basato sul tempo, è possibile utilizzare lo stesso tipo di dati per memorizzare un contatore semplice. Ciò consentirà sempre di almeno quanti più record di un ID basato sul tempo e probabilmente molti altri, poiché l'ID basato sul tempo spreca potenziali ID per ogni unità di risoluzione del timer in cui non viene generato un ID .

Se il timestamp è significativo, puoi salvarlo separatamente. Cercando una citazione per spiegare perché le chiavi primarie dovrebbero sempre essere arbitrarie, ho scoperto che questo è più controverso di quanto non pensassi; Pensavo che fosse ambientato vent'anni fa. Basti dire che esistono vantaggi importanti per l'utilizzo di ID arbitrari, a.k.a. surrogati.

    
risposta data 26.12.2015 - 19:08
fonte

Leggi altre domande sui tag