Laden...

Riesiger Key-Value-Store für 1 Mrd Datensätze benötigt - Welche DB nehmen?

Erstellt von Christoph K. vor 6 Jahren Letzter Beitrag vor 6 Jahren 8.117 Views
Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren
Riesiger Key-Value-Store für 1 Mrd Datensätze benötigt - Welche DB nehmen?

Hallo zusammen,

ich benötige einen riesigen Key-Value Store, der im Endeffekt nur folgende Aufgaben hat.
Er soll eine Vielzahl von URLs entweder in IDs auflösen, oder IDs wieder zurück in die entsprechenden URLs auflösen.

Die Daten die Anfallen werden sind ca. 10 Milliarden URLS, was eine Datenmenge von ca. 1 Terrabyte bedeutet.

Der Zugriff auf die Daten ist eigentlich immer der gleiche.

  1. Es wird geschaut, ob URLs bereits in der Datenbank liegen, wenn diese dort bereits vorhanden sind, werden die IDs zurückgegeben. Sind die Daten noch nicht vorhanden, werden diese eingetragen und im Anschluss werden die neuen IDs zurückgegeben.

  2. IDs werden im Bedarfsfall wieder gegen die entsprechenden URLs aufgelöst.

Der Zugriff auf die Daten soll zusätzlich extrem performant sein. Aufgrund der hohen Datenmenge ist es jedoch nicht möglich, alle Werte im Arbeitsspeichert zu halten. Selbst der Index auf die URL kann nicht im Arbeitsspeicher gehalten werden, da er ja fast so groß ist, wie die gesamte Datenmenge.

Ich habe bereits MongoDB sowie MySql als Datenbank getestet, beide haben bei wachsender Datenmenge, jedoch zu hohe Latenzzeiten (mehrere Sekunden) wenn ich z.B. zu 50 zufälligen IDs die URLs abfragen möchte.

Hat jemand eine Idee?

6.911 Beiträge seit 2009
vor 6 Jahren

Hallo Christoph K.,

erzähl uns noch ein wenig über die Infrastruktur-Bedingungen, dann lässt sich eine bessere Empfehlung abgeben.

On Premise od. Cloud?

Bei On Premise wie viele Server können verwendet werden (wegen Sharding, etc.)?

MySQL sowie die anderen "klassischen" SQL-DBMS würde ich für solche Aufgabe sowieso ausschließen und einen passenden Vertreter der NoSQL-Welt nehmen. Die sind aber sehr oft auf die Infrastruktur angepasst, daher ist dieses Detail wichtig zu wissen.

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Als Server steht erstmal ein Rechner bereit (xeon 6x3,5Ghz, 128MB DDR4, 1TB SSD). Dieser kann jedoch beliebig erweitert werden. Plattform ist Windows.

16.806 Beiträge seit 2008
vor 6 Jahren

Die einfache Anforderung von 1 Mrd Datensätzen und 1 TB Daten erfüllt jede übliche Datenbank wie SqlServer, MySql..... das alleine ist absolut kein Ausschlußkriterium.
"Extrem performant" ist auch ein sehr relativer Begriff. Was der eine extrem Performant nennt, nennt der andere Durchschnitt.

Wenn MySql und NoSQL hier mehrere Sekunden für so eine Abfrage benötigen, dann ist entweder die Maschine darunter völlig ungeeignet für einen Datenbankserver oder Du hast evtl. einfach die Indexe vergessen.

Die Rechnung 1 Mrd Datensätze = 1 TB Daten kann man hier aber nicht nachvollziehen.

PS: Wenn der Rechner eine 1 TB SSD hat, dann können darauf keine 1 TB Daten liegen.
Ein Rechner alleine könnte auch mit der Power evtl. nicht ausreichen, wenn es zu viele parallele Requests kommen.
Features wie (Auto)-Sharding funktioniert erst über mehrere Nodes.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Die Indexe sind richtig gesetzt.

Die SSD des Rechners zu erweitern ist kein Problem.

Ich denke, dass die Performance deshalb nicht so gut ist, weil der Index nicht komplett in den RAM rein passt. Der Index ist im Moment so groß wie die Daten selber, da ich direkt den Index auf die URL gesetzt habe. Vielleicht könnte ich hier noch optimieren, indem ich einen Hash der URL als Index verwenden würde!?!?

