Équilibrage de charge des serveurs Web

L'Internet subit de profonds changements en passant d'une infrastructure de communication à un média de gestion d'une multitude de services[1]. Avec la croissance rapide du stockage de l'information dans les serveurs Web du monde entier, rechercher et obtenir une donnée est devenu un comportement commun[2]. L'explosion du trafic sur le World Wide Web a entrainé une rapide augmentation du nombre de requêtes sur les sites Web populaires[3] - [4] - [5]. La plupart des services fournis par ces sites peuvent ainsi recevoir un nombre très important de connexions des clients dans une période très courte[2]. De plus, le trafic Internet en général et du World Wide Web en particulier a augmenté de manière exponentielle, et cette croissance est amenée à continuer[6].

Ce trafic grandissant peut entrainer des congestions importantes du réseau informatique[3] - [2] - [6] et des temps de réponses élevés[2] - [4]. Ces perturbations peuvent avoir pour conséquence une instabilité du site[2] et du service pour les utilisateurs[4]. Pour un site Web populaire, la congestion réseau et la surcharge des serveurs peuvent amener à des problèmes sérieux dans l'avenir[6].

Ces changements profonds de l'Internet placent le serveur Web au centre d'une infrastructure de services électroniques[1] - [7] et d'applications critiques[8], augmentant les exigences en termes de qualité de service, de disponibilité et de fiabilité dans un environnement imprévisible, rapide et très dynamique[1] - [7] - [8]. Les systèmes Web doivent être capables de démarrer petit et de grossir avec l'augmentation de la demande[7], créant un besoin de serveurs Web plus nombreux et plus puissants capables de servir les utilisateurs Internet[9]. L'augmentation croissante de la demande pour des serveurs Web de qualité est aujourd'hui incontestable[10].

L'amélioration de la performance des serveurs Web et la garantie de la fiabilité et de la disponibilité d'un site Web sont des notions importantes[2]. C'est pourquoi il arrive un moment ou soit le serveur Web doit être renforcé, soit la charge doit être répartie entre plusieurs serveurs[11]. Mais les sites Web populaires ne peuvent pas faire confiance à un seul serveur puissant pour faire face à la charge de requêtes toujours en augmentation[12]. La scalabilité et la disponibilité peuvent être fournis par une architecture Web qui régule les requêtes clientes à travers différents serveurs de manière transparente[12]. Dès lors comment fabriquer une grappe de serveurs Web qui traite et répond facilement aux requêtes devient un problème majeur[2].

Par le passé la seule solution pour élargir la capacité serveur était de remplacer l'ancien serveur par un nouveau. Perdre l'investissement dans l'ancien serveur pour en racheter un autre est une solution à court-terme et couteuse. Une solution à long terme passe par une scalabilité incrémentale qui fournit la possibilité de croitre graduellement avec la demande[9]. Pour construire des serveurs Web évolutifs, les constructeurs et les sites Web populaires se sont massivement tournés vers les architectures distribuées[13] - [14] - [15]. Les grappes de serveurs Web sont ainsi devenues l'une des principales solutions pour accroitre la disponibilité et éviter la surcharge d'un serveur seul[2].

Mais, alors que le World Wide Web peut apparaître comme possédant une scalabilité intrinsèque à travers la distribution des ressources sur des serveurs décentralisés, il existe des exemples où cette forme de distribution de charge est couteuse[16]. D'où l'importance d'un bon équilibrage de charge, qui peut être défini comme le processus de distribution des requêtes sur différents serveurs pour fournir un meilleur temps de réponse[17].

Logo de la NCSA

Le serveur Web de la NCSA subit un pic de charge, entre octobre et décembre 1993, qui surpassa sa capacité à répondre. La première solution fut d'utiliser un serveur informatique plus puissant qui ne tint pas la charge en février 1994. La NCSA a alors déterminée que la seule solution viable à long terme passait par une distribution de charge multi-serveurs[18].

La NCSA possédait deux solutions au problème de charge de son serveur Web : diviser l'arborescence à travers différents systèmes, chacun répondant à un nom d'hôte unique et traitant une partie de l'arbre. Cette solution requérait beaucoup de manipulations et entrainerait la cassure de liens existants, entrainant une grande complexité et un impact sur la communauté utilisateur. La deuxième solution était de partager l'ensemble des documents à travers plusieurs serveurs, chacun répondant à un nom d'hôte commun. Cette solution permettait de gérer la sollicitation croissante des serveurs tout en ayant peu d'impact sur la communauté utilisateurs[19].

L'architecture informatique mise en place permit à la NCSA d'augmenter dynamiquement la capacité des serveurs Web. L'équilibrage de charge élimina la plupart des points individuels de défaillance lié à l'implémentation d'un serveur unique. La stabilité et la fiabilité du système est ensuite assurée par l'ajout de nouvelles machines de manière transparente pour les utilisateurs. Cet équilibrage de charge des serveurs Web allait pouvoir être utilisé comme modèle pour d'autres implémentations[20].

