Quoi de neuf dans RedisGraph 1.2.0

Quoi de neuf dans RedisGraph 1.2.0

La semaine dernière, nous avons publié RedisGraph 1.2.0. Si vous avez utilisé RedisGraph ou si vous envisagez d’essayer le module, c’est le bon moment pour voir ce que nous avons fait alors que nous continuons à améliorer ses capacités de traitement de graphes. Passons en revue certains des ajouts les plus notables de la nouvelle version :

image6

Plusieurs arêtes du même type

Jusqu’à cette version, connecter le nœud A au nœud B via une arête de type R, puis former une autre connexion du même type entre les deux n’était pas possible. car ce dernier écraserait le premier, en raison de la manière dont les connexions étaient représentées dans RedisGraph.

Pour chaque type de relation, par exemple `friend`, `works_at` ou `owns`, RedisGraph maintient une matrice de mappage M, dans laquelle M[I,J] = EdgeID où I et J sont respectivement les ID de nœud source et de destination. Former la première connexion de type R entre A et B aurait M[I,J] défini sur X, et l’introduction d’un deuxième bord de type R entre les deux écraserait M[I,J] avec Y

image3

Plusieurs arêtes du même type

Avec la version 1.2.0, RedisGraph permet désormais plusieurs arêtes du même type. Notre matrice de mappage M peut contenir un pointeur vers un tableau d’ID d’arête, M[I,J] = [ID0, ID1, … IDn]spécifiant chaque arête de type R reliant I à J.

Pour éviter une fragmentation élevée de la mémoire, considérons un graphe avec 500 millions d’arêtes dont aucune ne partage les nœuds source ou destination, c’est-à-dire qu’il n’y a pas d’arêtes multiples du même type entre deux nœuds. Une approche naïve aurait alloué des tableaux de 500M de longueur 1, augmentant considérablement notre consommation de mémoire. Pour faire face à cela, notre type d’entrée de matrice de mappage est resté le même (UINT64). Commencer avec un graphique vide – M[I,J] est vide – lorsque le premier bord E est formé, reliant I à J, M[I,J] = ID(E) est une constante simple et aucune mémoire supplémentaire n’est allouée. A un moment donné, I est à nouveau connecté à J par une arête X du même type que E, M[I,J] = [ID(E), ID(X)]un tableau est alloué et un pointeur est placé dans M[I,J].

image1

M[1,3] ID de bord, M[3,1] pointeur de tableau

Recherche de nœuds en temps constant

Chaque fois qu’une entité graphique (nœud, bord) est créée, un identifiant interne unique lui est attribué. Cet ID est immuable tout au long de la vie de l’entité, et vous pouvez récupérer un ID d’entité en utilisant le IDENTIFIANT fonction: CORRESPONDANCE (N) RETOUR N, ID(N) LIMITE 10. De même, trouver un nœud par son ID : “MATCH (N) WHERE ID(N) = 9 RETURN N » utilisé pour effectuer une analyse complète, en inspectant chaque nœud du graphique.

Notre dernière version de RedisGraph introduit une optimisation qui remplace ces opérations d’analyse complète et de filtrage par une seule opération de “recherche de nœud par identifiant”, qui s’exécute en temps constant.

image5

Balayage complet et filtre O(N),

image4

Recherche de nœud optimisée O(1)

Transposer une fois

Dans RedisGraph, les parcours sont effectués par multiplication matricielle. Par exemple, considérons le modèle de recherche : (UN)-[X]->(B)-[Y]->(c). Pour trouver tous les nœuds source (A) qui sont connectés aux nœuds de destination (C), nous multiplions simplement la matrice [X] par matrice [Y], X*Y=Zet les lignes et les colonnes de Z représentent respectivement A et C.

Si nous ne sommes intéressés que par une poignée de nœuds C, nous voudrons éviter d’effectuer X*Y, car il peut s’agir de très grandes matrices. En tant que tel, nous allons ajouter une petite matrice de filtres F, (F*X)*Y. En multipliant F*X Premièrement, nous réduisons toutes les dimensions calculées par la matrice intermédiaire, ce qui réduit considérablement le temps de calcul.

En fonction du résultat de F*X*Y, nous pourrions nous retrouver à calculer une matrice de filtre F différente et à réévaluer cette expression pour obtenir des nœuds C supplémentaires. Ce processus peut se répéter plusieurs fois avant que nous ayons suffisamment de données. Maintenant, chaque fois qu’un motif de recherche contient des bords de gauche à droite et de droite à gauche : (UN)-[X]->(B)<-[Y]-(C), il va falloir transposer Y, (F*X)*Transposer(Y) = Z.

image2

Filtre * X * Transposition(Y)

Les versions précédentes de RedisGraph transposaient Y à chaque évaluation de cette expression, ce qui était coûteux. Désormais, à partir de la version 1.2.0, nous ne transposerons qu’une seule fois lors de la première évaluation. Bien que cela entraîne une consommation de mémoire plus élevée par requête, le gain de latence en vaut vraiment la peine.

Global RedisGraph 1.2.0 (notes de version) contient à la fois des fonctionnalités en retard et des optimisations intéressantes, Essaie Dites-nous ce que vous en pensez!

Development Source

Related Posts

RLEC 4.2.1 apporte des contrôles granulaires à la haute disponibilité et aux performances

RLEC 4.2.1 apporte des contrôles granulaires à la haute disponibilité et aux performances

Comment HolidayMe utilise Redis Enterprise comme base de données principale

Comment HolidayMe utilise Redis Enterprise comme base de données principale

Annonce de RedisGears 1.0 : un moteur sans serveur pour Redis

Annonce de RedisGears 1.0 : un moteur sans serveur pour Redis

Clés Redis dans la RAM |  Redis

Clés Redis dans la RAM | Redis

No Comment

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *