Zufallswert 6-stellig

[romy]

Hallo zusammen,

ich brüte ein Weile über einem Problemchen, was vermutlich gar keins ist. Vielleicht kann mir jemand das Brett vom Kopf nehmen.

Ausgangssituation: Ich verarbeite Dateien, denen ich eine eindeutige Ziffernfolge mitgeben möchte. Diese darf maximal 6 Stellen lang sein und muss nur eindeutig pro Tag sein.

Meine erste Idee war hhmmss, scheitert daran, dass mehrere Dateioperationen pro Sekunde passieren können. (Ich muss zumindest damit rechnen) Millisekunden mit einzubringen scheitert erst an der Länge und zum zweiten, wenn ich dafür beispielsweise die Minuten weglassen würde an der Eindeutigkeit.

Vielleicht ist da auch einfach alles zu kompliziert und es geht viel einfacher? Das Datum muss nicht drin vorkommen, es war nur meine Idee einer Eindeutigkeit pro Tag. 6 Stellen sind nicht wirklich ausreichend für mehr EIndeutigkeit.

Hat jemand von Euch eine Idee?

Danke!

ciao
romy

[Der Martin]

Hallo Romy,

ich brüte ein Weile über einem Problemchen, was vermutlich gar keins ist.

das ist oft so. :-)

Ausgangssituation: Ich verarbeite Dateien, denen ich eine eindeutige Ziffernfolge mitgeben möchte. Diese darf maximal 6 Stellen lang sein und muss nur eindeutig pro Tag sein.

Das impliziert, dass die Anzahl der Operationen pro Tag die Million nicht überschreiten darf.

Meine erste Idee war hhmmss, scheitert daran, dass mehrere Dateioperationen pro Sekunde passieren können. (Ich muss zumindest damit rechnen)

Stimmt, ebenso wenn du einheitlich mit Sekunden (0..86399) rechnen würdest.

Vielleicht ist da auch einfach alles zu kompliziert und es geht viel einfacher? Das Datum muss nicht drin vorkommen, es war nur meine Idee einer Eindeutigkeit pro Tag. 6 Stellen sind nicht wirklich ausreichend für mehr EIndeutigkeit.

Oh, ich finde schon. Wie wäre es mit einem einfachen Zähler, der mit jeder Operation inkrementiert wird, also von 000000 bis 999999 durchläuft? Dann hast du zwar eine nachvollziehbare Systematik, aber du hast ja auch nicht gefordert, dass die Kennzeichnung zufällig sein soll - nur eindeutig.
Einfache Lösungen sind oft die besten ...

Schönes Wochenende schon mal,
 Martin

[romy]

Hallo Martin,

Das impliziert, dass die Anzahl der Operationen pro Tag die Million nicht überschreiten darf.

ja, bei weitem nicht.

Oh, ich finde schon. Wie wäre es mit einem einfachen Zähler, der mit jeder Operation inkrementiert wird, also von 000000 bis 999999 durchläuft? Dann hast du zwar eine nachvollziehbare Systematik, aber du hast ja auch nicht gefordert, dass die Kennzeichnung zufällig sein soll - nur eindeutig.
Einfache Lösungen sind oft die besten ...

Ich habe eine Information vergessen, die wichtig war, sorry. Ein Zähler sollte nicht genommen werden, weil das ausführende Programm später mal mehrfach gestartet werden kann und dann parallel läuft und dann bräuchte man einen Zähler pro Programminstanz, der auch eindeutig ist über alle Instanzen. (Möglich ja irgendwie schon -> Instanznummer und nur noch 5-stellige Zählerzahl)
Ausgeschlossen ist der Zähler natürlich nicht, aber ich wollte mal schauen, ob es nicht noch eine kürzere Lösung gibt.

ciao
romy

[suit]

Ich habe eine Information vergessen, die wichtig war, sorry. Ein Zähler sollte nicht genommen werden, weil das ausführende Programm später mal mehrfach gestartet werden kann und dann parallel läuft und dann bräuchte man einen Zähler pro Programminstanz, der auch eindeutig ist über alle Instanzen.

