XML Daten Parallel parsen

Naja, mit DOM wirst du nicht glücklich da die Datei zu groß ist und mit dem XMLReader wirst du nicht glücklich da der sequentiell liest. Beides net ganz glücklich. Da hilft auch kein Multithreading irgend einer Art da du die Daten einfach net in der richtigen Form zur Verfügung hast.

Aber vielleicht kann man da ansetzen. Mit dem klassichen Divide & Conquer kann man ja so einiges zügiger bearbeiten. Wenn du genügend Festplattenspeicher zur Verfügung hast, könnte man hingehen und die große Datei teile in kleinere Dateien. Ist bei XML nicht ganz so trivial, aber bei Linq to XML brauchts z.B. keine kompletten XML Dokumente sondern da würde es reichen wenn du nur immer komplette daten Tags hast. Du könntest jetzt jedenfalls die große Datei von oben durchgehen, schreibst die Datentags in nen neues Dokument bis die Datei ne bestimmte Größe hat (so dass sie per XML to Linq noch in Speicher passt) und dann fängst ne neue Datei an usw. Soviele Dateien wie du halt gleichzeitig bearbeiten kannst. Die einzelnen Dateien kannst du jetzt wenn sie getrennt sind ja ganz normal parallel bearbeiten. Wenn die Bearbeitung abgeschlossen ist geht das ganze halt weiter und die große Datei wird in weitere kleinere geteil usw.

Kam die Idee rüber? Im Detail gibts viele knifflige Stellen, aber vom Prinzip her müssts funktionieren. Die Festplattenzugriffe die nötig sind dürften im Vergleich zur jetzigen Laufzeit auch net ins Gewicht fallen.

Erstmal ist es wichtig die Bottlenecks zu bestimmen. Als Kandidaten sind da:

IO Zugriff: KOmmend ie Daten von Festplatte, Netzlaufwerk etc? Mit welcher Datenrate können die Daten eingelesen werden?
Datenbank: Wie werden die Daten in die DB eingetragen? Vor allem hier kann man mächtig Performance killen. Benutzt Du Bulk-Inserts? Ist die Db auf dem gleichen Rechner auf dem auch deine Software läuft oder geht das übers Netz?

Natürlich ist es eine gute Idee alle Kerne zu beschäftigen, aber wenn das eigendliche Parsen am Ende nicht das Bottleneck ist, dann bringt die Verteilung auf mehrere Threads auch nix.

Da dies eine OPtimierungs-Frage ist wäre der erste und wichtigste Schritt einen Profiler zu verwenden um genau festzustellen wo denn die Performance verbraten wird. Nicht zu vergessen das man gerade im NEt Framework auch eine ganze Reihe von Performance-Sünden begehen kann...

Ich habe aktuell auch die Situation wo ich eine Xml-Datei (ca 20MB) in eine Datenbank importiere. Das Laden der Datei dauert ca 1, 2 Sekunden, der tatsächliche Import dann 15 Minuten. Will sagen, der XmlParser an sich ist nicht das Bottleneck.

Ringostarr

@theta: danke für den Link, ich werde es mir mal ansehen und gucken, ob ich was mit anfangen bzw. ob es sich für XML-Verarbeitung eignet.

@Zwergli: vom Prinzip hab ich verstanden was du meinst, jedoch finde ich diesen Ansatz etwas zu umständlich und Suboptimal.
1. weil man die Dateien aufsplitten muss, was wahrscheinlich nicht mal wirklich schwierig ist.
2. weil durch das aufsplitten ein gewisser Versatz im Bezug auf die Beendigung der Prozesse entsteht, d.h. das eine Datei theoretisch 10 Minuten früher abgearbeitet sein könnte als die andere, womit wieder ein Prozessor ungenutzt liegen würde.

@loks:
1. IO-Zugriffe sollten keine Bottlenecks darstellen, da die Dateien auf derselben Festplatte(SATA2) liegen, wie das Programm.
2. Die Daten werden über normale Inserts eingefügt. Über Bulk-Inserts habe ich dabei noch nicht nachgedacht. Die meiste Zeit wird jedoch wahrscheinlich beim parsen und verarbeiten der XML-Daten verbraucht. Die Datenbank liegt auch auf dem selben Rechner. Das ganze müsste jedoch tatsächlich erst mit einem Profiler überprüft und bestätigt werden. Jedoch habe ich bisher noch nie mit einem Profiler gearbeitet und weiß auch nicht, was für Profiler es für .NET gibt.

