FR3050848B1 - Architecture de serveurs et methode de redistribution des donnees pour la distribution d'un graphe versionne. - Google Patents

Abstract

L'invention présente un système informatique distribué comprenant une pluralité de serveurs comportant chacun un processeur pour exécuter des traitements informatiques et une mémoire pour l'enregistrement de graphes, ainsi que des moyens de routage entre les serveurs ainsi qu'un serveur d'interfaçage (7) pour traiter des requêtes provenant d'une pluralité d'équipements d'utilisateurs (8). Les serveurs sont organisés en N couches de serveurs (11 à14) formant, pour chacune desdites couches, un groupe de serveur, les serveurs d'une même couche présentant une topologie en anneau avec chacun des serveurs muni d'un protocole de communication vers le serveur suivant de l'anneau du groupe de machines, le système comportant en outre des moyens de communication avec un serveur de routage.

Description

Architecture de serveurs et méthode de redistribution des données pour la distribution d'un graphe versionné

Domaine de 1'invention

Le domaine de l'invention est celui des systèmes informatiques destinés à traiter des données versionnées pour répondre en temps réel à une requête. Il concerne plus particulière le traitement de données relativement peu nombreuses mais très contextualisées.

Etat de 1'art

On connaît dans l'état de la technique le brevet européen EP 1428117 B1 décrivant un procédé et un système destinés à organiser des éléments d'une application serveur dans un système client-serveur.

Selon cette solution de l'art antérieur, les composantes client et serveur d'une application sont organisées comme des graphes hiérarchiques complémentaires, tels que des arborescences ou des graphes acycliques dirigés. Un ou plusieurs noeuds dans le graphe serveur sont reliés par une interface de communication distribuée au(x) noeud(s) homologue(s) respectif(s) dans chaque graphe client. Le graphe serveur comprend des nœuds serveur correspondant à la réunion de tous les noeuds client, tandis que chaque graphe client correspond à un sous-ensemble des nœuds serveur associés. Des graphes objet autonomes, appelés acteurs, peuvent être assemblés pour former des graphes objet composites sur le client et le serveur. Des applications client-serveur peuvent ainsi être formées lors de l'exécution à partir de collections d'acteurs organisés de manière hiérarchique. Chaque acteur est sécurisé par rapport à ses homologues, et une interface sécurisée permet un accès distant et la mise à jour d'acteurs par des propriétaires, tels que des distributeurs de sources extérieures.

On connaît surtout dans l'état de la technique la demande de brevet US2012/0188249 décrivant un système qui comprend un graphe distribué pour former une ou plusieurs partitions, et un ou plusieurs services associé chacun à une partition du graphe. Les services des partitions du graphe sont en communication avec l’ensemble du graphe et le graphe distribué est utilisable pour être consultée en requêtant l’ensemble des sous-graphes.

Cette distribution est nécessaire pour permettre d'effectuer des traitements demandés par les différents utilisateurs, parfois plusieurs milliers voire plusieurs millions. Ces traitements sont exécutés sur le serveur de manière simultanée ce qui nécessite des ressources de calcul et des temps de traitement très importants voire rédhibitoires. En multipliant le nombre de machines, et en distribuant le graphe général, il devient alors possible pour chaque utilisateur d'exploiter le sous graphe du graphe général souhaité.

Inconvénients de 1'art antérieur

Les solutions de l'art antérieur, et notamment la solution décrite dans la demande de brevet US2012/0188249 prévoient que les utilisateurs partagent un même graphe global, modifié par tous les utilisateurs en même temps. La solution décrite permet à un utilisateur de récupérer par une requête le sous-graphe qui l'intéresse, en procédant à des traitements sur les serveurs sur lesquels sont distribuées les partitions du graphe général.

Cette solution de l'art antérieur prévoyant un seul graphe général et commun à tous les utilisateurs, distribué sur plusieurs serveurs, donne aussi lieu à des collisions entre les traitements demandés par différents utilisateurs. Il est impossible d'enregistrer un contexte spécifique à un utilisateur, le contexte n'étant pris en compte qu'au moment du traitement sur le graphe global.

De même, cette solution de l'art antérieur ne permet pas d'apporter à chaque utilisateur un graphe qui lui est propre. Dans les solutions de l'art antérieur, plusieurs utilisateurs accèdent au même graphe. De ce fait, il n'est pas possible de proposer un service personnalisé a un utilisateur donné, en s'appuyant sur des ressources informatiques partagées. Il en résulte une grande perte de performance du fait de la redondance de l'information dans les sous-graphes de chacun des utilisateurs. Cette perte de performance est rédhibitoire pour gérer un nombre de plusieurs milliers d'utilisateurs sur des graphes importants. L'homme du métier serait naturellement conduit pour répondre a cet inconvénient en dupliquant le graphe général ou les sous-graphes du graphe général pour autant d'utilisateurs qu'il puisse exister. Cela impliquerait donc de démultiplier les grappes serveurs pour pouvoir gérer ces données ou bien les laisser être gérer par la machine de l'utilisateur lui-même. Dans ces deux cas, on serait confronté à d'autres inconvénients : il n'y aurait pas possibilité de centraliser des informations communes à plusieurs utilisateurs pourtant très nombreuses. Par ailleurs les ressources matérielles seraient démultipliées sans qu'elles ne soient exploitées d'une manière optimisée.

Solution apportée par 1'invention

