petite génération d'identifiant aléatoire

Question

J'essaie de générer des identifiants uniques à utiliser dans une application Google App Engine. J'aimerais obtenir des informations sur la faisabilité de l'approche envisagée (questions à la fin). J'ai lu pas mal de questions sur ce sujet, mais je ne me souviens pas d'avoir abordé cette approche en particulier.

Je voudrais des identifiants aléatoires, par exemple les hachages MD5, mais je souhaite également qu'ils soient petits. Quatre à six personnages, le long des lignes de tinyurl, seraient idéaux. Les identifiants seront pour le contenu généré par l'utilisateur, dans le contexte de mon application, des choses comme des questions de test que les gens vont écrire. Il n'est pas nécessaire que les identifiants aient une apparence aléatoire (c'est bien s'ils ressemblent à des identifiants de série), mais l'approche que je pense utiliser convient à cela, donc ce n'est pas vraiment un problème.

Les personnes familiarisées avec Google App Engine sauront que les écritures dans le magasin de données sont particulièrement coûteuses et peuvent entraîner des délais d'attente si elles sont trop nombreuses dans le même groupe d'entités. Les compteurs fragmentés sont une approche souvent utilisée pour éviter les conflits d’écriture sur un seul compteur global et les transactions ayant échoué qui s’accompagnent.

En plus d’obtenir des identifiants courts et d’éviter les conflits d’écriture, j’essaie d’éviter le paradoxe des anniversaires. Je voudrais me préparer à la possibilité qu'il y ait des millions d'identifiants, même si cela va un peu trop loin.

Je pensais utiliser un compteur fragmenté dans le sens suivant:

• Le compteur est partagé sur les utilisateurs, de sorte qu'il existe un fragment pour chaque utilisateur. Chaque objet compteur a son propre compte spécifique à un utilisateur donné, qui est incrémenté lorsqu'un nouvel élément est créé par cet utilisateur. Le nombre est incrémenté, qu’un élément ait été créé ou non avec succès.
• La base d'un identifiant est un hachage MD5 de la chaîne suivante: " < adresse email de l'utilisateur > | < latest-counter-value gt; & ";
• Le hachage MD5 résultant est ensuite tronqué, initialement à quatre caractères.
• Un seul " global " la valeur est maintenue. Chaque fois que les étapes précédentes génèrent une clé en double (on imagine que cela se produira assez rapidement au début), la valeur de la longueur sera augmentée de un. Les hachages MD5 pour les nouveaux ID seront désormais tronqués à & "; Longueur &"; caractères au lieu de quatre.
• Je ne souhaite pas révéler l'adresse e-mail de l'utilisateur, ce qui suggère qu'une sorte de hachage serait une bonne solution.

Mes questions sont les suivantes: ai-je raison de penser que cela évitera dans une large mesure les conflits d’écriture dus à la duplication de clés et que les conflits d’écriture sur le champ de longueur ne seraient probablement pas un problème, en particulier pour les plus longs? Quelqu'un peut-il décrire les mathématiques impliquées ici? La longueur augmenterait-elle rapidement pour atteindre presque la longueur d'un hachage MD5, remettant en question la valeur de l'ensemble de l'approche? Serait-il préférable d’utiliser le hachage MD5 complet (plus long) afin de faciliter la maintenance? Y a-t-il quelque chose que je néglige?

Answer 1

Cet algorithme est intelligent et réduirait en effet les opérations d’écriture. Ainsi, la valeur de la longueur convergera vers un équilibre entre la longueur la plus courte et l ' absence des collisions.

Vous pouvez assouplir la contrainte d'absence de collision en utilisant les stratégies utilisées dans les tables de hachage. Essayez d’autres identifiants uniques avant de revenir à l’incrémentation de la longueur.

Je vous suggère donc d’ajouter un compteur de test à la fin de la chaîne hachée initialisée à 0. Si l’ID généré est déjà utilisé, incrémentez le compteur et réessayez jusqu’à atteindre une valeur de compteur maximale après laquelle vous augmentez la longueur.

Vous obtiendrez une utilisation plus efficace de votre espace d'adressage ID et des incréments de longueur beaucoup moins fréquents.

