ATTENTION : discussion ouverte qui nécessitera une étude algorithmique approfondie avant réalisation, même si elle est conceptuellement validée par le core groupe de GLPI.

Motivations

Un ordinateur a intrinsèquement une structure arborescente : sur le bus maître sont connectés les CPUs, la mémoire, des bus PCI, USB ...
Sur ces bus on trouve des périphériques (carte graphique, contrôleur de disque ...).
On peut également retrouver d'autres BUS sur certaines cartes (carte contrôleur USB sur bus PCI, GPIB ...), voire de la mémoire standard sur certains cartes contrôleur de disque.
Attaché à la machine il y a le système d'exploitation voire un hyperviseur. Sur cet OS sont installés des logiciels ou des machines virtuelles. Dans ce dernier cas, nous retrouvons une autre arborescence PC telle que décrite précédemment avec le bus maître les CPUs, la mémoire ...

Nous retrouvons une structure similaire quoique plus simple pour les switchs réseau ou les imprimantes. Par exemple, sur les switchs, il y a des ports qui accueillent directement le câble réseau et d'autres qui accueillent des GBIC qui sont des sous-composants avec des caractéristiques intrinsèques qu'il peut être utile de stocker (adresse MAC, numéro de série ...).

David: T'as aussi des chassis qui comportent des lame serveurs, des switchs, des alimentations..., donc on mélange les grands types de matériel 'GLPI' actuels.

Limitation actuelle

Pour chercher les composants logiciels ou matériels d'un ordinateur, on utilise le mécanisme getSearchOptions avec une recursivité prédéfinie : tout est directement rattaché à l'ordinateur central. Dans le cas des sous-composants (ie. GBIC sur un port réseau, mémoire sur carte contrôleur ...) les requêtes semblent plus complexe.
Elles pourraient même alourdir le système pour des cas qui resteront rare tant que les systèmes d'import de données extérieures n'en tiendront pas compte.

Proposition

Je propose de normaliser toute cette hiérarchie par élément physique (ordinateur, switch, imprimante) dans une table arborescente indérependante des tables de composants.
Outre les éléments indispensables à la gestion de la hiérarchie, cette table intègrerait deux champs : itemtype et items_id.
Donc, pour retrouver tous les composants d'un élément, il suffit d'une requête dans cette tables pour recueillir l'ensemble des couples <itemtype, items_id> qui définissent les enfants de l'élément qui nous intéresse.

Amélioration des requêtes de la classe Search

Jusqu'à maintenant, nous décrivions la hiérarchie complète dans les requête SQL à l'aide de LEFT JOIN. Avec cette nouvelle hiérarchie, la requête SQL serait plus simple :

  SELECT **fields**
  FROM `glpi_itemhierarchies`
  LEFT JOIN `**component table**` ON (
       `**component table**`.`id` = `glpi_itemhierarchies`.`items_id`
       AND `glpi_itemhierarchies`.`itemtype` = '**component type**')
  LEFT JOIN `**other component table**` ON (
       `**other component table**`.`id` = `glpi_itemhierarchies`.`items_id`
       AND `glpi_itemhierarchies`.`itemtype` = '**other component type**')
  WHERE **hierarchy request**

Jusqu'où aller dans la hiérarchie ?

D'un côté, nous pourrions envisager de regrouper les différents éléments (ordinateurs, switchs ...) dans un élément plus générique qui serait, par exemple, la baie informatique (ou "rack") ou encore les barettes électriques d'alimentations elle-même regroupées sur un onduleur etc...

À l'autre bout, je suggère d'ajouter les éléments "connexes". Par exemple, pour un équipement, mettre des liens vers les utilisateurs ou encore les réseaux wifi attachés aux cartes wifi. Ainsi, en tant que descendants d'un item selon la hiérarchie, la recherche des DropDown attachés (location, software, entities ...) serait simplifiée.

Jusqu'où s'arrêter dans la hiérarchisation ?

À terme, nous pourrions remplacer la définition directe des connexités d'un équipement actuelle (pour un ordinateur : operatingsystems_id, locations_id, domains_id, users_id ...) par cette structure arborescente.

Nous pourrions même tout structurer dans l'arborescence des entités. Par exemple, les entités contiennent des lieux qui contiennent des équipements (PC, switchs, imprimantes ...) qui contiennent des composants et ainsi de suite.

Mais avant de telles mises en oeuvre, il faudrait le valider conceptuellement et valider l'utilisabilité d'un tel système au regard des temps de réponse des requêtes SQL.

Implémentation

Hormis la validation par les membres du core groupe et les évolutions dans le coeur de GLPI, la grosse limitation de mise en oeuvre d'une telle hiérarchie est liée à la structure de donnée hiérarchique elle-même.

Modèle par liste adjacente

Ce modèle est celui en cours dans GLPI : chaque noeud possède l'identifiant de son noeud père. Cela permet de retrouver tous les noeuds fils ou les noeuds père par récursivité sur les identifiants.
Une première optimisation a été mise en oeuvre dans GLPI : la création d'un champs de "cache" (ancestors_cache, sons_cache). Cependant, ce mécanisme de cache ne semble pas adapté à une utilisation dans les requêtes de type LEFT JOIN. De plus, ce cache est une information redondante volatile en cas de modification de l'arborescence (ajout, dépplacement et retrait d'un noeud). Enfin, la recréation du cache de l'arborescence peut être très lourde.

Mais, sans passer par ce mécanisme de cache, on peut optimiser le modèle de donnée.

Changement de base de donnée

PostgreSQL, Oracle et SQLServer intègrent nativement des requêtes récursive. Ce n'est pas le cas de MySQL. Il pourrait être opportun de changer de serveur de base de donnée afin de profiter de ce mécanisme qui semble être l'un des plus optimums pour gérer efficacement une hiérarchie en base de donnée SQL.

Sans changer de base de donnée

Contrairement aux gestionnaires de base de données pré-cités, MySQL propose un mécanisme de variable de session et fonctions qui peuvent facilement simuler ces requêtes récursives. Même si elles sont moins efficaces que les mécanismes intégrés, cela permettrait d'améliorer cette gestion de la hiérarchie.

Mais ce n'est pas optimal

Si, comme préconisé précédemment, on envisage une hiérarchie plus globale qui intègre tous les noeuds d'un équipement, cette représentation des données ne semble pas optimale. En effet, il faudra toujours faire une récursivité afin de retrouver les noeuds qui nous intéressent. Ce parcourt peut être très gourmand en cas de base de données ayant beaucoup de niveaux.

Path finding

Une seconde méthode de définition d'une hiérarchie est l'utilisation de "path finding". À l'instar du champs completename dans les structure arborescente, cela consiste à définir une chaîne de caractères qui concatène, dans l'ordre du plus lointain au plus proche, des parents d'un noeud donné.
Cependant, cette méthode est lourde car elle requiert une comparaison de chaînes de caractères pour chaque entrée de la table.

Nested Set Model

Le Nested Set Model est un modèle relativement simple à implémenter. Chaque entrée de la table contient un intervalle composé de deux entiers. Tous les noeuds enfant sont inclus dans cet intervalle.

Malheureusement, chaque modification de la table (insertion, suppression ou déplacement d'un noeud) requiert de modifier les noeuds qui suivent le noeud modifié pour adapter leurs indexs.
Cette opération peut être particluièrement lourde sur une très grosse base de donnée.
Elle peut être d'autant plus lourde qu'il faut verrouiller (lock) la base de donnée à chaque opération d'insertion pour éviter des conflits d'accès aux ressources lorsque plusieurs utilisateurs travaillent en même temps dessus.
De plus, dans le cadre proposé de recensement hiérarchique des composants, la table serait particulièrement volumineuse.

Il existe également une limitation de performance dans la recherche des noeuds pères pour un noeud donnée car l'opération n'est pas symétrique : au niveau SQL, l'opération de recherche des éléments qui contiennent un intervalle (recherche des parents) est beaucoup plus lourde que l'opération de recherche des éléments qui sont contenus dans un intervalle (recherche des descendants).

Optimisation du Nested Set Model par restriction de domaine

En étudiant plus précisément les données contenues dans cette base de donnée des équipements, nous pouvons constaté qu'en fait, il y aura beaucoup d'équipements en tête, mais que chaque équipement aura une arborescence "peut développée". Donc, nous pourrions envisager de limiter chaque Nested Set à chaque équipement en ajoutant à chaque noeud de la structure les champs equipmenttype et equipments_id). Ainsi, cette renumérotation ne concernerait que les composants d'un équipement donné.

Nous pourrions également envisager d'utiliser ce modèle pour la table des entitées. En effet, ces dernières évoluent généralement peu. Donc, le mécanisme pénalisant de renumérotation ne semble pas trop contraignant pour cette table.

Nested Intervals Tree

En étudiant les défauts du Nested Set Model, des chercheurs de la société Oracle ont proposé le Nested Intervals Tree, qui repose non plus sur des index entiers, mais sur des index rationels. Ainsi, seul les noeuds à insérer sont modifiés.
Cependant, l'algorithmie doit être étudiée car certaines opération peuvent permettre un certain gain de performance, notament sur la recherche de parents (cf. limitation de performances cité précédemment).

De plus, il faut étudier l'impact d'une telle structure sur une grosse base de donnée. En effet, il faut prévoir le verrouillage de la base de donnée pour éviter un conflit d'accès aux ressources entre l'obtention depuis la table des anciens index d'un noeud que l'on souhaite modifier, le calcul des nouveaux et la modification de la table.