Afin de répondre à ces inconvénients, la présente invention concerne selon son acception générale un système informatique distribué comprenant une pluralité de serveurs comportant chacun un processeur pour exécuter des traitements informatiques et une mémoire pour l'enregistrement de graphes, ainsi que des moyens de routage entre les serveurs ainsi qu'un serveur d'interfaçage pour traiter des requêtes provenant d'une pluralité d'équipements d'utilisateurs, caractérisé en ce que : - Lesdits serveurs sont organisés en N couches de serveurs formant, pour chacune desdites couches, un groupe de serveur [groupe de machines], les serveurs d'une même couche présentant une topologie en anneau avec chacun des serveurs muni d'un protocole de communication vers le serveur suivant de l'anneau du groupe de machines - Des moyens de communication avec un serveur de routage.

Chacun des serveurs d'une couche communiquant avec chacun des serveurs de la couche directement inférieure.

Chaque serveur d'une couche est caractérisé par :

Une mémoire cache pour l'enregistrement de graphes propres à un utilisateur ou à un groupe d'utilisateurs.

Une mémoire cache pour l'enregistrement de données hachées résumant le contenu des graphes des couches inférieures affiliés aux graphes du serveur.

Une mémoire cache pour l'enregistrement éphémère de résultats de traitement propres à l'utilisateur, provenant des couches inférieures et/ou de la couche de l'utilisateur.

Une mémoire cache pour l'enregistrement éphémère de données provenant des couches inférieures, la couche supérieure de serveurs comportant des partitions spécifiques chacune à un utilisateur.

On entend par « éphémère » au sens du présent brevet le fait qu'une information enregistrée en mémoire cache est susceptible d'être modifiée fréquemment par rapport à l'évolution du contenu des couches inférieures.

On entend par « durable » au sens du présent brevet le fait qu'une information enregistrée en mémoire cache est susceptible d'être supprimées occasionnellement, typiquement une fois par jour. Ces suppressions ne sont pas liées aux requêtes d'un l'utilisateur mais elles sont liées de manière asynchrone à l'évolution des contenus des couches inférieures.

Cette solution permet d'améliorer considérablement les performances du système en optimisant la distribution des informations entre des couches supérieures, variables en fonction de chaque requête de chaque utilisateur, et d'enregistrer en mémoire cache du contexte de chacun des utilisateurs, d'une part, et d'autre part d'enregistrer dans les couches inférieures les informations communes à plusieurs utilisateurs. Les informations sont redistribuées aux couches supérieures.

La présente invention concerne également un procédé de requêtage en temps réel d'un système d'information structuré en graphe versionné multi-couches, permettant à chaque utilisateur d'utiliser un graphe qui lui est propre, et qui partagera un certain nombre d'informations avec les graphes des autres utilisateurs.

Par conséquent, le but de la méthode expliquée ici est de permettre à un utilisateur d'appeler son propre graphe et de le manipuler en -temps réel en effectuant dessus ses opérations.

Tout le principe est donc de reconstituer sur un serveur de la couche UTILISATEUR le graphe propre à l'utilisateur et de le rendre exploitable en temps réel par l'utilisateur.

De la sorte, on obtient une structure distribuée sur plusieurs serveurs pouvant gérer un graphe pour chaque utilisateur, avec pourtant des informations communes et partagées entre tous les utilisateurs.

Ledit système est constitué par un ensemble de groupe de machines de serveurs, un serveur de routage et par au moins un serveur de base de données,

Lesdits groupe de machines de serveurs hébergent les données spécifiques aux éléments dudit graphe versionné multicouches général.

Le procédé de requêtage comporte : des étapes d'instanciation des éléments dudit graphe versionné multicouches général consistant : à sélectionner l'un desdits serveurs en fonction de paramètres comprenant la charge CPU de chacun des serveurs, la mémoire disponible pour chacun des serveurs, la classe d'appartenance de l'élément, ainsi que la similarité entre les filiations des éléments déjà instanciés sur le serveur et la filiation de l'élément à enregistrer sur le serveur sélectionné à propager 1'instanciation dans le réseau de groupe de machines des étapes de complétion desdites données spécifiques hébergées, consistant à transférer récursivement des données entre deux couches adjacentes successives de serveurs, en réponse à la détection d'une lacune d'une information enregistrées dans la couche supérieure lesdites données transférées étant enregistrées dans les caches mémoire associés aux serveurs des couches inférieures et de la couche supérieure

Des étapes de synchronisation des données entre les couches inférieures et supérieures permettant de conserver l'intégrité de la structure de données lors de la production de contenu par l'utilisateur.

Description détaillée d'un exemple non limitatif de réalisation

La présentation invention sera mieux comprise à la lecture de la description d'un exemple non limitatif de réalisation, se référant aux dessins annexés où :

La figure 11 montre un graphe versionné multicouche gérant des données pour deux utilisateurs : user 1 et user 2.

Les figures 4 à 8 montrent les différents graphes versionnés du graphe versionné multicouche décrit dans la figure 1.

La solution décrite à titre d'exemple met en oeuvre deux graphes communs aux deux utilisateurs, décrits par les figures 4 et 5.

Au-dessus de la seconde couche de graphe décrit en l 5, le graphe versionné multicouche se divise en deux branches proposant chacune une version supplémentaire du graphe propre à chacun des utilisateurs 1 et 2.

Les figures 7 et 8 décrivent respectivement les informations propres à chacun des utilisateurs 1 et 2. » Les figures 9 et 10 montrent les graphes visibles pour chaque utilisateur.

