winzige Zufall aussehende ID Generation

https://stackoverflow.com/questions/815622

03-07-2019
|

Frage

Ich versuche, für die Verwendung in einer Google App Engine-Anwendung eindeutige IDs zu generieren und Feedback über die Durchführbarkeit des Ansatzes mag ich die Verwendung (Fragen am Ende) denke. Ich habe schon einige Fragen zu diesem Thema zu lesen, aber ich erinnere mich nicht über diesen speziellen Ansatz kommen.

Ich möchte zufällig aussehende IDs, beispielsweise MD5-Hashes, aber ich möchte sie auch klein sein. Vier bis sechs Zeichen, nach dem Vorbild der tinyurl, wäre ideal. Die IDs werden für Content nutzergenerierten sein, im Rahmen meiner Anwendung, Dinge wie Testfragen, die Menschen zu schreiben wird. Es ist nicht notwendig, dass die IDs sein zufällig aussehende (es ist in Ordnung, wenn sie wie serielle IDs aussehen), aber der Ansatz, den ich der Verwendung eignet sich dazu denke, es ist also nicht wirklich ein Problem.

Menschen vertraut mit Google App Engine wird wissen, dass auf den Datenspeicher schreibt, sind besonders teuer und in Timeouts führen können, wenn es zu viele von ihnen auf die gleiche Einheit Gruppe ist. Sharded Zähler sind ein Ansatz, der oft verwendet wird, Schreib Streit auf einem einzigen globalen Zähler und die gescheiterten Transaktionen zu vermeiden, die mit ihm zu gehen.

Zusammen mit kurzer IDs bekommen und Schreib Streit zu vermeiden, ich versuche das Geburtstagsparadoxon zu vermeiden. Ich möchte die Möglichkeit zur Vorbereitung von Millionen von IDs zu sein, auch wenn dies über Bord gehen ein wenig.

Ich dachte an einen sharded Zähler entlang der folgenden Zeilen ein:

Der Zähler ist sharded auf Benutzer, so dass es eine Scherbe für jeden Benutzer ist. Jeder Zähler Objekt hat eine eigene Zählung, die einen bestimmten Benutzer spezifisch ist, der erhöht wird, wenn ein neues Element durch den Benutzer erstellt wird. Die Zählung wird erhöht, unabhängig davon, ob ein Element erfolgreich erstellt wird.
Die Basis einer ID ist ein MD5-Hash-Wert des folgenden String: " | "
Der resultierende Hash-MD5 wird dann abgestumpften, anfänglich auf vier Zeichen.
Ein einziger globaler „Länge“ Wert wird beibehalten. Jedes Mal, wenn die vorherigen Schritte in einem doppelten Schlüssel führen (man sich vorstellt, das wird ziemlich schnell auf den ersten geschehen), wird der Wert der Länge um eins erhöht werden. MD5-Hashes für neue IDs werden nun bei „Länge“ Zeichen abgeschnitten werden, anstatt vier Zeichen.
Ich möchte nicht den Benutzer E-Mail-Adresse belichten, die ein Hash irgendeiner Art ein guter Weg, legt nahe, dass zu gehen wäre.

Meine Fragen sind: Bin ich recht in der Annahme, dass dies weitgehend Schreib Behauptung als Ergebnis der doppelten Schlüssel und dieser Schreib Anstoß auf dem Längenfeld würde vermieden, wird wahrscheinlich kein Problem sein, vor allem bei längeren Längen? Kann jemand die Mathematik hier beteiligt beschreiben? Würde die Länge erhöht schnell in der Nähe von der Länge eines MD5-Hash, in Frage zu dem Wert des gesamten Ansatzes? Wäre es besser, nur mit der vollen (länger) MD5-Hash zu gehen, um Dinge zu halten, leichter zu warten? Gibt es etwas, das ich mit Blick auf?

Lösung

Dieser Algorithmus ist die intelligente und wäre in der Tat Schreiboperationen minimiert. So wird der Längenwert zu einem Gleichgewicht konvergieren zwischen kürzester Länge und Abwesenheit von Kollisionen.

Sie können die constrain der Abwesenheit einer Kollision entspannen Strategien in Hash-Tabellen. Versuchen Sie, einige andere eindeutige IDs, bevor zurückzufallen, die Länge erhöht wird.

Ich würde daher vorschlagen, dass Sie am Ende des gehasht Zeichenfolge initialisiert auf 0 einen Test Zähler hinzufügen Wenn die erzeugen ID bereits verwendet wird, erhöhen den Zähler und wiederholen, bis ein maximaler Zählerwert nach dem Erreichen, was Sie über die Länge erhöhen.

Sie werden mit einer effizienteren Nutzung Ihres ID-Adressraumes am Ende und viel weniger häufig Längeninkrementen.

