minúscula generación de ID de aspecto aleatorio

Question

Estoy tratando de generar identificaciones únicas para usar en una aplicación de Google App Engine y me gustaría recibir comentarios sobre la viabilidad del enfoque que estoy pensando utilizar (preguntas al final). He leído bastantes preguntas sobre este tema, pero no recuerdo haber encontrado este enfoque en particular.

Me gustaría obtener ID de aspecto aleatorio, por ejemplo, hashes MD5, pero también quiero que sean pequeños. De cuatro a seis caracteres, a lo largo de las líneas de tinyurl, sería ideal. Los ID serán para contenido generado por el usuario, en el contexto de mi aplicación, cosas como preguntas de prueba que las personas estarán escribiendo. No es necesario que los ID sean aleatorios (está bien si se parecen a los ID de serie), pero el enfoque que estoy pensando usar se presta a esto, por lo que no es realmente un problema.

Las personas familiarizadas con Google App Engine sabrán que las escrituras en el almacén de datos son particularmente caras y pueden provocar tiempos de espera excedidos si hay demasiadas para el mismo grupo de entidades. Los contadores de Sharded son un enfoque que a menudo se usa para evitar la contención de escritura en un único contador global y las transacciones fallidas que lo acompañan.

Además de obtener identificaciones cortas y evitar la contención de escritura, intento evitar la paradoja del cumpleaños. Me gustaría prepararme para la posibilidad de que haya millones de ID, incluso si esto va un poco por la borda.

Yo estaba pensando en usar un contador fragmentada a lo largo de las siguientes líneas:

• el contador está fragmentada en usuarios, por lo que hay un fragmento para cada usuario. Cada objeto contador tiene su propia cuenta que es específica para un usuario dado, que se incrementa cuando ese usuario crea un nuevo elemento. El recuento se incrementa independientemente de si un elemento se ha creado correctamente.
• La base de un documento de identidad es un hash MD5 de la siguiente cadena: "< fácil de dirección de correo electrónico > | < última contravalor >".
• El hash MD5 resultante se trunca, inicialmente a cuatro caracteres.
• Se mantiene un único valor global de "longitud". Siempre que los pasos anteriores den como resultado una clave duplicada (uno imagina que esto ocurrirá bastante rápido al principio), el valor de la longitud se incrementará en uno. Los valores hash MD5 para nuevos ID ahora se truncarán en caracteres "longitud", en lugar de cuatro caracteres.
• No quiero exponer la dirección de correo electrónico del usuario, lo que sugiere que un hash de algún tipo sería una buena forma de hacerlo.

Mis preguntas son: ¿Estoy en lo cierto al pensar que esto evitará la contención de escritura como resultado de claves duplicadas y que la contención de escritura en el campo de longitud probablemente no sea un problema, especialmente en longitudes más largas? ¿Alguien puede describir las matemáticas involucradas aquí? ¿La longitud aumentaría rápidamente a casi la longitud de un hash MD5, poniendo en duda el valor de todo el enfoque? ¿Sería mejor simplemente usar el hash completo (más largo) MD5 para mantener las cosas más fáciles de mantener? ¿Hay algo que estoy pasando por alto?

Answer 1

Este algoritmo es inteligente y sería de hecho reducir al mínimo las operaciones de escritura. Por lo tanto, el valor de longitud convergerá a un equilibrio entre la longitud más corta y ausencia de colisiones.

Puede relajar la restricción de la ausencia de colisión mediante el uso de estrategias utilizadas en las tablas hash. Pruebe con otros ID únicos antes de volver a aumentar la longitud.

Por lo tanto, le sugiero que agregue un contador de prueba al final de la cadena hash inicializada a 0. Si la ID generada ya está utilizada, incremente el contador y vuelva a intentarlo hasta que se alcance el valor máximo .

Finalizará con un uso más eficiente de su espacio de direcciones de ID y con incrementos de longitud mucho menos frecuentes.

En relación con su pregunta sobre el límite de longitud de MD5, creo que la elección de MD5 es una exageración. Realmente no necesitas un hash criptográfico (pseudo) seguro. Lo que necesitas es un generador de bits aleatorio para el cual puedas usar crc32 (o adler, que es más rápido). Especialmente si el código se va a ejecutar en un teléfono móvil. Para implementar un generador de bits aleatorio con crc32, anteponga un valor de 32 bits a la cadena al hash e inicialícelo con un valor constante de su elección (la semilla). Luego calcule el crc32 en esta cadena. Si necesita más bytes, escriba el valor crc32 obtenido en los 32 bits delante de la cadena y vuelva a calcular el crc32. Itera hasta que tengas suficientes bits. Puede reemplazar el crc32 con el algoritmo de su elección. Esto produce un generador de bits aleatorio económico y rápido donde la constante inicial es la semilla.

Con este algoritmo, minimiza el número de bits aleatorios generados y tampoco tiene un límite superior de longitud.

En cuanto a la codificación, no especificó las restricciones. ¿Puedes usar letras mayúsculas y minúsculas con los dígitos? Su ejemplo usa un alfabeto de 36 valores ASCII diferentes. Una vez que tenga el generador de números pseudoaleatorios descrito anteriormente que puede generar tantos bytes como desee, simplemente defina la longitud como el número de letras de su ID y elija la siguiente letra con un módulo del siguiente byte aleatorio. Sabrá entonces exactamente cuántos bytes generar de una vez y generar la ID es trivial.

Answer 2

¿Qué tal algo como esto:

1. Si quieres 4 teclas de caracteres utilizando a-zA-Z0-9, entonces tendríamos: 62^4 => 14 millones de valores posibles.