Ob du einen Zähler nimmst oder eine Zufallszahl - du musst ohnehin über die Instanzen hinweg prüfen, ob der Wert schon existiert - ausser wie du schon sagst, ein Präfix für die Instanz - allerdings bist du dann im Dezimalsystem auf 10 Instanzen beschränkt.

[Der Martin]

Hallo,

Wie wäre es mit einem einfachen Zähler ...
Ich habe eine Information vergessen, die wichtig war, sorry. Ein Zähler sollte nicht genommen werden, weil das ausführende Programm später mal mehrfach gestartet werden kann und dann parallel läuft und dann bräuchte man einen Zähler pro Programminstanz, der auch eindeutig ist über alle Instanzen.

da würde ich dann eher dafür sorgen, dass -auch wenn das Programm in mehreren Instanzen läuft- die Vergabe der Nummer ein *einer* zentralen Stelle erfolgt. Dann können meinetwegen fünf Instanzen laufen, aber wenn jede sich brav die nächste Nummer zentral zuteilen lässt, ginge das auch. Oder muss an der Nummer nachher erkennbar sein, von welcher Instanz sie stammt?

Im anderen Fall bräuchtest du eindeutig getrennte Nummernkreise, und damit schaffst du dir indirekt immer eine zusätzliche Einschränkung.

(Möglich ja irgendwie schon -> Instanznummer und nur noch 5-stellige Zählerzahl)

Müssen diese 6stelligen Kennungen unbedingt rein numerisch sein? Nachdem ich Beats Beitrag gelesen habe, bin ich nämlich auch auf die Idee gekommen, eine 6stellige alphanumerische Kennung zu verwenden. Damit hättest du dann 36^6 = 2'176'782'336 mögliche Kombinationen bei Verwendung von [0-9A-Z]. Das reicht auch locker wieder für einen auf Millisekunden heruntergebrochenen Timestamp.

So long,
 Martin

[romy]

Hallo Martin,

da würde ich dann eher dafür sorgen, dass -auch wenn das Programm in mehreren Instanzen läuft- die Vergabe der Nummer ein *einer* zentralen Stelle erfolgt. Dann können meinetwegen fünf Instanzen laufen, aber wenn jede sich brav die nächste Nummer zentral zuteilen lässt, ginge das auch. Oder muss an der Nummer nachher erkennbar sein, von welcher Instanz sie stammt?

Nein, es müsste nicht erkennbar sein. Hier erkenne ich deutlich meine doch Verringerte Kenntnis in der Programmierung. Ich war davon ausgegangen, dass man dadurch damit rechnen müsste, dass mehrere Programme gleichzeitig auf dei Nummernquelle zugreifen. Aber das lässt sich programmiertechnisch bestimmt auch lösen.

Müssen diese 6stelligen Kennungen unbedingt rein numerisch sein? Nachdem ich Beats Beitrag gelesen habe, bin ich nämlich auch auf die Idee gekommen, eine 6stellige alphanumerische Kennung zu verwenden. Damit hättest du dann 36^6 = 2'176'782'336 mögliche Kombinationen bei Verwendung von [0-9A-Z]. Das reicht auch locker wieder für einen auf Millisekunden heruntergebrochenen Timestamp.

Ich habe herausgefunden, dass wir tatsächlich alphanumerische Werte benutzen können.

Ist die Beat-Variante denn dann eindeutig. Kann der Hashwert nicht zufällig auf den ersten 6-Stellen gleich sein? Ansonsten finde ich die Idee gut:

Timestamp hashen und das Ergebnis auf 6 Stellen kürzen. Ob das reicht?

ciao
romy

[Der Martin]

Hallo,

Ich habe herausgefunden, dass wir tatsächlich alphanumerische Werte benutzen können.
Ist die Beat-Variante denn dann eindeutig. Kann der Hashwert nicht zufällig auf den ersten 6-Stellen gleich sein?

