Cross-Plattform tauglicher GUID Generator


  • Administrator

    Also soweit mir bekannt ist, benutzt Windows für die GUID Erzeugung die UUID Version 4. Diese besteht ausschliesslich aus pseudo Zufallszahlen:
    http://en.wikipedia.org/wiki/UUID#Version_4_.28random.29
    http://msdn.microsoft.com/en-us/library/ms688568.aspx

    RFC: http://tools.ietf.org/html/rfc4122

    Grüssli



  • Stimmt schon...
    Wenn du also eine GUID einfach nur mit einem Zufallszahlengenerator erzeugst, kannst du nicht zu 100% sicher sein, dass sie sich von einer gegebenen zweiten GUID unterscheidet.

    ABER: vielleicht reicht dir ja eine 99,9999999999999999999999999999999999999706%, dass sich zwei gegebene GUIDs unterscheiden? Die Wahrscheinlichkeit, dass zwei echte 128 Bit Zufallszahlen übereinstimmen ist 2^-128 = 2,9387 * 10^-39

    Global gibts afaik keinen einheitlichen Standard für die Erzeugung von GUIDs - insofern wirds auch keine Garantie geben dass zwei gegebene GUIDs tatsächlich immer verschieden sind. Praktisch ists einfach nicht machbar die Unterschiedlichkeit sicherzustellen, du kannst schließlich nicht alle Rechner der Welt mal eben anfragen welche GUIDs schon belegt sind.

    Zu der ohnehin geringen Wahrscheinlichkeit, mit einem Zufallsgenerator eine bereits vergebene GUID zu erzeugen kommt die auch sehr geringe Wahscheinlichkeit, dass du im Falle einer duplizierten GUID mit dem Rechner überhaupt Kontakt hast der deine GUID bereits verwendet, ganz zu schweigen von der Chance dass dadurch wirklich ein Konflikt entsteht.



  • Pseudozufallszahlen muss man sowieso verwenden. Echte Zufallszahlen zu erzeugen ist doch relativ schwer ^^.

    Als seed könnte man eventuell die MAC Adresse der Netzwerkkarte + nen Timestamp nehmen und daraus dann eine UID erzeugen welche ziemlich sicher einzigartig ist.
    Die Frage ist wie viel Code du schreiben willst nur um eine gute Zufallszahl als seed zu erhalten.

    Vorschlag für nen GUID Standard:
    Google hat ne DB aufzusetzen in der jeder der eine GUID verwenden will zuerst nach schauen muss ob diese schon verwendet ist und falls nicht muss er diese eintragen xD

    Keros


  • Administrator

    Keros schrieb:

    Echte Zufallszahlen zu erzeugen ist doch relativ schwer ^^.

    Nein, man kann dazu das Rauschen vom PC nehmen. Schau dir mal /dev/random bei Linux an:
    http://en.wikipedia.org/wiki//dev/random

    Keros schrieb:

    Vorschlag für nen GUID Standard:
    Google hat ne DB aufzusetzen in der jeder der eine GUID verwenden will zuerst nach schauen muss ob diese schon verwendet ist und falls nicht muss er diese eintragen xD

    Wieso Google? Wenn schon wäre das die Aufgabe von der IETF.
    Allerdings wird das nicht funktionieren, weil eine GUID auch erstellt werden können muss, wenn keine Netzwerkkarte vorhanden ist und somit keine Internetverbindung.

    @Tachyon,
    Auf Unix/Linux/Mac soll man anscheinend libuuid verwenden können. Ich weiss nicht, ob es auch eine Portierung für Windows gibt. Aber unter Windows geht es ja ganz einfach über CoCreateGUID . Daher, für die Erstellung von GUIDs kann man wohl relativ schnell was kleines zusammenschustern.

    Grüssli



  • Dravere schrieb:

    Nein, man kann dazu das Rauschen vom PC nehmen. Schau dir mal /dev/random bei Linux an:
    http://en.wikipedia.org/wiki//dev/random

    Wenn man alle Variablen kennt wodurch das rauschen erzeugt wird kann man die Zufallszahlen nachrechnen. Somit eine zwar sehr gute Zufallszahl aber keine echte weil berechenbar.

    Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

    Dravere schrieb:

    Wieso Google?

    Das ist einfach.

    2^128 = 340282366920938463463374607431768211456
    340282366920938463463374607431768211456 * 128 = 43556142965880123323311949751266331066368 Bit
    
    43556142965880123323311949751266331066368 / 8 = 5444517870735015415413993718908291383296 Byte
    
    5444517870735015415413993718908291383296 / 1024 = 5316911983139663491615228241121378304 kB
    
    5316911983139663491615228241121378304 / 1024 = 5192296858534827628530496329220096 MB
    
    5192296858534827628530496329220096 / 1024 = 5070602400912917605986812821504 GB
    
    5070602400912917605986812821504 / 1024 = 4951760157141521099596496896 TB
    ...
    

    Darum Google 😉
    Und ja meine Aussage bezüglich Standard war nicht ernst gemeint (ich find nur die Ironie tags nicht ^^)

    MfG Spawn84



  • Spawn84 schrieb:

    Dravere schrieb:

    Nein, man kann dazu das Rauschen vom PC nehmen. Schau dir mal /dev/random bei Linux an:
    http://en.wikipedia.org/wiki//dev/random

    Wenn man alle Variablen kennt wodurch das rauschen erzeugt wird kann man die Zufallszahlen nachrechnen. Somit eine zwar sehr gute Zufallszahl aber keine echte weil berechenbar.

    Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

    Unfug.



  • Tachyon schrieb:

    hustbaer schrieb:

    Mit Boost.Random müsste sich was zusammenbasteln lassen.

    Ja, UIDs lassen sich damit mehr oder weniger gut zusammenbasteln. Das Problem für mich ist eher das G im GUID.
    (...)

    ???
    Seede dir einen boost::mt19937 Generator über boost::random_device, dann kannst du dir GUIDs generieren soviel du willst.



  • hustbaer schrieb:

    Unfug.

    Begründung?

    Ach ja und sorry wegen dem off topic gelabere hier ^^



  • Das einzige was mir jetzt einfällt und wo man nur annimmt das es zufällig ist, währe der zerfall von radioaktiven Materialien (eventuell fehlt aber derzeit auch nur das Wissen dafür).

    In der c't gabs mal 'nen netten Artikel, wie das thermische Rauschen von Webcams genutzt wird, um Zufallszahlen zu generieren. Diese Einfluesse kannst weder messen noch nachbilden.



  • knivil schrieb:

    In der c't gabs mal 'nen netten Artikel, wie das thermische Rauschen von Webcams genutzt wird, um Zufallszahlen zu generieren. Diese Einfluesse kannst weder messen noch nachbilden.

    Kann ich mir ehrlich gesagt nicht vorstellen. Ich würde eher sagen es sind zu viele Einflussfaktoren als das man sie messen könnte (oder es fehlen derzeit noch die Mittel hierfür). Oder wurde auf eine besondere Komponente eingegangen die den absoluten Zufall erzeugt?
    Ich bin mir fast sicher wenn man alle Umgebungsvariablen kennt (was in der Praxis derzeit nicht möglich ist) kann man auch das nachrechnen/simulieren.

    Es geht hier um eine reine Theoriefrage die mit der Praxis fast nichts bis gar nix zu tun hat. Wenn wer nen Artikel oder sonst was hat wo dazu etwas steht (eventuell bewiesen ist das es sich hierbei um absolute Zufall handelt) nur her damit. Würde mich sehr interessieren 🙂



  • Ich bin mir fast sicher wenn man alle Umgebungsvariablen kennt (was in der Praxis derzeit nicht möglich ist) kann man auch das nachrechnen/simulieren.

    Das ist das alte Problem der Chaos Theorie...


  • Administrator

    @Keros,
    Nun fragt man sich aber mehr und mehr, was dein erster Beitrag eigentlich sollte. Der grösste Teil war ja gar nicht ernst gemeint und der mittlere Teil nicht umsetzbar. Sehr sinnvoller Beitrag...

    Falls du etwas über Zufall lesen willst:
    http://de.wikipedia.org/wiki/Zufall

    Richtiger Zufall wird von der Newtonischen Mechanik (Physik) ausgeschlossen. Die Tendenz ist dort stark deterministisch:
    http://de.wikipedia.org/wiki/Determinismus

    In der Quantenphysik gibt es Theorien, dass es den Zufall tatsächlich gibt. Als Beispiel zu nennen, ist hier wohl die Kopenhagener Deutung:
    http://de.wikipedia.org/wiki/Kopenhagener_Deutung

    Damit solltest du bereits genügend Stoff haben, um Google oder eine andere Suchmaschine zu benutzen. Es gibt sicher genügend Artikel im Internet. Zudem findest du damit sicher auch Bücher.

    Grüssli



  • Naja die Chaostheorie ist für mich haltbar da ich glaube das es den Zufall gibt (so viel Philosophie und das bei nem technischen Thema 😃 ).

    Ich habe für mich eine Definition warum es den absoluten Zufall geben muss die mir reicht. Aber wie gesagt ist es im Computerbereich meiner Meinung nach sehr schwer bis gar nicht möglich echte Zufallszahlen zu erzeugen. Wobei das nicht nötig ist da Pseudozufallszahlen vollkommen ausreichen.



  • Ich leg mir jetzt nen Acc zu damit ich editieren kann ^^

    Mein erster post:
    1 -> War meine Meinung dazu (darf ich doch in nem Forum vertreten?)

    2 -> MAC Adresse + Timestamp ist nicht umsetzbar?

    3 -> Nen Spaß darf man sich doch mal erlauben 😉 (vor allem mit allwissenden google)

    Die restlichen Beiträgen waren dann was sich aus der Diskussion ergeben hat -> Forum ist glaub ich auch so gedacht?


  • Administrator

    Keros schrieb:

    1 -> War meine Meinung dazu (darf ich doch in nem Forum vertreten?)

    Doch, nur hat sie nichts mit dem Thema zu tun. Ich sagte damals, dass Pseudo Zufallszahlen verwendet werden, weil es in der Informatik eben auch andere Zufallszahlen gibt. Egal wie deine Meinung über Zufallszahlen aussieht:
    - True Random Numbers
    - Pseudo Random Numbers

    http://en.wikipedia.org/wiki/Random_number_generation#.22True.22_random_numbers_vs._pseudorandom_numbers

    Keros schrieb:

    2 -> MAC Adresse + Timestamp ist nicht umsetzbar?

    Habe ich dir schon zu deinem Ironie Standard gesagt. Eine GUID muss auch erstellt werden können, wenn keine Netzwerkkarte vorhanden ist. Wie du ohne Netzwerkkarte eine MAC Adresse holen willst, dass musst du mir mal zeigen...

    Keros schrieb:

    3 -> Nen Spaß darf man sich doch mal erlauben 😉 (vor allem mit allwissenden google)

    Darf man, aber dann sollte es immerhin klar ersichtlich sein. Zum Beispiel hiermit: 🤡
    Oder nimm [ironie] Tags.
    Zudem sollte zumindest im restlichen Beitrag was sinnvolles stehen.

    Keros schrieb:

    Die restlichen Beiträgen waren dann was sich aus der Diskussion ergeben hat -> Forum ist glaub ich auch so gedacht?

    Nur ist es Off-Topic.

    (und ich bin aktuell schlecht gelaunt, weil ich das Problem hier nicht geregelt bekomme. Aber es ist nicht nett dem Tachyon gegenüber, dass wir seinen Thread so ins Off-Topic führen ;))

    Grüssli



  • hustbaer schrieb:

    [...]Seede dir einen boost::mt19937 Generator über boost::random_device, dann kannst du dir GUIDs generieren soviel du willst.

    So, erstmal Danke für die ganzen Antworten.

    Also das mit dem random_device werde ich mal testen. Das klingt erstmal recht vielversprechend.

    Wegen vorangegangen Vorschlägen:
    Einfach nur Pseudorandomnummern zu erzeugen, reicht leider nicht. Irgendwoher muss ein Seed kommen, und dafür benutzt man üblicherweise die Systemzeit. Auf dem System, auf dem die Anwendungen laufen soll, wird die Zeit auf allen Plattformen synchronisiert, wodurch eine recht hohe Wahrscheinlichkeit besteht, dass man gleiche Zufallssequenzen auf verschiedenen Clustern produziert. Das darf aber nicht passieren.

    An die MAC-Addresse komme ich nicht plattformunabhängig ran (obwohl es überall eine gäbe, aber das System ist ziemlich heterogen und ich will möglichst wenig plattformspezifische Anteile in der Software haben).

    Das Boost auch einen nicht-deterministischen Generator liefert, ist mir entgangen. Das könnte aber die Lösung sein.

    Ansonsten werde ich wohl in den sauren Apfel beissen müssen, und die betriebssystemeigenen GUID-Funktionen wrappen. Das ist auf jeden Fall weniger aufwändig, als erst die MAC-Adresse oder ähnliches zu ermitteln, und dann daraus eine GUID zu erzeugen.

    EDIT: Nein, boost::random_device unterstützt Windows leider nicht. Das Ding kompiliert nur unter BSD oder Linux, wegen

    #if defined(__linux__) || defined (__FreeBSD__)
    

    in random_device.cpp . Eine Windows-Variante gibts nicht.



  • Hat mit dem Thema schon was zu tun. Wenn das erzeugen von echten Zufallszahlen trivial währe (was ich behaupte das es nicht ist) hätte Tachyon das Problem nicht 😉

    Das eine GUID auch ohne Netzwerkkarte erzeugt werden muss ist klar aber das eine Vorhanden ist entnahm ich schon der Aussage das es mit den Timestamps ein Problem gibt -> läßt auf Synchonisierung schließen -> Netzwerkkarte sehr wahrscheinlich
    Das die MAC auzulesen leider nicht Systemunabhängig ist hab ich mir fast gedacht, aber ne idee wars wert.

    Das mit dem Clown werd ich mir merken für mich hatte xD bis jetzt ca die selbe Bedetung

    Wenn mir wer "Unfug" vor den Kopf wirft ohne begründung muss ich nachfragen. Vielleicht weiß da wer was, dass ich noch nicht kenne.



  • Tachyon schrieb:

    EDIT: Nein, boost::random_device unterstützt Windows leider nicht. Das Ding kompiliert nur unter BSD oder Linux, wegen

    #if defined(__linux__) || defined (__FreeBSD__)
    

    in random_device.cpp . Eine Windows-Variante gibts nicht.

    Shit.
    Obwohl es recht einfach zu implementieren wäre.
    CryptGenRandom() is ja nu wirklich keine Hexerei.
    Vielleicht sollte ich nen Patch einschicken...



  • Tachyon schrieb:

    Wegen vorangegangen Vorschlägen:
    Einfach nur Pseudorandomnummern zu erzeugen, reicht leider nicht. Irgendwoher muss ein Seed kommen, und dafür benutzt man üblicherweise die Systemzeit. Auf dem System, auf dem die Anwendungen laufen soll, wird die Zeit auf allen Plattformen synchronisiert, wodurch eine recht hohe Wahrscheinlichkeit besteht, dass man gleiche Zufallssequenzen auf verschiedenen Clustern produziert. Das darf aber nicht passieren.

    Eine synchronisierte Systemzeit macht nur dann Probleme, wenn die Seeds alle zur gleichen Zeit genommen werden. Falls dem so ist hast du immernoch auf jedem Cluster irgendwo eine Kommunikationsschicht, die das Quatschen mit den anderen Rechnern übernimmt. Die Schicht ist eh schon Plattformabhängig, daher kannst du von ihr aus der Mac-Adresse oder IP-Adresse oder was auch immer eine plattformunabhängige Zahl generieren lassen, die von Cluster zu Cluster verschieden ist. Modifiziere die genommene Systemzeit in geeigneter Weise damit und du hast unterschiedliche Seeds, oder seh ich das falsch?



  • pumuckl schrieb:

    ...seh ich das falsch?

    Ja, aus meiner Sicht ist das Netzwerk plattformunabhängig, weil ich boost.asio benutze. Darüber gibt es aber keine Möglichkeit, an die MAC-Adresse heranzukommen. An IPs schon eher, aber die sind im System nicht eindeutig.


Anmelden zum Antworten