pequeña generación de identificación de aspecto aleatorio

Question

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

Me gustaría tener identificaciones de aspecto aleatorio, por ejemplo, hash MD5, pero también quiero que sean pequeñas. Cuatro a seis caracteres, en la línea de tinyurl, serían ideales. Los ID serán para contenido generado por el usuario, en el contexto de mi aplicación, cosas como preguntas de prueba que la gente escribirá. No es necesario que las ID tengan un aspecto aleatorio (está bien si se parecen a las ID en 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 costosas y pueden ocasionar tiempos de espera si hay demasiadas para el mismo grupo de entidades. Los contadores fragmentados son un enfoque que a menudo se utiliza para evitar la contención de escritura en un único contador global y las transacciones fallidas que lo acompañan.

Junto con obtener identificaciones cortas y evitar la disputa de escritura, estoy tratando de evitar la paradoja del cumpleaños. Me gustaría prepararme para la posibilidad de que haya millones de ID, incluso si esto se va un poco por la borda.

Estaba pensando en usar un contador fragmentado en las siguientes líneas:

• El contador está fragmentado en los usuarios, por lo que hay un fragmento para cada usuario. Cada objeto de contador tiene su propio recuento que es específico para un usuario determinado, que se incrementa cuando ese usuario crea un nuevo elemento. El recuento se incrementa independientemente de si un elemento se creó correctamente.
• La base de una ID es un hash MD5 de la siguiente cadena: " < dirección de correo electrónico de usuario > | < último valor de contador gt; " ;.
• El hash MD5 resultante se trunca, inicialmente a cuatro caracteres.
• Un único global " length " Se mantiene el valor. Siempre que los pasos anteriores den como resultado una clave duplicada (uno imagina que esto sucederá bastante rápido al principio), el valor de la longitud aumentará en uno. Los hash MD5 para nuevas ID ahora se truncarán en & Quot; length & Quot; caracteres, 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 manera de hacerlo.

Mis preguntas son: ¿Estoy en lo cierto al pensar que esto evitará en gran medida 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, cuestionando el valor de todo el enfoque? ¿Sería mejor ir con el hash MD5 completo (más largo) para mantener las cosas más fáciles de mantener? ¿Hay algo que esté pasando por alto?

Answer 1

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

Puede relajar la restricción de ausencia de colisión mediante el uso de estrategias utilizadas en las tablas hash. Pruebe otras identificaciones únicas antes de volver a aumentar la longitud.

Por lo tanto, sugeriría que agregue un contador de prueba al final de la cadena hash inicializada a 0. Si la ID generada ya está en uso, incremente el contador y vuelva a intentarlo hasta que se alcance un valor de contador máximo después de aumentar la longitud.

Terminará con un uso más eficiente de su espacio de dirección de ID e incrementos de longitud mucho menos frecuentes.

Con respecto a 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 necesita es un generador de bits aleatorio para el que pueda usar crc32 (o adler, que es más rápido). Especialmente si el código debe ejecutarse en un teléfono móvil. Para implementar un generador de bits aleatorio con crc32, anteponga un valor de 32 bits a la cadena a 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. Iterar hasta que tenga suficientes pedazos. Puede reemplazar el crc32 con el algoritmo de su elección. Esto produce un generador de bits aleatorio barato 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.

Con respecto a la codificación, no especificó las restricciones. ¿Puedes usar letras mayúsculas y minúsculas con los dígitos? Su ejemplo utiliza 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. Entonces sabrá exactamente cuántos bytes generar de una vez y generar la ID es trivial.

Answer 2

¿Qué tal algo como esto?

1. Si desea 4 teclas de caracteres usando a-zA-Z0-9, entonces tendría: 62 ^ 4 = & Gt; 14 millones de valores posibles.

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

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

Ahora, para generar una ID:

1. elige aleatoriamente una partición. Use la tecla de inicio para cada partición como clave. Iniciar transacción:
2. get_or_create () esa entidad de partición.
3. si la id actual == id final, vaya al paso 1
4. guardar ID actual
5. incrementa la identificación actual en uno Finalizar transacción

use la identificación actual que se guardó como su identificación.

Si elige N como 140, cada partición tendrá 100.000 valores. Esto permitiría bastantes inserciones concurrentes al tiempo que limita el número de reintentos debido a elegir un & Quot; vacío & Quot; dividir.

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

-Dave

Answer 3

Solo para agregar algunos números duros a la pregunta anterior, he implementado un pequeño programa para generar identificadores a lo largo de las líneas mencionadas en la pregunta, y estos fueron los resultados de una de las ejecuciones 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 aumentó, esto se debió 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 se produjera un error de clave duplicada. La columna en el extremo derecho muestra la clave en la base 62 (si he realizado la conversión correctamente).

Parece que cada vez se generan más claves con cada carácter adicional, que es lo que imagina. Espero que este enfoque se adapte al contenido generado por el usuario.

Para cualquiera que esté interesado, así es como obtuve la representación de base 62 para la última columna:

def base_62_encode(input):
    "Inspired by code at http://en.wikipedia.org/wiki/Base_36."
    CLIST="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    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 :)

Aquí hay una clase que se ocupa de varias cosas relacionadas con la generación de estos ID en el contexto de Google App Engine. De manera predeterminada, 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. Este requisito se ha abordado aquí utilizando la base 52 para el primer carácter.

La base primaria se puede cambiar a otra que no sea 62 alterando & "; clist &"; valor que se ha pasado (u omitido) al constructor. Es posible que desee eliminar caracteres que son fáciles de mezclar, por ejemplo, & Quot; 1 & Quot ;, & Quot; l & Quot ;, & Quot; 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='0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ', 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)