Le but d'un serveur Web est de stocker une information et de répondre aux requêtes clientes[3]. Pour récupérer une information du Web, le nom contenu dans l'URL doit être associé à une adresse IP, une adresse MAC et une localisation de l'objet[3] - [21]. Chaque association offre ainsi une opportunité de rediriger la requête vers la machine la plus appropriée[21]. Cette nécessité de diriger les connexions entrantes vers des hôtes individuels représente justement un important défi[13].

Par ailleurs, le protocole de communication entre les clients et les serveurs Web est fourni par le protocole HTTP, qui est un protocole basé sur un système de requêtes/réponses[8] et est utilisé pour le World Wide Web depuis les années 1990[22]. Ce protocole étant sans état, une connexion TCP doit donc être établie pour chaque objet d'une page Web. Chaque requête peut être routée de manière indépendante, permettant ainsi un équilibrage de charge des serveurs Web[11].

Une grappe de serveurs Web désigne un ensemble de serveurs informatiques hébergés localement et qui sont interconnectés à travers un réseau haut-débit[27] - [7]. De plus, cet ensemble de serveurs doit apparaitre comme un hôte unique pour le monde extérieur et les utilisateurs[24] - [11] - [28]. Une seule machine, dont l'adresse est publiée à travers le DNS, a la responsabilité de la répartition de charge à travers la grappe de serveurs[7]. Dans une grappe de serveurs, tous les serveurs contiennent la même donnée. Chaque serveur a donc la possibilité de prendre en charge la requête d'un client[29]. Cette approche peut potentiellement améliorer les performances de débit et fournir au système Web une haute disponibilité et une bonne scalabilité[3] - [4] car elle rend possible l'ajout de nouvelle machines sans interruption de service[11]. Elle peut également fournir une meilleure fiabilité par l'utilisation d'algorithmes de répartition de charge appropriés[11].

Une grappe de serveurs Web est composée d'un ordonnanceur, le répartiteur, situé entre les clients et les serveurs Web constitués de différents matériels ou systèmes d'exploitation[29]. Ce répartiteur est configuré avec une adresse IP particulière, l'adresse de la grappe de serveurs Web[23] - [30]. Ainsi c'est le répartiteur qui reçoit les requêtes et les redirigent vers un des serveurs de la grappe[30] - [14] - [29] grâce à l'implémentation d'un algorithme d'équilibrage de charge[29] - [28]. Il s'agit donc d'une approche centralisée qui n'est pas intrinsèquement élastique car le répartiteur central peut devenir un goulot d’étranglement en cas de forte charge[13]. Cependant, pour améliorer la fiabilité, un répartiteur de secours peut être déployé pour prendre le relais du répartiteur principal en cas de panne[23].

Grappe de serveurs Web

Cette approche est basée sur une architecture informatique complètement distribuée sans équipement centralisé en amont. Comme la grappe de serveurs Web, le système apparait comme une seule entité aux yeux du monde extérieur. La différence vient du fait que l'adresse IP de la grappe n'est plus portée par le répartiteur mais par chacun des serveurs, qui possèdent ainsi tous la même adresse IP[31] - [23]. Chaque machine de la grappe aura la responsabilité de traiter ou non les requêtes qui lui arrivent[23].

Grappe de serveurs Web virtuelle

Ce type d'architecture informatique comprend un ensemble de serveurs Web répartis et qui sont visibles de manière individuelle par les clients, contrairement aux grappes de serveurs qui ne présentent qu'une seule adresse IP. Il n'y a pas de répartiteur central, le routage des requêtes peut être effectué par un serveur DNS accompagné éventuellement d'un deuxième niveau de routage effectué par les serveurs eux-mêmes[31].

Systèmes Web distribués

Une approche particulière des systèmes distribués est la réplication en miroir d'un site Web en différents emplacements du monde. La page originale du site contient la liste des serveurs miroirs, ce qui permet à l'utilisateur de choisir le serveur en fonction de son emplacement[6]. Ce type d'approche pour la duplication de contenus populaires est chose commune[25]. Par exemple, apache.org maintient 246 sites miroirs à travers le monde (Liste des serveurs miroirs Apache).

Ce type de système peut réduire le temps de réponse utilisateur et réduire le trafic Internet[25]. Mais cette solution a plusieurs inconvénients, en particulier la non-transparence ainsi que le manque de contrôle sur la distribution des requêtes par le système Web[3] - [6].

Le routage par le réseau peut se faire à plusieurs niveaux : au niveau de la couche transport, entre la couche liaison et la couche réseau ou au niveau de la couche application[21] - [36].

Routage : différentes couches

L'élément qui assure le routage est appelé répartiteur[21] - [4]. Ce répartiteur à un rôle central sur le routage des requêtes et leur distribution aux serveurs[4]. Habituellement le routage se fait au plus près des serveurs. Ainsi la capacité réseau entre l'ordonnanceur et les serveurs est élevée et les informations de charge des serveurs sont fiables[21].

Dans le routage au niveau 2, les serveurs sont identiques au-delà de la couche 2 du modèle OSI. Ils ont un niveau 2 unique, chaque serveur a une adresse MAC, mais une couche 3 identique, donc une même adresse IP[30]. Avec ce mécanisme le routage est effectué entre la couche liaison et la couche réseau, et tous les serveurs ont la même adresse IP que l'adresse IP virtuelle (VIP) portée par le routeur et présentée au client[37]. Toutes les requêtes reçues par les serveurs ne sont traitées que par le serveur adéquat en se basant sur une fonction de hachage liée à l'adresse source du client[5] - [38].

