Performance des traversées dans Neo4j

Actualité ekino -

Les écueils du benchmark

Article paru le :
Performance des traversées dans Neo4j
Article paru le :

This article is available in English under “Performance of traversals in Neo4j”.

Le projet sur lequel je travaille actuellement (transparence de la chaîne d’approvisionnement, traçabilité alimentaire par une approche orientée graphes ou encore GraphConnect – Tracing the World Food from Farm to Fork) est développé autour de la base de graphes Neo4j (N.B. : ekino est partenaire de Neo Technology), et nous avons eu l’occasion il y a quelques temps de migrer l’application de la version 2.1 vers Neo4j 2.3. L’application effectue diverses traversées de graphes sur des centaines de milliers de nœuds et de relations, dans le cadre d’une application web et non pour faire de l’analyse hors ligne. La performance de ces traversées est donc essentielle.

Ça tombe bien, les releases 2.2 et 2.3 de Neo4j étaient axées sur la performance (notamment du côté de Cypher, le langage de requêtage de Neo4j), nous espérions donc un gain direct. Voyons ce qu’il en est, et analysons les raisons de l’évolution, dans un sens ou dans l’autre.

Mauvaise direction ?

Surprise ! La mise à jour montre des temps de réponse nettement plus importants dans nos tests de performance, jusqu’à un facteur 2. Je réalise une première comparaison avec un profiler qui me permet de constater une explosion du coût des opérations de l’API core de Neo4j manipulant les nœuds et relations, ainsi qu’une augmentation de la mémoire consommée par une requête (garbage : les objets créés lors de la requête et récupérables à la fin de celle-ci).

Je décide alors de créer un exemple simple permettant de reproduire le problème et de le pousser sur GitHub, afin d’avoir une base de discussion sur SlackHQ Neo4j.

Le démonstrateur

Il se présente sous la forme d’une unmanaged extension pour Neo4j, qui crée ses propres données de test et offre un service HTTP effectuant une traversée similaire à ce que nous faisons dans l’application, en utilisant diverses API core : Node::hasLabel, Node::getProperty, Node::getRelationships.

Les données sont organisées sous la forme d’un arbre, partant d’un nœud racine de type A, connecté à des nœuds de type B (par une relation HAS_B), connectés à des nœuds de type A (par une relation HAS_A), etc. sur 10 niveaux de A/B et avec 4 enfants attachés à chaque parent (soit 1 398 101 nœuds et 1 398 100 relations). Chaque nœud possède une propriété booléenne assignée avec une valeur aléatoire.

Portion du graphe de démonstration

Le traverseur suit les nœuds en mode breadth-first, et est configuré avec un PathExpander utilisant le libellé du nœud courant pour déterminer le type de relation à suivre et un Evaluator utilisant lui aussi le libellé du nœud pour ne sélectionner que les B, et comptant ceux dont la propriété vaut true. Il part du nœud central (identifié avec le libellé Root) pour faire sa traversée. Le service renvoie au final le compteur dans la réponse HTTP, afin de ne pas subir de Dead Code Elimination de la part du compilateur Just In Time (JIT) de la JVM.

Le volume de données est suffisant pour que le temps de traversée soit mesurable en secondes, rendant négligeable tout bruit lié à la mesure elle-même.

Comparaison de Neo4j 2.2 contre 2.3

L’extension est compilée puis déployée dans deux instances Neo4j 2.2 (car similaire à 2.1) et 2.3, avec un cache disque similaire dbms.pagecache.memory=500m (le jeu de données généré prend environ 400 Mo sur disque) et des paramètres de heap de la JVM valant respectivement -Xms2g -Xmx4g et -Xms512m -Xmx512m (Neo4j 2.3 ayant supprimé le cache des objets en mémoire, il nécessite moins de mémoire).

