minuscola generazione ID dall'aspetto casuale

Question

Sto provando a generare ID univoci da utilizzare in un'applicazione di Google App Engine e vorrei ricevere 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.

Mi piacerebbe avere ID a caso, ad esempio hash MD5, ma voglio anche che siano piccoli. Sarebbero ideali da quattro a sei caratteri, sulla falsariga di tinyurl. Gli ID saranno per i contenuti generati dagli utenti, nel contesto della mia applicazione, cose come le domande di prova 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 è davvero un problema.

Le persone che hanno familiarità con Google App Engine sapranno che le scritture sull'archivio dati sono particolarmente costose e possono causare timeout se ce ne sono troppe per lo stesso gruppo di entità. I contatori Sharded sono un approccio che viene spesso utilizzato per evitare conflitti di scrittura su un singolo contatore globale e le transazioni fallite che lo accompagnano.

Oltre a ottenere ID brevi ed evitare conflitti di scrittura, sto cercando di evitare il paradosso del compleanno. Mi piacerebbe preparare la possibilità che ci siano milioni di ID, anche se questo sta andando fuori bordo un po '.

Stavo pensando di utilizzare un contatore sharded secondo le seguenti linee:

• il contatore è sharded sugli utenti, in modo che ci sia un frammento per ciascun utente. Ogni oggetto contatore ha il proprio conteggio specifico per un determinato utente, che viene incrementato quando un nuovo elemento viene creato da tale utente. Il conteggio viene incrementato indipendentemente dal fatto che un articolo sia stato creato correttamente.
• La base di un ID è un hash MD5 della seguente stringa: "< indirizzo e-mail utente > | < ultimo contatore-valore >".
• L'hash MD5 risultante viene quindi troncato, inizialmente a quattro caratteri.
• Viene mantenuto un singolo valore "lunghezza" globale. Ogni volta che i passaggi precedenti danno come risultato una chiave duplicata (uno immagina che questo accada abbastanza rapidamente all'inizio), il valore della lunghezza sarà aumentato di uno. Gli hash MD5 per i nuovi ID ora verranno troncati a caratteri "length" anziché a 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 di pensare che questo sarà in gran parte evitare conflitti di scrittura a seguito di chiavi duplicate e tale affermazione di scrittura sul campo di lunghezza probabilmente non essere un problema, soprattutto in lunghezze superiori? Qualcuno può descrivere la matematica coinvolta qui? La lunghezza aumenterebbe rapidamente fino a raggiungere la lunghezza di un hash MD5, mettendo in discussione il valore dell'intero approccio? Sarebbe meglio andare semplicemente con l'hash MD5 completo (più lungo) per mantenere le cose più facili da mantenere? C'è qualcosa che sto trascurando?

Answer 1

Questo algoritmo è intelligente e sarebbe davvero ridurre al minimo le operazioni di scrittura. Quindi il valore della lunghezza convergerà in un equilibrio tra la lunghezza più breve e assenza di collisioni.

È possibile ridurre il vincolo di assenza di collisione utilizzando le strategie utilizzate nelle tabelle hash. Prova alcuni ID univoci prima di tornare a incrementare la lunghezza.

Suggerisco quindi di aggiungere un contatore di test alla fine della stringa hash inizializzata a 0. Se l'ID generato è già utilizzato, incrementare il contatore e riprovare fino a quando non viene raggiunto un valore contatore massimo dopo quello che si aumenta la lunghezza .

Si avrà un uso più efficiente dello spazio di indirizzamento dell'ID e incrementi di lunghezza molto meno frequenti.

Per quanto riguarda la domanda relativa al limite di lunghezza di MD5, ritengo che la scelta di MD5 sia eccessiva. Non hai davvero bisogno di un hash sicuro crittografico (pseudo). Quello 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, anteporre un valore a 32 bit alla stringa in hash e inizializzarlo con un valore costante di propria scelta (il seme). Quindi calcola crc32 su questa stringa. Se sono necessari più byte, scrivere il valore crc32 ottenuto nei 32 bit davanti alla stringa e ricalcolare crc32. Iterare fino ad avere abbastanza bit. È possibile sostituire crc32 con l'algoritmo desiderato. Questo produce un generatore di bit casuale economico e veloce in cui la costante iniziale è il seme.

Con questo algoritmo si riduce al minimo il numero di bit casuali generati e non si ha alcun limite superiore in lunghezza.

Per quanto riguarda la codifica, non sono stati specificati i vincoli. Puoi usare lettere maiuscole e minuscole con le cifre? Il tuo esempio utilizza un alfabeto di 36 valori ASCII diversi. Una volta ottenuto il generatore di numeri pseudocasuali sopra descritto che può generare il numero di byte desiderato, è sufficiente definire la lunghezza in base al numero di lettere dell'ID e selezionare la lettera successiva con un modulo del successivo byte casuale. Saprai quindi esattamente quanti byte generare in un colpo solo e generare l'ID è banale.

Answer 2

Che ne dite di qualcosa di simile:

1. Se volete 4 tasti dei caratteri utilizzando a-zA-Z0-9, allora si avrebbe: 62^4 => 14 milioni di valori possibili.

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

   Ogni partizione è rappresentato da un'entità con: inizio id fine id corrente id

Ora, per generare un ID:

1. scegliere a caso una partizione. Utilizzare il tasto Start per ogni partizione come chiave. Avvia transazione:
2. get_or_create() quell'entità di partizione.
3. se corrente id == fine id, passare al punto 1
4. Salva id corrente
5. incremento corrente id da una transazione Fine

utilizzare l'ID corrente che è stato salvato come ID.

Se si seleziona N come 140 ogni partizione avrà 100.000 valori. Ciò consentirebbe un numero considerevole di inserimenti simultanei limitando il numero di tentativi dovuti alla selezione di una partizione "vuota".

Potrebbe essere necessario pensarci di più. Soprattutto, come gestirai il caso quando avrai bisogno di spostarti su tasti a 5 o 6 cifre?

-Dave

Answer 3

solo aggiungere alcuni numeri duri alla domanda di cui sopra, ho implementato un piccolo programma per generare id lungo le linee indicate nella questione, e questi sono stati i risultati di una delle corse di prova :

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 del hash è aumentato, questo era a causa di una collisione, quindi c'erano sei collisioni in questo caso. 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 chiave duplicato. La colonna all'estrema destra mostra la chiave nella base 62 (se ho eseguito correttamente la conversione).

Sembra che vengano generate sempre più chiavi con ogni carattere aggiuntivo, che è ciò che si potrebbe immaginare. Spero che questo approccio sia scalabile 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="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz" 
    rv = "" 
    while input != 0: 
     rv = CLIST[input % 62] + str(rv) 
     input /= 62 
    return rv 

base62_id = base_62_encode(long(truncated_hash, 16)) 

---

(aggiunta in seguito :)

Ecco una classe che si prende cura di diverse cose legate 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 di un nome di chiave GAE deve essere alfabetico. Questo requisito è stato risolto qui utilizzando la base 52 per il primo carattere.

La base principale può essere modificata in qualcosa di diverso da 62 alterando il valore "clist" che è stato passato (o omesso) dal costruttore. Si potrebbe voler rimuovere caratteri facili da mescolare, ad esempio "1", "l", "i", ecc.

Usage:

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