TigerGraph: Die parallele Graphendatenbank erklärt

Victor Lee ist Director of Product Management bei TigerGraph.

Graphendatenbanken zeichnen sich durch die Beantwortung komplexer Fragen zu Beziehungen in großen Datenmengen aus. Sie stoßen jedoch an eine Wand - sowohl hinsichtlich der Leistung als auch der Analysefunktionen -, wenn das Datenvolumen sehr groß wird und die Antworten in Echtzeit bereitgestellt werden müssen.

Dies liegt daran, dass vorhandene Grafiktechnologien Probleme haben, große Datenmengen in Echtzeit zu laden oder schnell eintreffende Daten aufzunehmen. Sie kämpfen auch darum, eine schnelle Überquerungsgeschwindigkeit zu erreichen. Während tiefere Analysen ein tieferes Durchlaufen des Diagramms erfordern, werden die heutigen Diagrammdatenbanken in der Regel nach zwei Durchläufen langsamer oder es tritt eine Zeitüberschreitung auf.

TigerGraph ist eine verteilte, native Graph-Computing-Plattform, die entwickelt wurde, um diese Einschränkungen zu umgehen. Die native Parallelgraph-Architektur von TigerGraph und die Deep-Link-Analyse in Echtzeit bieten folgende Vorteile:

  • Schnelleres Laden von Daten, um schnell Diagramme zu erstellen
  • Schnellere Ausführung von Algorithmen für parallele Graphen
  • Echtzeitfunktion für das Streaming von Updates und Einfügungen mithilfe von REST
  • Vereinheitlichung von Echtzeitanalysen mit umfangreicher Offline-Datenverarbeitung
  • Skalierbarkeit und Skalierbarkeit für verteilte Anwendungen

In den folgenden Abschnitten werden wir einen kurzen Blick auf die Funktionsweise der Grafikverarbeitung werfen, die Vorteile der Deep Link-Analyse untersuchen und die Haube von TigerGraph aufheben, um zu verstehen, wie Deep Link-Analysen in Echtzeit bereitgestellt werden können.  

Graph Traversal: Mehr Hopfen, mehr Einsicht

Warum Deep Link Analytics? Denn je mehr Links Sie in einem Diagramm durchlaufen (hüpfen) können, desto größer ist der Einblick, den Sie erhalten. Betrachten Sie einen hybriden Wissens- und Sozialgraphen. Jeder Knoten verbindet sich mit dem, was Sie wissen und wen Sie kennen. Direkte Links (ein Sprung) zeigen, was Sie wissen. Zwei Hopfen enthüllen alles, was Ihre Freunde und Bekannten wissen. Drei Hopfen? Sie sind auf dem Weg zu enthüllen, was jeder weiß.

Der Vorteil des Diagramms besteht darin, die Beziehungen zwischen den Datenentitäten im Datensatz zu kennen, die das Herzstück der Wissensentdeckung, -modellierung und -vorhersage bilden. Jeder Sprung kann zu einem exponentiellen Wachstum der Anzahl der Verbindungen und dementsprechend des Wissensstands führen. Aber darin liegt die technologische Hürde. Nur ein System, das Hops effizient und parallel ausführt, kann Deep-Link-Analysen (Multi-Hop) in Echtzeit liefern.

Ein einfaches Beispiel wie eine personalisierte Empfehlung in Echtzeit zeigt den Wert und die Leistungsfähigkeit des Verfolgens mehrerer Links in einem Diagramm:

"Kunden, denen das gefallen hat, was Ihnen gefallen hat, haben diese Artikel auch gekauft."

Dies führt zu einer Drei-Hop-Abfrage:

  1. Identifizieren Sie ausgehend von einer Person (Ihnen) Artikel, die Sie angesehen / gemocht / gekauft haben.
  2. Zweitens finden Sie andere Personen, die diese Artikel angesehen / gemocht / gekauft haben.
  3. Drittens identifizieren Sie zusätzliche Artikel, die von diesen Personen gekauft wurden.

Person → Produkt → (andere) Personen → (andere) Produkte

Mit der vorherigen Grafiktechnologie sind Sie in größeren Datensätzen auf nur zwei Sprünge beschränkt. TigerGraph erweitert die Abfrage problemlos auf drei oder mehr Hops, um wichtige Erkenntnisse aus sehr großen Datenmengen zu liefern.

TigerGraphs Echtzeit-Deep-Link-Analyse

TigerGraph unterstützt drei bis mehr als 10 Durchlaufsprünge in einem großen Diagramm sowie eine schnelle Durchlaufgeschwindigkeit des Diagramms und Datenaktualisierungen. Diese Kombination aus Geschwindigkeit, tiefen Durchquerungen und Skalierbarkeit bietet enorme Vorteile für mehrere Anwendungsfälle.