In Bezug auf Ihre Frage über die Längenbegrenzung von MD5 Ich denke, die Wahl von MD5 zuviel des Guten ist. Sie brauchen nicht wirklich einen kryptographischen (pseudo) sicheren Hash. Was Sie brauchen, ist ein Zufallsbitgenerators, für die Sie crc32 (oder Adler, die schneller ist) verwenden können. Vor allem, wenn der Code auf einem Mobiltelefon ausgeführt werden. Um einen Zufallsbitgenerators mit crc32 zu implementieren, voranstellen, einen 32-Bit-Wert in den String Hash und es mit einem konstanten Wert Ihrer Wahl zu initialisieren (den Samen). Dann berechnet die crc32 auf dieser Zeichenfolge. Wenn Sie mehr Bytes benötigen, schreiben Sie den erhaltenen crc32 Wert in dem 32-Bit vor dem String und die crc32 neu berechnen. Iterieren, bis Sie genug Bits haben. Sie können die crc32 mit dem Algorithmus Ihrer Wahl ersetzen. Daraus ergibt sich eine günstige und schnelle Zufallsbitgenerators wo die anfängliche konstant ist der Samen.

Mit diesem Algorithmus die Anzahl der Zufallsbits erzeugt minimieren und haben auch keine Obergrenze in der Länge.

In Bezug auf Codierung, Sie nicht die Constraints angeben. Können Sie Groß- und Kleinbuchstaben mit den Ziffern verwenden? Ihr Beispiel wird ein Alphabet von 36 verschiedenen ASCII-Werten. Sobald Sie den Pseudozufallszahlengenerator oben beschrieben, haben so viele Bytes wie gewünscht erzeugen kann, einfach Länge definiert die Anzahl der Buchstaben Ihrer ID zu sein und die nächsten Buchstaben mit einer Modulo des nächsten Zufall Byte holen. Sie wissen dann genau, wie viele Bytes in einem Rutsch zu erzeugen und die ID zu erzeugen ist trivial.

Andere Tipps

Wie wäre es etwa so:

Wenn Sie 4 Zeichentasten wollen a-zA-Z0-9 verwenden, dann würden Sie haben: 62 ^ 4 => 14 Millionen mögliche Werte.
diese in N Partitionen Break up: 0000 ... 1000, 1001 ... 2000 ..., ZZAA ... ZZZZ

Jede Partition wird von einem Unternehmen vertreten mit: Start-ID Ende id Strom id

Nun, eine ID zu erzeugen:

zufällig eine Partition auswählen. Verwenden Sie die Starttaste für jede Partition als Schlüssel. Starten Sie die Transaktion:
get_or_create (), dass Partition Einheit.
, wenn Strom id == Ende id, gehen 1
speichern Strom id
erhöhen Strom id von einem Ende Transaktion

die aktuelle ID verwenden, die als ID gespeichert wurde.

Wenn Sie N als 140 wählen würden Sie jede Partition 100.000 Werte haben. Dies würde es ermöglichen schon einige gleichzeitige Einsätze während die Anzahl der Wiederholungen aufgrund Begrenzung eine „leere“ Partition Kommissionierung.

Sie können diese mehr zu denken. Vor allem, wie werden Sie den Fall behandeln, wenn müssen Sie 5 oder 6 Zifferntasten bewegen?

-Dave

Nur einige harte Zahlen auf die Frage oben hinzuzufügen, habe ich ein kleines Programm implementiert ids entlang der Linien in der Frage erwähnt zu erzeugen, und diese waren die Ergebnisse eines der Probeläufe:

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

Jedes Mal, wenn die Länge des Hash erhöht, war dies aufgrund einer Kollision, so gab es sechs Kollisionen in diesem Fall. Die Anzahl ist die Anzahl von Tasten einer gegebenen Länge, die vor einer Kollision erzeugt wurde. Die MD5-Spalte zeigt den letzten abgeschnittenen Schlüssel, der erfolgreich hinzugefügt wurde, bevor es ein doppelter Schlüssel Fehler war. Die Spalte ganz rechts zeigt den Schlüssel in der Basis 62 (wenn ich habe die Umwandlung richtig gemacht).

Es sieht aus wie mehr und mehr Tasten mit jedem zusätzlichen Zeichen erzeugt werden, das ist das, was Sie sich vorstellen würden. Ich bin zuversichtlich, dass dieser Ansatz für nutzergenerierte Inhalte skaliert.

Für alle, die interessiert sind, hier ist, wie ich die Basis 62 Repräsentation für die letzte Spalte bekam:

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

(Hinzugefügt später:)

Hier ist eine Klasse, die sich um mehrere Dinge braucht, um die Erzeugung dieser IDs im Rahmen der Google App Engine verwandt. Standardmäßig Schlüssel, die von dieser Klasse erzeugt werden, sind nicht rein Basis 62, da das erste Zeichen eines GAE Schlüsselnamen alphabetisch sein muss. Diese Anforderung wurde hier angesprochen durch die Basis 52 für das erste Zeichen verwendet wird.

Die primäre Basis kann durch Änderung der „clist“ anderen Wert als 62 etwas geändert werden, dass der Konstruktor in (oder weggelassen) übergeben wurde. Man könnte will Zeichen entfernen, die leicht zu verwechseln, zum Beispiel „1“, „l“, „i“, etc.

Verbrauch:

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

Hier ist die Klasse:

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)

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow