maleńka losowo wyglądająca generacja ID

Question

Próbuję wygenerować unikalne identyfikatory do użycia w aplikacji Google App Engine i chciałbym uzyskać opinię na temat możliwości podejścia, które zamierzam zastosować (pytania na końcu). Czytałem sporo pytań na ten temat, ale nie pamiętam, jakbym podszedł do tego konkretnego podejścia.

Chciałbym losowo wyglądające identyfikatory, np. Skróty MD5, ale chcę też, żeby były małe. Cztery do sześciu znaków, na wzór tinyurl, byłoby idealne. Identyfikatory będą dotyczyć treści generowanych przez użytkowników, w kontekście mojej aplikacji, takich jak pytania testowe, które ludzie będą pisać. Nie jest konieczne, aby identyfikatory były losowe (jest w porządku, jeśli wyglądają jak identyfikatory seryjne), ale podejście, które zamierzam użyć, nadaje się do tego, więc nie jest to problem.

Osoby znające mechanizm Google App Engine wiedzą, że zapisy do magazynu danych są szczególnie drogie i mogą skutkować przekroczeniem limitu czasu, jeśli jest ich zbyt wiele w tej samej grupie jednostek. Liczniki Sharded to podejście, które jest często stosowane w celu uniknięcia rywalizacji o zapis na pojedynczym globalnym liczniku i nieudanych transakcjach, które się z nim wiążą.

Wraz z otrzymywaniem krótkich identyfikatorów i unikaniem sporów o zapisy, staram się unikać urodzinowego paradoksu. Chciałbym przygotować się na możliwość pojawienia się milionów identyfikatorów, nawet jeśli trochę za mało.

Myślałem o użyciu sharded licznik wzdłuż następujących linii:

• Licznik jest sharded na użytkownikach, tak że nie jest odłamek dla każdego użytkownika. Każdy obiekt licznika ma swój własny licznik, który jest specyficzny dla danego użytkownika, który jest zwiększany, gdy nowy element jest tworzony przez tego użytkownika. Liczba jest zwiększana niezależnie od tego, czy element został pomyślnie utworzony.
• Podstawą identyfikatora jest skrót MD5 o następującym ciągu: "< adres e-mail użytkownika > | < najnowszej wartości licznika >".
• Wynikowy skrót MD5 jest następnie obcięty, początkowo do czterech znaków.
• Zostaje zachowana pojedyncza globalna wartość "length". Za każdym razem, gdy poprzednie kroki powodują duplikowanie klucza (jeden wyobraża sobie, że na początku będzie to dość szybko), wartość długości zostanie zwiększona o jeden. Skróty MD5 dla nowych identyfikatorów będą teraz obcięte na "długości" znaków, a nie czterech znaków.
• Nie chcę ujawniać adresu e-mail użytkownika, co sugeruje, że jakiś skrót jest dobrym sposobem.

moje pytania to: Czy mam rację sądząc, że będzie to w dużej mierze uniknąć rywalizacji zapisu wyniku duplikatów kluczy i tego zapisu rywalizacji na polu długości prawdopodobnie nie byłoby problemem, zwłaszcza przy dłuższych? Czy ktoś może opisać matematykę tutaj? Czy długość szybko wzrośnie do długości skrótu MD5, podważając wartość całego podejścia? Czy byłoby lepiej po prostu przejść z pełnym (dłuższym) hash MD5, aby zachować łatwiejsze utrzymanie? Czy jest coś, co przeoczyłem?

Answer 1

Algorytm ten jest silny i rzeczywiście zminimalizować operacji zapisu. Tak więc wartość długości będzie zbieżna do równowagi pomiędzy najkrótszą długością a nieobecnościami kolizji.

Można rozluźnić ograniczenie braku kolizji, stosując strategie stosowane w tabelach mieszania. Wypróbuj inne unikalne identyfikatory, zanim powrócisz do zwiększania długości.

Proponuję więc dodać licznik testowy do końca zaszyfrowanego łańcucha zainicjowanego na 0. Jeśli wygenerowany identyfikator jest już używany, należy zwiększyć licznik i ponowić próbę, aż do osiągnięcia wartości maksymalnego licznika po zwiększeniu długości .

W efekcie otrzymasz bardziej efektywne wykorzystanie przestrzeni adresowej ID i znacznie mniejszej częstotliwości.

