Pourquoi vaut-il mieux parier sur une base de données de graphes native ?

Toutes les bases de données de graphes ne se valent pas. Les développeurs vont devoir non seulement comprendre pourquoi utiliser les bases de données de graphes, mais aussi laquelle utiliser. Qu'est-ce qui définit un bon choix technologique pour la gestion des données connectées ? C'est avant tout la conception native ou non native du système de gestion des bases dedonnées (SGBD). Autrement dit, si le système est élaboré dès l'origine pour les graphes, ou si les graphes sont une extension ajoutée à un autre modèle.

Dans cet article, nous allons explorer des thèmes fondamentaux des sciences informatiques et de conception des systèmes en rapport avec le développement des SGBD. Nous allons voir comment chaque SGBD est conçu pour prendre en charge son modèle natif (ou primaire) et nous pencher sur les pièges qui apparaissent quand on essaie de prolonger ce modèle  vers d'autres modèles non natifs.

Nous sommes nombreux à avoir étudié les sciences informatiques ou des disciplines similaires et à avoir été exposés aux algorithmes et aux structures de données. Quand on évalue un algorithme ou une structure de données, on prend en compte la complexité en temps d'exécution et en occupation mémoire. Vous vous souvenez sans doute de la notation "grand O" ou O(f(n)) utilisée pour formuler la complexité de façon abrégée.

●   O(1) ou temps constant :Accéder à un élément se fait à coût constant. Même si le nombre d'éléments augmente, le temps pour trouver un élément  est toujours le même.

●   O(log n) : Accéder à un élément se fait à un coût proportionnel au nombre d’élément, mais de manière logarithmique.

●   O(n) : Accéder à un élément se fait à un coût proportionnel au nombre d’éléments. Autrement dit, plus la base de données contient d’éléments et plus les temps de traitements sont longs. Même si la requête ne concerne qu’une petite partie de celle-ci.

●   O(nm) : Accéder à un élément se fait à un coût proportionnel au nombre d’éléments, mais de manière exponentielle.

En général, on préfère les caractéristiques les moins coûteuses, à moins que le nombre d'éléments soit faible et limité, dans quel cas un ordinateur moderne peut rapidement les exécuter.

En suivant la théorie, voyons comment cela s'effectue en pratique dans l'élaboration d'un SGBD. Commençons par une liste chaînée et non ordonnée.

Cette liste chaînée est peu coûteuse en temps calcul pour les insertions sans conflit car sa complexité est de O(1). Toutefois, la lecture se fait à O(n) ce qui signifie que la performance se dégrade au fur et à mesure que la liste augmente.

Faut-il pour autant ne pas utiliser les listes chaînées ? Pas du tout, il faut comprendre qu'elles sont bien adaptées aux scénarios d'écriture sans conflit[2], mais moins efficaces pour les écritures avec conflit ainsi que pour la lecture. L'utilisation de types de données répliquées sans conflit (CRDTs) peut aider à diminuer le conflit d'écriture comme le font les stratégies de programmation sans blocage, donc tout n'est pas négatif. Mais cela montre que lorsque la théorie rejoint la pratique, la notation grand O procure un guide de conception, mais pas de garantie infaillible.

Les structures en arbre peuvent aider à compenser le déséquilibre entre lecture et écriture. La lecture comme l'écriture en arbre sont généralement de O(log n). Le conflit de lecture est également réduit car il existe de plus nombreux points d'attache dans un arbre que dans une liste (y compris dans un arbre binaire simple).

Les ingénieurs en bases de données apprécient depuis longtemps les différents arbres binaires car leurs feuilles (Ex. 7689, 66 et 6) procurent un index en plus de ce qui est enregistré dans les nœuds des feuilles. C'est astucieux car ça permet de garder les enregistrements d'index les plus volumineux dans la mémoire rapide pour un traitement accéléré, alors que les enregistrements de données moins importants sont relégués sur le disque.

Les structures en arbre fonctionnent bien pour les recherches ou les écritures uniques à coût de O(log n). Y compris dans les plus grands ensembles de plusieurs milliards de données, le nombre d'opérations requises reste gérable pour des recherches uniques.

Toutefois, si on réfléchit en termes d'arbres dans le contexte d'une base de données de graphes impliquant de nombreuses traversées, une complexité d'accès moins coûteuse est préférable. La différence entre O(n)  et O(m log n) en termes d'opération d'entrées/sorties sur le disque s'amplifie rapidement et dégrade la performance de requête.

Bien sûr, la conception de chaque SGBD présente une combinaison de structures pour répondre à sa charge de travail native. Le choix minutieux de ce type de structures de données en fonction du modèle et de la charge natifs des données donne lieu à la conception d'un SGBD cohérent. Chaque SGBD a évidemment son point fort : le modèle pour lequel il est nativement conçu.          