ONE-IP

Dans ONE-IP, un mécanisme de broadcast est utilisé pour envoyer une requête entrante sur toutes les machines de la grappe de serveurs. Les machines ont des adresses MAC et des adresses IP primaires différentes mais une adresse IP secondaire identique. Un filtre est mis en place sur la machine qui fait qu'une seule machine va traiter le paquet dans les couches réseaux supérieures[35]. Pour que ce mécanisme fonctionne, le routeur en amont des serveurs doit modifier l'adresse MAC de destination des paquets entrants par une adresse MAC de broadcast. Cela requiert d'avoir une entrée permanente dans le cache ARP associant l'adresse MAC de broadcast à l'adresse IP virtuelle du routeur[35] - [21].

Routage couche 2 par ONE-IP

Clone Cluster

Afin d'éviter une modification du routeur en entrée du réseau, cette approche propose que toutes les machines aient la même adresse IP et la même adresse MAC. Toutes les machines partagent le même segment LAN, ainsi tous les paquets sont vus par toutes les machines. Un filtre sur chaque machine est utilisé pour sélectionner les requêtes à traiter dans les couches réseaux supérieures[38] - [39].

Routage couche 2 par Clone Cluster

Cette approche nécessite une modification des serveurs afin de ne pas prendre en compte les requêtes ARP gratuites, utilisées notamment pour vérifier que deux adresses IP ne coexistent pas sur le réseau. Une deuxième modification est nécessaire afin de résoudre un problème lié à ICMP : puisque tous les serveurs ont la même MAC et la même IP, une réponse UDP ou ICMP à un paquet envoyé par l'un des membres sera reçu par tous les serveurs. Puisque les autres serveurs n'ont pas généré de paquet, un message ICMP "port inatteignable" sera envoyé. La modification consiste à empêcher l'envoi de ce paquet d'erreur ICMP[38].

Critiques

Ce type de routage évite d'avoir un goulot d'étranglement et un point individuel de défaillance représenté par le répartiteur. Par contre, il nécessite que toutes les machines soient sur le même segment réseau et l'algorithme d'équilibrage de charge est limité à une fonction de hachage[39]. De plus ces solutions utilisent le mécanisme de broadcast et envoient donc les paquets à tous les serveurs, induisant une charge de travail supplémentaire sur ces derniers[40] - [21]. Enfin, ces solutions nécessitent une modification des serveurs pour y implémenter les filtres nécessaires au routage des paquets[40].

Dans le routage couche 4, correspondant dans le modèle OSI à la couche transport, chaque serveur à une adresse IP unique[21]. Le routage réalisé au niveau de la couche 4 par un répartiteur distribue les requêtes en se basant sur l'adresse IP et le port TCP sources et destinations[15]. Afin de s'assurer que tous les paquets d'une connexion existante d'un client arrivent au même serveur, une table de session est maintenue par le répartiteur[34]. À noter que la capacité réseau du répartiteur doit être supérieur à celle de chacun des serveurs du cluster[37]. De plus, chaque paquet doit être inspecté par le répartiteur et la modification des champs du paquet IP comme le contrôle de redondance cyclique et le temps de vie induisent des coûts de traitement supplémentaires[21].

Simple réécriture du paquet

Dans cette approche le répartiteur route le paquet du client vers le serveur en modifiant l'adresse IP du paquet[33]. En effet tous les paquets destinés à l'adresse IP logique du répartiteur sont inspectés et l'adresse de destination est remplacée par l'adresse IP d'un des serveurs de la grappe de serveurs[21] - [5]. Puis le serveur renvoie la réponse directement au client et remplace l'adresse source du paquet par l'adresse source du répartiteur[5].

Routage couche 4 par simple réécriture du paquet

Cette solution est transparente pour le client mais nécessite une modification du noyau des serveurs Web puisque le remplacement de l'adresse IP s'effectue au niveau TCP/IP[5] - [33]. D'un autre côté, cette approche fournit une solution de haute disponibilité car en cas de panne d'un serveur, son adresse peut être supprimé de la table du répartiteur afin qu'il ne reçoive plus de requêtes des clients[33].

Double réécriture du paquet

Ce type de routage est aussi basé sur la présence d'un répartiteur central qui va recevoir les requêtes des clients et les distribuer sur les serveurs du cluster. La différence avec le routage par réécriture simple et qu'ici la réécriture par le répartiteur se fait également pour les paquets en provenance des serveurs et à destination des clients. Ce mécanisme de double réécriture est à la base du mécanisme de Network Address Translation (NAT)[41].

Routage couche 4 par double réécriture du paquet

Pour que le mécanisme soit transparent, le répartiteur doit modifier les adresses IP de tous les paquets dans les deux sens. De plus, les transactions doivent être routées vers le même serveur[37].

Critiques

Les solutions basées sur la double réécriture par le répartiteur ont l'inconvénient majeur de solliciter l'équipement à la fois pour la réécriture des paquets entrants et des paquets sortants, qui sont généralement plus nombreux[36]. Ces solutions ont par contre l'avantage que les serveurs peuvent être sur des réseaux locaux différents[42].