Odnośnie twojego pytania o limit długości MD5, uważam, że wybór MD5 jest przesadą. Tak naprawdę nie potrzebujesz kryptograficznego (pseudo) bezpiecznego hasha. Potrzebny jest losowy generator bitów, do którego można użyć crc32 (lub adler, który jest szybszy). Zwłaszcza jeśli kod ma być uruchamiany na telefonie komórkowym. Aby zaimplementować losowy generator bitów za pomocą polecenia crc32, dodaj wartość łańcuchową do wartości 32 bitów, a następnie zainicjuj ją za pomocą stałej wartości do wyboru (seed). Następnie obliczyć crc32 w tym łańcuchu. Jeśli potrzebujesz więcej bajtów, zapisz otrzymaną wartość crc32 w 32 bitach przed ciągiem i oblicz ponownie wartość crc32. Iteruj, aż masz wystarczająco dużo bitów. Możesz zastąpić crc32 wybranym algorytmem. Daje to tani i szybki generator bitów losowych, gdzie początkową stałą jest ziarno.

Za pomocą tego algorytmu można zminimalizować liczbę wygenerowanych bitów losowych, a także nie mieć górnej granicy długości.

Jeśli chodzi o kodowanie, nie określono ograniczeń. Czy można używać wielkich i małych liter z cyframi? Twój przykład wykorzystuje alfabet 36 różnych wartości ASCII. Gdy masz już generator liczb pseudolosowych opisany powyżej, który może generować tyle bajtów ile chcesz, po prostu zdefiniuj długość jako liczbę liter twojego ID i wybierz następną literę z modulo następnego losowego bajtu. Będziesz wtedy dokładnie wiedzieć, ile bajtów wygenerować za jednym razem, a generowanie ID jest banalne.

Answer 2

Jak o coś takiego:

1. Jeśli chcesz 4 klawisze postaciach używając a-zA-0-9, to że mają: 62^4 => 14 milionów możliwych wartości.

2. Przerwij na N partycji: 0000 ... 1000, 1001 ... 2000, ..., ZZAA ...ZZZZ

   Każda partycja jest reprezentowany przez jednostkę z: rozpocząć koniec id id bieżący identyfikator

teraz do generowania ID:

1. losowo wybrać partycji. Użyj klawisza Start dla każdej partycji jako klucza. Rozpocznij transakcję:
2. get_or_create() ten obiekt partycji.
3. jeśli prąd id == end id, przejdź do kroku 1
4. zapisać bieżące ID
5. przyrost bieżący identyfikator przez jedną transakcję End

używać bieżący identyfikator, który został zapisany jako swój identyfikator.

Jeśli wybierzesz N jako 140, każda partycja będzie miała 100 000 wartości. Umożliwiłoby to kilka współbieżnych wstawień przy jednoczesnym ograniczeniu liczby ponownych prób z powodu wybrania "pustej" partycji.

Być może trzeba będzie pomyśleć o tym więcej. W szczególności, jak sobie z tym poradzisz, gdy będziesz musiał przenieść się na 5 lub 6-cyfrową liczbę kluczy?

-Dave

Answer 3

Wystarczy dodać kilka konkretnych liczb na pytanie powyżej, mam realizowane mały program do generowania identyfikatorów wzdłuż linii wymienionych w pytaniu, a te były wyniki jednego z przejazdów próbnych :

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 

każdym razem, długość mieszania zwiększona, to w wyniku kolizji, tak więc sześć kolizje w tym przypadku. Liczba to liczba kluczy o określonej długości, które zostały wygenerowane przed kolizją. Kolumna MD5 pokazuje ostatni obcięty klucz, który został pomyślnie dodany, zanim wystąpił zduplikowany błąd klucza. Kolumna po prawej stronie pokazuje klucz w bazie 62 (jeśli poprawnie wykonałem konwersję).

Wygląda na to, że coraz więcej klawiszy jest generowanych z każdą dodatkową postacią, co można sobie wyobrazić. Mam nadzieję, że podejście to będzie skalowane pod kątem treści generowanych przez użytkowników.

Dla każdego, kto jest zainteresowany, oto jak mam podstawa 62 reprezentację ostatniej kolumnie:

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

---

(Dodano później :)

Oto klasa, która dba o kilka rzeczy związanych z generowaniem tych identyfikatorów w kontekście Google App Engine. Domyślnie klucze wygenerowane przez tę klasę nie mają czysto bazowej 62, ponieważ pierwszy znak nazwy klucza GAE musi być alfabetyczny. Ten wymóg został tutaj rozwiązany za pomocą podstawy 52 dla pierwszego znaku.

Podstawową zasadę można zmienić na wartość inną niż 62, zmieniając wartość "clist", która została przekazana do konstruktora (lub pominięta). Można chcieć usunąć znaki, które łatwo można pomylić, na przykład "1", "l", "i" itd.

Zastosowanie:

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

Oto klasa:

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)