PHP kurze eindeutige ID-Generierung mit auto_increment?

Question

Ich möchte eine kurze, eindeutige ID generieren, ohne auf Kollisionen prüfen zu müssen.

ich zur Zeit so etwas wie dieses, aber die ID ich generieren derzeit wird zufällig ausgewählt und überprüft für Kollisionen in einer Schleife ärgerlich und wird teuer, wenn die Anzahl der Datensätze deutlich wächst.

Normalerweise ist die Sorge um Kollisionen kein Problem, aber die eindeutige ID, die ich erzeugen möchte, ist eine kurze eindeutige Zeichenkette mit 5-8 Zeichen, alphanumerisch, wie tinyurl.

EDIT: Ich möchte mit 5 Zeichen beginnen, und wenn ich 60 Millionen Einträge getroffen, dann weiter mit 6 .. so weiter und so fort.

Zu diesem Zweck dachte ich, ich könnte einen Auto_increment-Wert, der von den Benutzern ausgeblendet ist, und präsentieren sie stattdessen mit einer MD5 oder eine andere Methode, um eine eindeutige Zeichenfolge daraus zu generieren.

Generierte Strings sollten nicht linear erscheinen, also ist die einfache Konvertierung der auto_incremented ID in base 36 [0-9A-Z] etwas zu einfach, aber eine Funktion wie das ist, wo ich damit hingehe.

EDIT: Sicherheit ist kein Problem, da dies nicht verwendet wird, um Informationen zu sichern. Es ist einfach eine Verknüpfung zu einer längeren Zeichenfolge. Danke.

Vielen Dank für Ihre Vorschläge und Entschuldigung für die Verzögerung. Zahnarzt ..

Answer 1

Sie benötigen etwas, das durch die Konstruktion, dh eine Permutationsfunktion korrekt ist: das ist eine Funktion, die eine tut Eins-zu-eins, reversible Zuordnung einer Ganzzahl (Ihr sequenzieller Zähler) zu einer anderen. Einige Beispiele (eine beliebige Kombination dieser sollte auch funktionieren):

• einige der Bits invertiert (fi eine XOR,^in PHP)
• die Orte von Bits Swapping (($ i & 0xc)> > 2 | ($ i & 0x3) < < 2) oder einfach die Reihenfolge aller Bits umkehren
• Hinzufügen eines konstanten Wertes modulo Ihre maximale Reichweite (muss ein Faktor von zwei sein, wenn Sie dies mit denen kombinieren oben)

Beispiel: Diese Funktion wird 0 umwandeln, 1, 2, 3, 5, .. in 13, 4, 12, 7, 15, .. für Zahlen von bis zu 15:

$i=($input+97) & 0xf; 
$result=((($i&0x1) << 3) + (($i&0xe) >> 1))^0x5; 

EDIT

eine einfachere Möglichkeit wäre einen Kongruenzgenerator (LCG, die in der Regel zur Erzeugung von Zufallszahlen verwendet wird) zu verwenden, die durch eine Formel der Form definiert ist:

X_n+1 = (a * X_n + c) mod m 

für good values von a, c und m , die Folge von X_0, X_1 .. X_m-1 enthält al l Zahlen zwischen 0 und m-1 genau einmal. Jetzt können Sie von einem linear ansteigenden Index ausgehen und den nächsten Wert in der LCG-Sequenz als Ihren "geheimen" Schlüssel verwenden.

EDIT2

Umsetzung: Sie können design your own LCG parameters, aber wenn man etwas falsch gemacht, es wird nicht das gesamte Spektrum abdecken (und damit Duplikate haben), so werde ich eine veröffentlichte verwenden und versucht, von Parametern hier aus this paper:

a = 16807, c = 0, m = 2147483647 

Dies gibt Ihnen einen Bereich von 2 ** 31. Mit pack() können Sie die resultierende ganze Zahl als String erhalten, base64_encode() macht es eine lesbare Zeichenkette (bis zu 6 signifikante Zeichen, 6 Bits pro Byte), so könnte dies Ihre Funktion sein:

substr(base64_encode(pack("l", (16807 * $index) % 2147483647)), 0, 6) 

Answer 2

Ich denke, das wird nie wirklich sicher sein, wie Sie nur die Verschlüsselungsmethode hinter der kurzen eindeutigen Zeichenfolge finden müssen eine ID kapern. Ist das Überprüfen auf Kollisionen in einer Schleife wirklich so problematisch in Ihrer Umgebung?

Answer 3