Mir ist jedoch auch dran gelegen, dass die Datenbestände noch weiter wachsen können. Irgendwann passt der Index dann nicht mehr in den RAM.

16.806 Beiträge seit 2008
vor 6 Jahren

Ich nehme es daher an, da ich selbst eine Produktdatenbank mit 600 Millionen Produktseriennummer (Varchar, 22 Zeichen) umgesetzt habe: mit dem SQL Server.
Es gab keinerlei Query Speed Probleme mit korrektem Index.

Hashs sind immer langsam, daher sind Hashs niemals eine Lösung für Performance-hungrige Anwendungen.
Nie.

Hast Du den Speed mit ADO.NET getestet oder wirklich einen optimierten Query direkt auf der Datenbank überprüft?
Oder woher Deine Annahmen? Hier nicht ersichtlich. Hast Du mal in den Ausführungsplan geschaut, ob Dein Query ein Full Table Scan auslöst? Dann ist Dein Index nämlich nutzlos.
Aktuell arbeitest Du irgendwie eher mit Hypothesen statt mit Fakten wie mir scheint 😉

6.911 Beiträge seit 2009
vor 6 Jahren

Hallo Christoph K.,

es spielen ja noch mehr Fragen mit:* von welcher Art sind die IDs? int, Guid, etc.

  • soll diese Datenbank nur für diese Daten verwendet werden od. auch andere Daten liefern?
  • du schreibst von einem Server, der erweitert werden kann. Können es auch mehr Server sein?
  • geht es (auch in Zukunft) rein nur ums Lesen/Schreiben der Key/Values?

Einen Url-Hash würde ich auch nicht verwenden. Du spart ev. etwas vom Speicherplatz, dafür brauchst du mehr CPU fürs Hashen.

Wenn die Datenbank nur für diesen Zweck ist, so halte ich es "übertrieben" eine allgemeine SQL Datenbank für Key-Value zu verwenden. Da gibt es spezialisiertere Varianten, die für diese Aufgaben passender sind. Redis wäre so ein klassischer Vertreter, allerdings wurde afaik das "virtual memory"-Projekt davon eingestellt. Aber es gibt dafür ja sonst genug Alternativen.

Sollten mehrere Server im Einsatz sein können, so kannst du v.a. die Disk-Operationen aufteilen und so (oft) viel an Performanz gewinnen (vorausgesetzt natürlich dass die Daten korrekt auf die Server verteilt wurden ~ Sharding).

128MB DDR4

Kein Wunder dass der Index nicht im RAM Platz hat 😉

mfG Gü

Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"

D
985 Beiträge seit 2014
vor 6 Jahren

Wie lautet denn das Create-Statement für die Tabelle?

Dann kann man sich mal einen Überblick verschaffen, was denn wie und in welcher Länge gespeichert werden soll.

Aus dem Bauch heraus würde ich allerdings sagen, dass hier die Uhren anders ticken als bei einem VARCHAR(22), denn ich vermute mal eher wir sprechen von einem VARCHAR(2000) für die Url.

PS Wie schätzt du das Verhältnis zwischen Insert und Query ein? Also erfolgen mehr Abfragen als Eintragungen?

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Hier ist das create statement für die MySQL -Tabelle

CREATE TABLE `universalkeywordrankingurls` (
  `Id` int(11) NOT NULL AUTO_INCREMENT,
  `Url` varchar(1000) COLLATE utf8_bin DEFAULT NULL,
  KEY `Url` (`Url`),
  KEY `Id_UNIQUE` (`Id`)
) ENGINE=InnoDB AUTO_INCREMENT=1DEFAULT CHARSET=utf8 COLLATE=utf8_bin

Du hast fast richtig getippt, es handelt sich um einen varchar(1000).

  • die IDs sind vom Typ Integer
  • Die Tabelle wird immer nur beschrieben und gelesen (nicht geupdatet oder etwas gelöscht)
  • Die Abfragen sind schätzungsweise 100 mal so viele wie die Inserts
  • Die Tabelle wird jedoch kontinuierlich gefüllt
16.806 Beiträge seit 2008
vor 6 Jahren