2. Divida esto en N particiones: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ...ZZZZ

   Cada partición está representado por una entidad con: ID de inicio final Identificación del Identificación del actual

Ahora, para generar un ID:

1. escogerán aleatoriamente una partición. Use la tecla de inicio para cada partición como una clave. Iniciar transacción:
2. get_or_create() esa entidad de partición.
3. si Identificación del actual == fines de identificación, vaya al paso 1
4. Guardar ID actual
5. incremento del ID actual en una transacción Fin

utilizar el ID de la corriente que se guardó como su identificador.

Si elige N como 140, cada partición tendrá 100.000 valores. Esto permitiría bastantes inserts simultáneos mientras se limita el número de reintentos debido a la selección de una partición "vacía".

Es posible que tenga que pensar en esto más. Especialmente, ¿cómo manejarás el caso cuando necesites cambiar a teclas de 5 o 6 dígitos?

-Dave

Answer 3

sólo para añadir algunas cifras concretas a la pregunta anterior, he implementado un pequeño programa para generar identificadores de líneas a lo largo de los mencionados en la pregunta, y estos fueron los resultados de uno de los viajes de prueba :

Length  Count  MD5    Base 62 
4   400  3d0e   446 
5   925  4fc04   1Myi 
6   2434  0e9368   40V6 
7   29155  e406d96   GBFiA 
8   130615  7ba787c8  2GOiCm 
9   403040  75525d163  YNKjL9 
10   1302992 e1b3581f52  H47JAIs 
Total:  1869561 

Cada vez que la longitud del hash aumenta, esto era debido a una colisión, por lo que hubo seis colisiones en este caso. El recuento es el número de claves de una longitud determinada que se generaron antes de una colisión. La columna MD5 muestra la última clave truncada que se agregó correctamente antes de que hubiera un error duplicado. La columna en el extremo derecho muestra la clave en la base 62 (si he hecho la conversión correctamente).

Parece que se están generando más y más claves con cada carácter adicional, que es lo que se podría imaginar. Tengo la esperanza de que este enfoque se escale para el contenido generado por el usuario.

Para cualquiera que esté interesado, aquí es como llegué a la representación de base 62 de la última columna:

def base_62_encode(input): 
    "Inspired by code at http://en.wikipedia.org/wiki/Base_36." 
    CLIST="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
    rv = "" 
    while input != 0: 
     rv = CLIST[input % 62] + str(rv) 
     input /= 62 
    return rv 

base62_id = base_62_encode(long(truncated_hash, 16)) 

---

(añadido más adelante :)

que aquí hay una clase que se encarga de varias cosas relacionadas con la generación de estos ID en el contexto de Google App Engine. Por defecto, las claves que genera esta clase no son puramente base 62, ya que el primer carácter de un nombre de clave GAE debe ser alfabético. Ese requisito se ha abordado aquí utilizando la base 52 para el primer personaje.

La base primaria se puede cambiar a algo distinto a 62 alterando el valor "clist" que se ha pasado (u omitido) del constructor. Es posible que desee eliminar los caracteres que son fáciles de mezclar, por ejemplo, "1", "l", "i", etc.

Uso:

keygen = LengthBackoffIdGenerator(SomeClass, initial_length=5) 
small_id, modified = keygen.small_id(seed_value_from_sharded_counter) 

Aquí está la clase:

class LengthBackoffIdGenerator(object): 
    """Class to generate ids along the lines of tinyurl. 

    By default, ids begin with a alphabetic character. Each id that is created is checked against previous ones 
    to ensure uniqueness. When a duplicate is generated, the length of the seed value used is increased by one 
    character. 

    Ids become gradually longer over time while remaining relatively short, and there are very few retries in 
    relation to the number of keys generated. 
    """ 
    ids = set() 

    def __init__(self, cls, clist='abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', alpha_first=False, 
      initial_length=5, check_db=False): 
     self.clist = clist 
     self.alpha_first = alpha_first 
     if self.alpha_first: 
      import re 
      alpha_list = re.sub(r'\d', '', clist) 
      if len(alpha_list) < 1: 
       raise Exception, 'At least one non-numeric character is required.' 
      self.alpha_list = alpha_list 
     self.cls = cls 
     self.length = initial_length 
     self.check_db = check_db 

    def divide_long_and_convert(self, radix, clist, input, rv): 
     "Inspired by code at http://en.wikipedia.org/wiki/Base_36." 
     rv += clist[input % radix] 
     input /= radix 
     return (input, rv) 

    def convert_long(self, input): 
     rv = "" 
     if self.alpha_first: 
      input, rv = self.divide_long_and_convert(len(self.alpha_list), self.alpha_list, input, rv) 
     while input != 0: 
      input, rv = self.divide_long_and_convert(len(self.clist),  self.clist,  input, rv) 
     return rv 

    def hash_truncate_and_binify(self, input, length): 
     """Compute the MD5 hash of an input string, truncate it and convert it to a long. 

     input - A seed value. 
     length - The length to truncate the MD5 hash to. 
     """ 
     from assessment.core.functions import md5_hash 
     input = md5_hash(input)[0:length] 
     return long(input, 16) 

    def _small_id(self, input): 
     """Create an ID that looks similar to a tinyurl ID. 

     The first letter of the ID will be non-numeric by default. 
     """ 
     return self.convert_long(self.hash_truncate_and_binify(input, self.length)) 

    def small_id(self, seed): 
     key_name = self._small_id(seed) 
     increased_length = False 
     if self.check_db and not self.cls.get_by_key_name(key_name) is None: 
      self.ids.add(key_name) 
     if key_name in self.ids: 
      self.length += 1 
      increased_length = True 
      key_name = self._small_id(seed) 
     self.ids.add(key_name) 
     return (key_name, increased_length)