Ein MD5 einer inkrementierenden Zahl sollte in Ordnung sein, aber ich befürchte, dass wenn Sie Ihre MD5 (die normalerweise 128 Bit ist) auf 5-8 Zeichen gekürzt werden, werden Sie fast sicher die Fähigkeit beschädigen, als zu handeln eine einzigartige Signatur ...

Answer 4

Sie könnten wahrscheinlich einen MD5-Hash der aktuellen Datetime/Zufallszahl und gestutzt es in die Länge, die Sie benötigen (5-8 Zeichen) und speichern Sie es als das ID-Feld erzeugen.

Wenn Sie verwenden diese Informationen in einer Datenbank zu speichern, müssen Sie nicht ein for-Schleife verwenden, um die Kollisionsprüfung zu tun, aber man konnte nicht nur eine select-Anweisung - so etwas wie

SELECT count(1) c FROM Table WHERE id = :id 

wo : ID wäre die neu generierte ID. Wenn c größer als 0 ist, wissen Sie, dass es bereits existiert.

EDIT

Dies kann, darüber gehen möglicherweise nicht der beste Weg sein. Aber ich gebe es eine Chance, also denke ich, was Sie brauchen, ist irgendwie eine Zahlen in eine einzigartige kurze Zeichenfolge zu konvertieren und das ist nicht in der Reihenfolge.

Ich denke, wie Sie schon gesagt haben, Base64-Codierung macht bereits die Nummer zu kurze String-Konvertierung. Um das Sequenzproblem zu vermeiden, könnten Sie eine Zuordnung zwischen Ihren automatisch generierten IDs zu einem "zufälligen" Wert haben (unique mapping). Dann können Sie Base64 diesen eindeutigen Wert kodieren.

Sie können diese Zuordnung wie folgt erstellen. Lassen Sie eine temporäre Tabelle Werte zwischen 1 und 10.000.000 speichern. Sortieren Sie es in zufälliger Reihenfolge und speichern Sie es in Ihrer Map-Tabelle.

INSERT INTO MappingTable (mappedId) SELECT values FROM TemporaryTable ORDER BY RAND() 

Wo Mapping die 2 Felder-ID (Ihre automatisch generierte ID aussehen würde gegen diese) und mappedId (das ist, was Sie die Base64-Codierung für erzeugen würde) haben würde.

Wenn Sie näher an 10.000.000 kommen, können Sie den obigen Code erneut ausführen und ändern Sie die Werte in der temporären Tabelle mit 10.000.001-20.000.000 oder so ähnlich.

Answer 5

Ein MD5 einer laufenden Nummer sollte in Ordnung sein, aber ich mache mir Sorgen, dass fast sicher, wenn sind Kürzen Sie Ihre MD5 (die normalerweise 128 Bit) bis zu 5-8 Zeichen, werden Sie schädigen seine Fähigkeit, als eine einzigartige Signatur zu handeln ...

Völlig wahr. Insbesondere, wenn Sie Ihre 80% ige Kollisionswahrscheinlichkeit erreichen, ist ein abgeschnittener MD5 so gut wie eine beliebige Zufallszahl, um die Eindeutigkeit für sich zu garantieren, d. H. Wertlos.

Aber da Sie sowieso eine Datenbank verwenden, warum nicht einfach einen UNIQUE INDEX verwenden? Auf diese Weise wird die Eindeutigkeitsprüfung (viel effizienter als eine Schleife) von MySQL selbst durchgeführt. Versuchen Sie einfach, die INSERT mit Ihrem MD5-generierten Schlüssel zu tun, und wenn es fehlschlägt, versuchen Sie es erneut ...

Answer 6

Sie verwenden können, eine bitweise XOR zu einigen der Bits Gerangel:

select thefield^377 from thetable; 

+-----+---------+ 
| a | a^377 | 
+-----+---------+ 
| 154 |  483 | 
| 152 |  481 | 
| 69 |  316 | 
| 35 |  346 | 
| 72 |  305 | 
| 139 |  498 | 
| 96 |  281 | 
| 31 |  358 | 
| 11 |  370 | 
| 127 |  262 | 
+-----+---------+ 

Answer 7

Wenn Sie nicht ein auto-increment-Feld verwenden können, und wollen eine absolut eindeutigen Wert, verwenden UUID. Wenn Sie sich dazu entschließen, etwas anderes zu verwenden (außer Autoinkrement), wäre es albern, NICHT nach Kollisionen zu suchen.

Answer 8

Dieser Blog-Eintrag hat etwas, was Sie suchen.

http://kevin.vanzonneveld.net/techblog/article/create_short_ids_with_php_like_youtube_or_tinyurl/