Bonsoir,

Vous l'aurez compris avec mes posts sur le topic "lib réseau", le load control c'est ma passion et mon travail.

Pourquoi gérer la charge?
Dans le monde d'internet et des réseaux informatiques, si la connexion échoue, tant pis.  Mais n'est-ce pas dommage?  Pourquoi se passer de mécanismes simples à mettre en oeuvre, qui améliorent l'expérience de l'internaute?  Parce que cela coute cher, n'est pas primordial, etc.

Soit.  Maintenant, vous sortez votre super jeu en ligne, le succès est au rendez-vous, et là boum! victime du succès, les serveurs ne suivent pas.  Les villes surpeuplées sont ingérables, le ping augmente, et finalement c'est la déconnexion.  Pas assez de moyens pour avoir des serveurs plus performants, vous voilà pris au piège.
Que faire?

Première étape: analyser les risques
Vous vous attendez à ce que certaines parties de votre jeu soient plus chargées que d'autres, c'est indéniable.  Mais à quel taux?  Un exemple simple: WoW.  La dernière extension a introduit des nouveaux continents, résultat: les vieux lieux sont quasi déserts.  Si votre jeu gérait statiquement cette situation en fonction du lieu, c'est perdu.

Deuxième étape: quels mécanismes?
Si vous possédez un seul serveur, pas de problème. Stop! ce n'est pas vrai.  Comment vos process vont-ils gérer les connexions?
Vous possédez plusieurs serveurs, pas de problème. Re-stop! quel serveur choisir en s'assurant que chacun est utilisé au mieux?
Dans les 2 cas, il faut gérer 2 choses: la balance de la charge, et le refus de connexion pour garder la charge optimale.

La balance de charge
L'idéal est d'avoir un point central, appelé dispatch ou broker.  C'est lui qui va utiliser un algorithme de balancement et distribuer la charge.  Il doit être simple, léger, rapide et efficace.  Il doit pouvoir gérer un changement de situation, par exemple une charge CPU trop élevée, tout en laissant passer le nombre optimal de connexions.  Pour cela, on utilise un monitor.  Idéalement centralisé, il fera office d'observateur et rapportera au process de balancement en cas de surcharge CPU.

Lors de l'étude théorique des risques, on aura modélisé la charge théorique supportable par chaque serveur et les process de traitement de chaque serveur.
A chacune de ces entités, on affectera un poids.  Ensuite, le process de balancement, en fonction des poids, distribuera la charge.  Le monitor analysera la charge CPU (entres autres) de chaque entité et en informera le process de balancement sur une base périodique.  Plus la charge observée augmentera, plus le poids associé diminuera et donc moins de connexions cette entité recevra.  Mais en quelles proportions?  C'est le controle de charge.

Le controle de charge
Il ne faut pas pousser le bouchon trop loin dirait-on... il en est de même pour le CPU.  Charger celui-ci à 100%, ou à 95%, ne représente pas un usage optimal de la machine. 80% par exemple est un bon quota.  Oui mais comment se limiter à ce taux?
Au démarrage de la charge, le serveur et ses process ne sont pas trop chargés.  On peut donc sans risque laisser passer les connexions, messages, etc. Ensuite la charge monte, il va falloir commencer à ralentir.  Pour ce faire, on va considérer un régulateur PID (proportionnel-intégral-dérivé), application la plus courante, appliqué au nombre de connexions que l'on désire accepter, le maximum (donné par les limites calculées) est appelé consigne.  Le système va calculer l'erreur entre la quantité de connexions actuelles et la consigne, et croître le plus vite possible tout en tentant de limiter les risques de dépassement (overshoot) car on sait que plus de connexions que la consigne peut être destructeur.  Mais ceci n'indique que la façon dont la charge doit évoluer, elle n'est pas effectivement limitée.

On va donc coupler cette courbe de charge à un algorithme de controle de charge en tout ou rien basé sur un taux d'acceptation.  Un algorithme très simple est celui dit du seau percé: le seau se vide à un certain taux Tf, ou taux de fuite, et se remplit à un taux Tr, ou taux de remplissage.  Le fonctionnement est simple: si le seau se remplit plus vite qu'il ne se vide, il déborde, et vice-versa.  Dans notre cas l'eau représente le flux de connexions.  Chaque fois que le seau manque de déborder, on refuse les connexions, et quand il s'est vidé assez, on accepte à nouveau, etc. etc.  Grâce à la courbe de charge en PID et le seau percé, on obtient un système de controle dynamique, c'est-à-dire que le PID va modifier le taux de fuite Tf de manière à ce que le seau soit toujours à la limite de déborder, mais sans le faire, et ce quel que soit Tr.  Chaque remplissage réussi (c'est-à-dire, qui ne cause pas le débordement du seau) va itérer le PID afin de faire monter la courbe.  Un débordement du seau est synonyme de refus mais n'a pas d'effet sur la courbe, qui reste donc à sa position.  Le fonctionnement est donc: tant que les connexions sont acceptées (pas de débordement), on itère le PID, qui modifie Tf, et à chaque moment le seau est à sa limite et le système en équilibre.  Une propriété importante de ceci est que Tf est égal au taux de connexions acceptées et est proportionnel à la valeur du PID.  Mais si la consigne est mal modélisée?

