piccola generazione di ID dall'aspetto casuale

Question

Sto cercando di generare ID univoci da utilizzare in un'applicazione di Google App Engine e vorrei un feedback sulla fattibilità dell'approccio che sto pensando di utilizzare (domande alla fine). Ho letto alcune domande su questo argomento, ma non ricordo di aver incontrato questo particolare approccio.

Vorrei ID dall'aspetto casuale, ad esempio hash MD5, ma voglio anche che siano piccoli. Da quattro a sei personaggi, sulla falsariga di tinyurl, sarebbero l'ideale. Gli ID saranno per i contenuti generati dagli utenti, nel contesto della mia applicazione, cose come testare domande che le persone scriveranno. Non è necessario che gli ID siano casuali (va bene se sembrano ID seriali), ma l'approccio che sto pensando di usare si presta a questo, quindi non è proprio un problema.

Le persone che hanno familiarità con Google App Engine sapranno che le scritture nell'archivio dati sono particolarmente costose e possono provocare timeout se ce ne sono troppe nello stesso gruppo di entità. I contatori frammentati sono un approccio che viene spesso utilizzato per evitare contese di scrittura su un singolo contatore globale e le transazioni non riuscite che ne conseguono.

Oltre a ottenere ID brevi ed evitare conflitti di scrittura, sto cercando di evitare il paradosso del compleanno. Vorrei prepararmi per la possibilità che ci siano milioni di ID, anche se questo sta esagerando un po '.

Stavo pensando di usare un contatore scheggiato seguendo le seguenti linee:

• Il contatore è suddiviso sugli utenti, in modo che vi sia un frammento per ogni utente. Ogni oggetto contatore ha il proprio conteggio specifico per un determinato utente, che viene incrementato quando un nuovo elemento viene creato da quell'utente. Il conteggio viene incrementato indipendentemente dal fatto che un elemento sia stato creato correttamente.
• La base di un ID è un hash MD5 della seguente stringa: " < user-email-address > | < latest-counter-value gt; <> quot;!.
• L'hash MD5 risultante viene quindi troncato, inizialmente a quattro caratteri.
• Un singolo " lunghezza " il valore è mantenuto. Ogni volta che i passaggi precedenti risultano in una chiave duplicata (si immagina che ciò accadrà abbastanza rapidamente all'inizio), il valore della lunghezza viene aumentato di uno. Gli hash MD5 per i nuovi ID verranno ora troncati a & Quot; lunghezza & Quot; personaggi, anziché quattro caratteri.
• Non voglio esporre l'indirizzo email dell'utente, il che suggerisce che un hash di qualche tipo sarebbe un buon modo per andare.

Le mie domande sono: ho ragione nel pensare che questo eviterà in gran parte la contesa di scrittura come risultato di chiavi duplicate e che la contesa di scrittura sul campo lunghezza probabilmente non sarebbe un problema, specialmente per lunghezze maggiori? Qualcuno può descrivere la matematica coinvolta qui? La lunghezza aumenterebbe rapidamente fino a raggiungere quella di un hash MD5, mettendo in discussione il valore dell'intero approccio? Sarebbe meglio solo andare con l'hash MD5 (più lungo) per mantenere le cose più facili da mantenere? C'è qualcosa che sto trascurando?

Answer 1

Questo algoritmo è intelligente e minimizzerebbe davvero le operazioni di scrittura. Quindi il valore della lunghezza converge in un equilibrio tra la lunghezza più breve e la assenza delle collisioni.

Puoi allentare il vincolo dell'assenza di collisione usando le strategie usate nelle tabelle hash. Prova alcuni altri ID univoci prima di ricorrere all'incremento della lunghezza.

Vorrei quindi suggerire di aggiungere un contatore di test alla fine della stringa con hash inizializzata su 0. Se l'ID generato è già utilizzato, incrementare il contatore e riprovare fino a raggiungere un valore di contatore massimo dopo aver aumentato la lunghezza.

Ti ritroverai con un uso più efficiente dello spazio degli indirizzi ID e incrementi di lunghezza molto meno frequenti.

Per quanto riguarda la tua domanda sul limite di lunghezza di MD5, penso che la scelta di MD5 sia eccessiva. Non hai davvero bisogno di un hash crittografico (pseudo) sicuro. Ciò di cui hai bisogno è un generatore di bit casuale per il quale puoi usare crc32 (o adler che è più veloce). Soprattutto se il codice deve essere eseguito su un telefono cellulare. Per implementare un generatore di bit casuale con crc32, anteponi un valore di 32 bit alla stringa per l'hash e inizializzalo con un valore costante di tua scelta (il seme). Quindi calcola il crc32 su questa stringa. Se hai bisogno di più byte, scrivi il valore crc32 ottenuto nei 32 bit davanti alla stringa e ricalcola il crc32. Scorrere fino a quando non si hanno abbastanza bit. Puoi sostituire crc32 con l'algoritmo di tua scelta. Ciò produce un generatore di bit casuale economico e veloce in cui la costante iniziale è il seme.

Con questo algoritmo minimizzi il numero di bit casuali generati e non hai limiti di lunghezza superiori.

Per quanto riguarda la codifica, non hai specificato i vincoli. Puoi usare lettere maiuscole e minuscole con le cifre? Il tuo esempio usa un alfabeto di 36 diversi valori ASCII. Una volta che hai il generatore di numeri pseudo casuali sopra descritto che può generare tutti i byte desiderati, definisci semplicemente la lunghezza come il numero di lettere del tuo ID e scegli la lettera successiva con un modulo del byte casuale successivo. Saprai quindi esattamente quanti byte generare in una volta sola e generare l'ID è banale.

Answer 2

Che ne dici di qualcosa del genere:

1. Se vuoi 4 chiavi di caratteri usando a-zA-Z0-9, allora avresti: 62 ^ 4 = & Gt; 14 milioni di valori possibili.

2. Suddividilo in N partizioni: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ... ZZZZ

   Ogni partizione è rappresentata da un'entità con: avvia id fine id ID corrente

Ora, per generare un ID:

1. scegli casualmente una partizione. Utilizzare la chiave di avvio per ogni partizione come chiave. Inizia transazione:
2. get_or_create () quell'entità di partizione.
3. se id corrente == id finale, vai al passaggio 1
4. salva ID corrente
5. incrementa l'ID corrente di uno Termina transazione

usa l'id corrente che è stato salvato come id.

Se scegli N come 140, ogni partizione avrà 100.000 valori. Ciò consentirebbe alcuni inserimenti simultanei, limitando il numero di tentativi dovuti alla selezione di un & Quot; vuoto & Quot; partizione.

Potrebbe essere necessario pensarci di più. In particolare, come gestirai il caso quando devi spostarti su tasti a 5 o 6 cifre?

-Dave

Answer 3

Solo per aggiungere alcuni numeri concreti alla domanda sopra, ho implementato un piccolo programma per generare ID lungo le linee menzionate nella domanda, e questi erano i risultati di una delle prove:

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

Ogni volta che la lunghezza dell'hash aumentava, ciò era dovuto a una collisione, quindi in questo caso c'erano sei collisioni. Il conteggio è il numero di chiavi di una determinata lunghezza che sono state generate prima di una collisione. La colonna MD5 mostra l'ultima chiave troncata che è stata aggiunta correttamente prima che si verificasse un errore di chiave duplicata. La colonna all'estrema destra mostra la chiave nella base 62 (se ho eseguito correttamente la conversione).

Sembra che vengano generati sempre più tasti con ogni personaggio aggiuntivo, che è quello che potresti immaginare. Spero che questo approccio si ridimensioni per i contenuti generati dagli utenti.

Per chiunque sia interessato, ecco come ho ottenuto la rappresentazione di base 62 per l'ultima colonna:

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

---

(Aggiunto in seguito :)

Ecco una classe che si occupa di diverse cose relative alla generazione di questi ID nel contesto di Google App Engine. Per impostazione predefinita, le chiavi generate da questa classe non sono puramente di base 62, poiché il primo carattere del nome di una chiave GAE deve essere alfabetico. Tale requisito è stato affrontato qui usando la base 52 per il primo carattere.

La base primaria può essere cambiata in qualcosa di diverso da 62 modificando il " clist " valore che è stato passato (o omesso) dal costruttore. Si potrebbe voler rimuovere i caratteri che sono facili da confondere, ad esempio & Quot; 1 & Quot ;, & Quot; l & Quot ;, & Quot; i " ;, ecc.

Utilizzo:

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

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