wie die entstandene Diskussion zeigt, könnte er das wohl.

Ansonsten finde ich die Idee gut:
Timestamp hashen und das Ergebnis auf 6 Stellen kürzen. Ob das reicht?

Ich verstehe nicht, warum die Jungs hier immer irgendeinen Hash-Wert bilden wollen. Ich würde einfach den auf Millisekunden aufgelösten Timestamp direkt nehmen und sozusagen in einem Zahlensystem zur Basis 36 schreiben. Dann habe ich kollisionsfreie Nummern, solange nicht zwei Zugriffe exakt in derselben Millisekunde stattfinden.

Ciao,
 Martin

[Jens Holzkämper]

Tach,

Ich verstehe nicht, warum die Jungs hier immer irgendeinen Hash-Wert bilden wollen.

ich auch nicht, im Zweifelsfall erzeugt das mehr Kollisionen als den Timestamp direkt zu nehmen.

Ich würde einfach den auf Millisekunden aufgelösten Timestamp direkt nehmen und sozusagen in einem Zahlensystem zur Basis 36 schreiben. Dann habe ich kollisionsfreie Nummern, solange nicht zwei Zugriffe exakt in derselben Millisekunde stattfinden.

Und sogar das kann man noch ausschließen indem man die PID des Prozesses voranstellt bei 6^36 Kombinationen bekommt man die auch noch locker unter.

mfg
Woodfighter

[romy]

Hallo Martin,

Ansonsten finde ich die Idee gut:
Timestamp hashen und das Ergebnis auf 6 Stellen kürzen. Ob das reicht?
Ich verstehe nicht, warum die Jungs hier immer irgendeinen Hash-Wert bilden wollen. Ich würde einfach den auf Millisekunden aufgelösten Timestamp direkt nehmen und sozusagen in einem Zahlensystem zur Basis 36 schreiben. Dann habe ich kollisionsfreie Nummern, solange nicht zwei Zugriffe exakt in derselben Millisekunde stattfinden.

Ein Timestamp ist 14-stellig, wenn ich den jetzt zur Basis 36 darstelle, habe ich doch mehr als 6 Ziffern, oder?

ciao
romy

[Der Martin]

Hi Romy,

Ein Timestamp ist 14-stellig

naja, ich zähle 13, aber sei's drum. Es ist ein Zahlenwert in der Größenordnung von einer Billion, wenn wir vom Unix-Timestamp reden (Anzahl der Millisekunden seit 01.01.1970). Das reicht natürlich nicht, ich hatte ja schon ausgerechnet, dass ich mit 6 Stellen zur Basis 36 Werte bis knapp über 2 Milliarden darstellen kann.

Aber du hattest ja auch gesagt, du bräuchtest Eindeutigkeit nur innerhalb eines Tages. Also kannst du die Timestamps ja auch auf 0 Uhr der Systemzeit beziehen; dann hast du nur Werte von 0 .. 84'399'999. Dann reicht's dicke. :-)

So long,
 Martin

[romy]

Hallo Martin,

naja, ich zähle 13, aber sei's drum. Es ist ein Zahlenwert in der Größenordnung von einer Billion, wenn wir vom Unix-Timestamp reden (Anzahl der Millisekunden seit 01.01.1970). Das reicht natürlich nicht, ich hatte ja schon ausgerechnet, dass ich mit 6 Stellen zur Basis 36 Werte bis knapp über 2 Milliarden darstellen kann.

Die 14 habe ich flüchtig mit google gelesen.

Aber du hattest ja auch gesagt, du bräuchtest Eindeutigkeit nur innerhalb eines Tages. Also kannst du die Timestamps ja auch auf 0 Uhr der Systemzeit beziehen; dann hast du nur Werte von 0 .. 84'399'999. Dann

reicht's dicke. :-)
Jetzt habe ich es verstanden, danke, so ist es schön.

ciao
romy

[suit]

Timestamp hashen und das Ergebnis auf 6 Stellen kürzen. Ob das reicht?