En ce qui concerne votre question sur la limite de longueur du MD5, je pense que le choix du MD5 est excessif. Vous n'avez pas vraiment besoin d'un hachage cryptographique (pseudo) sécurisé. Ce dont vous avez besoin est un générateur de bits aléatoire pour lequel vous pouvez utiliser crc32 (ou adler, qui est plus rapide). Surtout si le code doit être exécuté sur un téléphone portable. Pour implémenter un générateur de bits aléatoires avec crc32, ajoutez une valeur de 32 bits à la chaîne à hacher et initialisez-la avec une valeur constante de votre choix (la valeur de départ). Puis calculez le crc32 sur cette chaîne. Si vous avez besoin de plus d'octets, écrivez la valeur crc32 obtenue dans les 32 bits situés devant la chaîne et recalculez le crc32. Itérez jusqu'à ce que vous ayez assez de bits. Vous pouvez remplacer le crc32 par l'algorithme de votre choix. Cela donne un générateur de bits aléatoire bon marché et rapide où la constante initiale est la graine.

Avec cet algorithme, vous réduisez le nombre de bits aléatoires générés et vous n’avez aucune limite supérieure en longueur.

En ce qui concerne l'encodage, vous n'avez pas spécifié les contraintes. Pouvez-vous utiliser des lettres majuscules et minuscules avec les chiffres? Votre exemple utilise un alphabet de 36 valeurs ASCII différentes. Une fois que vous avez le générateur de nombre pseudo aléatoire décrit ci-dessus qui peut générer autant d’octets que vous le souhaitez, définissez simplement length comme étant le nombre de lettres de votre identifiant et choisissez la lettre suivante avec un modulo de l’octet aléatoire suivant. Vous saurez alors exactement combien d'octets à générer en une fois et générer l'identifiant est trivial.

Answer 2

Que diriez-vous de quelque chose comme ça:

1. Si vous voulez 4 touches de caractères avec a-zA-Z0-9, alors vous auriez: 62 ^ 4 = & Gt; 14 millions de valeurs possibles.

2. Découpez-le en N partitions: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ... ZZZZ

   Chaque partition est représentée par une entité avec: identifiant de démarrage identifiant de fin identifiant actuel

Maintenant, pour générer un identifiant:

1. choisissez une partition au hasard. Utilisez la clé de démarrage pour chaque partition en tant que clé. Démarrer la transaction:
2. get_or_create () cette entité de partition.
3. si id actuel == id fin, passez à l'étape 1
4. enregistrer l'identifiant actuel
5. incrémente l'identifiant actuel de un Mettre fin à la transaction

utilisez l'identifiant actuel qui a été enregistré comme identifiant.

Si vous choisissez N à 140, chaque partition aura 100 000 valeurs. Cela permettrait un bon nombre d'insertions simultanées tout en limitant le nombre de tentatives en raison de la sélection d'un & "Vide &"; cloison.

Vous devrez peut-être y réfléchir davantage. En particulier, comment allez-vous gérer le cas lorsque vous devez passer aux touches à 5 ou 6 chiffres?

-Dave

Answer 3

Juste pour ajouter des chiffres concrets à la question ci-dessus, j'ai mis en place un petit programme permettant de générer des identifiants correspondant aux lignes évoquées dans la question, et voici les résultats d'un des essais:

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

Chaque fois que la longueur du hachage augmentait, cela était dû à une collision. Il y a donc eu six collisions dans ce cas. Le compte est le nombre de clés d'une longueur donnée générées avant une collision. La colonne MD5 affiche la dernière clé tronquée ajoutée avec succès avant qu'une erreur de clé en double ne se produise. La colonne à l'extrême droite montre la clé en base 62 (si j'ai converti correctement).

Il semble que de plus en plus de clés soient générées avec chaque caractère supplémentaire, ce que vous imagineriez. J'espère que cette approche évoluera pour le contenu généré par l'utilisateur.

Pour ceux qui sont intéressés, voici comment j'ai obtenu la représentation en base 62 de la dernière colonne:

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))

(ajouté ultérieurement:)

Voici une classe qui traite de plusieurs choses liées à la génération de ces identifiants dans le contexte de Google App Engine. Par défaut, les clés générées par cette classe ne sont pas purement en base 62, car le premier caractère d'un nom de clé GAE doit être alphabétique. Cette exigence a été traitée ici en utilisant la base 52 pour le premier caractère.

La base primaire peut être modifiée pour autre chose que 62 en modifiant le & "clist &"; valeur qui a été transmise (ou omise) au constructeur. Vous voudrez peut-être supprimer les caractères faciles à mélanger, par exemple, & "1 &", & "L &", & "I " ;, etc.

Utilisation:

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

Voici la classe:

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)