Die Kombination von Neo4J und Hadoop (Teil II)

Im vorigen Beitrag Kombinieren von Neo4J und Hadoop (Teil I) haben wir beschrieben, wie wir Hadoop und Neo4J kombinieren und wie wir die Daten in Neo4J bekommen. In diesem zweiten Teil nehmen wir Sie mit auf die Reise, die wir unternommen haben, um einen verteilten Weg zur Erstellung einer Neo4J-Datenbank zu implementieren. Die Idee ist, unseren Hadoop-Cluster für die Erstellung der zugrunde liegenden Dateistruktur einer Neo4J-Datenbank zu verwenden.Dazu müssen wir zunächst diese Dateistruktur verstehen. Glücklicherweise hat Chris Gioran diese Struktur in seinem Blog Neo4J internal file storage sehr gut beschrieben. Die Beschreibung wurde für die Version 1.6 erstellt, stimmt aber weitgehend mit der Dateistruktur von 1.8 überein. Ich beginne zunächst mit einer kleinen Zusammenfassung der Dateistruktur.

Die Neo4J Dateistruktur Am wichtigsten für die Datenbank sind die Dateien innerhalb des Verzeichnisses graph.db neostore neostore.id neostore.nodestore.db neostore.nodestore.db.id neostore.relationshipstore.db neostore.relationshipstore.db.id neostore.relationshiphiptypestore.db neostore.relationshiptypestore.db.id neostore.relationshiptypestore.db.names neostore.relationshiptypestore.db.names.id neostore.propertystore.db neostore.propertystore.db.id neostore.propertystore.db.arrays neostore.propertystore.db.arrays.id neostore.propertystore.db.strings neostore.propertystore.db.strings.id neostore.propertystore.db.index neostore.propertystore.db.index.id neostore.propertystore.db.index.keys neostore.propertystore.db.index.keys.id Die erste Datei ist die Neostore-Datei, in der die Erstellungszeit, die Zufallszahl, die Version, die letzte Transaktions-ID, die Speicherversion und die nächste propertyid kodiert sind. Jeder Wert wird als Long zusammen mit einer ein Byte langen inUse-Markierung kodiert. Dies ergibt eine Datei mit 6 * 9 Bytes + 15 Bytes für den Dateityp und die Versionszeichenfolge "NeoStore v0.A.0"Jede Datei wird von einer .id-Datei begleitet. Darin wird die letzte freie ID gespeichert. Für den Neostore wird dies 6 sein, da wir bereits 5 Datensätze mit 9 Bytes verwenden.Die Knoten:Die Knoten werden in der Datei neostore.nodestore.db gespeichert. Die Knoten werden in Datensätzen mit einer Gesamtgröße von 9 Bytes kodiert. 1 Byte Use Flag 4 Byte ID der ersten Beziehung 4 Byte ID der ersten Eigenschaft Die Position in der Datei ergibt die nodeId, so dass wir mit diesen 9 Bytes alle Informationen haben, die wir für einen Knoten benötigen. Am Ende der Datei werden der Typ und die Version ("NodeStore v0.A.0") in 16 Bytes kodiert. Das sieht ungefähr so aus: 01 ff ff ff ff ff ff ff ff // root node, no relationships, no properties 01 00 00 00 00 00 00 00 01 // node 1, first relationship 0, first property 1 01 00 00 00 02 00 00 00 04 // node 2, first relationship 2, first property 4 4e 6f 64 65 53 74 6f 72 65 20 76 30 2e 41 2e 30 // NodeStore v0.A.0 Die Beziehungen: Beziehungen werden in der Datei neostore.relationshipstore.db gespeichert. Die Beziehungen sind in 33 Bytes kodiert 1 Byte Verwendungskennzeichen 4 Byte von der Knoten-ID 4 Byte zur Knoten-ID 4 Byte Beziehungstyp 4 Byte vom Knoten vorherige rel id 4 Byte vom Knoten nächste rel id 4 Byte zum vorherigen Knoten rel id 4 Byte zum nächsten Knoten rel id 4-Byte-ID der ersten Eigenschaft Die Position in der Datei ergibt wiederum die ID und am Ende der Datei werden der Typ und die Version in 24 Bytes kodiert ("RelationshipStore v0.A.0") Neben den Nodeids, den vorherigen und nächsten Beziehungen und der ersten Eigenschafts-ID gibt es einen Zeiger auf den Beziehungstyp, der in der neostore.relationshiptypestore.db gespeichert ist Damit sieht die Beziehungsdatei wie folgt aus: 01 00 00 00 02 00 00 00 01 00 00 00 00 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff // relationship 1, from node 2, to node 1, type 0, no prev, no next, 01 00 00 00 04 00 00 00 03 00 00 00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00 00 00 06 01 00 00 00 06 00 00 00 05 00 00 00 01 ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff ff 00 00 00 0a 52 65 6c 61 74 69 6f 6e 73 68 69 70 53 74 6f 72 65 20 76 30 2e 41 2e 30 Die Datei neostore.relationshiptypestore.db ist nur eine einfache 5-Byte-Codierung 1-Byte-Use-Flag 4-Byte-ID des Typnamens am Ende der Datei werden der Typ und die Version codiert ("RelationshipTypeStore v0.A.0") in 28 Bytes Die Id des Typnamens ist der Datensatz in der neostore.relationshiptypestore.db.names. Der Rest der Dateien wird im oben erwähnten Blog von Chris Gioran perfekt erklärt. Im vorherigen Blog haben wir bei Phase III aufgehört, also machen wir von dort aus weiter Phase IV: Wie nutzen wir nun diese Informationen, um diese Dateien auf verteilte Weise zu erstellen. In diesem Blog werde ich mich auf die Knoten, Beziehungen und Eigenschaften konzentrieren, da die anderen Dateitypen nur eine geringe Menge an Informationen enthalten. Da die Id der Knoten und Kanten auf der Position in der Datei basiert, benötigen wir eine Sequenznummer für die Knoten und die Kanten. Glücklicherweise hat mein Kollege Friso bereits einen solchen Versuch unternommen (siehe Monoton steigende Zeilen-IDs) Wie im vorherigen Blog erwähnt, beginnen wir mit zwei Eingabedateien. Eine für die Knoten und eine für die Kanten zwischen den Knoten. Die ersten beiden Aufgaben sind also ganz einfach. Nehmen Sie einfach die Knotendaten und fügen Sie eine Zeilennummer hinzu, dasselbe gilt für die Kantendaten So erhalten wir die folgenden Daten (basierend auf den Daten, mit denen wir im vorigen Blog begonnen haben) Die Tabelle/Datei für die Knoten sieht etwa so aus: RowNum NodeId Property1 Property2 PropertyN 0 AAA nameOfA amountOfA someAThing 1 BBB nameOfB amountOfB someBThing 2 CCC nameOfC amountOfC someCThing 3 DDD nameOfD amountOfD someDThing Die Kanten-Tabelle/Datei sieht in etwa so aus: RowNum fromNodeId ToNodeId EdgeProperty1 EdgePropertyN 0 AAA BBB someDate1 someNumber1 1 AAA DDD someDate2 someNumber2 2 BBB DDD someDate3 someNumber3 3 CCC BBB someDate4 someNumber4 4 DDD BBB someDate5 someNumber5 5 DDD CCC someDate6 someNumber6 Beginnen Sie mit den NODES Bei der Untersuchung der Dateiformate haben wir gelernt, dass Knoten einen Zeiger auf die erste Kante und einen Zeiger auf die erste Eigenschaft haben wenn wir die Anzahl der Eigenschaften eines Knotens kennen, ist der Zeiger auf die erste Eigenschaft leicht zu finden (multiplizieren Sie einfach die Nodeid mit der Anzahl der Knoteneigenschaften und schon sind wir startklar) Als nächstes müssen wir die folgenden Schritte durchführen: 1 - Knoten und Kanten auf id und idfrom verbinden (Eigenschaften können ignoriert werden) 2 - Knoten und Kanten auf id und idto verbinden (Eigenschaften können ignoriert werden) 3 - Vereinigen Sie diese beiden Verbindungen 4 - aufsteigend nach nodenum, absteigend nach relnum sortieren 5 - Nehmen Sie nur die erste von jeder Id 6 - sortieren nach rownum 7 - Byterecords pro Knoten erstellen Schritt 1 führt zu: nodeNum nodeId relNum fromNodeId ToNodeId fromNodeNum 0 AAA 0 AAA BBB 0 0 AAA 1 AAA DDD 0 1 BBB 2 BBB DDD 1 2 CCC 3 CCC BBB 2 3 DDD 4 DDD BBB 3 3 DDD 5 DDD CCC 3 Schritt 2 führt zu: nodeNum nodeId relNum fromNodeId ToNodeId toNodeNum 1 BBB 0 AAA BBB 1 3 DDD 1 AAA DDD 3 3 DDD 2 BBB DDD 3 1 BBB 3 CCC BBB 1 1 BBB 4 DDD BBB 1 2 CCC 5 DDD CCC 2 Schritt 3 führt zu: nodeNum nodeId relNum fromNodeId ToNodeId fromNodeNum toNodeNum 0 AAA 0 AAA BBB 0 1 0 AAA 1 AAA DDD 0 3 1 BBB 2 BBB DDD 1 3 2 CCC 3 CCC BBB 2 1 3 DDD 4 DDD BBB 3 1 3 DDD 5 DDD CCC 3 2 1 BBB 0 AAA BBB 0 1 3 DDD 1 AAA DDD 0 3 3 DDD 2 BBB DDD 1 3 1 BBB 3 CCC BBB 2 1 1 BBB 4 DDD BBB 3 1 2 CCC 5 DDD CCC 3 2 Schritt 4 führt zu: nodeNum nodeId relNum fromNodeId ToNodeId fromNodeNum toNodeNum 0 AAA 1 AAA DDD 0 3 0 AAA 0 AAA BBB 0 1 1 BBB 4 DDD BBB 3 1 1 BBB 3 CCC BBB 2 1 1 BBB 2 BBB DDD 1 3 1 BBB 0 AAA BBB 0 1 2 CCC 5 DDD CCC 3 2 2 CCC 3 CCC BBB 2 1 3 DDD 5 DDD CCC 3 2 3 DDD 4 DDD BBB 3 1 3 DDD 2 BBB DDD 1 3 3 DDD 1 AAA DDD 0 3 Schritt 5 und 6 ergeben: nodeNum nodeId relNum fromNodeId ToNodeId fromNodeNum toNodeNum 0 AAA 1 AAA DDD 0 3 1 BBB 4 DDD BBB 3 1 2 CCC 5 DDD CCC 3 2 3 DDD 5 DDD CCC 3 2 Jetzt können wir dies in der Datei neostore.nodestore.db wie folgt ausgeben: 1 1 0 1 4 4 1 5 8 1 5 12 Als nächstes verarbeiten wir die EDGES Die ersten Schritte sind die gleichen, die wir für die Nodes durchführen mussten 1 - join nodes and edges on id und idfrom (Eigenschaften können ignoriert werden) 2 - join nodes and edges on id und idto (Eigenschaften können ignoriert werden) 3 - union these two joins 4 - sort ascending on nodenum, descending on relnum Wir haben die Daten aus dem Nodes Schritt 4, um damit zu beginnen und wir können die nodeIds weglassen: nodeNum relNum fromNodeNum toNodeNum 0 1 0 3 0 0 0 1 1 4 3 1 1 3 2 1 1 2 1 3 1 0 0 1 2 5 3 2 2 3 2 1 3 5 3 2 3 4 3 1 3 2 1 3 3 1 0 3 5 - Bestimmen Sie die Reihenfolge der Beziehungen pro Knoten nodeNum relNum fromNodeNum toNodeNum next previous 0 1 0 3 0 x 0 0 0 1 x 1 1 4 3 1 3 x 1 3 2 1 2 4 1 2 1 3 0 3 1 0 0 1 x 2 2 5 3 2 3 x 2 3 2 1 x 5 3 5 3 2 4 x 3 4 3 1 2 5 3 2 1 3 1 4 3 1 0 3 x 2 6 - Erstellen Sie einen Self-Join auf relnum, fromNodeNum und toNodeNum, um den vorherigen/nächsten für den toNode zu bestimmen. nodeNum relNum fromNodeNum toNodeNum next previous nodeNum2 relNum2 fromNodeNum2 toNodeNum2 next2 previous2 0 1 0 3 0 x 0 1 0 3 0 x 0 1 0 3 0 x 3 1 0 3 x 2 0 0 0 1 x 1 0 0 0 1 x 1 0 0 0 1 x 1 1 0 0 1 x 2 1 4 3 1 3 x 1 4 3 1 3 x 1 4 3 1 3 x 3 4 3 1 2 5 1 3 2 1 2 4 1 3 2 1 2 4 1 3 2 1 2 4 2 3 2 1 x 5 1 2 1 3 0 3 1 2 1 3 0 3 1 2 1 3 0 3 3 2 1 3 1 4 1 0 0 1 x 2 1 0 0 1 x 2 1 0 0 1 x 2 0 0 0 1 x 1 2 5 3 2 3 x 2 5 3 2 3 x 2 5 3 2 3 x 3 5 3 2 4 x 2 3 2 1 x 5 2 3 2 1 x 5 2 3 2 1 x 5 1 3 2 1 2 4 3 5 3 2 4 x 3 5 3 2 4 x 3 5 3 2 4 x 2 5 3 2 3 x 3 4 3 1 2 5 3 4 3 1 2 5 3 4 3 1 2 5 1 4 3 1 3 x 3 2 1 3 1 4 3 2 1 3 1 4 3 2 1 3 1 4 1 2 1 3 0 3 3 1 0 3 x 2 3 1 0 3 x 2 3 1 0 3 x 2 0 1 0 3 0 x 7 - Entfernen Sie die Duplikate von id, from, to und relnum (die selbstverknüpften Datensätze). nodeNum relNum fromNodeNum toNodeNum next previous nodeNum2 relNum2 fromNodeNum2 toNodeNum2 next2 previous2 0 1 0 3 0 x 3 1 0 3 x 2 0 0 0 1 x 1 1 0 0 1 x 2 1 4 3 1 3 x 3 4 3 1 2 5 1 3 2 1 2 4 2 3 2 1 x 5 1 2 1 3 0 3 3 2 1 3 1 4 1 0 0 1 x 2 0 0 0 1 x 1 2 5 3 2 3 x 3 5 3 2 4 x 2 3 2 1 x 5 1 3 2 1 2 4 3 5 3 2 4 x 2 5 3 2 3 x 3 4 3 1 2 5 1 4 3 1 3 x 3 2 1 3 1 4 1 2 1 3 0 3 3 1 0 3 x 2 0 1 0 3 0 x 8 - filtern Sie die Duplikate heraus (auf relnum, form, to) und behalten Sie die, bei denen nodeNum == fromNodeNum nodeNum relNum fromNodeNum toNodeNum next previous nodeNum2 relNum2 fromNodeNum2 toNodeNum2 next2 previous2 0 1 0 3 0 x 3 1 0 3 x 2 0 0 0 1 x 1 1 0 0 1 x 2 1 2 1 3 0 3 3 2 1 3 1 4 2 3 2 1 x 5 1 3 2 1 2 4 3 5 3 2 4 x 2 5 3 2 3 x 3 4 3 1 2 5 1 4 3 1 3 x 9 - Sortieren nach relnum (Vorbereitung für die Ausgabe), Entfernen von unbenutzten Elementen wie nodeNum, nodenum2, relnum2, formNodeNum2 und toNodeNum2 relNum fromNodeNum toNodeNum fromnext fromprevious tonext toprevious 0 0 1 x 1 x 2 1 0 3 0 x x 2 2 1 3 0 3 1 4 3 2 1 x 5 2 4 4 3 1 2 5 3 x 5 3 2 4 x 3 x 10 - create byterecord per rel Jetzt müssen wir uns nur noch um die Eigenschaften kümmern. Damit dieser Beitrag nicht zu lang wird (dafür ist es wohl etwas zu spät), überlasse ich das einer Übung für den Leser. Diese Kombination von Aufträgen läuft also etwa 1 Stunde lang, aber das Übertragen der Dateien auf den lokalen Rechner dauerte 6 Stunden. Was ist hier passiert?Wir haben eine Datenbank mit einer Größe von 136 GB statt der 80 GB mit dem BatchimporterHoppla, wir haben irgendwo die Optimierung der Eigenschaften verpasst. zurück zum Zeichenbrett Eigenschaften werden in einem Datensatz mit 4 Longs (4 * 8 Bytes) gespeichert und für einige Eigenschaften ist das mehr als genug Platz, um mehrere Eigenschaften in einem Datensatz zu speichern. Auch das haben wir implementiert und uns eine schöne 80 GB große Datenbank zugelegt. Den Code für all dies finden Sie auf github. Ich habe dieses Projekt genutzt, um mich mit dem Map/Reduce-Paradigma besser vertraut zu machen. Daher habe ich alle Aufträge in reinen Java-Map/Reduce-Teilen codiert. Ich hoffe, dass dies für Sie von Nutzen war und ich hoffe, dass der Code sauber genug ist, um die Teile zu verstehen, die ich nicht im Detail beschrieben habe. Sie können mich gerne kontaktieren, wenn Sie den Code verwenden möchten und weitere Erklärungen benötigen. ---- Update ---- Michael Hunger von neotechnology hat mir ein schönes Bild gemailt, das das Dateispeicherformat etwas genauer erklärt. Da ein Bild mehr aussagt als die 1605 Worte, die ich verwendet habe, wollte ich es Ihnen nicht vorenthalten.