Wie schon mehrmals in diesem Thread erwähnt verringerst du damit nur die Entropie - egal wie oft du einen definierten Timestamp hasht, verschlüsselst oder sonstwas damit machst: das Ergebnis wird nach dem definitieren Algorithmus immer gleich sein. Es sieht nur "kompliziert" aus.

[Christoph]

Moin.

da würde ich dann eher dafür sorgen, dass -auch wenn das Programm in mehreren Instanzen läuft- die Vergabe der Nummer ein *einer* zentralen Stelle erfolgt [...]
[...] Ich war davon ausgegangen, dass man dadurch damit rechnen müsste, dass mehrere Programme gleichzeitig auf dei Nummernquelle zugreifen.

Schreib den Wert des globalen Zählers in eine Datei. Dank Locking-Mechanismen des Dateisystems ist es möglich, den Wert über Instanzen hinweg konsistent zu halten.

Müssen diese 6stelligen Kennungen unbedingt rein numerisch sein?
Ich habe herausgefunden, dass wir tatsächlich alphanumerische Werte benutzen können.

Wie wär's denn mit simpler Hex-Darstellung? Bei 6 Ziffern stehen dann 3 Byte, d.h. 2^24 ≈ 16.8 Mio Werte zur Verfügung. Das würde die Umrechnung erleichtern, da die Ausgabe hexadezimaler Werte in den Standardbibliotheken der meisten Programmiersprachen zu finden ist. Ansonsten ist der Algorithmus für die Kodierung der Zahl mit beliebigem Alphabet aber nicht wirklich kompliziert.

Christoph

PS: Statt dem UNIX timestamp könnte auch die vergangene Rechenzeit (clock ticks) als während der Laufzeit einer Instanz eindeutiger Wert verwendet werden, um Kollisionen zu vermeiden.

[suit]

PS: Statt dem UNIX timestamp könnte auch die vergangene Rechenzeit (clock ticks) als während der Laufzeit einer Instanz eindeutiger Wert verwendet werden, um Kollisionen zu vermeiden.

Kommt man da auch mit PHP ran? Ich kenne nur posix_times() - das liefert aber nur die vergangen Ticks seit dem letzten Reboot - ganz scheint das aber nicht zu stimmen. Eine 1,2-GHz-CPU bringts schließlich auf rund 1,2 Milliarden Ticks pro Sekunde :)

[Beat]

Hat jemand von Euch eine Idee?

Paradigma: bringe die grösst mögliche Informationsdichte in 6 zeichen.
Tue dies auf eine websichere Weise.

use Time::HighRes qw(time);
use Digest::SHA1  qw(sha1_base64);

nimm noch ein sprintf()

Und ich denke der Mix sollte klar sein.

mfg Beat

[romy]

Hallo Beat,

Paradigma: bringe die grösst mögliche Informationsdichte in 6 zeichen.
Tue dies auf eine websichere Weise.
use Time::HighRes qw(time);
use Digest::SHA1  qw(sha1_base64);
nimm noch ein sprintf()
Und ich denke der Mix sollte klar sein.

Klingt toll ;) Aber ich verstehe es noch nicht. (In Perl bin ich nicht zu Hause, aber ich denke, dass tut auch nichts zur Sache)

Ich verstehe Folgendes:

• nimm die Zeit (6 Zeichen)
• nimm eine Zeichenkette oder Hashwert (64/32 Zeichen)
• mache irgendwas mit einer formatierten Ausgabe (so interpretiere ich sprintf)

Wie muss ich die 2 Werte vermixen, damit es eindetig wird?

ciao
romy

[Beat]

Paradigma: bringe die grösst mögliche Informationsdichte in 6 zeichen.
Tue dies auf eine websichere Weise.
use Time::HighRes qw(time);
use Digest::SHA1  qw(sha1_base64);
nimm noch ein sprintf()
Und ich denke der Mix sollte klar sein.

Klingt toll ;) Aber ich verstehe es noch nicht. (In Perl bin ich nicht zu Hause, aber ich denke, dass tut auch nichts zur Sache)

