2009-10-30 25 views
7

Me gustaría generar una identificación corta y única sin tener que verificar las colisiones.Generación única de ID PHP corta usando auto_increment?

Actualmente hago algo como esto, pero el ID que actualmente genero es aleatorio y la comprobación de colisiones en un bucle es molesta y se volverá costosa si el número de registros crece significativamente.

Normalmente, preocuparse por las colisiones no es un problema, pero la ID única que quiero generar es una cadena única corta de 5-8 caracteres, alfanumérica, como tinyurl.

EDITAR: Me gustaría comenzar con 5 caracteres y si llego a 60 millones de entradas, entonces vaya a 6 ... y así sucesivamente.

Para este fin, estaba pensando que podría usar un valor auto_increment que está oculto a los usuarios, y presentarlos en su lugar con un MD5 o algún otro método para generar una cadena única a partir de eso.

Las cadenas generadas no deberían parecer lineales, por lo que simplemente convertir el ID autoincrementado en base 36 [0-9A-Z] es un poco demasiado simplista, pero una función como esa es a dónde voy con esto.

EDITAR: La seguridad no es un problema, ya que no se utilizará para proteger la información. Es simplemente un atajo a una cadena más larga. Gracias.

Gracias por sus sugerencias y disculpe el retraso. Dentista ..

Respuesta

6

Necesitará algo que sea correcto por construcción, es decir, una función de permutación: esta es una función que hace una uno a uno, mapeo reversible de un entero (su contador secuencial) a otro. Algunos ejemplos (cualquier combinación de éstos también debería funcionar):

  • invirtiendo algunos de los bits (fi usando un XOR,^en PHP)
  • intercambiar los lugares de bits (($ i & 0xc)> > 2 | ($ i & 0x3) < < 2), o simplemente invirtiendo el orden de todos los bits
  • agregando un módulo de valor constante a su rango máximo (debe ser un factor de dos, si combina esto con los arriba)

Ejemplo: esta función convertirá 0, 1, 2, 3, 5, .. en 13, 4, 12, 7, 15, .. para los números de hasta 15:

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

EDITAR

una forma más fácil sería utilizar un generador de congruencia lineal (LCG, que se utiliza generalmente para la generación de números aleatorios), que se define por una fórmula de la forma:

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

para good values de a, c y m , la secuencia de X_0, X_1 .. X_m-1 contendrá todos l numera entre 0 y m-1 exactamente una vez. Ahora puede comenzar desde un índice de aumento lineal y usar el valor next en la secuencia LCG como su clave "secreta".

Edit2

Implementación: Puede design your own LCG parameters, pero si uno se equivoca no cubrirá toda la gama (y por lo tanto tienen duplicados) así que voy a utilizar un publicada y trató conjunto de parámetros aquí desde this paper:

a = 16807, c = 0, m = 2147483647 

Esto le da un rango de 2 ** 31. Con el paquete() se puede obtener el entero resultante como una cadena, base64_encode() hace que sea una cadena legible (de hasta 6 caracteres significativos, 6 bits por byte) por lo que este podría ser su función:

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

Me gusta esta idea. ¿Tienes algún código para mí? 1-60000000 mapeo a una cadena alfa numérica de 5 caracteres? –

+0