Les solutions basées sur la simple réécriture du paquet doivent absorber la charge liée à la réécriture par le répartiteur mais réduisent le risque de goulot d’étranglement en reportant la réécriture des nombreux paquets sortants sur les serveurs Web[36]. Par contre, ils nécessitent une modification au niveau du système d'exploitation serveurs qui doivent prendre en charge la réécriture des paquets sortants[43]

Le routage à la couche 7, ou couche application selon le modèle OSI, permet d'effectuer une distribution des requêtes en prenant en compte le contenu HTTP de cette requête, fournissant ainsi des stratégies de routage plus flexibles. En contrepartie, la charge générée sur le répartiteur est plus importante[15] - [44] - [25].

Passerelle TCP

Dans cette architecture, un proxy implémenté sur le répartiteur va jouer le rôle d'intermédiaire réseau entre les clients et les serveurs. Le proxy maintient une connexion persistante avec chacun des serveurs Web par laquelle vont transiter les paquets dans les deux sens, du client vers le serveur et inversement[44] - [45]. Le proxy fonctionne selon deux modes : un mode de transfert des paquets et un mode de contrôle des paquets. Les deux modes sont activés pour les requêtes des clients, mais généralement seul le mode de transfert est activé pour les réponses des serveurs[46].

Epissage TCP

Ce mécanisme se veut être une amélioration de la passerelle TCP, lourde en termes de charge de travail car chaque paquet de requête/réponse doit être inspecter jusqu'à la couche application[44] - [45]. L'épissage TCP est une interface de programmation applicative qui va détecter le passage en mode transfert du proxy et gérer ces opérations directement au niveau de l'espace noyau plutôt qu'au niveau de l'espace utilisateur[47]. Ainsi seules les opérations propres à la couche application, celles du mode de contrôle, seront traités dans l'espace utilisateur[45]. L'implémentation de cette technique permet dans la plupart des cas d'éviter le goulot d'étranglement que représente le simple transfert des paquets du client au serveur, qui ne nécessitent pas d'opérations particulières au niveau de la couche application[48].

Routage couche 7 par aller retour (Passerelle TCP et Epissage TCP)

Remise TCP

Le principe de cette approche est la remise au serveur sélectionné de la connexion TCP établie entre le client et le répartiteur. Une fois remise, le répartiteur transfert les paquets du client vers le serveur, et le serveur répond directement au client sans passer par le répartiteur[49] - [50] - [51]. Cette remise est transparente à la fois pour le client et pour les applications du serveur Web. Par contre, elle nécessite une modification de la gestion du réseau par le noyau du système d'exploitation qui doit accepter de prendre en charge une connexion TCP pour laquelle il n'a pas réalisé l'initialisation[49]. Cette approche améliore la performance du répartiteur qui n'a plus à traiter les paquets jusqu'à la couche application, puisqu'il ne fait que transférer les paquets au niveau TCP, majoritairement des paquets d'acquittement, une fois la remise effectuée à un serveur[49] - [50].

Routage couche 7 par aller simple (Remise TCP)

Critiques

Les répartiteurs couche 7 qui permettent aux serveurs de répondre directement aux clients permettent d'avoir une plus grande scalabilité[43]. Ainsi, le mécanisme de remise TCP offre plus de scalabilité que le mécanisme d'épissage TCP[50].

Par contre, la réponse directe du serveur au client nécessite des modifications au niveau du système d'exploitation du serveur et du répartiteur. De plus, la gestion des requêtes et des réponses permet de bénéficier de fonctionnalités de Cache web prises en charge directement par le répartiteur[43].

Le routage client peut être appliqué pour n'importe quelle architecture Web répliquée même si les nœuds ne sont pas du tout coordonnés. Le routage peut se faire par le client Web ou par le serveur mandataire côté client[24].

Les mécanismes de routage par le client peuvent être classés en deux groupes : ceux qui sont transparents et ceux qui ne le sont pas[21].

À la demande de la DARPA, Jon Postel et Paul Mockapetris ont conçu le « Domain Name System » en 1983 et en écrivirent la première réalisation. La plupart des liens Web utilise un nom canonique (CNAME) plutôt qu'une adresse IP. La correspondance entre le CNAME et l'IP est réalisée par un serveur DNS[11]. En plus de fournir l'adresse IP, le DNS spécifie également une période de validité ou Time to live (TTL) de mise en cache[52]. Le routage DNS est simple à implémenter mais possède deux défauts. Premièrement, la mise en mémoire (cache) des adresses IP dans les clients et les serveurs DNS secondaires conduira à une charge non équitablement répartie sur les serveurs. Deuxièmement, si un serveur n'est plus disponible, il n'y a pas de moyen automatique pour le serveur DNS de le savoir et d'arrêter d'y envoyer des requêtes[35]. Cette approche est transparente pour le client[21].

Schéma d’approche basée sur le DNS

Algorithme avec TTL constant