Les figures de 4 à 11 montrent un exemple concret de graphe versionné multicouche représentant une simple ontologie. Dans le graphe global 1 (Fig. 4), « chat » est seulement un « mammifère », un « animal » et un « être vivant ». Dans le graphe global 2 (Fig 5), « chat » devient un « félin », un « mammifère », un « animal » et un « être vivant » · A partir du graphe 2, l'arborescence se divise en deux graphes feuilles, chacun propre à un utilisateur (l'utilisateur 1 et 2). Dans le graphe de l'utilisateur 1 (Fig. 9), un « chat » est gentil, dans le graphe de l'utilisateur 2 (Fig. 10), un « chat » est gentil.

Les figures 1 et 2 représentent une vue schématique de l'architecture matérielle d'un exemple de système selon 1'invention.

La figure 3 représente une vue schématique de la séquence de traitement de recherche d'information : on cherche à collecter toutes les arêtes d'un sommet à travers la filiation de graphes.

Terminologie

Dans la présente brevets, les termes techniques suivants sont définis comme suit : • Un GRAPHE est un ensemble de sommets relies par des arêtes. • Un GRAPHE VERSIONNE MULTI-COUCHES (graphe versionné multicouche) est un arbre de graphes. Chaque graphe dépend des informations contenues dans les graphes parents de sa filiation.

Chaque graphe peut ajouter ou retirer des sommets ou des arêtes en comparaison avec son graphe parent.

Par conséquent, un sommet dispose de plusieurs versions de lui-même à travers l'arborescence des graphes. Il existe un SOMMET RACINE dans un graphe parent, contenant toutes les informations internes au sommet ainsi que ses arêtes de base. Dans les graphes héritant du graphe parent, le SOMMET RACINE devient un SOMMET VERSIONNE mettant à jour les arêtes du sommet pour chaque nouveau graphe ajouté à la filiation du graphe parent.

Un graphe peut utiliser l'information des graphes inférieurs dont il hérite. Par conséquent, quand on considère un sommet et ses arêtes dans un graphe particulier, l'information complète sera les arêtes totales contenues dans le graphe présent, mais aussi dans les graphes inférieurs dont le graphe présent hérite.

Les graphes dans un GRAPHE VERSIONNE MULTI-COUCHES peuvent être classifiés par le niveau d'information qu'ils contiennent. • Une COUCHE est un niveau d'information. Les graphes de l'arborescence d'un graphe versionné multicouche appartiennent aux différents types de couche : • Les couches UTILISATEUR sont les couches qui ne gèrent les graphes qui contiennent des informations propres à chaque utilisateur. • Les Couches SWARM sont les Couches qui contiennent des informations communes à un groupe d'utilisateurs. • Les Couches GLOBAL sont les couches qui contiennent des informations communes à tous les utilisateurs. • Un SERVEUR DE GRAPHES est un ordinateur disposée à l'intérieur d'un groupe de machines. Le groupe de machines n'héberge que des serveurs dédiés à un niveau d'information précis : le niveau d'information du groupe de machines.

Une grappe DE GRAPHES est un groupe de serveurs de graphes dédiés à une couche d'information particulière. Chaque couche d'information est hébergée par un groupe de machines particulier qui est autorisé à ne gérer exclusivement que des graphes de cette couche.

Par conséquent, il a uniquement trois types de groupe de machines : • Le groupe de machines UTILISATEUR, qui héberge les graphes propres à chaque utilisateur. • Les groupe de machines SWARM qui hébergent les graphes propres à chaque groupe d'utilisateurs. • Les groupes de machines GLOBAL qui hébergent des graphes propres à tous les utilisateurs.

Architecture matérielle générale

Les figures 1 et 2 représentent une vue schématique de l'architecture matérielle du système.

Le système est constitué par un ensemble de serveurs formant des grappes organisées en plusieurs couches : - une couche utilisateur ( 1 ) ou « supérieure » comprenant des serveurs (11 à 14) des couches (2 à 5) hiérarchisées en fonction du niveau d'informations. un serveur de routage (6).

Le système comprend aussi un serveur (6) d'interfaçage comprenant les moyens d'interfaçage avec les équipements (8) des utilisateurs. Il comprend aussi un serveur SQL (8) gérant le code attribué à chacun des utilisateurs pour sécuriser l'accès d'un utilisateur au réseau qui lui est propre.

Serveur d'interfaçage

Le serveur d'interfaçage (7) est constitué par un ordinateur comportant un processeur multi-cœurs pour traiter un parallèle les requêtes des différents utilisateurs. Il exécute une application de serveur gérant chaque session utilisateur en parallèle.

Il comprend par ailleurs des moyens de cryptage des informations transitant pendant chaque session.

Le serveur d'interfaçage (7) assure également un découplage entre les serveurs des couches (1 à 5 ) et le serveur de routage (6) et les équipements des utilisateurs (8) pour assurer une protection des données enregistrées dans le système.

Ce serveur d'interfaçage (7) communique uniquement avec : le serveur de routage (6) la couche supérieure (1) de serveurs (11 à 14) le serveur SQL (9).

Le serveur d'interfaçage (7) est constitué par une machine unique.

Couche supérieure (1) et couches inférieures (2 à 5)

La couche supérieure ( 1 ) est constituée par une grappe de serveurs (11 a 14) comprenant chacun un processeur multi-cœurs et des mémoires vives ainsi qu'un moyen de stockage permanent tel qu'un disque dur.

Les serveurs (11 à 14) de la couche supérieure (1) communiquent entre eux par un protocole en anneau. Le serveur 11, 12, 13 et 14 ne communiquent dans le groupe de machines respectivement qu'avec les serveurs 12, 13, 14 et 11.

La communication entre le serveur d'interfaçage (7). et l'un des serveurs (11 à 14) de la couche supérieure (1) est commandé par le serveur de routage (6).

Chaque serveur (11 à 14) de la couche supérieure (1) communique avec chaque serveur (21 à 23) de la couche inférieure (2), et ce de manière récursive sous le contrôle du serveur de routage (6) et/ou des informations enregistrées localement.

Chaque serveur d'une couche communique avec chaque serveur d'une couche adjacente.

Les serveurs (11 a 14) assurent les fonctions suivantes : - Requêtage des serveurs des couches inférieures pour compléter les informations dont il a besoin. - Prétraitement des informations disponibles à son niveau de contexte.

Envoi des informations collectées et prétraitées au serveur d'interfaçage (7).

Chaque serveur (11 à 14) comprend une mémoire cache destinée à l'enregistrement des données éphémères et durables. Ces données numériques correspondent à des parties d'informations issues des graphes.

Lorsqu'un utilisateur émet une requête, cette requête va être exécutée de manière arborescente au niveau des différentes couches (1 à 5) de serveurs.

Dans chacune des couches (1 à 5), un serveur détermine les informations à transmettre à un serveur de la couche supérieure, après avoir éventuellement exécuté un traitement local et/ou après avoir requêté la couche inférieure.

Le serveur de routage (6) détermine les chemins de communication entre les couples de serveurs à mettre en relation en fonction d'une table de routage associée aux identifiants de chacun des graphes. Le serveur devant procéder à une communication avec un serveur d'une couche adjacente envoie au serveur de routage (6) un message numérique contenant une clé calculée en fonction de son identifiant et de l'identifiant du graphe à traiter ainsi que de l'identifiant du parent du graphe à traiter.

Configuration finale obtenue

Si les serveurs du groupe de machines (1 à 4) sont respectivement connectés à chacun des serveurs du groupe de machines (2 à 5) toutes les routes de communication entre chaque couple de serveurs ne sont pas exploitées. Etant donné que les graphes sont organisés en priorité selon la similitude d'arborescence qu'il partage avec les autres graphes hébergés sur leur serveur, certaines routes seront exploitées totalement tandis que d'autres seront sous-exploitées.

Les figures 11 à 18 représentent l'évolution des données à l'intérieur du cache du serveur utilisateur hébergeant un graphe sur lequel un utilisateur exécute 500 requêtes successives.

Les figures 11 à 14 traitent le cas où la taille de données exploitée par l'utilisateur est supérieure de 50% à la taille maximale du cache.

On voit que le graphe versionné multicouche a une stabilisation de la taille du cache correspondant à la taille maximale du cache du serveur.

Etant donné que l'utilisateur nécessite plus d'information que ce que le cache peut en contenir, les informations les moins exploitées sont constamment détruites et rechargées à partir des serveurs des couches inférieures.

Les figures 15 à 18 traitent le cas où la taille des données exploitées par l'utilisateur est inférieure à la taille maximale du cache.

On voit qu'il graphe versionné multicouche a une stabilisation de la taille du cache correspondant à la taille de données voulue par l'utilisateur.

Etant donné que l'utilisateur nécessite moins d'information que ce que le cache peut en contenir, toutes les informations sont conservées dans le cache. Seules celles qui ne sont plus du tout exploitées sont détruites.

Comme le montre la figure 3, lorsqu'une requête sur le graphe est effectuée, la requête sera exécutée récursivement par chaque serveur hébergeant chaque élément de la filiation du graphe.

Pour chaque requête exécutée, le cache de chaque serveur sera mis à jour. De la sorte, quand une requête est exécutée, on cherchera d'abord si le résultat n'existe pas dans le cache.

Architecture fonctionnelle

La description qui suit présente un exemple d'architecture fonctionnelle pour gérer les spécificités d'un graphe versionné multicouches en répartissant et manipulant les données sur plusieurs serveurs. Chaque graphe propre à chacun des utilisateurs ne sera en fait qu'une version d'un graphe racine. Un graphe pour un utilisateur sera donc définit par les informations qu'il contient certes, mais surtout par les informations contenues dans la lignée des graphes dont il hérite. Les différentes couches du graphe sont manipulées par des groupes de machines de serveurs différents. Le but est de gérer les transferts d'informations entre les couches de graphes afin de pouvoir exécuter in fine convenablement le traitement demandé sur le serveur manipulant le graphe de l'utilisateur. Le but est de gagner beaucoup de temps en répartissant le traitement des graphes sur des serveurs différents répartis en groupe de machines et de rendre le système plus stable en évitant de centraliser toute l'information et son traitement sur un unique serveur.

Description du procédé de requêtage - Allocation d'un nouveau graphe - Interaction avec le serveur d'interfaçage.

Quand un utilisateur charge un graphe, le graphe doit être alloué dans le groupe de machines UTILISATEUR. Ensuite, l'utilisateur pourra l'utiliser. L'utilisateur se connecte tout d'abord au serveur d'interfaçage. Lorsque l'utilisateur est connecté, il dispose des graphes qui lui sont associés dans la base de données. Les graphes d'un utilisateur sont référencés dans une base de données SQL afin de savoir quels sont les graphes appartenant à l'utilisateur.

Un utilisateur ne peut uniquement interagir qu'avec les graphes qui lui appartiennent. Ces graphes ne peuvent appartenir qu'à la couche supérieure du graphe versionné multicouche global.