Le test consiste à mesurer les temps de réponse de 100 requêtes de traversée effectuées de manière séquentielle et mono-thread, après avoir « pré-chauffé » la JVM avec 100 requêtes non mesurées, pour permettre la compilation JIT et l’atteinte d’un régime stable.

Il est exécuté sur mon Mac Book/ Pro 15 pouces mi-2014 équipé d’un processeur Intel Core i7 2,2 GHz avec 4 cœurs, et de 16 Go de RAM, tournant sous OS X 10.11.4 (El Capitan).

Sans aller jusqu’au facteur 2 précédemment observé, les résultats montrent bien des temps de réponse dégradés de plus de 50 %, j’ai donc un exemple à partager.

Comparaison des temps de réponse en millisecondes entre 2.2 et 2.3
Version Neo4j Enterprise 2.2.7 Neo4j Enterprise 2.3.2
Moyenne 1914 3109
50 % (médiane) 1890 3088
90 % 2169 3358
95 % 2254 3470
Maximum 2322 3707
Histogramme des temps de réponse 2.2 et 2.3, plus élevés pour 2.3

Les temps en 2.3 sont plus élevés qu’en 2.2 avec notre benchmark, dans tous les quantiles observés

La discussion

S’ensuit alors une discussion par Slack et GitHub interposés, notamment avec Michael Hunger (@mesirii, Developer Relations chez Neo Technology), qui obtient des résultats différents dans un fork de mon projet où il a créé un test unitaire utilisant mon code avec une base Neo4j embarquée : les résultats de ses comparatifs montrent que la 2.3 est plus rapide que la 2.2.

Il y a en réalité plusieurs différences entre les comparatifs à ce stade :

  • ses résultats montrent une dépendance à la taille de la heap que je n’avais pas observée initialement ;
  • ses traversées sont parallélisées au lieu d’être séquentielles, nous ne mesurons donc pas la même charge ;
  • en utilisant une base embarquée, il utilise Neo4j Community Edition alors que j’utilise Neo4j Enterprise Edition, qui intègre notamment un High-Performance (Object) Cache jusqu’en 2.2 ;
  • enfin, il a changé le mode de traversée de breadth-first en depth-first.

Je modifie légèrement son code pour repasser en exécution séquentielle et donner plus de temps au pré-chauffage et au JIT, mais j’obtiens néanmoins des résultats du même ordre.

Nous discutons du dernier point sur Slack : le mode depth-first consomme moins de mémoire puisqu’il s’agit d’une simple récursion, alors que le mode breadth-first nécessite de maintenir en mémoire l’état de toutes les branches visitées. Comme nous avons a priori besoin du mode breadth-first pour diverses optimisations dans l’application (la vraie, pas le démonstrateur), c’est le mode que j’avais retenu.

Pour avoir une meilleure vision, j’ajoute néanmoins le support du mode depth-first dans le démonstrateur (à travers un query parameter), et je refais un tir de test en utilisant les deux modes et diverses tailles de heap.

Et là, on commence à avoir des résultats intéressants qui émergent, et qui vont me permettre d’avancer ma réflexion :

  1. Neo4j 2.3 est nettement moins sensible à la taille de la heap ;
  2. Le mode depth-first est nettement plus rapide que breadth-first ;
  3. Avec « suffisamment » de mémoire, Neo4j Enterprise 2.2 reste plus rapide que 2.3.
Comparaison des temps de réponse entre les 2 versions, en fonction du mode de traversée et de la heap
Version Neo4j Enterprise 2.2.7 Neo4j Enterprise 2.3.2
Traversée Breadth-First Depth-First Breadth-First Depth-First
Heap (Go) 1 2 4 1 2 4 1 2 4 1 2 4
Moyenne 6616 3441 2045 2229 2209 1276 2771 2500 2465 1544 1543 1540
50 % 6308 3281 2022 2228 2208 1277 2748 2487 2443 1549 1517 1547
90 % 8520 3823 2296 2406 2415 1391 2981 2672 2674 1679 1690 1693
95 % 8820 5268 2353 2454 2488 1424 3145 2773 2709 1711 1727 1716
Maximum 10591 5807 2856 2485 2795 1513 3722 3321 2936 1882 1771 1757

