8 Zeichen Zufallscode

Question

Ich habe mir die Antworten auf einige ähnliche Fragen auf SO angesehen, konnte aber nicht finden, wonach ich gesucht habe.

Gibt es einen effizienteren Weg, 8-stellige eindeutige IDs zur Basis 36 (0-9A-Z) zu generieren, als eine eindeutige ID zu erzeugen und die DB abzufragen, um zu sehen, ob sie bereits existiert, und dies zu wiederholen, bis man eine eindeutige ID erhält, die noch nicht verwendet wurde?

Andere Lösungen, die ich gefunden habe, verwenden die Zeit, aber das ist vielleicht zu einfach zu erraten und funktioniert möglicherweise nicht gut in verteilten Systemen. Betrachten Sie diese IDs als Promo-Codes.

Answer 1

Eine Möglichkeit ist, es andersherum zu machen: eine große Anzahl von ihnen in der Datenbank zu erzeugen, wann immer Sie sie brauchen, und dann entweder eine einzelne aus der DB zu holen, wenn Sie eine brauchen, oder eine ganze Reihe von ihnen für Ihren speziellen Prozess zu reservieren (d.h. sie als "potenziell verwendet" in der Datenbank zu markieren) und sie dann aus dem Speicher zu verteilen.

Answer 2

Ich bezweifle, dass Ihr "ineffizienter" Ansatz tatsächlich ineffizient ist. Bedenken Sie dies:

• Es gibt 36^8 == 2.821.109.907.456 (2,8 Billionen) mögliche IDs.
• Bei N existierenden IDs ist die Chance, dass eine neue, zufällig generierte ID mit N in ~2,8 Billionen kollidiert.
• Sofern N nicht in die Hunderte von Milliarden geht, wird Ihr Algorithmus "Erzeugen einer eindeutigen ID und Abfrage der DB, um zu sehen, ob sie bereits existiert" fast immer in einem Zyklus enden.

Bei sorgfältigem Design sollten Sie in der Lage sein, eine garantiert eindeutige ID in einer Datenbankabfrage zu generieren, und zwar fast immer ... es sei denn, Sie haben eine schrecklich große Anzahl von bestehenden IDs. (Und wenn das der Fall ist, fügen Sie einfach ein paar weitere Zeichen an die ID an, und das Problem verschwindet wieder).

Wenn Sie möchten, können Sie die durchschnittliche Anzahl der Datenbankoperationen auf weniger als eine pro ID reduzieren, indem Sie die IDs in Stapeln generieren, aber das bringt potenzielle Komplikationen mit sich, insbesondere wenn Sie die Anzahl der tatsächlich verwendeten IDs aufzeichnen müssen.

Aber wenn Sie höchstens 150.000 IDs haben (ich nehme an, die über einen langen Zeitraum generiert wurden), dann lohnt sich die Erstellung der IDs in Stapeln nicht ... es sei denn, Sie führen einen Massen-Upload durch.

Answer 3

Leider sind 8 Ziffern zur Basis 36 ein bisschen wenig. Es gibt nur 2 Millionen mögliche IDs. Wenn Sie also 1,4 Millionen zufällig generieren, haben Sie eine halbe Chance auf eine Kollision.

Sie könnten einen PRNG mit einer großen Periode verwenden und seinen aktuellen Zustand über eine Bijektion auf Ihren ID-Raum abbilden. Ein 41-Bit-LFSR wäre zwar nicht unknackbar, könnte aber einigermaßen in Ordnung sein, wenn das, was Sie schützen wollen, nicht allzu wertvoll ist. Man könnte etwas verteilen, ohne ständig auf die DB zugreifen zu müssen, indem man verschiedene Knoten mit einer anderen Position für den Start des Zyklus versieht.

Das Problem bei jeder derartigen deterministischen Methode ist natürlich, dass sie, wenn sie einmal kaputt ist, komplett kaputt ist, und man kann sich nicht mehr auf irgendwelche IDs verlassen. Daher ist es wahrscheinlich der richtige Weg, die Nummern aus einer Datenbank zu ziehen und sie in Stapeln von tausend Stück oder so zu verteilen.

Hätte man einen größeren ID-Raum, könnte man sicherere Techniken verwenden, z. B. könnte die ID aus etwas bestehen, das die Quelle identifiziert, einer inkrementellen Seriennummer für diese Quelle und einem HMAC, der einen eindeutigen Schlüssel für die Quelle verwendet.

Answer 4

Wenn es nur eine Quelle für IDs gibt (d. h. Sie müssen nicht mehrere unabhängige Quellen auf verschiedenen Rechnern koordinieren), können Sie wie folgt vorgehen:

• Berechnen Sie die maximale Anzahl von Bits, die eine Zahl haben darf, damit sie die in einer 8-Zeichen-Zeichenfolge von 0-9A-Z enthaltenen Informationen nicht überschreitet. Dies wäre floor(log2(36^8)) = 41 Bits.

• Ein Zähler (mit 41 Bits) soll bei Null beginnen

• Rückkehr transform(counter++) für jede ID-Anfrage

En transform Funktion muss bijektiv sein und kann eine beliebig lange Folge der folgenden Operationen sein (die alle selbst bijektiv sind, wenn sie modulo berechnet werden 2^41 ):

• xor mit einem festen Wert
• Drehen nach links oder rechts um einen festen Wert
• die Bits durch eine feste Zuordnung neu anordnen (eine Verallgemeinerung der obigen Drehung)
• einen festen Wert addieren oder subtrahieren

Wenn Sie damit fertig sind, brauchen Sie nur noch eine weitere Funktion encode(number) um die Zahl zur Basis 36 umzurechnen.

Answer 5

Hier ist ein Python-Code zum Erzeugen von zufälligen Base36-IDs.

import random

def base36encode(number, alphabet='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'):
    '''
    Convert positive integer to a base36 string.

    Source: http://en.wikipedia.org/wiki/Base_36#Python_Conversion_Code
    '''
    if not isinstance(number, (int, long)):
        raise TypeError('number must be an integer')

    # Special case for zero
    if number == 0:
        return '0'

    base36 = ''

    sign   = ""
    if number < 0:
        sign  ='-'
        number=-number

    while number != 0:
        number, i = divmod(number, len(alphabet))
        base36 = alphabet[i] + base36

    return sign + base36

def generateID(length=8):
    '''Generates a base36 ID.'''

    random.seed()
    id = base36encode(random.randint(0, (36**length)-1))

    # append 0s to ensure desired length
    while len(id) < length:
        id = '0' + id

    return id

def generateMultipleIDs(n):
    '''Generate n number of unique, base36 IDs.'''

    output = set()

    while len(output) < n:
        output.add(generateID())

    return output