Gedankenspiel:
gibt es nicht sowas wie einen Triggergesteuerten XML-Parser, der nach dem einlesen eines Knotens eine bestimmte Funktion Asynchron aufruft und dann gleich mit dem einlesen des nächsten Knotens weitermacht usw.
Natürlich liest er immer nur dann den nächsten Knoten ein, wenn ausreichend Ressourcen, also Prozessoren/Kerne frei sind bzw. eine selbstdefinierte maximale Anzahl an Threads nicht überschritten sind.
Ich hoffe es ist verständlich, wie ich das meine.

mogel

loks schrieb:

der erste und wichtigste Schritt einen Profiler zu verwenden um genau festzustellen wo denn die Performance verbraten wird.

an der Datenbank ... die arbeitet mit der Festplatte und die ist nunmal langsam ... das einzige wo man trennen könnte wäre zwischen XML parsen und den DB Inserts ... vermutlich wird auch kein StringBuilder sondern String verwendet

mogel schrieb:

loks schrieb:

der erste und wichtigste Schritt einen Profiler zu verwenden um genau festzustellen wo denn die Performance verbraten wird.

an der Datenbank ... die arbeitet mit der Festplatte und die ist nunmal langsam ...

So pauschal eine falsche Aussage. Datenbanken sind extrem performant _wenn_ man sie richtig bedient und konfiguriert. Ist schon ein paar Jahre her das ich mit ner Oracle-DB gearbeitet habe, aber schon da gingen locker 1000 Inserts pro Sekunde im Bulk-Modus.

Come to think of it. Bei dem Projekt braucht der DB-Loader anfangs 10 Minuten weil er jeden Datensatz einzeln verarbeitet wurde. Nach Umstellung auf Bulk dauerte der gleiche Vorgang nur noch knapp 6 Sekunden...

Ringostarr

ok, ich habe vielleicht noch etwas vergessen zu erwähnen.
Und zwar wird nicht bei jedem Knoten etwas in die Datenbank geschrieben, sondern nur wenn in der description gewisse sachen drinstehen. Alles in allem werden bei einer XML-Datei ca. 150000 Einträge in der Datenbank generiert, d.h. über 2 Tage gerechnet entspricht das ca. 1 Eintrag pro Sekunde. Somit sollte die Datenbank kein wirkliches Bottleneck sein.
Selbst wenn es parallisiert wäre und theoretisch bei 8 Kernen nur noch 6 Stunden dauert, sind es 8 Einträge pro Sekunden, was immer noch nicht wirklich viel ist.

Andorxor

Könntest du nicht mit regulären Ausdrücken die Knoten die du willst aus der dicken XMl Datei extrahieren,bevor du das Xml verarbeitests?

Hallo,

. weil durch das aufsplitten ein gewisser Versatz im Bezug auf die Beendigung der Prozesse entsteht, d.h. das eine Datei theoretisch 10 Minuten früher abgearbeitet sein könnte als die andere, womit wieder ein Prozessor ungenutzt liegen würde.

Nee, wieso? Wenn du 8 Kerne hast, könnten doch 7 das parsen übernehmen und einer ist dediziert für die Bereitstellung der Daten. Und der eine könnte doch immer fortwährend Teile aus der großen Datei zum parsen generieren so dass bei Beendigung eines Parserthreads einfach das neue Dateistück mit angegeben wird und der Thread kann von vorne losgehen. Da muss nichts warten wenn man das geschickt anstellt.

Das mit dem Bulkinsert solltest du dir unbedingt anschaun, das kann massig bringen.

Aber ich find das Parsen an sich dauert auch viel viel zu lange. Ne Sekunde pro Eintrag ist sowas von arschlangsam, selbst wenn die zu parsenden Nodes recht komplex sind. Man kann beim Parsen auch besonders viel falsch machen was z.B. Stringoperationen angeht, unnötige Objekte erstellen usw. Da solltest du mal schaun.

Wärte es möglich vielleicht mal bissle Code von deinem Parsen, am besten mit nem Stück konkreten XML welches geparste werden soll zu sehen? Also zumindest von der Struktur her, richtige Daten müssen ja nicht drin stehen. Mit dem beiden zusammen, Code + XML, kann man ganz gut sagen ob es da noch irgendwie hakt.

Ringostarr

Andorxor schrieb:

Könntest du nicht mit regulären Ausdrücken die Knoten die du willst aus der dicken XMl Datei extrahieren,bevor du das Xml verarbeitests?

wäre evtl. auch ne Möglichkeit, wenn er das durchsuchen mit regulären Ausdrücken nicht alles auf einmal macht und somit alle treffer gleich in den Speicher laden will!? Wenn das nicht der Fall ist, kann man gucken, ob man das denn parallelisieren kann.

@Zwergli:

Zwergli schrieb:

. weil durch das aufsplitten ein gewisser Versatz im Bezug auf die Beendigung der Prozesse entsteht, d.h. das eine Datei theoretisch 10 Minuten früher abgearbeitet sein könnte als die andere, womit wieder ein Prozessor ungenutzt liegen würde.

Nee, wieso? Wenn du 8 Kerne hast, könnten doch 7 das parsen übernehmen und einer ist dediziert für die Bereitstellung der Daten. Und der eine könnte doch immer fortwährend Teile aus der großen Datei zum parsen generieren so dass bei Beendigung eines Parserthreads einfach das neue Dateistück mit angegeben wird und der Thread kann von vorne losgehen. Da muss nichts warten wenn man das geschickt anstellt.

Das wäre doch dann sowas wie mein Gedankenspiel, oder?

Zwergli schrieb:

Aber ich find das Parsen an sich dauert auch viel viel zu lange. Ne Sekunde pro Eintrag ist sowas von arschlangsam...

nee, da hast du was falsch verstanden. Er schafft so ca. 20-100 XML-<daten>-Knoten pro Sekunde zu parsen, je nach Komplexität, aber von den 20-100 Knoten wird nur ca. einer in die Datenbank eingetragen

Code + XML Schnipsel liefere ich noch nach.

Ringostarr

entschuldigt, dass ich solange gebraucht habe, aber hier sind der Codeausschnitt und der XML-Part:

XmlReader tWikiXmlReader;
FileStream tWikiXmlStream = File.OpenRead(tFileName);

string tTitle = "";
string tDescription = "";

tWikiXmlReader = XmlReader.Create(tWikiXmlStream);

while (tWikiXmlReader.Read())
{
    RepeatSql = true;

    if (tWikiXmlReader.NodeType == XmlNodeType.Element)
    {
        if (tWikiXmlReader.Name == "title")
        {
            tDescription = "";

            tWikiXmlReader.Read();
            tTitle = tWikiXmlReader.Value;
            continue;
        }
        else if (tWikiXmlReader.Name == "text")
        {
            tWikiXmlReader.Read();
            tDescription = tWikiXmlReader.Value;
            if (tDescription.Length > 0)
                AllEntries++;
        }
        else
            continue;
    }
    if (tDescription.Length > 0 && tWikiXmlReader.NodeType == XmlNodeType.Text)
    {
        // hier werden diverse Sachen gefiltert und extrahiert, damit sie in die Datenbankfelder eingetragen werden können.
        ...

        // Wenn entsprechende Daten gefunden wurden, dann in die Datenbank eintragen.
        if(!(Latitude == 0 && Longitude == 0))
        {
            tDbCommand = new MySqlCommand("INSERT INTO enwiki (title, description, lat, long) VALUES (?title, ?description, ?lat, ?long, ?population)", tDbConnection);
            tDbCommand.Parameters.AddWithValue("?title", Encoding.UTF8.GetBytes(tTitle));
            tDbCommand.Parameters.AddWithValue("?description", Encoding.UTF8.GetBytes(tDescription));
            tDbCommand.Parameters.AddWithValue("?lat", Encoding.UTF8.GetBytes(Latitude.ToString()));
            tDbCommand.Parameters.AddWithValue("?long", Encoding.UTF8.GetBytes(Longitude.ToString()));
            tDbCommand.Parameters.AddWithValue("?population", Encoding.UTF8.GetBytes(Population.ToString()));
        }
    }
}

und ein XML-Beispiel:

<mediawiki>
    <page>
        <title>Actinium</title>
        <id>3</id>
        <revision>
            <text>Chemiches Element ...</text>
        </revision>
    </page>
    ...
</mediawiki>

Erstmal fehlen wie immer die interessanten Punkte

// hier werden diverse Sachen gefiltert und extrahiert, damit sie in die Datenbankfelder eingetragen werden können

Gerade in dem Bereich dürfte es am ehesten Optimierungs-Potential geben:

tDbCommand.Parameters.AddWithValue("?title", Encoding.UTF8.GetBytes(tTitle));
            tDbCommand.Parameters.AddWithValue("?description", Encoding.UTF8.GetBytes(tDescription));
            tDbCommand.Parameters.AddWithValue("?lat", Encoding.UTF8.GetBytes(Latitude.ToString()));
            tDbCommand.Parameters.AddWithValue("?long", Encoding.UTF8.GetBytes(Longitude.ToString()));
            tDbCommand.Parameters.AddWithValue("?population", Encoding.UTF8.GetBytes(Population.ToString()));

Hier drängt sich direkt die Frage auf warum alles umständlich in Bytes konvertiert wird. Wichtig wäre hier die Tabellen-definition zu kennen. u.U. triggerst Du hier auto-konvertierungen die dann wieder von bytes in die richtigen Datentypen verwandeln -> teuer... Auch wäre es sinnvoller das SQL-Command nur einmal zu erzeugen anstatt jedesmal ein neues -> stressed nur die Speicherverwaltung und erfordert jedesmal ein neues Parsen des SQL auf der Datenbank...

Ansonsten, wie vermutet ist der eigendliche XMlTextReader nicht das Bottleneck, sondern die Verarbeitung der Daten. Bei einem Test mit 10 Millionen PAges läuft der Reader in knapp 2 Minuten durch (ohne internes Parsing).

Vielleicht hilft Dir folgender Ansatz:

using System;
using System.Collections.Generic;
using System.Windows.Forms;
using System.Xml;
using System.Text;
using System.IO;
using System.Threading;

namespace XmlTestStuff
{
    static class Program
    {
        public static Queue<String> NodeQueue = new Queue<string>();
        /// <summary>
        /// The main entry point for the application.
        /// </summary>
        [STAThread]
        static void Main()
        {
            Thread thread = new Thread(new ThreadStart(Worker));
            thread.IsBackground = true;
            thread.Start();

            // of course you can start more than one worker here, i.e. one worker per core)
            // when using more than one worker thread it might be needed to add synchronization code,
            // but not sure...

            using (XmlReader reader = XmlTextReader.Create("E:\\xmltest.xml"))
            {
                reader.ReadToDescendant("page"); // find the very first node and read it

                NodeQueue.Enqueue(reader.ReadInnerXml());

                while (reader.ReadToNextSibling("page") ) // now find all the sibling, aka nodes at the same depth like the first one.
                {
                    NodeQueue.Enqueue(reader.ReadInnerXml());
                }
            }
        }

        static void Worker()
        {
            while (true)
            {
                while (NodeQueue.Count == 0)
                {
                    Thread.Sleep(250);
                }

                StringReader stringreader = new StringReader(NodeQueue.Dequeue());
                using (XmlReader reader = XmlReader.Create(stringreader))
                {

                    // do ther parsing
                }
            }
        }
    }
}

EXDW

also ich wuerd sagen
-> profiler
alles andere ist bisher nur spekulation - am ende liegt das problem ganz woanders - dann hat man am falschen ende zeit investiert

ich selber benutz immer den build in profiler der beim vs team system dabei ist - n externen kenn ich grad nicht

Ringostarr

@loks:
man kann mit Sicherheit noch hier und da ein paar Sachen optimieren, da werden im code noch einige reguläre Ausdrücke verwendet etc. und bei den SQL-Parametern ging es glaube ich um Sonderzeichen und UTF-8 Kodierung. Ich kann ja mal schauen, ob ich es auch noch anders machen kann, ohne das Fehler auftreten.

Aber Primär ging es mir ja um die Frage, wie ich die ungenutzten Kerne ausnutzen kann und die Rechenlast effizient darauf verteilen kann.

Ansonsten gefällt mir der Ansatz, wie du die page-Nodes durchgehst ganz gut, ich denke, das werde ich mal für meine sache übernehmen. Vielleicht kann ich aber mit der vorgehensweise 8 Threads erzeugen, die dann gleichzeitig die Nodes bearbeiten können, wobei die Worker-Methode und der NodeQueue nicht statisch sein dürfen, oder man legt jeweils einen pro Thread an, was aber glaube ich dann wieder nicht so intelligent sein dürfte

@Mr. Evil:
Nach nem Profiler werde ich auch mal schauen, ich benutze Visual Studio 2008 Express Edition bzw. auch die Beta von Visual Studion 2010.