Histogramme des temps de réponses en fonction de la version, du mode de traversée et de la mémoire

Les révélations

Depth-first est plus rapide que breadth-first

Nos vrais traverseurs dans l’application gèrent eux-mêmes le fait de rencontrer le même nœud enfant à travers plusieurs chemins depuis la racine, notamment parce que nous conservons la meilleure « distance » au nœud racine pour certains nœuds clés. Puisque cette mesure nous permet de ne pas continuer au delà d’un nœud déjà connu si la nouvelle distance est moins bonne, nous avons désactivé la gestion des doublons de Neo4j (pour ne pas faire le travail en double) et activé le mode breadth-first, puisqu’il garantit qu’on tombera sur un nœud donné par le plus court chemin possible.

Ça paraissait logique, mais l’erreur aura été de ne pas comparer les deux modes pour vérifier. Le benchmark de mon démonstrateur montre que le résultat n’est pas si garanti que ça.

En pratique, cela m’a effectivement permis de rebasculer en mode depth-first qui s’est avéré plus rapide malgré la probabilité de travail en double (étant donné 2 chemins menant au même nœud depuis le point de départ, il y a 50 % de chances de prendre le plus court en premier) : les gains dans la gestion des états et la moindre consommation mémoire sont en réalité meilleurs.

Avec suffisamment de mémoire, Neo4j 2.2 semble plus rapide

Quelle utilisation est donc faite de cette mémoire pour permettre à 2.2 de repasser devant 2.3 ? Le cache, bien sûr ! Plus précisément, l’« object cache », celui qui a été supprimé en 2.3 et qui conserve en mémoire les données des nœuds et relations qu’il peut (le fameux High-Performance Cache de l’Enterprise Edition s’adapte à la mémoire disponible). Il évite ainsi les lectures sur disque.

Mais qu’est-ce que ça signifie exactement dans mon scénario de test ? J’ai un jeu de données (à la fois dans mon démonstrateur et dans l’application) qui a certes une taille conséquente pour la traversée, mais qui tient encore en RAM.

La comparaison était biaisée depuis le début

C’est le problème des benchmarks dits « synthétiques » : on mesure un unique scénario, en conditions parfaites, et il faut faire très attention à ce qu’on mesure effectivement. En pratique, avec mon instance 2.2, je ne mesurais pas la vitesse d’une traversée brute, mais d’une traversée avec l’ensemble des données en cache – un cache parfait, en quelque sorte.

Que se passe-t-il le jour où l’application contient suffisamment de données pour ne plus tenir en RAM ? Soit on rajoute de la RAM (scalabilité verticale, mais ça ne fonctionne qu’un temps, avec des effets négatifs bien réels et quasiment exponentiels sur les temps de pause lors des garbage collections), soit les temps de réponse se dégradent brutalement et ressemblent plus à la situation limitée en RAM du tableau de comparaison.

Si Neo4j 2.3 a vu ce cache supprimé, c’était pour améliorer la scalabilité, pas forcément la performance : sur un « petit » jeu de test, l’effet est négatif, mais en contrepartie les performances sont bien plus prévisibles et bien moins dépendantes de la taille totale des données.

Ajustons la comparaison de performance

Pour comparer la traversée brute dans les deux cas, il faut un moyen de vider le cache entre chaque appel dans l’instance 2.2. Le High-Performance Cache de l’Enterprise Edition expose un MBean (JMX) permettant justement de faire cela.

J’ajoute donc un nouveau service dans le démonstrateur appelant ce MBean, et je reprends les tests, en me limitant au cas le plus favorable (heap de 4 Go, mode depth-first) qui permettait à Neo4j 2.2 d’être plus rapide.