L'avantage d'une base de données de graphes native

Une base de données de graphes native est conçue dès le départ pour traiter les charges de travail des graphes en toute sécurité et efficacement, qu'il s'agisse du langage de requête, du moteur de gestion de la base de données, du système de fichiers, du clustering, de la sauvegarde ou de la supervision.

Une technologie native de graphes tend à traiter les requêtes plus rapidement, à mieux se dimensionner et à s'exécuter avec bien plus d'efficacité sur moins de matériel. Le champ d’actions des requêtes est plus important et leur surface d'exécution est grandement améliorée pour les charges de travail spécifiques aux graphes.

Un langage de graphes natif tel que OpenCypher est un élément clé pour simplifier l’écriture des requêtes connectées. Un planificateur de requêtes et un stockage natif permettent d’effectuer des optimisations qui ne sont pas possibles avec les stockages non natifs. Nous avons réalisé des analyses de graphes simples dans lesquelles la solution native s'avérait des centaines de milliers de fois plus rapide qu'un stockage non natif.

Le stockage natif de graphes est conçu pour utiliser le système de fichiers d'une façon expressément compatible avec les graphes. Traverser une relation coûte O(1) quelle que soit la taille du graphe, qu’il soit sur disque ou en mémoire. De ce fait, traverser plusieurs relations revient à un coût prévisible de O(n). La latence de la requête est donc proportionnelle à la portion du graphe que l'on choisit d'inspecter et non à la taille globale de la base de données : une avancée majeure.

Mécaniquement, le coût de chaque traversée est mineur grâce à une compatibilité parfaite entre le logiciel et le matériel. Les bases de données de graphes natives sont conçues en fonction de ce qu'un ordinateur peut faire le plus vite : gérer des pointeurs pour naviguer efficacement dans le graphe à très grande vitesse. A contrario, traiter des données non nativement stockées en graphes (colonnes, relationnelles, document ou clés-valeurs) nécessite des transformations coûteuses depuis et vers le modèle interne utilisé.

Les bases de données de graphes natives incluent des mécanismes transactionnels qui sauvegardent les données de façon sûre et insensible aux défaillances du réseau ou aux pannes serveurs et aux conflits provoqués par des transactions concurrentes. Des protocoles comme Raft et des mécanismes tel que l'envoi des journaux de transactions permettent aux clusters des bases de données de graphes natives d'offrir de solides garanties de cohérence (par exemple, Neo4j assure une cohérence causale). Le principe du "Log Shipping" ou envoi des journaux de transactions, consiste à maintenir une base de données esclave en état de restauration permanente pour qu’en cas de cas de sinistre on puisse basculer la production sur le serveur de secours qui prends alors le relais de la base maître. Le basculement ne pouvant se faire que manuellement même s’il est possible d’automatiser ceci au moyen d’un développement particulier.

De plus, un  stockage natif permet d'adapter l'implémentation aux architectures techniques de demain. Les technologies de stockages  évoluent et l'implémentation native de graphes la suit pour en tirer parti. A l'avenir, Neo4j se prépare à adapter son modèle natif aux futures plateformes de stockage sur disque et aux architectures de mémoire telles que  la RAM non volatile.

Maintenant, étudions ce qui se passe quand on adapte d'autres conceptions de SGBD à l'exécution de charges de travail de graphes.

Les requêtes de graphes sur les SGBD non nativement graphes

Notre brève réflexion sur les structures classiques de données nous rappelle de façon très simplifiée mais utile, que le choix des structures de données se fait dans un but précis et qu'il n'existe aucune structure de données offrant une application universelle. Quand on conçoit un SGBD, on choisit la structure de données en fonction du modèle des données et de la charge machine estimée. Des structures plutôt différentes peuvent être choisies telles que le stockage en colonnes, en documents ou relationnel. On optimise ensuite la conception du système pour la rendre aussi efficace que possible pour le modèle de données de travail. Le logiciel qui en découle est natif : pour les colonnes, pour les documents ou pour les tableaux. Mais il n'est pas natif pour les graphes.

Afin de prendre en charge les graphes sur des bases de données non nativement graphes, il faut d'une façon ou d'une autre y apporter une extension en transposant des fonctionnalités de graphe sur leur modèle natif. En général, deux approches se présentent aux bases de données non nativement  graphes : ajouter une API de graphe au SGBD existant ou ajouter des fonctionnalités de graphe dans un langage de requête non graphe.

Il ne faut pas écarter ce point comme étant un simple détail d'implémentation. Le type d’implémentation d'un SGBD le renforce pour certaines charges de travail (celles pour lesquelles il est nativement conçu) mais l'affaiblit pour les autres charges (celles pour lesquelles il n'a pas été conçu). Ceci apparaît clairement en faisant l'extension de deux modèles non graphes bien connus en bases de données de graphes.