Une mécanisme utilisé pour la distribution des requêtes est le système DNS round-robin qui résout un nom d'hôte unique en plusieurs adresses IP[23]. Un nom de domaine est associé à plusieurs adresses IP correspondant à chaque serveur du cluster. Cette approche, pour la première fois mise en œuvre par le NCSA, afin de gérer l'augmentation du trafic sur son site, était dans le cadre d'un architecture homogène[53]. Très simple à mettre en œuvre, il pose cependant un problème fondamental d'efficacité en raison de la mise en cache sur les DNS locaux. Tant que la valeur du Time to live (TTL) n'est pas expiré, les futures demandes n'accèdent pas au cluster DNS ce qui génère une répartition déséquilibrée de la charge[54]. Cet algorithme ne tenant compte ni de la capacité ni de la disponibilité des serveurs (algorithme apatride), aucun mécanisme ne peut arrêter les clients d'essayer d'accéder au serveur par son adresse en cache[55]. La connaissance de l'état des serveurs est essentielle pour un système hautement disponible afin d'exclure les serveurs inaccessibles en raison de défauts ou de congestion. Combiner la politique basée sur le DNS avec un mécanisme d'alarme évite toute surcharge du système serveur-web[56].

L'algorithme lbnamed exige que le DNS définisse la valeur du TTL à zéro. Ainsi, le DNS, après avoir reçu une demande d'adresse, va sélectionner le serveur le moins chargé et inhiber l'adresse mis en cache sur les serveurs de noms[57]. La connaissance de l'état client est également fort intéressante, deux types d'informations peuvent provenir du côté client : la charge qui arrive au système serveur-web et la localisation géographique[57]. L'index de poids de charge caché mesure le nombre moyen de requêtes de données envoyées à partir de chaque domaine connecté à un site web, au cours de la période de mise en cache (TTL)[56]. Cet ordonnancement DNS, qui utilise principalement ces informations pour attribuer des requêtes au serveur le plus approprié, essaye d'identifier le domaine demandeur et le poids de charge caché imposée par ce domaine[56]. Un exemple de cet algorithme est le Round robin multi niveau. Ces algorithmes basés sur la localisation géographique ne fonctionne pas bien si le mappage URL-IP est caché par les serveurs de noms intermédiaires. Pour les faire fonctionner, le cluster DNS définit le TTL à zéro, cependant cette solution est limitée par les serveurs de noms non coopératifs[57]. Les algorithmes qui utilisent à la fois la connaissance de l'état client et de l'état serveur sont les plus efficaces. L'acquisition de ces informations d'état du système nécessaire exige des estimateurs efficaces, plusieurs approches dynamiques ont été suggérées[57].

Algorithme avec TTL adaptatif

Ces algorithmes utilisent un processus de décision en deux étapes. Tout d'abord, le DNS sélectionne le serveur web de manière similaire aux algorithmes de poids de charge cachés, puis il choisit la valeur TTL appropriée. Les demandes d'adresses provenant de domaines très populaire recevront un TTL inférieur à celui des requêtes en provenance de petits domaines[58]. Pour équilibrer les demandes entre les systèmes de serveurs Web répartis, les algorithmes avec TTL adaptatifs sont les plus robustes et efficaces, malgré des charges asymétriques et serveurs de noms non coopératives. Ces algorithmes, cependant, ne considèrent pas le client à distance de serveur à prendre des décisions de planification[57].

Le client Web peut jouer un rôle actif dans le routage s'il a connaissance des différents serveurs Web répliqués[59]. Une fois que le client Web a reçu la requête de l'utilisateur, il est capable de sélectionner un serveur Web dans la grappe de serveurs et de lui soumettre la requête. Ce serveur Web est alors responsable du traitement de la requête[59].

La manière d'accéder au site de Netscape Communication à travers le navigateur Netscape a été le premier exemple d'architecture Web distribué dont le routage est géré par le client. Le mécanisme était le suivant : lorsque l'utilisateur accédait à la page d'accueil de Netscape (www.netscape.com), le navigateur sélectionnait un nombre aléatoire i entre 1 et le nombre de serveurs. Puis il envoyait la requête de l'utilisateur à l'adresse wwwi.netscape.com. Cette approche n'est généralement pas applicable, puisque le nombre de sites ayant le privilège de posséder leur propre navigateur pour répartir la charge est très limité. Par ailleurs la solution n'est pas flexible à moins de réinstaller le navigateur. Enfin, le mode de sélection aléatoire ne garantit pas la disponibilité du serveur et le bon équilibrage de charge[59]. Cette approche est non-transparente puisqu'elle nécessite une modification du navigateur du client[21].

L'approche du client intelligent vise à transférer certaines fonctionnalités du serveur vers le client. Les requêtes de l'utilisateur sont traitées à travers une applet Java, installée sur le client, qui connait les adresses IP des serveurs et peut les interroger pour connaitre leur statut et leur charge de travail. Ces informations sont ensuite analysées pour choisir le serveur le plus approprié. Les requêtes du client seront alors transférées à ce serveur. L'inconvénient majeur de cette approche est l'augmentation du trafic réseau lié aux messages de statut envoyés aux serveurs par le client[59] - [5]. Cette approche permet de masquer au client les détails de la connexion vers les différents serveurs[5].

