TigerGraph: la base de données de graphes parallèles expliquée

Victor Lee est directeur de la gestion des produits chez TigerGraph.

Les bases de données de graphes excellent pour répondre à des questions complexes sur les relations dans de grands ensembles de données. Mais ils se heurtent à un mur - en termes de performances et de capacités d'analyse - lorsque le volume de données devient très important et que les réponses doivent être fournies en temps réel.

En effet, les technologies graphiques existantes ont du mal à charger de grandes quantités de données ou à ingérer des données à arrivée rapide en temps réel. Ils ont également du mal à offrir une vitesse de déplacement rapide. Alors que des analyses plus approfondies nécessitent une traversée plus profonde du graphique, les bases de données de graphiques actuelles ralentissent ou expirent généralement après deux sauts de parcours.

TigerGraph est une plate-forme de calcul graphique native distribuée conçue pour contourner ces limitations. L'architecture de graphes parallèles native de TigerGraph et l'analyse des liens profonds en temps réel visent à offrir les avantages suivants:

  • Chargement plus rapide des données pour créer rapidement des graphiques
  • Exécution plus rapide des algorithmes de graphes parallèles
  • Capacité en temps réel pour diffuser les mises à jour et les insertions à l'aide de REST
  • Capacité à unifier les analyses en temps réel avec un traitement de données hors ligne à grande échelle
  • Capacité à évoluer et à évoluer pour les applications distribuées

Dans les sections qui suivent, nous examinerons brièvement le fonctionnement du traitement des graphiques, explorerons les avantages de l'analyse de liens profonds et soulèverons le capot de TigerGraph pour comprendre comment il est capable de fournir des analyses de liens profonds en temps réel.  

Traversée du graphique: plus de sauts, plus d'informations

Pourquoi l'analyse des liens profonds? Parce que plus vous pouvez traverser (sauter) de liens dans un graphique, plus vous obtiendrez d'informations. Considérez un graphique hybride des connaissances et des réseaux sociaux. Chaque nœud se connecte à ce que vous savez et à qui vous connaissez. Les liens directs (un saut) révèlent ce que vous savez. Deux sauts révèlent tout ce que vos amis et connaissances savent. Trois sauts? Vous êtes sur le point de révéler ce que tout le monde sait.

L'avantage du graphe est de connaître les relations entre les entités de données dans l'ensemble de données, qui est au cœur de la découverte, de la modélisation et de la prédiction des connaissances. Chaque saut peut conduire à une croissance exponentielle du nombre de connexions et, par conséquent, de la quantité de connaissances. Mais c'est là que réside l'obstacle technologique. Seul un système qui effectue des sauts efficacement et en parallèle peut fournir des analyses de liens profonds (multi-sauts) en temps réel.

Un exemple simple comme la recommandation personnalisée en temps réel révèle la valeur et la puissance de suivre plusieurs liens dans un graphique:

"Les clients qui ont aimé ce que vous avez aimé ont également acheté ces articles."

Cela se traduit par une requête à trois sauts:

  1. À partir d'une personne (vous), identifiez les articles que vous avez consultés / aimés / achetés.
  2. Deuxièmement, trouvez d'autres personnes qui ont vu / aimé / acheté ces articles.
  3. Troisièmement, identifiez les articles supplémentaires achetés par ces personnes.

Personne → produit → (autres) personnes → (autres) produits

En utilisant la technologie graphique précédente, vous seriez limité à seulement deux sauts dans des ensembles de données plus volumineux. TigerGraph étend facilement la requête à trois sauts ou plus pour fournir des informations clés à partir de très grands ensembles de données.

Analyse des liens profonds en temps réel de TigerGraph

TigerGraph prend en charge trois à plus de 10 sauts de traversée sur un grand graphique, ainsi que la vitesse de traversée rapide du graphique et les mises à jour des données. Cette combinaison de vitesse, de traversées profondes et d'évolutivité offre d'énormes avantages pour plusieurs cas d'utilisation.

Un cas d'utilisation est la prévention de la fraude. Une façon pour les entreprises de détecter les fraudes potentielles est de trouver des connexions avec des transactions erronées connues. Par exemple, à partir d'une transaction entrante par carte de crédit, voici un chemin vers les mauvaises transactions:

Nouvelle transaction → carte de crédit → titulaire de la carte → (autres) cartes de crédit → (autres) mauvaises transactions

En tant que requête graphique, ce modèle utilise quatre sauts pour rechercher des connexions à une seule carte de la transaction entrante. Les fraudeurs d'aujourd'hui tentent de dissimuler leur activité par des connexions détournées entre eux et de mauvaises activités connues ou de mauvais acteurs. Pour détecter avec précision la fraude, vous devez explorer plusieurs modèles possibles et créer une vue plus holistique.

Avec la possibilité de découvrir plusieurs connexions cachées, TigerGraph est capable de minimiser la fraude par carte de crédit. Ce modèle de parcours s'applique à de nombreux autres cas d'utilisation, où vous pouvez simplement remplacer la transaction par carte de crédit par un événement de clic Web, un enregistrement d'appel téléphonique ou un transfert d'argent.