Lorsque l'utilisateur souhaite travailler sur un de ses graphes, le serveur d'interfaçage envoie une requête pour allouer le graphe demandé ainsi que sa filiation dans les groupes de machines de serveurs.

Processus de décision du serveur chargé de l'allocation.

Quand un graphe doit être instancié par un groupe de machines, les serveurs du groupe de machines doivent choisir quel serveur d'entre eux l'allouera.

Afin de le décider, les serveurs du groupe de machines se concertent entre eux pour déterminer qui parmi eux le fera.

Les serveurs du groupe de machines sont organisés en anneau. Chaque serveur ne connaît qu'un seul autre serveur du groupe de machines. Chaque fois qu'un graphe doit être instancié, une requête circule dans l'anneau. Le serveur de routage contacte l'un des serveurs du groupe de machines et lui demande de faire circuler la requête.

La requête doit faire trois fois le tour de l'anneau :

Lors du premier tour, chaque serveur doit compléter la requête avec les informations sur sa charge CPU, sa mémoire disponible et l'indice de filiation. L'indice de filiation I_fil (G,S)est la corrélation entre la filiation du graphe que l'on souhaite instancier, et la filiation des graphes déjà hébergés sur le serveur. G est le graphe à instancier, S est le serveur testé pour accueillir le graphe.

Cet indice suit l'équation suivante : I_fil (G,S)= argmax-r( VG_i tq G_i hébergé sur S)((taille_filiationcommune (G,G_i ))/(max(taille_filiation (G),taille_filiation (G_i)))

Lors du second tour, la requête contient désormais les informations de tous les serveurs du groupe de machines.

Le serveur recevant la requête la complète avec sa décision à propos de quel serveur doit gérer le graphe à allouer.

Chaque serveur pour savoir quel serveur dans l'anneau doit héberger le graphe demandé par l'utilisateur associe aux serveurs de l'anneau un indice calculé : l'indice d'allocation. L'indice d'allocation est décrit par la simple formule :

Cet indice suit l'équation suivante : I_all (G,S)= 4~ (5&((mémoire disponible*charge CPU moyenne [/(mémoire totale*charge CPU maximale))Λ2*Ι_ίil (G,S))

Ainsi, le serveur le moins chargé, et avec la filiation la plus proche du graphe que l'utilisateur souhaite sera choisi. Cela permet de centraliser au maximum les informations requises des couches inférieures et de réduire drastiquement la taille des caches décrit à partir de la section OOXX.

Lors du troisième tour, la requête contient la décision de chacun des maillons de l'anneau du groupe de machines. La requête tourne jusqu'à arriver au serveur désigné. Il ne redirige pas la requête, instancie le graphe et en informe le serveur de routage.

Connexion du serveur du graphe utilisateur avec les serveurs de la filiation du graphe

Un graphe dispose d'un parent. Cependant, ici, le parent n'est pas sur le même serveur ni le même groupe de machines que le graphe. Il faut donc localiser ou se trouve le parent du graphe pour pouvoir lui envoyer des requêtes.

Lors de la première requête, le serveur doit donc envoyer une requête au serveur de routage pour savoir l'adresse du graphe parent. Par ce moyen, un graphe peut donc récupérer des informations en provenance de son parent, qui est hébergé sur un autre groupe de machines de serveurs.

Chaque serveur de chaque groupe de machines communique avec le serveur de routage pour savoir à quel autre serveur il doit s'adresser pour requérir les informations manquantes dans un graphe plus profond.

Un serveur de graphes envoie une clé au serveur de routage, contenant trois attributs : l'identifiant unique de la clé, l'IP du serveur envoyant la clé et l'identifiant du graphe parent dont on souhaite la localisation.

Le serveur de routage envoie une réponse contenant trois attributs : l'identifiant de la clé envoyée en requête, le résultat booléen de la requête, et l'IP du serveur contenant le graphe parent souhaité.

Quand un serveur alloue un graphe, il envoie une requête au serveur de routage.

La requête contient cinq attributs : l'IP du serveur, l'identifiant et le niveau d'information du graphe, l'identifiant et le niveau d'information de son graphe parent.

Le serveur de routage met à jour sa table de routage chaque fois qu'il reçoit une telle requête.

Quand un graphe est alloué, le serveur associe l'identifiant du graphe et l'IP du serveur qui 1'héberge.

Allocation récursive du graphe et de sa filiation

Si l'identifiant du graphe parent n'existe pas dans la table de routage, le serveur de routage va envoyer une requête au groupe de machines pertinent selon le niveau d'information du graphe parent pour que le groupe de machines 1'alloue.

Il en résulte une allocation récursive de toute la filiation du graphe demandé.

Complétion des informations manquantes du graphe alloué

Les données requises par l'utilisateur sont réparties dans la filiation du graphe. Les parents du graphe sont hébergés sur plusieurs serveurs différents chacun d'un groupe de machines différent.

Il devient important alors de faire remonter les données des graphes inférieurs pour compléter les données que les graphes supérieurs doivent traiter.

La complétion des données est cruciale pour qu'un graphe distribué fonctionne.

La complétion d'information ne peut avoir lieu que sur les informations des sommets. Un sommet possède deux attributs : ses informations internes et ses arêtes.

Un sommet contenu dans un graphe de l'arborescence d'un graphe versionné multicouche sera soit un sommet racine, soit un sommet versionné qui se référera donc à un sommet racine contenu dans un graphe inférieur.

Seul un sommet racine dispose d'informations internes. Les sommets versionnés ne font qu'ajouter des informations sur l'ajout ou le retrait d'arêtes.