Le serveur mandataire est un autre élément d'Internet qui peut distribuer les requêtes clients vers les serveurs Web. Cependant toute implémentation d'un mécanisme de répartition de charge requiert des modifications du serveur mandataire qui n'est généralement pas géré par la même organisation que celle qui gère le site Web[60].

Ces techniques utilisent un mécanisme de répartition à deux niveaux. D'abord le DNS primaire du système Web attribue les demandes des clients aux nœuds de serveurs Web, puis, chaque serveur peut réaffecter une demande reçue à tout autre serveur du système[61]. Cette approche distribuée permet à tous les serveurs de participer à l'équilibrage de charge du système, en la couplant avec l'approche centralisée basée sur les DNS, elle permet de résoudre la plupart des problèmes d'ordonnancement de DNS[61]. Une solution repose sur la redirection de paquets, l'autre sur la redirection HTTP.

Distributed Packet Rewritting (DPR) ou réécriture de paquet par serveur, utilise un mécanisme de Round robin pour planifier les demandes entre les serveurs web[62]. Le serveur accessible par une demande redirige la connexion à un autre serveur à travers un mécanisme de réécriture de paquets qui est transparent pour le client[63]. Avec DPR chaque machine du cluster a connaissance de la charge des autres serveurs. Les adresses IP de toutes les machines sont publiées, ainsi chacune peut recevoir des requêtes. Une requête entrante sur n'importe quelle machine sera dirigée sur la machine la moins chargée en utilisant le TCP hand-off[35] Cependant, le hand-off des connexions TCP est un problème complexe à résoudre et requiert que la machine d'origine qui a effectué le hand-off ait en mémoire la connexion jusqu'à ce qu'elle soit terminée[35]..

L'architecture du système World Wide Web (SWEB) utilise un politique DNS de Round Robin comme premier niveau de planification puis un système asynchrone distribué comme second niveau[63]. Chaque serveur web redirige les requêtes en fonction de la sélection du serveur qui minimise le temps de réponse de la demande du client, il s'agit d'une valeur estimée sur la base des capacités de traitement du serveur et de la bande passante/délai d'internet[63]. L'inconvénient de cette solution est que le routage est fait au niveau application, la requête doit donc remonter toute la pile de protocole[21]. Cette solution peut être intéressante lorsque le facteur limitant est le temps de traitement de la requête. Dans la plupart des cas, le serveur sera un goulot d’étrangement et cette solution n'est pas élastique[21].

Les algorithmes statiques distribuent les requêtes aux serveurs de la grappe sans utiliser les informations d'état de charge de ces serveurs[5]. Ils sont par conséquent très rapides et simples à implémenter mais ne sont pas optimaux car la non prise en compte de ces informations peut les amener à prendre de mauvaises décisions et conduire à un déséquilibre de la charge[67] - [68] - [29].

Aléatoire

Distribution aléatoire des requêtes sur les serveurs Web

Dans la répartition aléatoire, chaque requête entrante est envoyée à un serveur sélectionné aléatoirement. Cet algorithme est très rapide et il assure un bon équilibrage de charge sur une période de temps donnée. Par contre, si le nombre de requêtes est faible, la probabilité d'un déséquilibre de charge est forte[28] - [66].

Round-Robin

L'algorithme de round-robin transfère chaque requête entrante au prochain serveur de la liste[66]. Tous les serveurs sont traités de manière égalitaire sans prendre en compte leur nombre de connexions entrantes ou leur temps de réponse[28] - [69] - [35].

Distribution round-robin des requêtes sur les serveurs Web

Contrairement au DNS Round-robin, la granularité est plus fine puisqu'elle se situe au niveau de la connexion réseau plutôt qu'au niveau de l'hôte. Cela évite les inconvénients liés au cache du DNS qui peut conduire à un déséquilibre de charge[28] - [70]. Par contre, le mécanisme du Round-Robin peut engendrer un déséquilibre de charge si le temps des requêtes ou la capacité des serveurs sont différents. Ceci est dû au fait qu'ils ne prennent pas en compte la charge de travail des serveurs[2].

Round-robin à poids

L'algorithme de round-robin à poids est mis en place pour mieux gérer les serveurs ayant des capacités de traitement différents. Chaque serveur se voit assigner un poids qui indique sa capacité de traitement. L'ordonnancement par le répartiteur tiendra alors compte de ce poids pour transférer les requêtes aux serveurs[28] - [71].

La répartition par round-robin à poids est plus efficace que par round-robin simple lorsque la capacité des serveurs est différente. Cependant, cela peut conduire à un déséquilibre si la charge des requêtes varie beaucoup. Il est possible que la majorité des requêtes lourdes soit toujours dirigée vers le même serveur[28] - [70].

Ces algorithmes sont dits dynamiques car ils ont besoin de collecter dynamiquement les informations des clients ou des serveurs pour déterminer vers quel serveur sera envoyée la requête du client[28] - [69] - [5]. Les informations doivent être accessibles au répartiteur et peuvent être récupérées par le protocole ICMP, par un agent installé sur les serveurs, par une inspection des paquets ou par une analyse du temps de réponse[69] - [68] - [35]. Les algorithmes dynamiques sont plus performants mais la charge réelle de serveurs Web est difficile à quantifier car variable et le transfert de ces informations alourdit grandement le réseau[67] - [68] - [29].