Présentation du système TigerGraph

La capacité à établir des connexions profondes entre les entités de données en temps réel nécessite une nouvelle technologie conçue pour évoluer et être performante. Il existe de nombreuses décisions de conception qui fonctionnent en coopération pour atteindre la vitesse et l'évolutivité révolutionnaires de TigerGraph. Ci-dessous, nous examinerons ces caractéristiques de conception et discuterons de la manière dont elles fonctionnent ensemble.

Un graphe natif

TigerGraph est une base de données de graphiques pure, à partir de zéro. Son magasin de données contient des nœuds, des liens et leurs attributs, période. Certains produits de base de données de graphiques sur le marché sont en fait des wrappers construits sur un magasin de données NoSQL plus générique. Cette stratégie de graphe virtuel a une double pénalité en termes de performances. Premièrement, la conversion de l'opération de graphe virtuel en opération de stockage physique introduit un travail supplémentaire. Deuxièmement, la structure sous-jacente n'est pas optimisée pour les opérations graphiques.

Stockage compact avec accès rapide

Nous ne décrivons pas TigerGraph comme une base de données en mémoire, car avoir des données en mémoire est une préférence mais pas une exigence. Les utilisateurs peuvent définir des paramètres qui spécifient la quantité de mémoire disponible pouvant être utilisée pour conserver le graphique. Si le graphique complet ne tient pas dans la mémoire, alors l'excédent est stocké sur le disque. Les meilleures performances sont obtenues lorsque le graphique complet tient en mémoire, bien sûr. 

Les valeurs de données sont stockées dans des formats codés qui compressent efficacement les données. Le facteur de compression varie avec la structure du graphe et les données, mais les facteurs de compression typiques sont compris entre 2x et 10x. La compression présente deux avantages: Premièrement, une plus grande quantité de données graphiques peut tenir en mémoire et en cache. Une telle compression réduit non seulement l'encombrement de la mémoire, mais également les erreurs de cache du processeur, ce qui accélère les performances globales des requêtes. Deuxièmement, pour les utilisateurs avec de très grands graphiques, les coûts de matériel sont réduits. Par exemple, si le facteur de compression est 4x, une organisation peut être en mesure de ranger toutes ses données dans une machine au lieu de quatre.

La décompression / décodage est très rapide et transparente pour les utilisateurs finaux, de sorte que les avantages de la compression l'emportent sur le petit délai de compression / décompression. En général, la décompression n'est nécessaire que pour afficher les données. Lorsque les valeurs sont utilisées en interne, elles peuvent souvent rester codées et compressées.

Les indices de hachage sont utilisés pour référencer les nœuds et les liens. En termes Big-O, notre temps d'accès moyen est O (1) et notre temps moyen de mise à jour de l'indice est également O (1). Traduction: l'accès à un nœud ou un lien particulier dans le graphique est très rapide et reste rapide même lorsque la taille du graphique augmente. De plus, le maintien de l'index au fur et à mesure que de nouveaux nœuds et liens sont ajoutés au graphique est également très rapide.

Parallélisme et valeurs partagées

Lorsque la vitesse est votre objectif, vous avez deux itinéraires de base: effectuez chaque tâche plus rapidement ou effectuez plusieurs tâches à la fois. La dernière avenue est le parallélisme. Tout en s'efforçant d'accomplir chaque tâche rapidement, TigerGraph excelle également dans le parallélisme. Son moteur graphique utilise plusieurs threads d'exécution pour parcourir un graphique.

La nature des requêtes graphiques est de «suivre les liens». Commencez par un ou plusieurs nœuds. Regardez les connexions disponibles à partir de ces nœuds et suivez ces connexions vers certains ou tous les nœuds voisins. Nous disons que vous venez de «traverser» un «saut». Répétez ce processus pour aller aux voisins des voisins du nœud d'origine, et vous avez traversé deux sauts. Étant donné que chaque nœud peut avoir de nombreuses connexions, cette traversée à deux sauts implique de nombreux chemins pour aller des nœuds de départ aux nœuds de destination. Les graphiques conviennent parfaitement à une exécution parallèle et multithread.

Une requête doit bien sûr faire plus que simplement visiter un nœud. Dans un cas simple, nous pouvons compter le nombre de voisins uniques à deux sauts ou faire une liste de leurs ID. Comment calculer un nombre total, lorsque vous avez plusieurs compteurs parallèles? Le processus est similaire à ce que vous feriez dans le monde réel: demandez à chaque compteur de faire sa part du monde, puis combinez leurs résultats à la fin.

Rappelez-vous que la requête demandait le nombre de nœuds uniques . Il est possible que le même nœud ait été compté par deux compteurs différents, car il y a plus d'un chemin pour atteindre cette destination. Ce problème peut se produire même avec une conception à un seul thread. La solution standard consiste à affecter une variable temporaire à chaque nœud. Les variables sont initialisées à False. Lorsqu'un compteur visite un nœud, la variable de ce nœud est définie sur True, afin que les autres compteurs sachent ne pas le compter.

Moteurs de stockage et de traitement écrits en C ++

