Il y a de cela un an, j'ai pris au mot l'auteur de Nagios lorsqu'il écrit dans la documentation de Nagios concernant les vérifications effectuées au démarrage :

"That means all you CompSci graduate students who have been emailing me about doing your thesis on Nagios can contribute some code back. :-)"

Je ne sais pas qui ils sont, mais j'ai essayé de résoudre le problème poser : la vérification des liens de parentés dans Nagios était horriblement longue.

En fait, j'ai même réussi.

Pour rappel, Nagios permet de définir pour un host un ou plusieurs parents (en terme de réseau):

• De cette manière, si un switch tombe par exemple et que l'administrateur a bien configuré ses serveurs pour qu'ils soient des fils du switch en question, il ne va recevoir qu'une seule alerte, celle du switch, plutôt que N alertes des serveurs. C'est la dépendance réseau.
• Cette relation forme un arbre : Nagios remonte les branches pour trouver la cause du problème. La racine est le noeud Nagios lui même.
• Mais que se passe-t-il si on autorise les cycles dans la configuration? Nagios va tourner en rond lors de la recherche de l'erreur! :evil:

Pour éviter cela, Nagios fait une vérification au démarrage afin de trouve les cycles dans cette configuration s'ils existent. Un premier algorithme naïf est en O(n²). Et bien dans Nagios arrivait à faire du O(n3)...

Vous aller me dire que ce n'est pas si grave que ça. Et bien en fait si. Prenons une configuration "costaux" de 40000 hosts avec des relations de parentées. Et bien la vérification prends 70s sur un Core2 à 2.4Ghz. Ce n'est pas négligeable, car pendant ce temps, il n'y a pas de supervision...

J'ai donc décidé d'appliquer mes cours de théorie des graphes et de faire un simple parcours en profondeur, aussi nommé Deep First Search (DFS). C'est donc un algorithme récursif, ce qui n'a rien d'étonnant dans le monde des graphs :mrgreen:

Son fonctionnement est légèrement différent du DFS standard, car le but n'était pas de savoir si une boucle existait, mais de trouver TOUS les noeuds étant dans une boucle, afin d'aider l'utilisateur à corriger les problèmes en un passage.De plus, il n'y a pas de noeud root sur cet arbre de relation. On peut potentiellement partir en plein milieu de l'arbre, ce qui ne facilite pas les choses.

Les noeuds peuvent avoir plusieurs attributs :

• DFS_UNCHECKED : 0 (valeur par défaut)
• DFS_TEMPORARY_CHECKED : 1 (a été parcouru une fois)
• DFS_OK : 2 (pas de problème)
• DFS_NEAR_LOOP : 3 (a des fils à problèmes)
• DFS_LOOP_INSIDE : 4 (fait parti d'une boucle)

Nouveau test avec ce parcours en profondeur au lieu de l'algorithme initial : 0.006864 sec :-D

Après une longue période de non réponse de l'auteur de Nagios et le "coup de pied au cul" de Icinga avec leur tentative de Fork (NOTE 2021: bah plus qu'une tentavive finalement ^^), de nouveaux développeurs ayant accès au CVS de Nagios ont été nommés. C'est ainsi que mon patch a été intégré dans la version 3.1.2 de Nagios et que des milliers d'administrateurs vont voir leur Nagios démarrer bien plus rapidement.

Reste à appliquer ce principe aux autres relations de dépendances dans Nagios...

NOTE 2021: Ca reste à ce jour un de mes algorithmes favoris, car trouver une boucle est trivial, trouvé l'ensemble des éléments les constituant c'est tout autre chose ^^

Jean Gabès