PHP breve generazione di ID univoci utilizzando auto_increment?

Question

Vorrei generare un ID breve e univoco senza dover verificare la presenza di collisioni.

Al momento faccio qualcosa del genere, ma l'ID che sto generando è casuale e controllare le collisioni in un ciclo è fastidioso e diventerà costoso se il numero di record aumenta in modo significativo.

Di solito preoccuparsi delle collisioni non è un problema, ma l'ID univoco che voglio generare è una breve stringa univoca di 5-8 caratteri, alfanumerica, come fa tinyurl.

MODIFICA: Vorrei iniziare con 5 caratteri e, se colpisco 60 milioni di voci, vado al numero 6 ... e così via.

A tal fine, stavo pensando di poter usare un valore auto_increment nascosto agli utenti e presentarli invece con un MD5 o un altro metodo per generare una stringa univoca da ciò.

Le stringhe generate non dovrebbero apparire lineari, quindi semplicemente convertendo l'ID autoincrementato in base 36 [0-9A-Z] è un po 'troppo semplicistico, ma una funzione simile è quella in cui sto andando.

EDIT: la sicurezza non è un problema in quanto non verrà utilizzata per proteggere le informazioni. È semplicemente una scorciatoia per una stringa più lunga. Grazie.

Grazie per i tuoi suggerimenti e scusa per il ritardo. Dentista ..

Answer 1

Avrai bisogno di qualcosa che sia corretto per costruzione, cioè una funzione di permutazione: questa è una funzione che esegue una mappatura uno a uno e reversibile di un intero (il tuo contatore sequenziale) ad un altro. Alcuni esempi (anche qualsiasi combinazione di questi dovrebbe funzionare):

• invertendo alcuni dei bit (f.i. usando un XOR, ^ in PHP)
• scambio dei posti dei bit (($ i & amp; 0xc) > > 2 | ($ i & amp; 0x3) < < ; 2), o semplicemente invertendo l'ordine di tutti i bit
• aggiungendo un valore costante al tuo intervallo massimo (deve essere un fattore due, se lo stai combinando con quelli sopra)

Esempio: questa funzione converte 0, 1, 2, 3, 5, .. in 13, 4, 12, 7, 15, .. per numeri fino a 15:

$i=($input+97) & 0xf;
$result=((($i&0x1) << 3) + (($i&0xe) >> 1)) ^ 0x5;

Modifica

Un modo più semplice sarebbe usare un generatore congruenziale lineare (LCG, che di solito è usato per generare numeri casuali), che è definito da una formula del modulo:

X_n+1 = (a * X_n + c) mod m

Per buoni valori di a, c e m, la sequenza di X_0, X_1. X_m-1 conterrà tutti i numeri tra 0 e m-1 esattamente una volta. Ora puoi iniziare da un indice che aumenta in modo lineare e utilizzare il valore next nella sequenza LCG come & Quot; secret & Quot; chiave.

EDIT2

Implementazione: Puoi progettare i tuoi parametri LCG , ma se sbagli non coprirà il gamma completa (e quindi avere duplicati) quindi userò un set di parametri pubblicato e provato qui da questo documento :

a = 16807, c = 0, m = 2147483647

Questo ti dà un intervallo di 2 ** 31. Con pack () puoi ottenere l'intero risultante come stringa, base64_encode () lo rende una stringa leggibile (fino a 6 caratteri significativi, 6 bit per byte), quindi questa potrebbe essere la tua funzione:

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6)

Answer 2

Probabilmente potresti generare un hash MD5 del numero datetime / random corrente e troncarlo nella lunghezza necessaria (5-8 caratteri) e memorizzarlo come campo id.

Se stai utilizzando la memorizzazione di queste informazioni in un database, non è necessario utilizzare un ciclo for per eseguire il controllo delle collisioni, ma potresti semplicemente fare un'istruzione select - qualcosa come

SELECT count(1) c FROM Table WHERE id = :id

dove: id sarebbe l'id appena generato. Se c è maggiore di 0, sai che esiste già.

Modifica

Questo potrebbe non essere il modo migliore per farlo. Ma ci proverò, quindi immagino che ciò di cui hai bisogno sia in qualche modo convertire un numero in una stringa corta unica e che non sia in sequenza.

Immagino come hai detto, la codifica base64 fa già il numero per la conversione di stringhe corte. Per evitare il problema della sequenza potresti avere un po 'di mappatura tra i tuoi ID generati automaticamente su alcuni & Quot; random & Quot; valore (mappatura unica). Quindi puoi base64 codificare questo valore univoco.

È possibile generare questo mapping come segue. I valori di archivio di una tabella temporanea sono compresi tra 1 e 10.000.000. Ordinalo in ordine casuale e memorizzalo nella tabella della mappa.

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND()

Dove MappingTable avrebbe i 2 campi id (il tuo ID generato automaticamente cercherebbe rispetto a questo) e mappedId (che è ciò per cui potresti generare la codifica base64).

Man mano che ti avvicini a 10.000.000 potresti rieseguire il codice sopra riportato e modificare i valori nella tabella temporanea con 10.000.001-20.000.000 o qualcosa del genere.

Answer 3

puoi usare un XOR bit per bit per mescolare alcuni dei bit:

select thefield ^ 377 from thetable;

+-----+---------+
| a   | a ^ 377 |
+-----+---------+
| 154 |     483 |
| 152 |     481 |
|  69 |     316 |
|  35 |     346 |
|  72 |     305 |
| 139 |     498 |
|  96 |     281 |
|  31 |     358 |
|  11 |     370 |
| 127 |     262 |
+-----+---------+

Answer 4

Penso che questo non sarà mai veramente sicuro, poiché devi solo trovare il metodo di crittografia dietro la breve stringa univoca per dirottare un ID. Controllare le collisioni in un ciclo è davvero così problematico nelle tue impostazioni?

Answer 5

  

Un MD5 di un numero crescente   dovrebbe andare bene, ma mi preoccupo che se   stai troncando il tuo MD5 (che è   normalmente 128 bit) fino a 5-8   personaggi, quasi sicuramente   essere dannoso è la capacità di agire come   una firma unica ...

Completamente vero. Soprattutto se raggiungi la tua probabilità di collisione dell'80%, un MD5 troncato sarà buono come qualsiasi numero casuale per garantire l'unicità da solo, vale a dire senza valore.

Ma dal momento che stai usando un database comunque, perché non usare un INDICE UNICO? In questo modo il controllo uniquness viene eseguito (in modo molto più efficiente rispetto all'utilizzo di un loop) dallo stesso MySQL. Prova a fare INSERT con la chiave generata da MD5 e, se fallisce, riprova ...

Answer 6

Se non puoi utilizzare un campo di incremento automatico e desideri un valore univoco assolutamente , usa UUID . Se decidi di utilizzare qualcos'altro (oltre all'incremento automatico), sarebbe sciocco NON controllare le collisioni.

Answer 7

Questo post sul blog ha qualcosa di simile a quello che stai cercando.

http://kevin.vanzonneveld.net/techblog/article_c a>

Answer 8

Un MD5 di un numero in aumento dovrebbe andare bene, ma temo che se stai troncando il tuo MD5 (che normalmente è 128 bit) fino a 5-8 caratteri, quasi sicuramente danneggerai la sua capacità di agire come un firma unica ...