Ich verstehe Folgendes:

• nimm die Zeit (6 Zeichen)

Time::HiRes gibt über time() eine Fliesskomma Zahl in Sekunden aus, deren Genauigkeit dem OS unterliegt, aber in aller Regel Genauigkeit bin in 100stel Sekunden ergibt.

• nimm eine Zeichenkette oder Hashwert (64/32 Zeichen)

Nimm die Fliesskommazahl und bilde einen base_64 kodierten Hash

• mache irgendwas mit einer formatierten Ausgabe (so interpretiere ich sprintf)

Kürze den Hash auf 6 Stellen

Wie muss ich die 2 Werte vermixen, damit es eindetig wird?

my $id = sprintf("%6s", sha1_base64( time() ) );

mfg Beat

[romy]

Hallo Beat,

Time::HiRes gibt über time() eine Fliesskomma Zahl in Sekunden aus, deren Genauigkeit dem OS unterliegt, aber in aller Regel Genauigkeit bin in 100stel Sekunden ergibt.
Nimm die Fliesskommazahl und bilde einen base_64 kodierten Hash
my $id = sprintf("%6s", sha1_base64( time() ) );

Wie ich schon Martin fragte, ob das reicht, könnten dann die 6 Zeichen nicht mehrfach vorkommen? Sonst wäre das genau perfekt.

ciao
romy

[Beat]

my $id = sprintf("%6s", sha1_base64( time() ) );

Wie ich schon Martin fragte, ob das reicht, könnten dann die 6 Zeichen nicht mehrfach vorkommen? Sonst wäre das genau perfekt.

Die Wahrscheinlichkeit einer Kollision entspricht der Bittiefe, wobei base_64 dir eine websichere bittiefe gibt, also 6 der 8 Bits.
time() ergibt eine Fliesskommazahl mit 9 Stellen vor dem Komma (nur 4 Stellen sind für den tag relevant) und 4 bis 7 Stellen nach dem Komma.
Zusammen also 13 bis 17 bits. 3 Dezimalstellen entsprechen 10bits. Du hast also hier mindestens 30 bits.

Wie immer bei ids kannst du das verbessern durch
my $id = sprintf("%6s", sha1_base64( time() . rand() . "Salzstengel" ) );

Die Auflösung aber reicht, dass der hash zuerst einmal sicher ist.
Da uniqueness nur pro Tag gefordert wird, ist die Wahrscheinlichkeit für Kollisionen gering. Du kannst mit einem Raum von 6 x 3 Bits rechnen.
Dieser Raum wird durch den time() input nicht ganz ausgeschöpft, durch sich das zu etwa 14 bits verringert.
Die Wahrscheinlichkeit für eine Kollission pro tag ist Abhängig von der Erwarteten Menge an zu produzierenden IDs.

Dies nur als grobe Schätzung.

Wenn du mehr Willst musst du mehr Zeichen-Raum zulassen.

mfg Beat

[suit]

Die Wahrscheinlichkeit für eine Kollission pro tag ist Abhängig von der Erwarteten Menge an zu produzierenden IDs.

Die Wahrscheinlichkeit dass eine Kollision auftritt, wenn die 2 Instanzen zur selben Sekunde ausgeführt werden ist 100%.

[Beat]

Die Wahrscheinlichkeit für eine Kollission pro tag ist Abhängig von der Erwarteten Menge an zu produzierenden IDs.
Die Wahrscheinlichkeit dass eine Kollision auftritt, wenn die 2 Instanzen zur selben Sekunde ausgeführt werden ist 100%.

Erklärung?

mfg Beat

[suit]

Erklärung?

Wenn du 2x einen Hash aufgrund einer Zahl erzeugst die in beiden Fällen identisch ist, erhältst du 2x denselben Hash. Wenn du diesen Hash nun als Base64 darstellst, ist er immer noch identisch.

z.B.:

1251459373 ist Freitag, 14. August 2009 + Zeit (heute "jetzt")