Ein Anwendungsfall ist die Betrugsprävention. Eine Möglichkeit, wie Unternehmen potenziellen Betrug erkennen können, besteht darin, Verbindungen zu bekannten fehlerhaften Transaktionen zu finden. Ausgehend von einer eingehenden Kreditkartentransaktion gibt es beispielsweise einen Weg zu fehlerhaften Transaktionen:

Neue Transaktion → Kreditkarte → Karteninhaber → (andere) Kreditkarten → (andere) schlechte Transaktionen

Als Diagrammabfrage verwendet dieses Muster vier Sprünge, um Verbindungen zu finden, die nur eine Karte von der eingehenden Transaktion entfernt sind. Die heutigen Betrüger versuchen, ihre Aktivitäten durch umständliche Verbindungen zwischen sich und bekannten schlechten Aktivitäten oder schlechten Schauspielern zu verschleiern. Um Betrug genau zu erkennen, müssen Sie mehrere mögliche Muster untersuchen und eine ganzheitlichere Ansicht erstellen.

Durch die Möglichkeit, mehrere versteckte Verbindungen aufzudecken, kann TigerGraph Kreditkartenbetrug minimieren. Dieses Durchlaufmuster gilt für viele andere Anwendungsfälle, bei denen Sie die Kreditkartentransaktion einfach durch ein Webklickereignis, einen Telefonanrufdatensatz oder eine Geldüberweisung ersetzen können.

TigerGraph Systemübersicht

Die Fähigkeit, tiefe Verbindungen zwischen Dateneinheiten in Echtzeit herzustellen, erfordert eine neue Technologie, die auf Skalierbarkeit und Leistung ausgelegt ist. Es gibt viele Entwurfsentscheidungen, die zusammenarbeiten, um die Durchbruchgeschwindigkeit und Skalierbarkeit von TigerGraph zu erreichen. Im Folgenden werden wir uns diese Konstruktionsmerkmale ansehen und diskutieren, wie sie zusammenarbeiten.

Ein nativer Graph

TigerGraph ist von Grund auf eine reine Grafikdatenbank. Der Datenspeicher enthält Knoten, Links und deren Attribute, Punkt. Einige Graph-Datenbankprodukte auf dem Markt sind wirklich Wrapper, die auf einem allgemeineren NoSQL-Datenspeicher basieren. Diese Strategie für virtuelle Graphen hat eine doppelte Strafe, wenn es um Leistung geht. Erstens führt die Übersetzung vom virtuellen Diagrammbetrieb zum physischen Speicherbetrieb zu zusätzlicher Arbeit. Zweitens ist die zugrunde liegende Struktur nicht für Diagrammoperationen optimiert.

Kompakter Speicher mit schnellem Zugriff

Wir beschreiben TigerGraph nicht als In-Memory-Datenbank, da das Speichern von Daten eine Präferenz, aber keine Voraussetzung ist. Benutzer können Parameter festlegen, die angeben, wie viel des verfügbaren Speichers zum Halten des Diagramms verwendet werden darf. Wenn das vollständige Diagramm nicht in den Speicher passt, wird der Überschuss auf der Festplatte gespeichert. Die beste Leistung wird natürlich erzielt, wenn das vollständige Diagramm in den Speicher passt. 

Datenwerte werden in codierten Formaten gespeichert, die die Daten effektiv komprimieren. Der Komprimierungsfaktor variiert mit der Diagrammstruktur und den Daten, typische Komprimierungsfaktoren liegen jedoch zwischen 2x und 10x. Die Komprimierung hat zwei Vorteile: Erstens kann eine größere Menge von Diagrammdaten in den Speicher und in den Cache passen. Eine solche Komprimierung reduziert nicht nur den Speicherbedarf, sondern auch CPU-Cache-Fehler, wodurch die Gesamtleistung der Abfrage beschleunigt wird. Zweitens werden für Benutzer mit sehr großen Grafiken die Hardwarekosten reduziert. Wenn der Komprimierungsfaktor beispielsweise 4x beträgt, kann eine Organisation möglicherweise alle Daten auf einen Computer anstatt auf vier Computer übertragen.

Die Dekomprimierung / Dekodierung ist für Endbenutzer sehr schnell und transparent, sodass die Vorteile der Komprimierung die geringe Zeitverzögerung für die Komprimierung / Dekomprimierung überwiegen. Im Allgemeinen wird die Dekomprimierung nur zur Anzeige der Daten benötigt. Wenn Werte intern verwendet werden, bleiben sie häufig codiert und komprimiert.