Les choix de langue affectent également les performances. Le moteur de stockage de graphes et le moteur de traitement de TigerGraph sont implémentés en C ++. Dans la famille des langages procéduraux à usage général, C et C ++ sont considérés comme de niveau inférieur par rapport à d'autres langages comme Java. Cela signifie que les programmeurs qui comprennent comment le matériel informatique exécute leurs commandes logicielles peuvent faire des choix éclairés pour optimiser les performances. TigerGraph a été soigneusement conçu pour utiliser efficacement la mémoire et libérer la mémoire inutilisée. Une gestion minutieuse de la mémoire contribue à la capacité de TigerGraph à parcourir de nombreux liens, à la fois en termes de profondeur et de largeur, en une seule requête.

De nombreux autres produits de base de données de graphes sont écrits en Java, ce qui présente des avantages et des inconvénients. Les programmes Java s'exécutent dans une machine virtuelle Java (JVM). La JVM s'occupe de la gestion de la mémoire et du garbage collection (libérant de la mémoire qui n'est plus nécessaire). Bien que cela soit pratique, il est difficile pour le programmeur d'optimiser l'utilisation de la mémoire ou de contrôler le moment où la mémoire inutilisée devient disponible.

Langage de requête graphique GSQL

TigerGraph a également son propre langage d'interrogation et de mise à jour de graphes, GSQL. Bien qu'il existe de nombreux détails intéressants sur GSQL, je me concentrerai sur deux aspects essentiels pour prendre en charge un calcul parallèle efficace: la clause ACCUM et les variables d'accumulateur.

Le cœur de la plupart des requêtes GSQL est l'instruction SELECT, calquée sur le modèle de l'instruction SELECT dans SQL. Les clauses SELECT, FROM et WHERE sont utilisées pour sélectionner et filtrer un ensemble de liens ou de nœuds. Après cette sélection, la clause optionnelle ACCUM peut être utilisée pour définir un ensemble d'actions à effectuer par chaque lien ou nœud adjacent. Je dis «exécuter par» plutôt que «exécuter sur» car, conceptuellement, chaque objet graphique est une unité de calcul indépendante. La structure du graphe agit comme un maillage de calcul massivement parallèle. Le graphique n'est pas seulement votre stockage de données; il s'agit également de votre moteur de recherche ou d'analyse.

Une clause ACCUM peut contenir de nombreuses actions ou instructions différentes. Ces instructions peuvent lire les valeurs des objets graphiques, effectuer des calculs locaux, appliquer des instructions conditionnelles et planifier des mises à jour du graphique. (Les mises à jour n'ont pas lieu tant que la requête n'est pas terminée.)

Pour prendre en charge ces calculs distribués en requête, le langage GSQL fournit des variables d'accumulateur. Les accumulateurs sont disponibles dans de nombreuses versions, mais ils sont tous temporaires (existant uniquement lors de l'exécution de la requête), partagés (disponibles pour l'un des threads d'exécution) et mutuellement exclusifs (un seul thread peut le mettre à jour à la fois). Par exemple, un simple accumulateur de somme serait utilisé pour effectuer le comptage de tous les voisins des voisins mentionnés ci-dessus. Un accumulateur d'ensemble serait utilisé pour enregistrer les ID de tous les voisins de ces voisins. Les accumulateurs sont disponibles dans deux portées: global et par nœud. Dans l'exemple de requête précédent, nous avons mentionné la nécessité de marquer chaque nœud comme visité ou non. Ici, des accumulateurs par nœud seraient utilisés.

Modèle de calcul MPP

Pour réitérer ce que nous avons révélé ci-dessus, le graphe TigerGraph est à la fois un modèle de stockage et un modèle de calcul. Chaque nœud et lien peut être associé à une fonction de calcul. Par conséquent, TigerGraph agit comme une unité parallèle de stockage et de calcul simultanément. Ce serait irréalisable en utilisant un magasin de données NoSQL générique ou sans l'utilisation d'accumulateurs.

Partitionnement automatique

Dans le monde du Big Data d'aujourd'hui, les entreprises ont besoin de leurs solutions de base de données pour pouvoir évoluer vers plusieurs machines, car leurs données peuvent devenir trop volumineuses pour être stockées de manière économique sur un seul serveur. TigerGraph est conçu pour partitionner automatiquement les données graphiques sur un cluster de serveurs, tout en fonctionnant rapidement. L'index de hachage est utilisé pour déterminer non seulement l'emplacement des données au sein du serveur, mais également quel serveur. Tous les liens qui se connectent à partir d'un nœud donné sont stockés sur le même serveur. La théorie informatique nous dit que trouver le meilleur partitionnement de graphe global, si nous pouvions même définir «meilleur», est généralement très lent, donc nous n'essayons pas. Notre mode par défaut est d'utiliser le hachage aléatoire, qui fonctionne très bien dans la plupart des cas. Le système TigerGraph prend également en charge le partitionnement dirigé par l'utilisateur pour les utilisateurs qui ont un schéma de partitionnement particulier à l'esprit.

Mode de calcul distribué