SHA1 produziert daraus das hier: 5057c2b8640e5b3240bf61da1a00ea00c28d2cf7

In Base64 sieht das so aus: NTA1N2MyYjg2NDBlNWIzMjQwYmY2MWRhMWEwMGVhMDBjMjhkMmNmNw==

Und egal wie oft du das machst - zum selben Zeitpunkt gestartet, ist das Ergebnis gleich.

[Beat]

Und egal wie oft du das machst - zum selben Zeitpunkt gestartet, ist das Ergebnis gleich.

Das habe ich schon verstanden.
Die Tatsache dass Time::HiRes verwendet und noch eine Zufallszahl im hash verwendet werden, sollte das wohl ausmerzen.

Streng genommen ist es auf jedem OS unmöglich, dass zwei Prozesse gleichzeitig gestartet werden. Möglich ist, dass eine ungenaue Uhr eine zufällige Gleichzeitigkeit angibt.

Kollisionen sind dann nur noch von der Bittiefe des resultierenden base64 Strings abhängig.

mfg Beat

[suit]

Wie ich schon Martin fragte, ob das reicht, könnten dann die 6 Zeichen nicht mehrfach vorkommen? Sonst wäre das genau perfekt.

Die aktuelle Zeit zu hashen erzeugt, wenn das zwei Mal gleichzeitig passiert auch zweimal denselben Hash - auch wenn man diesen dann als Base64 darstellt, wird er dadurch nicht eindeutig - dir bleiben dann noch bei einem 6-Stelligen String exakt 68.719.476.736 - der ursprüngliche SHA1-Hash hätte aber (theoretisch) ~1,461x10^48 Möglichkeiten. Allerdings erzeugt Time ohnehin nur 2^32 bzw 2^64 eindeutige Werte - nachdem ein Tag aber nur 86400 Sekunden hat, gewinnst du dadurch nichts. Du verringerst den Wertepool tendentiell sogar, da der Hash kollisionen haben kann und du tendentiell =< 86400 mögliche Werte hast.

[Bobby]

Moin

Wie ich schon Martin fragte, ob das reicht, könnten dann die 6 Zeichen nicht mehrfach vorkommen? Sonst wäre das genau perfekt.

Dann füge dem Timestring ein Zufalls-Salt hinzu und bilde daraus den Hash. Dann ist es defintiv ein anderer Hash!

Beispiel (ungeprüft, nur theoretisch)

$salt=mt_rand();
$id = sprintf("%6s", sha1_base64( time().$salt ) );

Gruß Bobby

[suit]

Dann füge dem Timestring ein Zufalls-Salt hinzu und bilde daraus den Hash. Dann ist es defintiv ein anderer Hash!

Warum so herumplagen - uniqid() mit einem Präfix tuts doch auch? Aber das ist auch nur Pseudozufällig und nicht eindeutig.

[ChrisB]

Hi,

Ausgangssituation: Ich verarbeite Dateien, denen ich eine eindeutige Ziffernfolge mitgeben möchte. Diese darf maximal 6 Stellen lang sein und muss nur eindeutig pro Tag sein.

Meine erste Idee war hhmmss

YYMMDD?

MfG ChrisB

[Encoder]

Stimmt, den Wunsch "pro Tag eindeutig" kann man eigentlich auch so verstehen ;-)

[Gunnar Bittersmann]

@@ChrisB:

nuqneH

YYMMDD?

Stotterst du?

Qapla'

[Beat]

YYMMDD?

Stotterst du?

alle 100 Jahre... doch mit Geduld kann ich es hören.

mfg Beat

[Encoder]

Ausgangssituation: Ich verarbeite Dateien

Mit was, wie und wo? Wenn du eine Datenbank zur Hand hast, könntest du dort eine ID generieren lassen.
Die Idee mit der Basis 36 wäre auch noch erweiterbar auf Base64, da kriegst du dann alles mögliche mehr unter.
Oder unterscheide zwischen Groß und Kleinbuchstaben, dann kriegst du eine noch breitere Basis.