Une librairie de graphes sur un stockage en colonnes

Les stockages orientés colonnes contemporains fournissent nativement un modèle de données basé sur les tables de hachage. Ils offrent un moyen simple de répartir les données autour d'un cluster et permettent une tolérance aux pannes.

Pour configurer un stockage en colonnes afin qu'il se comporte comme une base de données de graphes, nécessite le déploiement d’un moteur de graphe au-dessus. Celui-ci fournit à l’utilisateur une librairie et un langage de requête pour les graphes qui sont attachés à la base de données sous-jacente grâce à un code de liaison.

En général, une  table de hachage présente une excellente complexité algorithmique en O(1) pour à la fois l’écriture et la lecture. Toutefois, une bonne fonction de Hachage tente également d’éclater les données similaires afin d’éviter les conflits. Malheureusement, cela réduit leur proximité et la performance globale du système.

Stocker à proximité physique des données dont le format est du graphe est essentiel pour en garantir les performances.

Chaque recherche d'opération en O(1) dans un stockage orienté colonnes en cycle de hachage devient une opération sur le réseau, donc mécaniquement coûteuse. Ceci implique que la performance pour traverser les graphes s'avère souvent faible et nécessite un important investissement en matériel pour atteindre des performances de traversée qui restent modeste. Même lorsqu'une connexion astucieuse entre la librairie de graphes et la base de données sous-jacente dénormalise radicalement les données pour préserver la proximité, on se heurte toujours à un mur quand les limites de cette dénormalisation sont atteintes.

Chez Neo4j, nous l'avons vite compris : nos premières implémentations de graphes (qui remontent à 2000) n'étaient pas natives et utilisaient une librairie de graphe sur une base de données relationnelle. Quand les requêtes allaient au delà d'une profondeur avoisinant trois, leur performance se dégradait significativement, ce qui a motivé nos efforts à développer un moteur réellement natif pour les graphes.

Finalement, comme l'infrastructure sous-jacente est conçue pour être tolérante aux pannes et, pour stocker et extraire des valeurs uniques de données plutôt que des graphes, il est vite fait de corrompre les données de ce type de systèmes. Le modèle classique de cohérence à terme n'est pas assez puissant pour les graphes.

Stockage de documents avec opérateur de requêtes de graphes

Les stockages contemporains orientés documents utilisent des arbres binaires pour indexer les données du SGBD, un peu comme dans une armoire de classement sophistiquée. Dans ce type de système basé sur un arbre, rechercher un document coûte O(log n). C'est sans doute suffisant pour des recherches ou des écritures ponctuelles, mais le coût passe à O(m log n) quand on utilise des index pour reproduire la traversée d'un graphe de m sauts. À ce coût, la performance de traversée en pâtit grandement dès que la profondeur atteint deux ou trois.

Certains stockages de documents proposent un opérateur de recherche de graphes pour aider les utilisateurs à lier les données de façon rudimentaire. Après examen, nous avons constaté que cette implémentation créait l'équivalent d'un tableau de liaison pour connecter les éléments du graphe. A l’évidence, elle ne procure pas la richesse d’implémentation nécessaire pour extraire une réelle valeur des graphes car elle ajoute uniquement une syntaxe limitée.

Le plus dommageable est sans doute de dénaturer le modèle de documents pour qu’il fasse du graphe puisque le SGBD sous-jacent ne sais pas travailler avec les relations. Dans la mesure où il est nativement conçu pour les documents, un utilisateur peut corrompre le graphe (par exemple en laissant des liens vers des documents n’existant plus) car le moteur est incapable d'intervenir pour maintenir la cohérence, ou même la vérifier. Au fil du temps, le graphe devient un ensemble d'ilots de liens orphelins qui détruit toute sa valeur.

"Faire 'assez bien' n’est pas suffisant"

Il est souvent commode de supposer que les technologies non-natives sont suffisantes pour certains graphes, en particulier si on dispose déjà d'une telle technologie pour des raisons historiques.

Cependant avec une volumétrie de données toujours croissante, des structures de données de plus en plus variables et une interconnexion/corrélation en expansion, si vous tenez à faire sens de vos données, vous devez intégrer une technologie de graphe native à vos systèmes.

Nous savons également que la valeur d’une donnée tient aussi dans ses relations,  or une approche non native ne permet pas d’en profiter. Une base de données de graphes native vous sera plus utile à long terme, sans nécessiter d'investissements importants en matériel.

Savoir quelle architecture de graphes convient n'est pas toujours évident. Toutefois, quand l'entreprise a besoin de traiter des connexions efficaces, la technologie de graphes native apparaît neuf fois sur dix comme la seule véritable option,  du fait de son intégrité, de sa performance, de son efficacité et de ses avantages en terme d'évolutivité.