Les requêtes de complétions d'informations sont exécutées récursivement (Fig 2C). Chaque serveur qui contient respectivement chaque graphe de la filiation exécute la requête pour compléter la requête initiale du graphe supérieur.

Il graphe versionné multicouche a plusieurs requêtes de complétion différentes :

Requête de complétion des arêtes : Récupère toutes les arêtes d'un sommet dans le graphe parent hébergé dans un groupe de machines inférieur. Cette requête est nécessaire pour récupérer les arêtes véritables d'un sommet, en fonction de sa version. - Requête de complétion des informations internes : Récupère une copie des informations internes d'un sommet racine dans le graphe parent hébergé dans un groupe de machines inférieur. Cette requête est nécessaire pour récupérer la nature effective d'un sommet versionné dans les graphes supérieurs.

Constitution d'un cache dégénératif

Conservation dans un cache des résultats de requêtes et d'opérations effectuées.

Pour réduire les requêtes d'informations de graphes supérieurs vers des graphes inférieurs, chaque serveur de graphes dispose de son propre cache.

Un cache dégénératif contient trois types d'informations :

Des informations propres à des traitements effectués sur des graphes hébergés sur le serveur.

Les informations propres aux sommets et aux arêtes des graphes parents des graphes hébergés sur le serveur.

Les informations propres à des traitements effectués sur les graphes parents des graphes hébergés sur le serveur.

Par conséquent, quand un graphe requiert une information d'un parent, le serveur vérifie auparavant si l'information n'est pas déjà contenue dans le cache dégénératif.

Quand une opération est exécutée ou une information est requise de graphes inférieurs, le résultat est stocké dans le cache dégénératif du serveur exécutant l'opération.

Lorsqu'une opération récursive est exécutée sur une filiation de graphe, les caches dégénératifs des serveurs hébergeant cette filiation seront remplis.

Par conséquent, plus le nombre de requêtes effectuées par le serveur est important, moins il deviendra nécessaire de faire ces requêtes dans le futur.

Les flots de données entre les serveurs de graphes décroissent rapidement, jusqu'à ce qu'un changement intervienne dans les données contenues dans la filiation des graphes.

Lorsqu'un changement s'opère dans un graphe inférieur, les caches dégénératifs des serveurs hébergeant le graphe et sa descendance de graphes suppriment toute information relative à l'altération des données.

Lors d'un changement dans un graphe, le serveur qui l'héberge envoie donc une requête à tous les serveurs du groupe de machines supérieur pour effectuer le nettoyage des caches dégénératifs.

Plus le graphe est profond dans l'arborescence des graphes, moins il sera fréquent qu'il change. Par conséquent, les suppressions d'informations est parfaitement peu fréquente et contrôlée.

De plus, chaque serveur de la filiation du graphe dispose de son propre cache dégénératif. Par conséquent, un changement dans un graphe de la filiation ne requerra pas la suppression d'informations dans les caches dégénératifs des serveurs de son ascendance de graphes.

Destruction progressive des informations non utilisées

Le principe du cache dégénératif est simplement d'assurer un équilibre entre le flux de requêtes entre les groupes de machines et l'espace mémoire de chacun des serveurs de graphes. A chaque nouvelle requête, l'information à des chances d'être détruite si elle n'est pas utilisée. Moins l'information est utilisée, et plus elle a des chances d'être détruite. β est une variable indiquant le facteur de dégénérescence d'un cache dégénératif. Le serveur change constamment la valeur de β pour faire convenir la taille du cache à celle de la taille qui lui a été allouée.

On définit la fonction f_space (k) pour calculer la charge mémoire du cache : f_space (k)=(taille_(cache) (k)-taille_(maximale du cache))/(taille_(maximale du cache) )

La valeur de β est itérativement calculée à chaque nouvelle requête. Δ_β = 0,01, α_β= 1,08 et [min] _β= 0,001. β (k+l)=max( [ min ] _β,β(k) + ( (2*Δ_β) / ( l+eA (- aJ3*f_space (k) ) )-1)) A chaque nouvelle requête reçue, le serveur teste chacune des informations présentes dans son cache. k est le nombre de requêtes utilisateur effectuées depuis l'utilisation la plus récente de l'information. Chaque information stockée dans le cache dégénératif est associé à une probabilité de survie P(k) subissant une loi de décroissance exponentielle.

La probabilité P(k) pour que lors d'une nouvelle requête, l'information ne soit pas détruite suivent l'équation suivante : P(k)= eA(-Pk)

Chaque fois qu'une information dans un cache est appelée, sa durée de vie k est réinitialisée.

Par conséquent, la taille du cache n'augmentera pas indéfiniment. Le cache ne contiendra toujours que l'information réellement utile pour le serveur. Il atteindra vite une taille permanente.

Comptabilité du nombre de requêtes effectuées.

Un cache dégénératif dispose comme unité de temps le nombre de requêtes effectuées par un graphe et sa descendance.

De par ce fait, il n'est possible de connaître le nombre de requêtes effectuées par un graphe et sa descendance qu'en créant une requête régulière récursive de ping, informant le graphe parent du nombre de requêtes effectuées par son enfant.

Le nombre de requêtes effectuées par le graphe parent sera alors la somme des requêtes effectuées par sa descendance.

Création de contenu dans le graphe de l'utilisateur

La création de contenu dans le graphe nécessité d'un système d'identifiant pour les sommets.

Un sommet dans un graphe versionné multicouche est toujours étiqueté par un identifiant. Un identifiant correspondra toujours à un sommet racine et ses différentes versions à travers l'arborescence de graphes.

