Recherche opérationnelle - Programmation linéaire - Application à la virtualisation

Jean Baptiste FAVRE

mars 2011

English version is available here: Linear programming applied to virtualization

Introduction

La recherche opérationnelle est une discipline mathématique fournissant des outils d'aide à la décision. Parmis les problème pouvant être résolus à l'aide de ces techniques, on trouve les problèmes combinatoires. Un exemple de ce type de problème: le dimensionnement d'une infrastructure de virtualisation, ou comment trouver la meilleure combinaison de serveurs physiques pour héberger des machines virtuelles au meilleur coût?

Cette fois, nous n'utiliserons pas GLPK mais LibreOffice. Grâce à l'optimiseur linéaire intégré à la suite bureautique, il devient très simple et presque convivial de résoudre ce type de problème. Il ne s'agit évidemment que d'un exemple parmis tant d'autre de ce que l'on peut faire avec LibreOffice.

Énoncé du problème

Une entreprise souhaite déployer une plate-forme web sous forme de machines virtuelles. Ces machines virtuelles ont bien entendu différentes fonctions: Front, Cache, Proxy, BDD slave et BDD master.

Les équipes techniques de l'entreprise ont effectué des tests de la future plate-forme web et ont déterminé les besoins en terme d'I/O disque, CPU et mémoire. De plus, l'entreprise ne souhaite pas acquérir de nouveaux types de matériels. Il faut donc héberger cette plate-forme sur des serveurs existants. Ces serveurs sont de 3 types et possèdent des capacités I/O disque, CPU et RAM connues des équipes techniques, là encore après des tests. De plus, les équipes techniques ont constaté des effets de seuil, qui dégradent les performances des serveurs. Ces effets de seuils, ici appelés Saturation sont également indiqués.

<Avertissement> Les valeurs présentées ici n'ont pas de réelle base concrètes. Elles ne sont ici que pour illustrer mon propos. L'important ici est de conserver une cohérence par critère. Par exmple, les I/O disque peuvent être indiquées en iops ou opérations I/O par seconde. De même pour le CPU dont la valeur peut représenter un indice relatif de performance.</Avertissement>

Besoin des machines virtuelles par type
 I/OCPURAMNombre de VM
Front10075840
Cache1501501620
Proxy502503220
BDD Slave2002006410
BDD Master2502506410

Connaissant les besoins de chaque type de machines virtuelles, ainsi que leur nombre, il est trivial de déterminer le besoin total.

Capacités des serveurs en service
 I/OCPURAMCoût d'hébergementCoût d'achatDurée d'amortissement
SRV190090012855550036 mois
SRV26007506440300036 mois
SRV33006004830200036 mois
Saturation60%60%95%  

Là encore, il est trivial de déterminer la capacité totale.

L'objectif final est de déterminer le nombre de serveur de chaque type à acheter pour pouvoir héberger la plate-forme tout en minisant les coûts.

Énoncé mathématique du problème

Soit x1, x2 et x3 le nombre de serveurs de type SRV1, SRV2 et SRV3 à acquérir.

Pour chaque critère (I/O disque, CPU et mémoire), il faut bien entendu que le besoin total des machines virtuelles soit couvert par l'apport des serveurs physiques. Pour chacun des critère de chacun des serveurs, on applique la saturation, c'est à dire que seuls 60% de la capacité I/O disque, 60% de la capacité CPU et 95% de la capacité mémoire sont effectivement "disponibles".

Ceci nous donne 3 contraintes à respecter:

Les valeurs de droite pour chacune de ces inéquations représentent le besoin total des machines virtuelles.

Le coût total de la plate-forme web dépendra du nombre de serveur de chaque type à acheter. Le calcul de coût est finalement assez simple:

Résolution avec LibreOffice

Une fois les bases du problème posé, nous pouvons le résoudre. Dans ce cas précis, nous allons utiliser OpenLibreOffice, et plus précisément Calc. Vous pouvez récupérer le classeur Calc utilisé pour cet exercice.

Aperçu de la feuille Calc d'optimisation en virtualisation

Les cellules en vert clair peuvent, et devraient, être modifiées par vous. Ceci vous permettra de jouer plusieurs scénarios.

Les cellules contenant les informations Besoin des machines virtuelles et Capacités des serveurs peuvent également être modifées. Bien évidemment, il faudra y inscrire des valeurs représentatives de votre matériel et/ou machines virtuelles.