Les résultats cache vide sont nettement plus mauvais, et il est difficile de croire que ce soit uniquement le coût de gestion du cache lui-même. Au delà de la suppression de l’object cache, les performances ont donc été largement améliorées dans la version 2.3. 👍

Comparaison des temps de réponse entre les 2 versions, en fonction du cache
Version Neo4j Enterprise 2.2.7 Neo4j Enterprise 2.3.2
Scénario Cache conservé Cache vidé Pas de cache
Moyenne 1276 2938 1540
50 % 1277 2889 1547
90 % 1391 3178 1693
95 % 1424 3238 1716
Maximum 1513 3642 1757
Histogramme des temps de réponse pour les 3 scénarios, montrant l'avantage en performance de la 2.3 sur la 2.2 sans cache

La 2.3 est bien meilleure que la 2.2 dès que les données ne sont plus en cache

Ça explique aussi en partie les différences de résultats avec Michael Hunger : les implémentations de cache disponibles dans Neo4j Community Edition sont moins performantes que le High-Performance Cache, et ne permettent pas de compenser les moindres performances intrinsèques de la 2.2. Le corollaire est qu’il n’y a plus de différence notable de performance de traversée en 2.3 entre la Community Edition et l’Enterprise Edition : les différences essentielles restent au niveau opérations (backup, haute disponibilité), ou dans l’optimiseur Cypher.

Quelques chiffres pour approfondir

J’ai exécuté une unique requête pour obtenir à la fois les allocations de la requête et la heap utilisée au final, la mesure étant faite avec Yourkit. L’instance de Neo4j a toujours 4 Go de heap, et la traversée se fait toujours en mode depth-first.

Évidemment, la heap utilisée dans les deux scénarios utilisant la 2.2 est similaire, puisque le cache se trouve rempli avec la même chose après la requête, mais les allocations de la requête sont bien plus importantes quand le cache est vide, puisque Neo4j doit lire les données sur disque puis les mettre en cache. La 2.3, sans l’object cache, a une empreinte mémoire minimale, et on peut voir que les allocations de la requête sont bien plus faibles que dans les deux autres cas. Le temps de réponse est moins bon qu’en utilisant le cache de la 2.2, malgré les plus faibles allocations, car limité par les lectures sur disque quand la 2.2 fait des accès purement en RAM.

Comparaison de la consommation mémoire entre les 2 versions, en fonction du cache
Version Neo4j Enterprise 2.2.7 Neo4j Enterprise 2.3.2
Scénario Cache conservé Cache vidé Pas de cache
Heap utilisée (Mo) 372 374 24
Allocations de la requête (Mo) 144 332 76
Positionnement des 3 scénarios en fonction de la mémoire utilisée, en statique et en dynamique

La 2.3 a un net avantage en terme d’utilisation mémoire, que ce soit en statique ou en dynamique

Conclusion

Neo4j 2.3 a sacrifié une partie de la performance native des opérations répétitives sur des données tenant dans le cache, afin de mieux adresser le cas général. Oui, il y a des effets négatifs sur certains scénarios, mais le gain global est positif :

  • meilleure prévisibilité des performances
  • moins de pression sur la heap de la JVM, donc moins de garbage collection, moins de pauses

L’autre élément essentiel à retenir, c’est bien sûr qu’au delà de la mesure de performance elle-même, il faut comprendre comment elle est constituée, ce qui compliqué par l’utilisation de code tiers avec lequel nous sommes moins familier que notre propre code. Mais de toute manière, il vaut toujours mieux mesurer que deviner.

Enfin, dans un prochain article, je reviendrai sur les changements que nous avons effectués dans le code pour atténuer la dégradation réelle des temps de réponse vue par les utilisateurs, et j’élargirai également la comparaison à Neo4j 3.0, sorti depuis.

Mise à jour le 20/7/2016 : l’article faisant suite est disponible sous « Stratégies d’optimisation des traversées dans Neo4j ».