Lorsque l'utilisateur travaille sur son graphe, le graphe génère constamment de nouveaux sommets.

Par conséquent, dans un graphe versionné multicouche, un graphe doit être synchronisé avec tous les autres graphes de sa filiation pour ne jamais allouer un identifiant qui aurait déjà été utilisé dans un autre graphe.

Pour cela, chaque graphe dispose d'une plage d'identifiant qui lui est propre. Cette plage d'identifiants disponibles lui est délivrée par son graphe parent.

Tous les graphes partagent dans leur filiation le même graphe racine. Par conséquent, c'est ce graphe racine qui générera les plages d'identifiants pour les délivrer à son arborescence.

Quand un graphe veut allouer un nouvel identifiant, il doit envoyer une requête à son parent qui lui répondra par une nouvelle plage d'identifiants disponibles.

Le graphe parent doit constamment subvenir aux besoins en plages d'identifiants disponibles de ses graphes enfants.

Ce protocole est récursif. Lorsqu'un parent délivre une plage d'identifiants disponibles, il puise dans sa propre plage d'identifiants disponibles. Si le parent a consommé sa propre plage d'identifiants disponibles, il enverra une requête à son propre graphe parent pour en recevoir une nouvelle.

Branchement d'un nouveau sommet créé par l'utilisateur

Lorsque l'utilisateur crée du contenu dans le graphe qui lui est associé, il est susceptible de créer de nouveaux sommets qui existeront pourtant dans les graphes inférieurs. Nous aurions donc deux fois la même étiquette pour deux sommets différents dans la filiation du graphe.

Pour éviter ce cas, nous faisons appel à une requête de branchement à chaque fois qu'un nouveau sommet est créé dans le graphe de l'utilisateur.

Une requête de branchement va chercher dans les couches inférieures s'il existe un sommet disposant des mêmes informations internes que le sommet nouvellement créé.

Si un tel sommet est trouvé, il est renvoyé comme résultat. Le sommet qui devait être créé n'est alors plus un nouveau sommet racine, mais un nouveau sommet versionné qui complétera l'arborescence d'un sommet racine connu dans les graphes inférieurs.

Table de hachage.

Un tel mécanisme ne peut soutenir une création intensive de contenu de la part de l'utilisateur. Pour cette raison, à chaque graphe est associée une carte de hachages.

Une fonction de hachage de type SHA-2 est définie pour transformer les informations internes d'un graphe en une empreinte de 8 octets.

Sur un nombre de un million de sommets dans la filiation de graphes utilisée par l'utilisateur, le risque de collision faisant coïncider deux sommets aux informations internes différentes a la même empreinte de hachage sera de 5.4* [101 Λ(-12)% lors de la création d'un nouveau sommet.

Lorsqu'un graphe créé un nouveau sommet, il met à jour sa table de hachage faisant correspondre son identifiant avec le 1'empreinte obtenue par la fonction de hachage.

Lors de l'allocation d'un nouveau graphe, sa table de hachage est remplie à partir de l'agrégation de toutes les tables de hachage de sa filiation. Cette agrégation se trouve être directement la table de hachage du parent du nouveau graphe.

Comme nous l'avons vu dans la section 00ΧΧ, l'allocation de graphes est récursive : toute la filiation du graphe est instanciée pour pouvoir instancier ensuite le graphe lui-même.

Par conséquent, l'initialisation d'une table de hachage suivra la même récursion. Chaque graphe verra sa table de hachage initialisée par les empreintes de ses sommets ainsi qu'avec le contenu de la table de hachage de son graphe parent.

Lorsqu'un sommet sera créé par l'utilisateur, une recherche dans la table de hachage du graphe de l'utilisateur sera effectuée. Ainsi, il sera aisé de savoir s'il existe dans la filiation du graphe un sommet racine équivalent à celui qui veut être créé.

Si une empreinte est trouvée, il est nécessaire d'effectuer la requête de branchement. Sinon, on considère qu'il n'existe pas de branchement possible.

Lorsqu'un graphe inférieur se voit ajouter des sommets, il doit informer sa descendance de graphe afin qu'ils puissent mettre à jour leur table de hachage.

Cela ne pose nullement problème, car la modification des graphes inférieurs est un phénomène programmé et peu fréquent, comme la section OOXX le spécifie.

Lorsqu'un graphe est instancié, le graphe parent doit donc lui envoyer sa table de hachage agrégée. Cela représente un envoi d'une taille de 8 méga-octets pour une filiation de graphes d'un million de sommets. Etant donné que les groupes de machines sont tous connectés de manière locale par connexion éthernet, cela induit un temps d'attente de moins de 100 millisecondes pour le chargement d'un nouveau graphe.

En termes de stockage et d'envoi de tables de hachage, on utilisera la propriété récursive de celles-ci en stockant les tables de hachage reçues par le serveur dans le serveur lui-même. Les tables de hachage des graphes se reposeront sur ces données pour se reconstituer.

On réduit de la sorte le nombre de redondance de tables de hachages stockées dans la mémoire vive, en se reposant sur le fait que de nombreux graphes du serveur ont la même filiation. De ce fait, la majeure partie de leurs tables de hachage auront une large base commune. Déconnexion d'un utilisateur

Lorsque l'utilisateur souhaite se déconnecter, il faut désallouer le graphe qu'il manipulait.

Le serveur de routage met à jour durant les requêtes d'allocation une table de dépendance. Cette table référence toutes les dépendances entre les graphes alloués.

