nicht angemeldet
Zentrale Vergabe von Id's
0 0 0
Zentrale Vergabe von Id's
Hallo!
ich habe eine grundsätzliche Frage zu einem Datenbank-Konzept. Bei Facebook hat jedes Objekt (User, Page, Event usw.) eine eindeutige Id.
In irgendeiner Form muss diese ja zentral vergeben werden. Für ein Projekt würde ich auch eine zentralisierte Id benötigen (es ist auch eine Art social Network, bei dem Daten zu einem Objekt über eine Api abgefragt werden).
Wie bekomme ich eine performante und sinnvolle Vergabe der Id hin? Auf ein DBMS habe ich mich noch nicht festgelegt. Eine zenrale MySQL Tabelle wird wohl sehr schnell an den entstehenden Deadlocks scheitern. Welche Alternativen gibt es?
Gruss
Claudia
-
Moin!
Wie bekomme ich eine performante und sinnvolle Vergabe der Id hin? Auf ein DBMS habe ich mich noch nicht festgelegt. Eine zenrale MySQL Tabelle wird wohl sehr schnell an den entstehenden Deadlocks scheitern. Welche Alternativen gibt es?
Welche Deadlocks? Programmier dir halt keine. :-P
Ansonsten gibt es viele Konzepte eindeutiger ID-Generierung. UUID würde mir als allererstes einfallen.
- Sven Rautenberg
-
Hi!
Ansonsten gibt es viele Konzepte eindeutiger ID-Generierung. UUID würde mir als allererstes einfallen.
Und das Tolle daran ist, dass man sie auch dezentral generieren kann. Denn gemäß ihrem Wesen sind sie ja weltweit eindeutig. Man kann sie also gleich bei der Objektgenerierung mit erstellen und muss nicht erst warten, bis man das Objekt als Datensatz in ein DBMS schreibt, um beispielsweise eine dort vergebene auto_increment-ID zu bekommen.
Lo!
-
Hello,
Ansonsten gibt es viele Konzepte eindeutiger ID-Generierung. UUID würde mir als allererstes einfallen.
Und das Tolle daran ist, dass man sie auch dezentral generieren kann. Denn gemäß ihrem Wesen sind sie ja weltweit eindeutig.
...und das war sogar schon zu Kaisers Zeiten so, als noch Hollerith noch ein Novum war :-P
Damals nannte man das nur "abgeschlossener Nummernkreis".
Liebe Grüße aus dem schönen Oberharz
Tom vom Berg
-
Hi!
Ansonsten gibt es viele Konzepte eindeutiger ID-Generierung. UUID würde mir als allererstes einfallen.
Und das Tolle daran ist, dass man sie auch dezentral generieren kann. Denn gemäß ihrem Wesen sind sie ja weltweit eindeutig.
...und das war sogar schon zu Kaisers Zeiten so, als noch Hollerith noch ein Novum war :-PUUID ist eine spezifisches Format, das unter anderem MAC-Adressen einbezieht. Die kann es auch zu Hollerith Zeiten noch nicht gegeben haben.
Damals nannte man das nur "abgeschlossener Nummernkreis".
Und dass ich diesen Begriff nicht mit Google finde, liegt wohl daran, dass es zu Kaisers Zeiten noch kein Google gab. Schade, denn ich hätte gern gewusst, wie die damals eine weltweite Eindeutigkeit ohne ein zentrales koordinierendes Element hinbekommen haben.
(OK, UUID hat, wenn es die MAC-Adresse einbezieht, implizit ein zentral koordiniertes Element.)
Lo!
-
Hello,
Ansonsten gibt es viele Konzepte eindeutiger ID-Generierung. UUID würde mir als allererstes einfallen.
Und das Tolle daran ist, dass man sie auch dezentral generieren kann. Denn gemäß ihrem Wesen sind sie ja weltweit eindeutig.
...und das war sogar schon zu Kaisers Zeiten so, als noch Hollerith noch ein Novum war :-PUUID ist eine spezifisches Format, das unter anderem MAC-Adressen einbezieht. Die kann es auch zu Hollerith Zeiten noch nicht gegeben haben.
Ja nee is schon kalr, Murath :-P
Damals nannte man das nur "abgeschlossener Nummernkreis".
Und dass ich diesen Begriff nicht mit Google finde, liegt wohl daran, dass es zu Kaisers Zeiten noch kein Google gab.
Mein Gott, er hat es!
Schade, denn ich hätte gern gewusst, wie die damals eine weltweite Eindeutigkeit ohne ein zentrales koordinierendes Element hinbekommen haben.
Der Media Access Contol NAME (es IST KEINE Adresse, sondern ein Name) ist hier die "Name Authority". Diese hat dann für Eineindeutigkeit innerhalb ihrer Autorität zu sorgen.
Da aber der MAC-Name technisch betrachtet auch frei gewählt werden kann, hat es sich was mit abgeschlossenem Nummernkreis. Der wäre nur vorhanden, wenn der MAC-Name noch per Order de Mufti von einer zentralen Stelle vergeben werden würde.
Das war auch am Anfang mal so gedacht. Da hatte jeder NIC-Hersteller wiederum einen eigenen Nummernkreis, innerhalb dessen er dann für die von ihm hergestellten NICs für Eineindeutigkeit sorgen musste und dies auch tat, sofern es nicht andere Gründe (Gemeindienste) gab MAC-Namen doppelt zu vergeben.
UUID ist also nur der WUNSCH nach Eineindeutigkeit, aber keine Garantie dafür.
Liebe Grüße aus dem schönen Oberharz
Tom vom Berg
-
UUID kannte ich nicht ... aber genau das löst mein Problem.
Herzlichen Dank!
-
Hello,
UUID kannte ich nicht ... aber genau das löst mein Problem.
bis die Chinesen oder die Mönche aus Tibet oder die Inder oder sonst irgendwer ein anderes "weltumspannedes" Identifikationssystem einführen.
Die Arroganz unserer (westlichen) Technikinhaber bezüglich Weltgültigkeit ist kaum zu übertreffen.
Liebe Grüße aus dem schönen Oberharz
Tom vom Berg
-
Hallo,
zur Benutzung von UUIDs oder GUIDs möchte ich nur nebenbei bemerken, dass die Vergabe quasi pseudozufällig erfolgt. Es gibt keine Garantie, dass nach Vergabe eine UUID #1 die darauf vergebenen UUIDs (immer) grösser oder kleiner sind. Das hat Nachteile bei der Verwendung solcher Konstrukte in einem Index, genannt Fragmentierung. Weniger beim Lesen als beim Schreiben. Darüber hinaus sind UUIDs ein recht grosser Datentyp. Wenn man also nur 2 Milliarden Ids braucht (und 2 Mia Datensätze in einer Tabelle ist schon nicht übel), dann spart man mit Integer (4 Byte) gegenüber UUIDs (16 Byte) also 12 Byte. Das macht etwa 24 000 000 000 Byte ... wiederum etwa 20GB, die weniger gespeichert und gesichert werden müssen und auch 20 GB, die weniger in den Ram gelesen werden müssen.
Falls das DBMS kein Feature für Sequenzen hat, kann man sich mithilfe von einer einzigen Tabelle (die unter anderem niemals auch nur einen Datensatz haben wird) mit einer Auto-Increment Spalte und Transaktionen selbst eine basteln. Der Overhead für den Rollback des Inserts ist minimal.
Cheers, Frank
-
Moin Moin!
UUID kannte ich nicht ... aber genau das löst mein Problem.
Vorsicht: Es gibt aktuell fünf verschiedene UUID-Typen, die sehr unterschiedliche Eigenschaften haben.
Version 1 bastelt aus MAC-Adresse und einer möglichst hoch auflösenden Uhr IDs. Hat die Uhr Probleme (Vorgehen / Nachgehen + Nachstellen, fehlende Uhr-Hardware), sind die IDs nicht mehr garantiert eindeutig. Außerdem läßt sich aus diesem UUID-Typ die Erstellungszeit und der Rechner bestimmen, was typischerweise nicht gewollt ist.
Version 2 ersetzt ein paar Bytes in der Zeitangabe der Version 1 durch mehr oder weniger konstante Werte (User-ID, Group-ID). Damit lecken diese Informationen auch noch heraus, außerdem läuft der Timer früher über als in Version 1.
Version 3 nutzt MD5-Summen von irgendwelchen Identifiern, ist also alles andere als zufällig. MD5 hat, wie jede andere Hash-Funktion auch, Kollisionen, d.h. es ist nicht ausgeschlossen, dass zwei Identifier die selbe UUID haben.
Version 4 nutzt einen Zufallsgenerator. Ob so generierte UUIDs eindeutig sind, hängt damit ausschließlich von der Qualität des Zufallsgenerators ab. Pseudo Random Number Generators, also das Erzeugen von pseudo-zufälligen Zahlen rein in Software, kann problematisch werden. Der PRNG in Turbo Pascal hatte deutlich unter 100.000 mögliche Werte (15 Bit oder 16 Bit). Modernere PRNGs liefern mehr Bits, aber 120 Bit sind eher selten und vor allem selten einzigartig. Auch Hardware-RNGs liefern keine EINZIGARTIGEN Werte, sondern ZUFÄLLIGE Werte. Ein RNG, egal ob Hardware oder Software, darf jeden Wert beliebig oft, auch mehrfach direkt nacheinander liefern. Damit könnte der RNG letztlich mehrfach die selbe UUID liefern.
Version 5 ist identisch mit Version 3, außer das statt MD5 SHA-1 benutzt wird.
Das UUIDs überhaupt funktionieren, liegt daran, dass der Wertebereich so astronomisch groß (2^128 ist etwa 3*10^38) ist, dass Kollisionen meistens unwahrscheinlich sind. Aber sie sind eben nicht AUSGESCHLOSSEN.
Sequenzen in gängigen RDBMS (wie z.B. PostgreSQL und Oracle) dagegen sind GARANTIERT eindeutig, so lange niemand an den Sequenz-Parametern herumadministriert. Oracle liefert pro Sequenz bis zu 10^28 Werte, PostgreSQL bis zu 2^64 (ca. 1,8*10^19) Werte. Das ist zwar deutlich weniger als der UUID-Wertebereich, aber immer noch deutlich mehr, als die meisten Anwendungen je benötigen werden.
Alexander
--
Today I will gladly share my knowledge and experience, for there are no sweeter words than "I told you so".
-
-
-
-
-
-
-
Bei Facebook hat jedes Objekt (User, Page, Event usw.) eine eindeutige Id.
Du redest hier von Typ-übergreifenden IDs? Weiß nicht ob das wirklich so ist, was könnte das bringen?
Eine zenrale MySQL Tabelle wird wohl sehr schnell an den entstehenden Deadlocks scheitern.
Da muss aber schon seeeeeehr viel auf der DB abgehen dass es hier Engpässe gibt. Aber Deadlocks ja eigentlich nicht?
Irgendwo brauchst du ja eine Tabelle die dir erst mal sagt was für ein Objekttyp sich hinter einer ID verbirgt.-
Irgendwo brauchst du ja eine Tabelle die dir erst mal sagt was für ein Objekttyp sich hinter einer ID verbirgt.
Wieso?
-
Irgendwo brauchst du ja eine Tabelle die dir erst mal sagt was für ein Objekttyp sich hinter einer ID verbirgt.
Wieso?
Die Frage mit der zentralen Tabelle usw. klingt als wär für alle Objekttypen global eine eindeutige ID gewollt. Wenn man dann eine Zahl kriegt, muss man ja erst mal auflösen um was es überhaupt geht.
-
Hi,
die Tabelle hat dann wahrscheinlich eine weitere Spalte namens EntityType oder ObjectType mit einem diskreten Wert. Die Abfrage beinhaltet dann sowohl ID als auch den Typ (WHERE ID = param1 AND ObjectType = param2).Da nicht alle Objekttypen gleich sein können, wird vielleicht auch vertikal partitioniert.
Es gibt durchaus einige Anwendungsszenarien für solche Konstrukte.
Grüsse aus Vegas,
Frank-
die Tabelle hat dann wahrscheinlich eine weitere Spalte namens EntityType oder ObjectType mit einem diskreten Wert. Die Abfrage beinhaltet dann sowohl ID als auch den Typ (WHERE ID = param1 AND ObjectType = param2).
Wenns dann wirklich eine einzige Tabelle ist ok, aber dann würde das auch mit IDENTITY gehen.
Ich hab das mit dem Deadlock usw. alles so verstanden als wären es separate Tabellen, eine pro Typ. Weiß aber nicht genau warum ich da drauf komme, das mit dem Deadlock klang so, als würds dann eine extra Tabelle geben die nur Identities hochzählt.-
Hi
wenn du ne grosse Tabelle hast mit vielen Spalten und Datensaetzen, dann kann das Hinzufuegen schon zu Locks fuehren (Sperrung der Tabelle), Betonung auf KANN.
Natuerlich brauechte man keine eigene Tabelle, IDENTITY in der Tabelle wuerde theor. ausreichen. Haengt stark vom Bedarf ab, was besser oder optimalerererer ist. :-)
Cheers, Frank
-
-
-
-
-
-
hi,
Wie bekomme ich eine performante und sinnvolle Vergabe der Id hin? Auf ein DBMS habe ich mich noch nicht festgelegt. Eine zenrale MySQL Tabelle wird wohl sehr schnell an den entstehenden Deadlocks scheitern. Welche Alternativen gibt es?
Wenn Dir 4 Milliarden IDs reichen: das könnte über eine Datei, Größe 4 Byte, gemacht werden, die fürs Lesen+Schreiben exclusive gelockt wird, die IDs sind numerisch und forlaufend.
Hotti
-
Hello Hotti,
Wie bekomme ich eine performante und sinnvolle Vergabe der Id hin? Auf ein DBMS habe ich mich noch nicht festgelegt. Eine zenrale MySQL Tabelle wird wohl sehr schnell an den entstehenden Deadlocks scheitern. Welche Alternativen gibt es?
Wenn Dir 4 Milliarden IDs reichen: das könnte über eine Datei, Größe 4 Byte, gemacht werden, die fürs Lesen+Schreiben exclusive gelockt wird, die IDs sind numerisch und forlaufend.
Darf ich dich für einen der vielen Nobelpreise vorschlagen?
Erklär mir doch bitte mal, wie Du 4 Milliarden IDs in einer Datei der Größe 4 Byte unterbringen willst.
Liebe Grüße aus dem schönen Oberharz
Tom vom Berg
-
Hi, ganz einfach, nur eine Zahl speichern, binär von -2 Mia bis plus 2 Mia. Datei sperren, öffnen, wert inkrementieren, wert in variable, Datei wieder zu und fertsch. Braucht 4 Byte für den Integerwert.
Ciao, Frank-
Hello,
Hi, ganz einfach, nur eine Zahl speichern, binär von -2 Mia bis plus 2 Mia. Datei sperren, öffnen, wert inkrementieren, wert in variable, Datei wieder zu und fertsch. Braucht 4 Byte für den Integerwert.
Und das gibt dann vier Milliarden IDs?
Oder gibt das eine von vier Milliarden?Liebe Grüße aus dem schönen Oberharz
Tom vom Berg
-
Hi Tom,
von -2 bis +2 Mia ergibt (meiner Rechnung nach) etwa 4 Mia moegliche Werte. Es geht ja auch nicht darum, alle 4 Mia IDs in der Datei gleichzeitig drin zu haben (sondern nur den letzten Wert), sondern es interessiert die atomare/zentrale Vergabe. :-)
Oder hab ich da Ironie in deinem Beitrag uebersehen ... mir flunkern eh immer noch die Augen vor lauter Einarmigen Banditen aus den letzen Tagen.
Cheers, Frank
-
Hello Tom,
Hi, ganz einfach, nur eine Zahl speichern, binär von -2 Mia bis plus 2 Mia. Datei sperren, öffnen, wert inkrementieren, wert in variable, Datei wieder zu und fertsch. Braucht 4 Byte für den Integerwert.
Und das gibt dann vier Milliarden IDs?
Oder gibt das eine von vier Milliarden?Das ist wie bei (D)einem Kontoauszug: Wenn da als Saldo haben 4 Milliarden draufsteht, heißt das noch lange nicht, dass Du vier Milliarden da abheben kannst ;)
O'Hotti
--
Wer Äpfel mit Birnen vergleicht, neigt dazu, Kopf und Arsch zu verwechseln.
-
-
-
Guten Morgen Tom,
Erklär mir doch bitte mal, wie Du 4 Milliarden IDs in einer Datei der Größe 4 Byte unterbringen willst.
Nacheinander.
Schöne Grüße,
Hotti ;)PS: Pferd in Kühlschrank tun? Kein Problem, Kühlschranktür auf, Pferd rein, Tür zu. Kuh in Kühlschrank tun? Das ist fies! Trick: Erst das Pferd raus...
-
Hi,
[Titel] Nobelpreis für Mathematik
Darf ich dich für einen der vielen Nobelpreise vorschlagen?den gibts gar nicht.
Bis die Tage,
Matti
-
-