Verarbeitung großer Datenmengen mit Java

Question

Als Teil der Anforderung müssen wir fast 3 Millionen Datensätze verarbeiten und sie einem Bucket zuordnen. Diese Zuordnung wird anhand eines Regelsatzes (bestehend aus 5-15 Attributen mit einem oder mehreren Werten und einer Rangfolge) festgelegt, die den Bucket für einen Datensatz ableiten. Die sequentielle Verarbeitung einer so großen Anzahl ist eindeutig nicht möglich. Kann uns jemand bei der Vorgehensweise leiten, um eine Lösung effektiv zu gestalten?

Answer 1

3 Millionen Datensätze ist nicht wirklich viel von einem Datenvolumen Sicht (abhängig von der Größe des Datensatzes, offensichtlich), so würde ich vorschlagen, dass die Parallelisierung der Verarbeitung über mehrere Threads am einfachsten ist (mit dem Framework java.util.concurrent.Executor). Solange Sie mehrere CPU-Kerne zur Verfügung haben, sollten Sie in der Lage sein, nahezu lineare Leistungssteigerungen zu erzielen.

Answer 2

Ich bin mir nicht ganz sicher, was Sie wollen but here's a blog post about how the New York Times used Apache Hadoop Project to process a large volume of data.

Answer 3

Es hängt von der Datenquelle ab. Wenn es sich um eine einzelne Datenbank handelt, verbringen Sie die meiste Zeit damit, die Daten trotzdem abzurufen. Wenn es sich um eine lokale Datei handelt, können Sie die Daten in kleinere Dateien partitionieren oder die Datensätze auf gleiche Größe auffüllen - dies ermöglicht den wahlfreien Zugriff auf einen Stapel von Datensätzen.

Wenn Sie einen Multi-Core-Rechner haben, können die partitionierten Daten parallel verarbeitet werden. Wenn Sie die Record-Bucket-Zuordnung festgelegt haben, können Sie die Informationen mit der Batch-Funktion von PreparedStatement in die Datenbank zurückschreiben.

Wenn Sie nur eine einzelne Kernmaschine haben, können Sie dennoch einige Leistungsverbesserungen erzielen, indem Sie eine Datenabfrage - Datenverarbeitung - Batch-Writeback-Trennung durchführen, um die Pausenzeiten der E/A-Vorgänge zu nutzen.

Answer 4

Gibt es einen Grund, dass Sie Java verwenden müssen, um die Daten zu verarbeiten? Könnten Sie nicht SQL-Abfragen verwenden, um in Zwischenfelder zu schreiben? Sie können auf jedem Feld - Attribute - aufbauen, bis Sie alles in dem Eimer haben, den Sie brauchen.

Oder Sie könnten eine Hybrid von SQL und Java verwenden ... Verwenden Sie unterschiedliche Verfahren, um verschiedene "Buckets" von Informationen zu erhalten und senden Sie dann einen Thread-Pfad für detailliertere Verarbeitung und eine weitere Abfrage, um einen anderen Datensatz zu erhalten senden Sie das einen anderen Thread-Pfad ...

Answer 5

Dies gilt auch für die meisten Projekte, wo Sie große Mengen an Informationen verarbeiten müssen. Ich gehe davon aus, dass jeder Datensatz derselbe ist, z. Sie verarbeiten es auf die gleiche Weise jedes Mal, das wäre der Punkt, an dem Sie einen separaten Thread erstellen können, um die Verarbeitung durchzuführen.

Der zweite offensichtliche Punkt ist, wo Sie Ihre Informationen abrufen, in diesem Fall erwähnten Sie eine Datenbank, aber das ist wirklich ziemlich irrelevant. Sie möchten Ihre E/A- und Verarbeitungselemente in Ihrem Code in separate Threads (oder wahrscheinlicher, einen Pool von Executoren für die Verarbeitung) aufteilen.

Versuchen Sie, jedes so unabhängig wie möglich zu machen, und denken Sie daran, bei Bedarf Sperren zu verwenden. Hier sind einige Links, die Sie vielleicht lesen möchten.

http://www.ibm.com/developerworks/library/j-thread.html
http://www.ibm.com/developerworks/java/library/j-threads1.html http://www.devarticles.com/c/a/Java/Multithreading-in-Java/

Answer 6