La boucle de rétroaction
Il se peut que, pour une raison X ou Y, le serveur ne puisse pas gérer le nombre de connexions espéré.  On ne peut pas aller au maximum car la situation est telle que le CPU est en passe d'être surchargé avant que le maximum de connexions ne soit atteint.  C'est ici que le monitor entre en jeu: il va informer le seau percé que l'on approche de la limite CPU.  Le PID va alors se caler sur ce nouveau comportement de feedback - proportionnellement au delta mesuré par le monitor - de manière à diminuer Tf et donc augmenter le nombre de refus, déchargeant progressivement le CPU.  Pour éviter un risque de reprise qui serait destructeur, on va même forcer le PID à redescendre plus que nécessaire, afin d'éviter qu'en cas de pic de connexions le système n'explose avant d'avoir le temps de réagir.  Cette descente est à définir avec soin car elle caractérise l'amplitude de l'oscillation (voir paragraphe suivant).

Le CPU va donc être déchargé, ce qui va impacter le monitor qui à son tour impactera de moins en moins négativement le PID.  La courbe de PID va remonter, Tf également et donc la charge va augmenter, et ainsi de suite (oscillation) jusqu'à se stabiliser (l'amplitude de chaque oscillation successive va diminuer puisqu'elle est fonction de l'erreur entre la limite CPU et celle observée).  Cette oscillation est la boucle de rétroaction.  Lorsque la courbe de PID se stabilise, l'équilibre est trouvé entre la charge CPU limite et le taux maximum de connexions en fonction de cette charge.  Note: puisque le PID se cale sur la boucle de feedback, même si Tf est à 0, le fait que le monitor n'indique plus de surcharge aura pour effet de faire itérer le PID positivement, permettant la reprise du système.

Il en résulte que le système est quasi idéalement chargé (l'idéal n'existant pas), car toute connexion supplémentaire provoquerait une surcharge CPU, et un défaut de connexion une sous charge.  Il est important de noter qu'au démarrage, le système part avec le maximum de refus afin de ne pas arriver trop vite à la limite surtout si le CPU supporte mal une montée directe de charge; cela permet de protéger le système et assurer une montée en douceur.  Chaque variation de charge du CPU aura un effet sur le nombre de connexions acceptées; de plus, ce système est rapide et précis, et si bien configuré (notamment au niveau du coefficient de montée de la courbe) on évite l'overshoot.  Il peut traiter indifféremment les situations transitoires (pic de charge dû notamment à un process parasite) ou de longue durée.

Quelques exemples
- tenir un oeuf entre 2 doigts: si on serre trop fort, on casse l'oeuf; si on ne serre pas assez fort, l'oeuf tombe.  C'est la rétroaction.  Elle est faite de manière naturelle par l'homme.
- lecteur CD de voiture: en cas de choc (trou dans la route, etc.), un système d'amortisseur compense le choc pour maintenir la lentille en position et assurer la lecture du CD.  C'est un exemple d'application de tout le mécanisme présenté plus haut.  Le choc représente une arrivée massive d'eau dans le seau (le mouvement de translation de la lentille), la courbe PID tente de faire placer la lentille à distance optimale du CD (consigne), le monitor est le calculateur du delta de la distance modifiée due au choc, et au résultat la lentille sera placée à distance optimale du CD, c'est-à-dire en assurant une lecture en fonction de l'état de la route.  Evidemment les lecteurs CD peuvent ne pas fonctionner tout à fait ainsi, mais cela permet d'imager l'usage de cet algorithme.
- remplissage de caisses de tailles différentes avec des balles: le monitor va analyser les caisses et le nombre de balles, et piloter le bras robotisé qui va remplir les caisses en s'assurant que les caisses sont pleines quasi en même temps.  C'est un balancement de charge.  Si une caisse est retirée, le bras ne doit plus remplir que les caisses restantes et arrêter s'il n'y a plus de place.  C'est un contrôle de charge associé à un balancement.

Quelques liens
http://fr.wikipedia.org/wiki/Seau_perc%C3%A9
http://fr.wikipedia.org/wiki/R%C3%A9gulateur_PID

Voilà, c'était très long et j'en suis désolé, mais j'espère que cela vous intéressera.

Bonne soirée,
valholl

PS: la prochaine fois que vous prendrez un bain, imaginez-vous un robot analysant le niveau d'eau et pilotant le robinet, et si gaspiller l'eau ne vous pose pas de problème (et c'est mal!), enlevez le bouchon et regardez le robot tâcher de récupérer le coup

Dernière modification par valholl (10-01-2009 00:15:38)

très intéressent
merci !

De rien, mais j'ai dû modifier un peu pour éclaircir certains passages ^^"

yamashi :

Tu travailles uniquement sur d'ancienne technologie il y a eu pas mal d'évolution depuis les clusters fait maison maintenant tout se fait seul...

Tout se fait seul grâce à ces techniques de régulation justement, implémentées dans des kernel, CPUs ou des systèmes embarqués

Note bien que c'est la technique que je présente, pas le fait qu'il faut l'implémenter soi-même... quand cela existe tout fait, il faut bien entendu l'utiliser.  Mon souci majeur est que, oui les clusters automatiques existent, mais beaucoup ne les utilisent pas, ou ne comprennent pas comment ils fonctionnent, et j'espère que grâce à ceci ils ont une explication

valholl

Cuda = Réseau ?

Non cuda c'est le langage de prog inventer par nvidia pour utiliser les cartes graphiques comme processeur.

Cool !