Lo siento, no estoy confiando en mis matemáticas a esta hora del día, así que es una de 31 bits. Para uno de 30 bits, tendría exactamente 5 (significativo, es decir, sin el relleno = 's) caracteres después de base64_encode, pero no pude encontrar un conjunto de parámetros para eso. – Wim

+0

Creo que este puede funcionar para uno de 30 bits: a = 357913942, c = 1, m = 1073741823 (Si no me equivoco, cumple los criterios en el artículo de Wikipedia para tener un archivo completo período: m = 2 ** 31-1 = 3 ** 2 * 7 * 11 * 31 * 151 * 331, c = 1 por lo que obviamente es coprime con m, y a-1 = 3 * 7 * 11 * 31 * 151 * 331 que es divisible por todos los factores primos de m ...) – Wim

0

Creo que esto nunca será realmente seguro, ya que solo necesita encontrar el método de cifrado detrás de la cadena única corta para secuestrar una identificación. ¿Verifica las colisiones en un bucle realmente problemático en tu entorno?

+0

No en este momento, pero a 50 millones de enlaces y 5 caracteres, algo así como el 80% colisiones convertirse. –

-1

Un MD5 de un número creciente debería estar bien, pero me preocupa que si estás truncando tu MD5 (que normalmente es de 128 bits) hasta 5-8 caracteres, es casi seguro que estarás perjudicando su capacidad para actuar como una firma única ...

+0

MD5 (o cualquier hash para el caso) nunca puede actuar como una firma única. Entonces sus preocupaciones de trunicación son un poco discutibles. –

+0

Los hash se utilizan como firmas todo el tiempo ... – dicroce

+0

No estoy seguro de cómo eso niega mi respuesta. La gente hace cosas tontas todo el tiempo, eso no hace que los hashes se vuelvan mágicamente "únicos". –

1

Probablemente pueda generar un hash MD5 del número de fecha/hora actual y truncarlo a la longitud que necesite (5-8 caracteres) y almacenarlo como el campo de id.

Si está utilizando el almacenamiento de esta información en una base de datos, no es necesario utilizar un bucle para hacer la prueba de colisión, pero sólo podía hacer una declaración de selección - algo así como

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

donde : id sería la nueva ID generada. Si c es mayor que 0, entonces sabes que ya existe.

EDITAR

esto puede no ser la mejor manera de hacerlo. Pero le daré una oportunidad, así que supongo que lo que necesita es convertir un número en una cadena corta única y no en secuencia.

Creo que como dijiste, la codificación base64 ya hace el número de conversión de cadena corta. Para evitar el problema de secuencia, podría tener alguna asignación entre los identificadores generados automáticamente a algún valor "aleatorio" (asignación única). Entonces puede base64 codificar este valor único.

Puede generar esta asignación de la siguiente manera. Tener un valor de tienda de tablas temporal de 1 - 10,000,000. Ordénelo en orden aleatorio y guárdelo en su tabla de mapas.

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

Dónde MappingTable tendría el 2 campos de ID (su identificación generada automáticamente se vería en contra de esto) y mappedId (que es lo que se genera la codificación base64 para).

A medida que se acerca a los 10,000,000, puede volver a ejecutar el código anterior y cambiar los valores en la tabla temporal con 10,000,001-20,000,000 o algo así.

+0

El bucle se origina para generar otra identificación única si fallo. Sé que esto apesta a una optimización prematura, pero espero que haya una mejor manera. –

0

un MD5 de un número incremental debe estar bien, pero me preocupa que si que está truncando su MD5 (que es normalmente 128 bits) hasta 5-8 caracteres, es casi seguro que dañe su capacidad de actuar como una firma única ...

Totalmente cierto. Especialmente si alcanza su probabilidad de colisión del 80%, un MD5 truncado será tan bueno como cualquier número aleatorio para garantizar la singularidad en sí mismo, es decir, inútil.

Pero ya que está usando una base de datos de todos modos, ¿por qué no simplemente utiliza un ÍNDICE ÚNICO? De esta manera, la comprobación de la unicidad se realiza (de una manera mucho más eficiente que utilizando un bucle) por MySQL. Intente hacer el INSERT con la clave generada por MD5 y, si falla, intente nuevamente ...

+0

Sí, pero aún me queda para recalcular el azar y volver a intentar el inserto. Eso es lo que hago ahora. Estaba buscando una forma de asegurar automáticamente que soy único en el primer intento. El método base 36 haría esto en el primer intento, pero el primer enlace sería 00000, el segundo 00001 y así sucesivamente. –

+0

Quizás un voto positivo del comentario que citó esté en orden? :) – dicroce

+0

Claro, una vez que tenga suficiente reputación ...;) – Wim

1

se puede utilizar un XOR bit a bit para codificar algunos de los bits:

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 | 
+-----+---------+ 
+0

Sí, eso parece funcionar también. –

0

Si no puede utilizar un campo de incremento automático, y quieren un valor único absolutamente, utilice UUID. Si decide usar cualquier otra cosa (además del incremento automático), sería una tontería NO verificar las colisiones.

Cuestiones relacionadas