Effektive Konstruktionsschritte für dieses Szenario bestehen aus ersten, jede und alle Orte zu bestimmen, wo Sie die Datensätze verarbeitet werden partitionieren können Vollmotor Parallelisierung (dh zu ermöglichen, vier Einheiten gegen 750k Datensätze sind jeweils vergleichsweise billig). Dann, abhängig von den Kosten der Regeln, die Ihren Datensatz zusammenfassen (ich sehe die Zuordnung eines Buckets als Zusammenfassung Operation), bestimmen Sie, ob Ihre Operation wird CPU-gebunden oder Datensatz Abruf gebunden.

Wenn Sie an die CPU gebunden sind, ist die Erhöhung der Partitionierung der beste Leistungsgewinn. Wenn Sie IO-gebunden sind, ist die Regelverarbeitung von Worker-Threads, die parallel zum Abruf von Chunked-Daten arbeiten können, ein leistungsfähigeres Design.

All dies setzt voraus, dass Ihre Regeln nicht zu einem Zustand führen, der zwischen Datensätzen verfolgt werden muss. Ein solches Szenario bedroht den Parallelisierungsansatz zutiefst. Wenn die Parallelisierung keine handhabbare Lösung ist, weil der kumulative Status eine Komponente des Regelsatzes ist, ist die beste Lösung möglicherweise die sequenzielle Verarbeitung einzelner Datensätze.

Answer 7

Sequenzielle Verarbeitung einer so großen Nummer ist eindeutig außerhalb des Geltungsbereichs.

Ich glaube nicht, dass Sie das wissen. Wie lange dauert es, um 1.000 Datensätze auf diese Weise zu verarbeiten? 10.000? 100.000? 1.000.000? Wenn die Antwort wirklich "zu lang" ist, dann in Ordnung: Beginne nach Optimierungen zu suchen. Aber du findest vielleicht die Antwort "unbedeutend" und dann bist du fertig.

Andere Antworten haben darauf hingewiesen, aber es ist meine gesamte Antwort. Beweisen Sie, dass Sie ein Problem haben, bevor Sie mit der Optimierung beginnen. Dann haben Sie zumindest ein einfaches, korrektes System zum Profilieren und vergleichen es mit optimierten Antworten.

Answer 8

Als bedeutungsloser Benchmark haben wir ein System mit einem internen Cache. Wir laden gerade 500K Zeilen. Für jede Zeile erstellen wir Statistiken, platzieren Schlüssel in verschiedenen Caches, etc. Derzeit dauert dies < 20s für uns zu verarbeiten.

Es ist ein bedeutungsloser Benchmark, aber es ist eine Instanz, die, je nach den Umständen, 3M Zeilen nicht viele Zeilen auf der heutigen Hardware ist.

Das sagte.

Wie andere vorgeschlagen haben, brechen Sie den Job in Stücke auf und parallelisieren Sie die Läufe, 1-2 Threads pro Kern. Jeder Thread behält seine eigenen lokalen Datenstrukturen und -zustände bei, und am Ende konsolidiert der Masterprozess die Ergebnisse. Dies ist ein grober "Map/Reduce" -Algorithmus. Der Schlüssel hier ist, sicherzustellen, dass die Threads nicht über globale Ressourcen wie globale Zähler usw. streiten. Lassen Sie die abschließende Verarbeitung der Thread-Ergebnisse mit diesen seriell umgehen.

Sie können mehr als einen Thread pro Kern verwenden, wenn jeder Thread DB IO ausführt, da kein einzelner Thread rein CPU-gebunden ist. Führen Sie den Vorgang einfach mehrere Male mit unterschiedlichen Fadenzahlen durch, bis er am schnellsten abschneidet.

Wir haben 50% Beschleunigung gesehen, selbst wenn wir Chargen durch ein beständiges Warteschlangensystem wie JMS laufen lassen, um die Arbeit vs lineare Verarbeitung zu verteilen, und ich habe diese Gewinne auf 2-Kern-Laptop-Computern gesehen, so gibt es definitiv Raum für den Fortschritt hier.

Eine andere Sache, wenn möglich ist keine Festplatte IO (speichern Sie die Daten aus der DB lesen) bis zum Ende. An diesem Punkt haben Sie viel mehr Gelegenheit, alle Aktualisierungen, die vorgenommen werden müssen, zu chargen, so dass Sie zumindest die Umlaufzeiten des Netzwerks reduzieren können. Selbst wenn Sie jede einzelne Zeile aktualisieren mussten, zeigen große SQL-Chargen immer noch einen Leistungszuwachs. Offensichtlich kann dies speicherintensiv sein. Glücklicherweise haben die meisten modernen Systeme viel Speicher.