Quand un graphe est désalloué, le serveur de routage supprime l'association entre l'identifiant du graphe et l'IP de son serveur dans la table de routage. Il supprime également toute dépendance impliquant le graphe désalloué. A chaque désallocation, le serveur de routage analyse les dépendances de chacun des graphes connus pour voir si il certains d'entre eux n'avaient que pour graphe fils unique actif le graphe désalloué.

Si un graphe n'a plus aucune dépendance dans la table des dépendances, alors il est inutile de le conserver. Le serveur de routage demande au serveur qui héberge le graphe devenu inutile de le désallouer.

Il en résulte une désallocation récursive de toute la descendance du graphe qui n'avait plus de dépendance allouée.

Claims (2)

1. Revendications 1 — Système informatique distribué comprenant une pluralité de serveurs comportant chacun un processeur pour exécuter des traitements informatiques et une mémoire pour l'enregistrement de graphes, ainsi que des moyens de routage entre les serveurs ainsi qu’un serveur d'interfaçage (7) pour traiter des requêtes provenant d'une pluralité d'équipements d'utilisateurs (8), caractérisé en ce que lesdits serveurs sont organisés en N couches de serveurs formant, pour chacune desdites couches, un groupe de serveur, les serveurs d'une même couche présentant une topologie en anneau avec chacun des serveurs muni d'un protocole de communication vers le serveur suivant de l'anneau du groupe de machines, le système comportant en outre des moyens de communication avec un serveur de routage, et en ce que Chacun des serveurs d'une couche communiquant avec chacun des serveurs de la couche directement inférieure. - Chaque serveur d'une couche comprend : - une mémoire cache pour 1’enregistrement de graphes propres à un utilisateur ou à un groupe d'utilisateurs - une mémoire cache pour l'enregistrement de données hachées résumant le contenu des graphes des couches inférieures affiliés aux graphes du serveur Une mémoire cache pour l'enregistrement éphémère de résultats de traitement propres à l'utilisateur, provenant des couches inférieures et/ou de la couche de l'utilisateur Une mémoire cache pour l'enregistrement éphémère de données provenant des couches inférieures. 2 — Système informatique distribué selon la revendication 1 caractérisé en ce que la couche supérieure de serveurs comporte des partitions spécifiques chacunes à un utilisateur. 3 — Système informatique distribué selon la revendication 1 caractérisé en ce que le système comprend aussi un serveur (7) d'interfaçage comprenant les moyens d'interfaçage avec les équipements (8) des utilisateurs. 4 — Système informatique distribué selon la revendication 1 caractérisé en ce que le système comprend aussi un serveur de base de données de type SQL (9) gérant le code attribué à chacun des utilisateurs pour sécuriser l'accès d'un utilisateur au réseau qui lui est propre. 5 — Système informatique distribué selon la revendication 3 caractérisé en ce que le serveur d'interfaçage (7) est constitué par un ordinateur comportant un processeur multi-cœurs pour traiter en parallèle les requêtes des différents utilisateurs et pour exécuter une application de serveur gérant chaque session utilisateur en parallèle. 6 — Système informatique distribué selon la revendication 5 caractérisé en ce que le serveur d'nterfaçage comprend par ailleurs des moyens de cryptage des informations transitant pendant chaque session. 7 — Système informatique distribué selon la revendication 3 caractérisé en ce que le serveur d'interfaçage (7) assure un découplage entre les serveurs des couches (1 à 5) et le serveur de routage (6) et les équipements des utilisateurs (8) pour assurer une protection des données enregistrées dans le système. 8 — Système informatique distribué selon la revendication 3 caractérisé en ce que le serveur d'interfaçage ( 7 ) communique uniquement avec le serveur de routage ( 6 ), la couche supérieure (1) de serveurs (11 à 14) et le serveur SQL (9). 9 — Système informatique distribué selon la revendication 7 caractérisé en ce que le serveur d'interfaçage (7) est constitué par une machine unique. 10 - Procédé de requêtage en temps réel d'un système d'information structuré en graphe multicouche conforme à la revendication 1, constitué par un ensemble de groupe de machines de serveurs, un serveur de routage et par au moins un serveur de base de données, lesdits groupe de machines de serveurs hébergeant les données spécifiques aux éléments dudit graphe multicouche ; Ledit procédé de requêtage comportant î a) des étapes d'instanciation des éléments dudit graphe versionné multi-couches général consistant : à sélectionner l'un desdits serveurs en fonction de paramètres comprenant la charge CPU de chacun des serveurs, la mémoire disponible pour chacun des serveurs, la classe d'appartenance de l'élément, ainsi que la similarité entre les filiations des éléments déjà instanciés sur le serveur et la filiation de l'élément à enregistrer sur le serveur sélectionné - à propager 1'instanciation dans le réseau de groupe de machines b) Des étapes de complétion desdites données spécifiques hébergées, consistant à transférer récursivement des données entre deux couches adjacentes successives de serveurs, en réponse à la détection d'une lacune d'une information enregistrées dans la couche supérieure Lesdites données transférées étant enregistrées dans les caches mémoire associés aux serveurs des couches inférieures et de la couche supérieure c) Des étapes de synchronisation des données entre les couches inférieures et supérieures permettant de conserver 1 ' intégrité de la structure de données lors de la production de contenu par l'utilisateur.
2. 11 - Procédé de requêtage en temps réel d'un système d'information structuré en graphe multicouche selon la revendication 10 caractérisé en ce qu'il comporte une étape de destruction progressive des informations non utilisées.