MySQL hat keinen Query Plan Cache; muss also jedes Mal durch den (teuren) Optimizer.
Klarer Nachteil bei solch einer Konstellation gegenüber dem Sql Server. Zudem versucht, wenn möglich, der SQL Server Queries zu parallelisieren, was MySql nicht kann.

Die Größe des Index (22 vs. 1000) spielt gar keine sooo große Rolle wie man denkt...
Es geht vor allem darum, einen Full Table Scan zu vermeiden.

Je nach Zweck des ganzen kann es sich lohnen, die Datenbank einfach nur die Datenbank sein zu lassen, und drüber für die Abfragen eine Suchenengine (zB. Azure Search) drauf zu setzen.
Wir konnten damit (zB. Abfragen über Rechnungen) enorm beschleunigen. Die Datenbank wird bei Abfragen gar nicht mehr verwendet; quasi nur noch für das Schreiben.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Habe gerade im Execution-Plan gesehen das MySql einen "Index-Range-Scan" verwendet, sobald ich mir mehr als 3 Einträge (über ID-Selection in der Where-Bedingung) zurückgeben lasse.

Hier wäre doch ein "Key Lookup" deutlich performanter bzw. bei MsSql heist es glaube ich Index-Seek.

Warum macht MySql das ?

16.806 Beiträge seit 2008
vor 6 Jahren

Ohne Kontext kann man darauf nicht antworten.
Poste Dein Execution Plan XML hier www.PasteThePlan.com und verlink ihn dann hier.

Riecht für mich aber weiterhin, dass Deine Indexe nicht gut sind.
Bisher hast Du nicht gezeigt wie oder ob Du überhaupt einen Index angelegt hast.
Du hast nur zwei unabhängige Keys angelegt.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Sind Keys keine Indexe ?

16.806 Beiträge seit 2008
vor 6 Jahren

Ein Key erzeugt im Hintergrund nur einen clustered index über diese eine Spalte.
Aber da Du den Execution Plan nicht zeigst ist alles, was wir hier machen, raten.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Der müsste doch genügen, oder was soll ich am Index Verändern?

Ich muss morgen erstmal schauen, wie ich den execution plan bei mysql exportiere. ich arbeite zur zeit mit MySql Workbench.

H
523 Beiträge seit 2008
vor 6 Jahren

Den Export kannst Du leicht mit HeidiSQL bewerkstelligen. Tolles, kostenloses Tool, wenn man viel mit mySQL arbeitet 😃

T
2.219 Beiträge seit 2008
vor 6 Jahren

Wäre ggf. ein Wechsel auf PostgreSQL möglich?
Gerade MySql ist seit der Übernahme durch Oracle in der Entwicklungs sowohl eingeschlafen als auch sehr intransparent geworden.
Wir setzen gerade unser aktuelle Produkt mit PostgreSQL um.
Die Performance ist dabei sehr schnell und bei guter DB Struktur und Indizies auch extrem performant.

Anbei, was spricht z.B. dagegen deine Daten nicht in der DB sondern als Hierachie im Dateisystem zu speichern.
Als Beispiel eine Textdatei mit id.txt als Name und darin dann die Url.
Dürfte dein Performance Problem ohne DB auch lösen 😃

Nachtrag:
Wenn ich das richtige sehe und deine Antworten auch richtig verstehe, dann hast du aktuell folgende Indizies.

1.PK Index bestehtend aus ID + Url
2.Ein zusätzlicher Index auf URL

Ist dies so korrekt?
Hier hast du schon das Problem, dass deine DB Struktur sich selbst beisst.
Im Endeffekt wird dein Index immer gleich groß bzw. größer sein als deine Daten selbst da du sowohl die ID + Url im PK indizierst und auch zusätzlich die Url.

Hier müsst du auf eine Lösung setzen, die im Bestfall nicht über die Url geht.
Oder brauchst du immer eine ID und/oder Url bei Abfragen?
Alternativ versuch eine Lösung außerhalb der DB.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Hi T-Virus

Anbei, was spricht z.B. dagegen deine Daten nicht in der DB sondern als Hierachie im Dateisystem zu speichern.
Als Beispiel eine Textdatei mit id.txt als Name und darin dann die Url.
Dürfte dein Performance Problem ohne DB auch lösen 😃