Informations du client

Du côté des informations clients, puisque le répartiteur n'a pas accès au contenu de la requête, il est limité aux informations des couches 4 et inférieures du modèle OSI contenues dans les paquets TCP et IP. Ces informations peuvent être utilisées pour équilibrer la charge en distribuant les requêtes des mêmes clients aux mêmes serveurs en utilisant par exemple une fonction de hachage appliquée à l'adresse IP du client[66].

Informations du serveur

Une première application d'utilisation des informations du serveur pour équilibrer la charge consiste à transférer les requêtes entrantes vers le serveur possédant le moins de connexions établies[69] - [28]. Ce type de répartition est utile pour équilibrer la charge lorsque la charge des requêtes varie beaucoup et que les serveurs ont des performances comparables[28]. Si deux serveurs ont le même nombre de connexions, le serveur avec l'identifiant le plus petit sera choisi. Cela signifie que les nouvelles connexions dans un système vide arriveront toujours sur le même serveur[69].

Une deuxième application est de se baser sur la charge réelle du serveur, et pas seulement sur le nombre de connexions, pour optimiser la distribution des requêtes[72] - [71].

Une autre application est l'exploitation du temps de réponse. Les requêtes entrantes seront en priorité distribuées aux serveurs possédant le temps de réponse le plus rapide[71].

Informations du client et du serveur

Les informations des clients et des serveurs peuvent être combinées pour rendre compatible l'équilibrage de charge avec un besoin fonctionnel. Des applications comme FTP ou SSL peuvent nécessiter l’existence d'une affinité du client avec le serveur, c'est-à-dire que les connexions d'un client donné soit redirigées sur le même serveur que la toute première connexion. Ce mécanisme nécessite le maintien d'une table de correspondance client/serveur par le répartiteur[73] - [74] - [75].

Les algorithmes de répartition basée sur la connaissance du contenu des requêtes sont de plus en plus populaires dans les grappes de serveurs Web[76]. Ces algorithmes sont complexes car ils doivent inspecter le paquet reçu jusqu'à la couche HTTP avant de prendre une décision de routage[77]. Ils utilisent les informations ainsi récupérées dans plusieurs buts[78] - [79] - [80] - [81] :

• améliorer l’indexation des contenus dans le cache Web du serveur afin de réduire les accès disques
• utiliser des serveurs spécialisés selon le contenu à servir (pages statiques, dynamiques, diffusion en flux, ...)
• accroitre le partage de la charge entre les différents serveurs
• améliorer l'affinité client/serveur à travers l'utilisation d'informations SSL et des témoins de connexions
• améliorer la granularité de la distribution des requêtes en cas d'utilisation de la version 1.1 du protocole HTTP

Ces algorithmes examine toutes les couches de la requête HTTP reçue par le client. Les informations récupérées sont utilisées pour prendre une décision sur le routage de la requête[82].

Affinité du cache

Dans ce schéma, l'information client utilisée est le localisateur uniforme de ressource (URL). Une fonction de hachage est utilisée par le répartiteur sur l'URL demandée par le client afin de diriger la requête vers l'un des serveurs de la grappe[83]. L'avantage est une optimisation importante du cache Web du serveur puisqu'il reçoit un ensemble défini de requêtes. Par contre cela ne fonctionne que pour les contenus statiques[83]. L'inconvénient est l'absence de partage équitable de charge dû à la difficulté de définir une fonction de hachage qui prenne en compte la taille et la fréquence d'utilisation des contenus demandés. Cela peut conduire à des goulots d'étranglements lorsque les contenus les plus demandés se trouvent sur le même serveur[84] - [85].

Serveurs spécialisés

Pour les sites Web fournissant des services hétérogènes, l'URL envoyée par le client peut être utilisée pour répartir les requêtes vers le serveur correspondant au service demandé. Les services auront été partitionnés sur les différents serveurs de la grappe[83] - [86]. Le but de cette approche est de prendre en compte les différences de traitement entre contenus afin d'améliorer les performances du système. Par exemple, l'exécution d'un script CGI demande beaucoup plus de ressources au serveur Web que pour servir un fichier statique. Cette approche permet dans ce cas d'utiliser des serveurs puissants pour les CGI et des serveurs moins puissants pour les contenus statiques[86].

Partage de charge

Ces algorithmes ont pour but de partager la charge sans partitionnement logique ou physique prédéfini comme précédemment[83].

Un premier algorithme utilisé, nommé SITA-E pour Size Interval Task Assigment with Equal load, établit un partitionnement dynamique des requêtes en fonction de la taille des fichiers demandés[83] - [87]. Les intervalles de ces partitions, définis par la taille des fichiers, sont réévalués régulièrement par le répartiteur pour équilibrer la charge sur les différents serveurs[87]. Cette implémentation est surtout performante lorsque les tailles des fichiers demandés par les clients sont très variables[87]. Par ailleurs, l'algorithme part du postulat que le temps de réponse d'une requête est proportionnelle à la taille, ce qui le réserve à l'utilisation de ressources statiques[83].

