Bei meiner Arbeit sollte ich eine Lösung für das folgende Problem entwickeln und implementieren:
Gegeben ein Datensatz von 30M Datensätze Tupel (Schlüssel, Wert) Tupel aus dem bestimmten Datensatzfeld, gruppieren sie nach Schlüssel und Wert speichert die Anzahl der gleichen Werte für jeden Schlüssel. Schreiben Sie die 5000 häufigsten Werte für jeden Schlüssel in eine Datenbank. Jede Datensatzzeile enthält bis zu 100 (Schlüssel-, Wert-) Tupel in Form von serialisiertem XML.
Ich habe die Lösung so gefunden (mit Spring-Batch ):
Stapeljobschritte:
Schritt 1. Iteriere über die Datensatzzeilen und extrahiere (Schlüssel-, Wert-) Tupel. Nachdem Sie eine bestimmte Anzahl von Tupeln erhalten haben, legen Sie sie auf der Festplatte ab. Jedes Tupel geht in eine Datei mit dem Namen pattern '/ chunk-', daher werden alle Werte für einen bestimmten Schlüssel in einem Verzeichnis gespeichert. Innerhalb einer Datei werden Werte sortiert gespeichert.
Schritt 2. Iterieren Sie über alle Verzeichnisse und fügen Sie ihre Chunk-Dateien in eine Gruppierung derselben Werte zusammen. Da die Werte sortiert gespeichert werden, ist es trivial, sie für die Komplexität O (n * log k) zusammenzufassen, wobei 'n' die Anzahl der Werte in einer Chunk-Datei und 'k' die anfängliche Anzahl der Chunks ist.
Schritt 3. Lesen Sie für jede zusammengeführte Datei (mit anderen Worten für jeden Schlüssel) sequenziell ihre Werte mit PriorityQueue , um die obersten 5000 Werte beizubehalten, ohne alle Werte in den Speicher zu laden. Schreiben Sie den Inhalt der Warteschlange in die Datenbank.
Ich habe ungefähr eine Woche mit dieser Aufgabe verbracht, hauptsächlich weil ich vorher nicht mit Spring-Batch gearbeitet habe und weil ich versucht habe, auf Skalierbarkeit zu setzen, die eine genaue Implementierung des Multithreading-Teils erfordert.
Das Problem ist, dass mein Manager diese Aufgabe als zu einfach erachtet, um so viel Zeit darauf zu verwenden.
Und die Frage ist - wissen Sie eine effizientere Lösung oder ist weniger effizient, die einfacher zu implementieren wäre? Und wie viel Zeit benötigen Sie, um meine Lösung zu implementieren?
Ich kenne MapReduce-ähnliche Frameworks, aber ich kann sie nicht verwenden, weil die Anwendung auf einem einfachen PC mit 3 Kernen und 1 GB für Java-Heaps ausgeführt werden soll.
Vielen Dank im Voraus!
UPD: Ich glaube, ich habe meine Frage nicht klar formuliert. Lass mich anders fragen:
Angesichts des Problems und als Projektmanager oder zumindest als Aufgabenprüfer akzeptieren Sie meine Lösung? Und wie viel Zeit würden Sie dieser Aufgabe widmen?
Sind Sie sicher, dass dieser Ansatz schneller ist als ein Vorab-Scan der XML-Datei, um alle Schlüssel zu extrahieren, und dann die XML-Datei für jeden Schlüssel wieder und wieder analysieren? Sie machen eine Menge Dateimanagementaufgaben in dieser Lösung, die definitiv nicht kostenlos ist.
Da Sie drei Kerne haben, können Sie drei Schlüssel gleichzeitig parsen (solange das Dateisystem die Ladung verarbeiten kann).
Ihre Lösung scheint vernünftig und effizient zu sein, aber ich würde wahrscheinlich SQL verwenden.
Beim Parsen der Schlüssel / Wert-Paare würde ich in eine SQL-Tabelle einfügen / aktualisieren. Ich würde dann die Tabelle nach den Spitzensätzen abfragen.
Hier ist ein Beispiel, das nur T-SQL verwendet (SQL 2008, aber das Konzept sollte in den meisten mordernen rdbms praktikabel sein)
Die SQL zwischen / START / und / END / würde die Anweisungen sein, die Sie in Ihrem Code ausführen müssen.
%Vor%Wenn die "einfache" Lösung aufgrund der Größe der Daten keine Option ist, wäre meine nächste Wahl die Verwendung einer SQL-Datenbank. Da die meisten davon jedoch ziemlich viel Arbeitsspeicher benötigen (und wenn sie im RAM stark überlastet sind), sollten Sie Ihre Suche vielleicht in eine NoSQL-Datenbank wie MongoDB , das selbst bei Festplatten meist recht effizient sein kann. (Was Ihre Umgebung im Grunde benötigt, nur 1 GB Heap verfügbar).
Die NoSQL-Datenbank übernimmt die grundlegende Buchhaltung für Sie (Speicherung der Daten, Verfolgung aller Indizes, Sortierung) und kann es wahrscheinlich ein wenig effizienter als Ihre Lösung machen, aufgrund der Tatsache, dass alle Daten dies können bereits beim Einfügen sortiert und indexiert werden, wobei die zusätzlichen Schritte des Sortierens der Zeilen in den / chunk-Dateien, Zusammenführen usw. wegfallen.
Sie erhalten eine Lösung, die wahrscheinlich viel einfacher zu verwalten ist, und Sie können auch verschiedene Arten von Abfragen einrichten, anstatt nur für diesen speziellen Fall optimiert zu werden.
Als Projektmanager würde ich Ihre derzeitige Lösung nicht ablehnen. Es ist schon schnell und löst das Problem. Als Architekt würde ich jedoch einwenden, dass die Lösung ein wenig schwierig zu warten ist und dass Sie keine bewährten Technologien verwenden, die im Grunde zum Teil dasselbe sind, was Sie selbst programmiert haben. Es ist schwer, die Baum- und Hashimplementierungen moderner Datenbanken zu übertreffen.
Tags und Links algorithm java bigdata spring-batch batch-processing