hmm, hatte ich auch schonmal drüber nachgedacht. allerdings entsteht da glaube ich ein sehr großer overhead und das dateisystem kann ja im ende auch nicht performanter sein, als eine eigene DB.

Hier müsst du auf eine Lösung setzen, die im Bestfall nicht über die Url geht.
Oder brauchst du immer eine ID und/oder Url bei Abfragen?
Alternativ versuch eine Lösung außerhalb der DB.

Ich brauche beide Abfragen. Hintergrund ist folgender: Die eigentlich Abfrage geht immer dahin, dass ich eine ID gegen eine URL auflösen muss. Jedoch habe ich das Problem, das ich beim eintragen neuer URLs in die Datenbank natürlich prüfen muss, ob die URLs bereits vorhanden sind und entsprechende URLs die ich als Rohdaten bekomme gegen die IDs auflösen muss. Daher brauche ich auch diese Richtung.

Hier habe ich mittlerweile auch sehr starke Performance Probleme, da die Abfrage "Wer von den 500 URLs ist schon in der Datenbank" mittlerweile auch mehrere Sekunden dauert.

Im Moment bin ich ein wenig ratlos.

Der Ausführungsplan für die Abfrage nach ID sieht wie folgt aus:
'1', 'SIMPLE', 'universalkeywordrankingurls', NULL, 'range', 'Id_UNIQUE', 'Id_UNIQUE', '4', NULL, '50', '100.00', 'Using where'
Es erfolgt also ein Index-Range-Scan. Kann mir aber immer noch nicht erklären, warum die Abfragen von Daten für 50 IDs bereits über 2 Sekunden dauert.

J
641 Beiträge seit 2007
vor 6 Jahren

Bringt denn ein Index wirklich was wenn jeder Datensatz unterschiedlich ist? Dachte indizes bringen nur was wenn die Daten in verschiedenen Zeilen die gleichen sind.

cSharp Projekte : https://github.com/jogibear9988

16.806 Beiträge seit 2008
vor 6 Jahren

Ein Index hilft der Datenbank die Daten (die in Blöcken gehalten werden) zu strukturieren.
Das bewirkt, dass bei Queries je nach Abfragen nicht alle Blöcke angefasst werden müssen.

Sind die Queries ungeeignet oder es fehlen entsprechende Indexe, dann erfolgt ein Full Table Scan.
Sprich jeder Datensatz wird angefasst und auf ein potentielles Trefferbild geprüft.
Das ist natürlich viel langsamer, als wenn man über den Index gehen kann.

Und ja, ein Index ist nicht auf die Gleichheit einer Zeile angewiesen.
zB. bei IDs sortiert er diese, sodass er direkt weiß, in welchem Block er eine ID findet und alle potentiellen Treffer auch direkt nebeneinander liegen.

T
2.219 Beiträge seit 2008
vor 6 Jahren

@Christoph K.
Eine Lösung im FS bei bestimmten Situationen um längen schneller sein als in der DB.
Gutes Beispiel ist bei unserer Flottenlösung die Speicherung von GPS Daten.

Dort haben wir bei dem größten Web pro Woche ca. 4 Mio. Datensätze.
Diese werden bei uns über die Imei der GPS Box + Zeitstempel indiziert.
Nun läuft dieses Web nun aber schon seit ca. 6-7 Jahren und hat auch entsprechend viele Daten aufgezeichnet.

Da wir mit den Daten auch Auswertungen für Berichte fahren, hatten wir irgendwann zu viele Daten.
Dabei hat dann auch der Index nicht mehr geholfen.

Entsprechend hatten wir die Daten ausgelagert, was sowohl die DB Größe als auch die Performance hoch hält.
Die Altdaten werden dann als Hierachie im FS geschrieben.
Dies lässt sich durch entsprechende Pfade im FS schneller verarbeiten als über die DB.
Gerade relationale Datenbanken haben ab einer bestimmten Größe eben ein Problem noch mit zu halten.
Umso größer dann auch die Bereiche werden, die verarbeiten werden müssen, umso weniger bringt ein Index.

Hier würde ich auch fast nachdenken, einen Ansatz ohne DB zu wählen, vorausgesetzt dein Index sowie deine Abfragen sind sauber.