Hash-Indizes werden verwendet, um auf Knoten und Links zu verweisen. In Big-O-Begriffen beträgt unsere durchschnittliche Zugriffszeit O (1) und unsere durchschnittliche Indexaktualisierungszeit ebenfalls O (1). Übersetzung: Der Zugriff auf einen bestimmten Knoten oder Link im Diagramm ist sehr schnell und bleibt auch dann schnell, wenn das Diagramm größer wird. Darüber hinaus ist es sehr schnell, den Index beizubehalten, wenn neue Knoten und Links zum Diagramm hinzugefügt werden.

Parallelität und gemeinsame Werte

Wenn Geschwindigkeit Ihr Ziel ist, haben Sie zwei grundlegende Routen: Führen Sie jede Aufgabe schneller aus oder erledigen Sie mehrere Aufgaben gleichzeitig. Der letztere Weg ist Parallelität. TigerGraph ist bestrebt, jede Aufgabe schnell zu erledigen, zeichnet sich jedoch auch durch Parallelität aus. Die Diagramm-Engine verwendet mehrere Ausführungsthreads, um ein Diagramm zu durchlaufen.

Die Art der Diagrammabfragen besteht darin, den Links zu folgen. Beginnen Sie an einem oder mehreren Knoten. Sehen Sie sich die verfügbaren Verbindungen von diesen Knoten an und folgen Sie diesen Verbindungen zu einigen oder allen benachbarten Knoten. Wir sagen, Sie haben gerade einen "Sprung" "durchquert". Wiederholen Sie diesen Vorgang, um zu den Nachbarn des ursprünglichen Knotens zu gelangen, und Sie haben zwei Sprünge durchlaufen. Da jeder Knoten viele Verbindungen haben kann, umfasst diese Zwei-Sprung-Durchquerung viele Pfade, um von den Startknoten zu den Zielknoten zu gelangen. Diagramme eignen sich natürlich für die parallele Ausführung mit mehreren Threads.

Eine Abfrage sollte natürlich mehr als nur einen Knoten besuchen. In einem einfachen Fall können wir die Anzahl der eindeutigen Nachbarn mit zwei Hops zählen oder eine Liste ihrer IDs erstellen. Wie berechnet man eine Gesamtzahl, wenn man mehrere parallele Zähler hat? Der Prozess ähnelt dem, was Sie in der realen Welt tun würden: Bitten Sie jeden Zähler, seinen Anteil an der Welt zu leisten, und kombinieren Sie am Ende die Ergebnisse.

Denken Sie daran, dass in der Abfrage nach der Anzahl der eindeutigen Knoten gefragt wurde . Es besteht die Möglichkeit, dass derselbe Knoten von zwei verschiedenen Zählern gezählt wurde, da mehr als ein Pfad vorhanden ist, um dieses Ziel zu erreichen. Dieses Problem kann auch bei Single-Threaded-Designs auftreten. Die Standardlösung besteht darin, jedem Knoten eine temporäre Variable zuzuweisen. Die Variablen werden auf False initialisiert. Wenn ein Zähler einen Knoten besucht, wird die Variable dieses Knotens auf True gesetzt, damit andere Zähler wissen, dass sie ihn nicht zählen sollen.

In C ++ geschriebene Speicher- und Verarbeitungs-Engines

Sprachauswahl wirkt sich auch auf die Leistung aus. Die Graph Storage Engine und die Processing Engine von TigerGraph sind in C ++ implementiert. In der Familie der allgemeinen prozeduralen Sprachen gelten C und C ++ im Vergleich zu anderen Sprachen wie Java als untergeordnete Ebenen. Dies bedeutet, dass Programmierer, die verstehen, wie die Computerhardware ihre Softwarebefehle ausführt, fundierte Entscheidungen treffen können, um die Leistung zu optimieren. TigerGraph wurde sorgfältig entwickelt, um Speicher effizient zu nutzen und nicht verwendeten Speicher freizugeben. Eine sorgfältige Speicherverwaltung trägt dazu bei, dass TigerGraph viele Links in Bezug auf Tiefe und Breite in einer einzigen Abfrage durchlaufen kann.

Viele andere Graphendatenbankprodukte sind in Java geschrieben, das Vor- und Nachteile hat. Java-Programme werden in einer Java Virtual Machine (JVM) ausgeführt. Die JVM kümmert sich um die Speicherverwaltung und die Speicherbereinigung (wodurch nicht mehr benötigter Speicher freigegeben wird). Dies ist zwar praktisch, für den Programmierer jedoch schwierig, die Speichernutzung zu optimieren oder zu steuern, wann nicht verwendeter Speicher verfügbar wird.