Un autre algorithme, nommé CAP pour Client-aware policy, peut être utilisé sur le répartiteur qui classe alors les requêtes Web selon leur impact sur les ressources physiques (CPU, disque) des serveurs[88]. Le répartiteur ne peut pas obtenir la charge du serveur mais peut estimer le type de charge d'une requête à partir de l'URL reçue. En fonction de l'impact principal, la requête est dirigée vers un serveur d'une liste préétablie en fonction des ressources utilisées[89] - [90] - [83].

Affinité du client

Dans cette approche, les requêtes d'un client donné seront toujours envoyées au même serveur, créant une affinité client-serveur. Cette stratégie est similaire à celle utilisée lorsque le répartiteur n'a pas la connaissance du contenu de la requête. L'apport de la connaissance du contenu permet de créer une affinité non plus uniquement via les informations TCP mais avec des informations plus précises telles que l'identifiant SSL ou le témoin de connexion du client[91].

En plus des informations du client, ces algorithmes prennent également en compte les informations du serveur comme la disponibilité ou la charge[82].

Affinité du cache

Ces algorithmes sont similaires aux algorithmes basés sur l'affinité du cache à partir des informations du client. En plus des informations du clients, ils étendent les possibilités de distribution des requêtes en prenant en compte les informations du serveur telles que la charge et la disponibilité[90] - [91].

Partage de charge

Un algorithme de répartition nommé LARD pour Locality-Aware Request Distribution[81] se base à la fois sur l'emplacement des ressources et sur la charge des serveurs[90] - [91]. Le principe de base de LARD est de rediriger toutes les requêtes d'une ressource Web donnée vers un même serveur Web, optimisant ainsi l'utilisation du cache Web, jusqu'à l'atteinte d'un seuil de charge. Une fois le seuil atteinte, les requêtes seront dirigées vers un serveur moins chargé[92] - [90] - [91]. Cet algorithme est surtout performant lorsque la plupart des contenus Web est statique[90].

La standardisation du nouveau protocole HTTP/1.1 ajoute une fonctionnalité permettant de transférer plusieurs requêtes dans une même connexion[93]. Pour les routages aux couches 4 et 7, la charge de travail générée par l'établissement d'une nouvelle connexion par le répartiteur peut être amortie par le grand nombre d'objets utilisant cette connexion. Par contre la charge engendrée par le transfert des paquets restera la même. L'équilibrage de charge devient plus difficile puisque chaque décision de routage peut avoir un impact important dû aux variations de bande passante en cas de connexion longue. Pour le routage couche 2, où la charge de travail est liée à l'établissement de la connexion, cette nouvelle version du protocole HTTP réduit donc globalement la charge[21].

Le HTTP 2.0 est également en étude, l'IETF HTTPbis-WG a pris comme base de cette prochaine version : SPDY (prononcé « speedy », comme « rapide » en anglais), conçu et proposé par Google[94]. Le flux multiplexage est au cœur de la performance de SPDY, elle réduit le nombre de rotations nécessaires pour aller chercher les ressources, réduisant ainsi la charge[95].

Aujourd'hui, le partage de la charge et le temps de réponses sont les principaux défis pour les algorithmes d'équilibrage de charge, qui deviennent de plus en plus centraux dans la performance d'un système Web[96] - [64] - [4]. Les principales difficultés des algorithmes dynamiques d'équilibrage de charge sont les suivantes[64] :

• mesure de la charge : les informations de charge arrivent très régulièrement et le calcul doit être le plus fiable possible
• l'échange d'informations : la collecte et le maintien des informations de charge représentent un compromis entre le coût du stockage et la fiabilité de la connaissance des systèmes. Le principal problème est la période d’échantillonnage
• l'opération d'équilibrage de charge : elle doit avoir lieu au bon moment, suffisamment rapide pour éviter qu'un serveur ne s'écroule mais pas suffisamment lente pour ne pas être contre-productive.

Les algorithmes d'équilibrage de charge traditionnels fonctionnent en point-à-point et génèrent un grand nombre d'erreurs qui affectent négativement la recherche du meilleur résultat. De par leur forte capacité à effectuer des recherches globales multi-points, les algorithmes génétiques pourraient être une solution optimale d'équilibrage de charge[96].

Les algorithmes génétiques s'inspirent des mécanismes de sélection naturelle et de la génétique pour gagner en efficacité[97]. En plus d'être utilisés dans différents domaines, ce type d'algorithme intéresse également les chercheurs en équilibrage de charge. Mais il leur manque aujourd'hui les capacités de régulation automatiques[97] et ilspeuvent avoir pour défaut une convergence trop rapide, et non optimale, des solutions[96]. Les recherches récentes sur les améliorations des algorithmes génétiques pour l'équilibrage de charge tendent à les améliorer et donnent des résultats concluants[98] - [99]. Par exemple, les travaux sur l'ajout d'algorithmes de type ISODATA lors de la phase de mutation permet d'ajouter à l'algorithme génétique une fonctionnalité de régulation automatique qui lui manquait[98]. Pour autre exemple, les travaux sur un algorithme génétique immunitaire introduit les concepts d'antigène, d'anticorps et de vaccination afin de pallier la convergence trop rapide des solutions des algorithmes génétiques standards[99].