Hier wäre eben noch die Index Definition hilfreich.
Auch MySql Workbench müsste den Create Index Befehl generieren können oder?
Kannst du mal die Befehle sowohl für den PK als auch deinen Url Index zeigen?

Eigentliche müsste dein PK die Spalte ID und dann Url haben.
Dein zweiter Index müsste dann nur auf die Url zeigen.

Hier wäre auch noch hilfreich zu wissen, welche Urls im groben dort gespeichert und wie diese abgefragt werden.
Wenn du z.B. ähnlich einer Suchmaschine wirklich alle Dateien/Urls einer Domain dort als eigene Einträge speicherst, könnte es für den Index schon wieder zu viel werden.
Hier könntest du prüfen ob es helfen würde deine Url in die Haupt Domain samt unter Ordner/Dateien zu zerlegen und diese seperat zu speichern.
So kannst du dann eine Tabelle mit den Domains haben(ID, Domain).
Dann kannst du zu dieser Domain dann die restlichen Teile der Url als Relativen Pfad speichern.
Z.B. ID, Path
Dazu brauchst du dann noch eine Relationstabelle zu (DomainID, PathId) um die Daten zusammen zu setzen.

Noch einen Schritt weiter könnte man gehen, in dem man pro Domain einfach eine Tabelle mit festen Prefix anlegt und dort dann nur die Urls speichert für diese Domain.
Bsp. "urls_mycsharp_de(id, url)"

Falls es diese nicht gibt, muss man diese mit fester Struktur(Id, Url) anlegen.
Dadurch hast du deine Daten dann auch gleich partitioniert, was die Performance der Abfrage wieder hoch ziehen dürfte.
Hier dürfte aber bei einigen Tausend Domains dann die Anzeige in der Workbench Probleme machen 😃
Wäre aber wahrscheinlich der bessere Weg, da du die Daten pro Domain dann in einer eigenen Tabelle hast.
Dann kannst du auch auf den Index für die Url verzichten.
Problem dürftest du dann nur mit der ID haben.
Hier wäre es besser anstelle eines int z.B. eine uuid zu nehmen.
Dann hast du garantierte eindeutige IDs auch bei X Tabellen.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

F
10.010 Beiträge seit 2004
vor 6 Jahren

Man sollte aber bei den ganzen Überlegungen auch daran denken das bei einer einzelnen separaten Abfrage immer auch der Verbindungsaufbau hinzukommt und der kann u.U. schon ziemlich langsam sein.

Das ist dann einer der Gründe mal am Anfang eine "grundlose" abfrage zu machen um den ConnectionPool vorzuinitialisieren.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Also ich hab jetzt mehrere Datenbanken ausprobiert:
MSSQL, MySQL, Cassandra, MongoDB

Alle werden extrem unperformant, sobald man sich einer bestimmten Menge an Daten annähert, die beim Einfügen auf Gleichheit zu den bereits gespeicherten Daten geprüft werden müssen.

Die Abfragen werden auch mit wachsender Datenmenge immer langsamer, bzw. sieht es so aus, als wenn es ab dem Zeitpunkt wäre, wo die entsprechenden Index-Daten nicht mehr in den Ram passen.

Ich folge jetzt T-Virus-Ansatz und programmiere die Datenbank selber. Erste Versuche hierzu zeigen einen enormen Geschwindigkeitszuwachs.

D
985 Beiträge seit 2014
vor 6 Jahren

Also das mit dem Datei-System ist auf jeden Fall sehr schnell.

Für die Bildung des Index würde ich einen Hash nehmen (auch wenn alle sagen, das ist langsam, die dürfen mir dann gerne eine wirklich schnellere Variante zeigen).

Also wir nehmen uns einen 32Bit Hashwert von der URL.
Aus der Hexdarstellung desselbigen bekommen wir den Pfad zu der Datei


05AAF367 => ./05/AA/F3/05AAF367.urls

Dadurch liegen in jedem Verzeichnis maximal 256 Einträge (Ordner bzw. Dateien)-

Datei öffnen und die Url mit den Einträgen in der Datei vergleichen.
Wenn vorhanden, dann den Zeilenindex merken, ansonsten anhängen, speichern und ebenfalls den Zeilenindex merken.

Die Id für die Url setzt sich nun aus dem Hashwert (32Bit) und dem Zeilenindex in der Datei (32Bit) zusammen und ergibt somit einen 64Bit Integer Wert.