Answer 9

Basierend auf der überarbeiteten Beschreibung, ich denke, ich würde versuchen, die Sortierung der Daten zu betrachten.

Sortierung kann ein Protokoll (n) Prozess sein; und wenn die meisten Vergleiche für direkte Gleichheit auf sortierbaren Feldern sind, sollte dies eine Gesamtkomplexität von ~ 0 (n log (n)) ergeben. Theoretisch. Wenn es nach dem Zuweisen eines Elements zu einem Bucket nicht mehr benötigt wird, entfernen Sie es einfach aus der Liste der Daten.

Auch wenn die Daten für verschiedene Schritte in der Logik ein paar Mal neu sortiert werden mussten, sollte es immer noch etwas schneller sein als dann n^2 Ansatz.

Im Grunde würde dies eine Vorverarbeitung der Daten erfordern, um die eigentliche Verarbeitung zu erleichtern.

Dies macht gewisse Annahmen über die Logik der Bucket-Zuweisung (nameley, dass es nicht zu weit von der pseudo-Code zur Verfügung gestellt wird); und wäre ungültig, wenn Sie Daten aus jedem Paar von A, B extrahieren müssten.

Hoffe, das hilft.

Edit: Ich würde kommentieren, wenn ich könnte; aber leider bin ich zu neu. Die Vorverarbeitung gilt für die Daten genauso wie für die einzelnen Kategorien. Letztendlich müssen Sie nur 15 Minuten Rechenzeit und 5 Minuten Rechenzeit benötigen, um 2/3s + der Kategorien, die nicht übereinstimmen und niemals übereinstimmen werden, in weniger als O (n) amortisierbar zu bestimmen Zeit. Was vielleicht nicht auf Ihre spezifische Situation zutrifft, gebe ich zu.

Answer 10

Ich würde mich bemühen, mit dem Autor der Spezifikation zurückzutreten, um mich mehr darauf zu konzentrieren, was getan werden muss, als wie. Ich kann mir nicht vorstellen, warum eine Spezifikation "Java" für eine datenintensive Operation drücken würde. Wenn es mit Daten zu tun hat, tun Sie es mit SQL. Wenn Sie Oracle verwenden, gibt es eine Funktion namens nTile. So einen festen Satz von Buckets zu schaffen ist so trivial wie:

select NTILE (4) über (um durch empno) GRP, empno, ename von emp

was dazu führt:

GRP EMPNO ENAME 
--- ----- --------- 
1 7369 SMITH 
1 7499 ALLEN 
1 7521 WARD 
1 7566 JONES 
2 7654 MARTIN 
2 7698 BLAKE 
2 7782 CLARK 
2 7788 SCOTT 
3 7839 KING 
3 7844 TURNER 
3 7876 ADAMS 
4 7900 JAMES 
4 7902 FORD 
4 7934 MILLER 

Zumindest könnten Sie zumindest Ihre Buckets in SQL einrichten, dann müsste Ihr Java-Code nur einen bestimmten Bucket verarbeiten.

Worker worker = new Worker(bucketID); 
worker.doWork(); 

Wenn Sie nicht über die Anzahl der Schaufeln ist es egal (das obige Beispiel für 4 Eimer bat) TBUT eher eine feste Größe von jedem Eimer (5 Datensätze pro Eimer), dann die SQL ist:

select ceil(row_number()over(order by empno)/5.0) grp, 
    empno, 
    ename 
from emp 

Ausgang:

GRP  EMPNO ENAME 
    --- ---------- ------- 
1  7369 SMITH 
1  7499 ALLEN 
1  7521 WARD 
1  7566 JONES 
1  7654 MARTIN 
2  7698 BLAKE 
2  7782 CLARK 
2  7788 SCOTT 
2  7839 KING 
2  7844 TURNER 
3  7876 ADAMS 
3  7900 JAMES 
3  7902 FORD 
3  7934 MILLER 

Beide Beispiele oben vom tollen Buch kommen: SQL-Kochbuch, 1. Ausgabe von Anthony Molinaro