En revanche, ne modifiez rien en dehors de l'étape 1, sauf à savoir ce que vous faites: l'étape 2 consolide les besoins et capacités, l'étape 3 vous donne les informations Nombre de serveurs physiques. Quant à l'étape 4, vous aurez deviné qu'elle vous donne le résultat final avec le coût de votre infrastructure. Le tout utilise des formules Calc, il est donc important de ne les modifier qu'en connaissance de cause.

Utilisation de l'optimiseur LibreOffice

Une fois la feuille Calc remplie avec les valeurs, utilisez le menu Outils > Solveur comme indiqué à l'image ci-dessous

Menu LibreOffice Outils - Solveur

Dans la fenêtre qui s'ouvre, la cellule cible correspond à notre objectif, soit le coût final. il s'agit donc de la cellule F24. L'objectif étant de minimiser les coûts, vous cocherez l'option Minimum. Les cellules à modifier concernent le nombre de serveurs physiques, soit les cellules C24 à E24. Enfin, les contraintes à respecter sont:

Fenêtre du Solveur LibreOffice - Paramétrage des champs

Nous y sommes presque. Un dernier détail à régler: il faut s'assurer que le nombre de serveur soit positif d'une part, et surtout un nombre entier. Je doute que 2,3215 serveur vous soit d'une quelconque utilité, ni à vous, ni au directeur financier :). Pour cela, cliquez sur Options et cochez les 2 cases comme indiqué ci-dessous:

Fenêtre des options du Solveur - Paramétrage

Une fois les Options enregistrées, vous pouvez alors demander la résolution du problème en cliquant sur le bouton Résoudre de la fenêtre Solveur. Le calcul est alors effectué et le résultat affiché:

Fenêtre de résultat du Solveur après optimisation

Vous aurez noté que la feuille Calc a été mise à jour. Cliquez sur Conserver le résultat pour fermer la fenêtre du Solveur et retourner à la feuille Calc:

Aperçu de la feuille Calc après optimisation

Vous êtes alors capable d'annoncer l'investissement nécessaire pour la mise en production de la plate-forme:

Le coût total étant de 4833,33 € par mois, soit 174 000 € sur la période d'amortissement.

Conclusion

Vous pouvez également tester différents scénarii, par exemple pour tester l'impact d'un ajout de RAM dans un type de serveur. Pour cela, modifier la ou les cellules à l'étape 1 et recommencez l'optimisation. À chaque fois, l'optimiseur vous donnera la combinaison dont le coût sera le plus faible... Magie des mathématiques !

Autre exemple, comment "neutraliser" un type de serveur physique ? Simplement en mettant ses capacités à 0 ! :)

Bien entendu, lancer l'optimisation manuellement peut se révéler fastidieux. À cela, une solution: les macros. L'optimiseur est un composant de LibreOffice parmis d'autre, et il est poassible de le contrôler à partir d'une macro. Vous pourrez alors actualiser la feuille d'un simple clic sur un bouton. Mais ça, c'est une autre histoire.

Cet exemple est évidemment, et volontairement, simplifié. Bien d'autres paramètres entrent en ligne de compte. Mais, maintenant que vous savez comment faire, libre à vous d'adapter la feuille de calcul. À titre d'exercice, vous pouvez chercher la répartition idéale des machines virtuelles sur les différents serveurs.

À propos de Jean Baptiste FAVRE

Je passe le plus clair de mon temps libre sur Internet à travailler sur GNU/Linux avec Debian ou CentOS, la virtualisation avec Xen et KVM et les technologies cluster avec Corosync et OpenAIS. Particulièrement intéressé par Linux, Netfilter, la virtualisation, le monitoring et les clusters, la plupart de mes travaux personnels sont publiés sur ce site et les autres ne sauraient tarder.

A titre professionnel, j'administre des serveurs sous RedHat ou CentOS ainsi qu'une ferme de serveurs VMware ESXi version 4.

De temps, à autre, je parviens à lâcher mon clavier pour lire un bon bouquin tout en écoutant de la musique, mais ça ne dure jamais longtemps.

License

Creative Commons License Cette publication est publiée sous contrat Creative Common by-nc-sa

Valid XHTML 1.0 Strict | Valid CSS | contrat Creative Common by-nc-sa

Table des matières

  1. Introduction
  2. Énoncé du problème
  3. Énoncé mathématique
  4. Résolution avec LibreOffice
  5. Utilisation de l'optimiseur LibreOffice
  6. Conclusion
  7. À propos ...
  8. License