Beim Lesen der Url über die Id trennt man diese wieder auf in Hashwert und Index, öffnet die Datei und liefert die Zeile am Index zurück.

Geht höllenschnell (trotz Hash) und ist im Prinzip von der Funktionsweise wie ein HashSet oder Dictionary, wo auch mit Buckets gearbeitet wird.

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Hab es ein wenig anders gelöst:

Ich bilde von allen URLs den MD5 Hash. Das das lange dauert war eine Fehlinformation, oder eine falsche Auslegung von "lange", ich schaffe ca. 1Mio! Hashes alle 2 Sekunde.

Ich füge die URL in meine Datendatei ein und merke mir die Position. Die Position trage ich zusammen mit dem Hash wert ein einer weitere Datei zusammen. Diese Datei ist natürlich sortiert.

Somit habe ich zwei Dateien urls.daten und urls.index, die alle Informationen enthalten. Aus der Index-Datei hole ich mir bei Bedarf die Daten-Position mit binarer Suche und lese die Daten dann aus der Daten-Datei aus.

Zur Zeit entwickel ich noch etwas, um Daten-Datei und Index-Datei beliebig zu splitten, um sie handelbarer zu machen und einen neuen Index, der mir ein String-Contains bzw. SQL-"LIKE%" ermöglicht.

@Sir Rufo: Warum arbeitest du mit einem 32bit Hash ? Ich verwende den Md5-Hash, weil dieser (quasi keine) Kollision erzeugen kann und ich somit bei vielen Operationen nur mit dem Index arbeiten kann.

T
2.219 Beiträge seit 2008
vor 6 Jahren

@Christoph K.
Freut mich, dass mein Denkansatz dir hilft.
Wenn du eine performante Lösung hast, würde ich mich freuen die Lösung zu hören.
Der aktuelle Ansatz mit Url Hash klingt schon recht interessant.

T-Virus

Developer, Developer, Developer, Developer....

99 little bugs in the code, 99 little bugs. Take one down, patch it around, 117 little bugs in the code.

16.806 Beiträge seit 2008
vor 6 Jahren

Hashen braucht immer Zeit. Immer.
Aber Zeit ist relativ.

Und die Aussage von mir

Hashs sind immer langsam, daher sind Hashs niemals eine Lösung für Performance-hungrige Anwendungen.

ist keine Fehlinformation, sondern schlicht und einfach korrekt.

Der Sinn eines Hashes ergibt sich hier gar nicht. Du kannst genauso gut eine einfache String-Verkettung verwenden, um Deine Information zu speichern.
Den Nutzen eines Hashes hast Du hier gar nicht, wobei Du sowieso auch nur ein 1-Wege Hashverfahren verwendest.

Die Dauer eines Hashvorgangs ist immer von den Gegebenheiten abhängig, zB. Verfahren, Environment, Länge.
Nur weil Deine 1 Mio Hashvorgänge "nur" 2 Sekunden dauert, ist das relativ gesehen nicht wenig.

1.000.000 = 2.000 ms = 2 Sekunden
10.000.000 = 20.000 ms = 20 Sekunden
100.000.000 = 200.000 ms = 200 Sekunden
1.000.000.000 = 2.000.000 ms = 2000 Sekunden = 33 Minuten
10.000.000.000 = 20.000.000 ms = 20.000 Sekunden = 333 Minuten = 5,5 Stunden

Davon abgesehen, dass ich nicht noch einen Rechenfehler habe: ){gray}Siehst Du welchen Zeitaufwand Du total für das Hashen hast, ohne einen direkten Nutzen zu erziehlen?
Ja, das ist langsam.

PS: Md5 ist kollisionsanfällig und gilt u.a. deswegen auch nicht mehr als sicheres Hashverfahren.Ein MD5 Resultat hat schließlich nur 128 Bit.

D
985 Beiträge seit 2014
vor 6 Jahren

Weil ich mit dem Verfahren rund 2 Milliarden Dateien erzeuge die im Schnitt nicht größer als 4096 Bytes sind und somit (idR) einen Cluster auf der Festplatte belegt.

Bei 10 Milliarden Einträgen befinden sich im Schnitt 5 Einträge in jeder Datei.