Abfragesprache für GSQL-Diagramme

TigerGraph hat auch eine eigene Grafikabfrage- und Aktualisierungssprache, GSQL. Obwohl es viele nette Details zu GSQL gibt, werde ich mich auf zwei Aspekte konzentrieren, die für die Unterstützung einer effizienten parallelen Berechnung von entscheidender Bedeutung sind: die ACCUM-Klausel und die Akkumulatorvariablen.

Der Kern der meisten GSQL-Abfragen ist die SELECT-Anweisung, die eng an die SELECT-Anweisung in SQL angelehnt ist. Die Klauseln SELECT, FROM und WHERE werden verwendet, um eine Reihe von Links oder Knoten auszuwählen und zu filtern. Nach dieser Auswahl kann die optionale ACCUM-Klausel verwendet werden, um eine Reihe von Aktionen zu definieren, die von jeder Verbindung oder jedem benachbarten Knoten ausgeführt werden sollen. Ich sage eher "Durchführen von" als "Durchführen von", da konzeptionell jedes Diagrammobjekt eine unabhängige Recheneinheit ist. Die Graphstruktur wirkt wie ein massiv paralleles Rechennetz. Das Diagramm ist nicht nur Ihr Datenspeicher. Es ist auch Ihre Abfrage- oder Analyse-Engine.

Eine ACCUM-Klausel kann viele verschiedene Aktionen oder Anweisungen enthalten. Diese Anweisungen können Werte aus den Diagrammobjekten lesen, lokale Berechnungen durchführen, bedingte Anweisungen anwenden und Aktualisierungen des Diagramms planen. (Aktualisierungen finden erst statt, wenn die Abfrage beendet ist.)

Um diese verteilten In-Query-Berechnungen zu unterstützen, stellt die GSQL-Sprache Akkumulatorvariablen bereit. Akkumulatoren gibt es in vielen Varianten, aber sie sind alle temporär (nur während der Ausführung der Abfrage vorhanden), gemeinsam genutzt (für jeden der Ausführungsthreads verfügbar) und schließen sich gegenseitig aus (jeweils nur ein Thread kann sie aktualisieren). Zum Beispiel würde ein einfacher Summenakkumulator verwendet, um die Zählung aller oben erwähnten Nachbarn der Nachbarn durchzuführen. Ein festgelegter Akkumulator würde verwendet, um die IDs aller Nachbarn dieser Nachbarn aufzuzeichnen. Akkus sind in zwei Bereichen verfügbar: global und pro Knoten. Im vorherigen Abfragebeispiel haben wir die Notwendigkeit erwähnt, jeden Knoten als besucht zu markieren oder nicht. Hier würden Akkumulatoren pro Knoten verwendet.

MPP-Rechenmodell

Um das oben Gesagte noch einmal zu wiederholen, ist das TigerGraph-Diagramm sowohl ein Speichermodell als auch ein Rechenmodell. Jeder Knoten und jede Verbindung kann einer Rechenfunktion zugeordnet werden. Daher fungiert TigerGraph gleichzeitig als parallele Speicher- und Recheneinheit. Dies wäre mit einem generischen NoSQL-Datenspeicher oder ohne die Verwendung von Akkumulatoren nicht möglich.

Automatische Partitionierung

In der heutigen Big-Data-Welt benötigen Unternehmen ihre Datenbanklösungen, um auf mehrere Computer skaliert werden zu können, da ihre Daten möglicherweise zu groß werden, um wirtschaftlich auf einem einzigen Server gespeichert zu werden. TigerGraph wurde entwickelt, um die Diagrammdaten automatisch auf einen Servercluster zu verteilen und dennoch eine schnelle Leistung zu erzielen. Der Hash-Index wird verwendet, um nicht nur den Speicherort innerhalb des Servers zu bestimmen, sondern auch den Server. Alle Links, die von einem bestimmten Knoten aus eine Verbindung herstellen, werden auf demselben Server gespeichert. Die Theorie der Informatik sagt uns, dass das Finden der besten Partitionierung von Graphen insgesamt, wenn wir sogar „am besten“ definieren könnten, normalerweise sehr langsam ist, also versuchen wir es nicht. Unser Standardmodus ist die Verwendung von zufälligem Hashing, was in den meisten Fällen sehr gut funktioniert. Das TigerGraph-System unterstützt auch die benutzergesteuerte Partitionierung für Benutzer, die ein bestimmtes Partitionierungsschema berücksichtigen.

Verteilter Berechnungsmodus