Beim Lesen einer Url über die Id wird eine Datei gelesen und daraus eine Zeile zurückgeliefert.

Auch das Eintragen geht dadurch sehr schnell.

  • Hash bilden
  • Datei öffnen
  • max. 5 Einträge vergleichen (statistisch gesehen)
  • evtl. schreiben

Natürlich kostet hashen Zeit, das Suchen nach einem Eintrag kostet aber auch Zeit.

16.806 Beiträge seit 2008
vor 6 Jahren

Dann ist der direkte Nutzen, dass Du monolithisch, schwer skalierbar Performance investierst, um IO-Aufgaben zu übernehmen, sodass Du die Festplatte als Träger verwendest? 🤔

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

@Abt:

Der Hash-Vergleich ist wesentlich schneller als der String-Vergleich. Daher der Hash. Zudem lässt sich mit festen Längen der Hash-Werte leichter arbeiten als mit variablen Strings im Index (was auch möglich wäre).

Bei deiner Rechnung hast du nicht berücksichtigt, dass ich ja nicht immer alle Hashes neu berechnen muss, sondern immer nur die Hashes für die neuen Daten. Hier geh ich zur Zeit von 1 Millionen neuen Daten pro Tag aus, die 2 Sekunden kann ich am Tag verkraften 😄

Zur Kollisionswahrscheinlichkeit habe ich berechnet, dass es bei 128 Bit und einer Gesamtanzahl von einer Billiarden Werte (das Millionenfache von dem was ich ca brauche) eine Kollisionwahrscheinlichkeit von 0,00000014694 % habe.
Damit kann ich sehr gut leben 😄

Nähe Infos: http://big.info/2013/04/md5-hash-collision-probability-using.html

Natürlich kostet hashen Zeit, das Suchen nach einem Eintrag kostet aber auch Zeit.

=> Genau, und die Zeit, die das Suchen kostet fällt mehrfach an.

16.806 Beiträge seit 2008
vor 6 Jahren

Ich verwende den Md5-Hash, weil dieser (quasi keine) Kollision erzeugen kann

Diese Aussage von Dir ist halt nicht ganz korrekt.
Wenn es Dir ausreicht, dann ist es eine andere Sache und hat mit der Aussage selbst recht wenig zutun.

Aber selbst in der Wikipedia Einleitung kannst Du entnehmen:

Sie gilt inzwischen nicht mehr als sicher, da es mit überschaubarem Aufwand möglich ist, unterschiedliche Nachrichten zu erzeugen, die den gleichen MD5-Hashwert aufweisen.

Meine Berechnung bezieht sich rein auf den Initialwert, nicht auf die laufende Berechnung.
Wenn es Dir als Schlüssel dient und Du mit der zusätzlichen Last leben kannst, dann ist das okay. Das Ziel ist ja das entscheidende.
Aber Hashing ist und bleibt eines der langsamsten Elemente in einem System.
Daher gibt es auch alle 1-2 Jahre neue Hashing verfahren, die versuchen schneller und schneller zu werden.

Selbst im .NET Framework unterscheidet sich auch die Implementierung massiv.
So ist MD5() viel viel langsamer als der MD5CryptoServiceProvider; und SHA512Managed ist mit der schnellste.

Was ihr da gebastelt habt ist nichts anderes als ein auf der Festplatte basierender Redis. Und Redis wurde ja ganz am Anfang des Threads schon als potentielles System genannt (mit dem Unterschied, dass man sich bei Redis das Hashen hätte sparen können).

Christoph K. Themenstarter:in
821 Beiträge seit 2009
vor 6 Jahren

Redis viel für mich raus, da es auf die größe des Rams beschränkt ist.
Es gab wohl mal ein Projekt, was auch mit Festplatte gearbeitet hat, aber das wurde wohl eingestellt.

2.760 Beiträge seit 2006
vor 6 Jahren

Als Hash könnte für Dich auch noch MurMur3 in Frage kommen. Das sollte nochmal ein Stück schneller sein als MD5, ist aber keine kryptographische Hash-Funktion (was in Deinem Fall ja wurscht sein sollte).
Eine weitere NoSQL-DB, die ich in diesem Thread noch nicht entdeckt habe (edit: und die für Deinen Fall passen sollte) wäre LMDB.