C10k problem

Le c10k problem que l'on pourrait traduire en français par le problème des dix mille connexions simultanées, est un code numérique utilisé pour exprimer la limitation que la plupart des serveurs ont en termes de connexions au réseau. Cette limite repose sur le constat que dans les différentes configurations matérielles et logicielles possibles, les grands serveurs actuels ne semblent pas capables de supporter plus de dix mille connexions simultanées. Cette limitation est partiellement imputable à des contraintes liées aux systèmes d'exploitation et à la conception des applications clients-serveurs auxquelles ils prennent part

Dans le contexte particulier des serveurs web, depuis l'identification de ce problème, quelques solutions ont été proposées, mais la plupart des serveurs utilisés ne parviennent pas à dépasser cette limite.

Problème

La démocratisation de l'Internet depuis le début des années 1990 et les millions d'internautes qui l'accompagnent, posent aux serveurs gérant ces services, le problème de leur capacité à prendre en charge cette fréquentation, notamment pour les services à forte fréquentation (moteur de recherche, sites de réseaux sociaux, jeux en ligne, etc.), qui est leur capacité à prendre en charge un nombre important de clients et donc de requêtes simultanées - Microsoft comptabilisait 300 millions de hits par jour sur ses sites web pour 4,1 millions d'utilisateurs.

Ce problème s'est accéléré avec les réseaux haut débit notamment l'ATM transmettant toujours plus rapidement des requêtes aux serveurs frontaux lesquels devant prendre en charge ces requêtes sans générer de goulots d'étranglements. Les infrastructures réseaux ayant apporté des solutions notamment des fonctions de cache afin d'améliorer les performances, le cœur du problème s'est focalisé sur les serveurs eux-mêmes.

Si aujourd'hui les limites physiques liées au matériel sont repoussées, plusieurs éléments de l'architecture d'un système d'exploitation dont la gestion des entrées-sorties et le modèle de communication concurrente peuvent influer et sont, à ce titre, déterminants voire structurants pour la performance de la gestion des accès concurrents.

Modèle de communication concurrente

Lorsqu'un serveur web traite une requête HTTP pour laquelle il retourne un simple fichier proposant un contenu HTML, différentes étapes nécessaires à la fourniture de cette réponse vont s’enchaîner successivement :

1. accepter la connexion entrante du client et créer la socket associée ;
2. lire la requête et l'entête HTTP ;
3. rechercher le fichier demandé dans le système de fichiers avec contrôle des droits de lecture ;
4. transmettre l'entête de réponse sur la socket client ;
5. lire le fichier ;
6. et transmettre son contenu sur la socket ouverte.

Chacune de ces étapes inclut des opérations de lecture et d'écriture, mais aussi d'ouverture de socket de connexion et de fichier. Et chacune de ces opérations peut générer le blocage (ou du moins la suspension) du processus lorsque les données attendues ne sont pas présentes. Le système d'exploitation des serveurs intercale (entrelace) ces différentes étapes pour les différentes requêtes qu'il reçoit, afin d'optimiser l'utilisation des ressources.

La stratégie mise en œuvre pour gérer cet entrelacement est donc déterminante. On distingue 2 principaux modèles de communication pour la gestion des accès concurrents formalisés pour la première fois en 1978 par Lauer et Needham. Le débat récurrent qui oppose ces 2 modèles sévit depuis des décennies.

Modèle thread-driven (thread-based)

Modèle thread-driven ou Système orienté process.

Alors qu'un processus est un programme en exécution, l’unité de travail dans un système en temps partagé, un thread, également appelé processus léger, est quant à lui l'unité de base d’utilisation du processeur. Il utilise les mêmes ressources et le même espace mémoire que le programme dans lequel il est exécuté, mais possède son propre pointeur d’instructions et sa propre pile d’exécution.

Le modèle thread-driven s'appuie donc sur un ensemble de threads de contrôle qui vont prendre en charge les différentes tâches d'exécution. Dès lors qu'un thread est bloqué sur une opération d'entrée-sortie, il passera la main à un autre thread éligible au sein du même espace d'adressage. Jusqu'à ce que l'entrée-sortie soit terminée, après quoi, le thread redevient prêt à utiliser. La coopération entre les threads est assurée par des mécanismes de synchronisation matérialisés sous forme de verrous, sémaphores ou autre mutex et qui permettent de gérer les accès à des ressources partagées.

Une optimisation a été apportée en mettant en œuvre un pool de threads qui distribue les tâches d'exécution sur des threads créés, initialisés par avance. Ainsi, le gain se situe au niveau du temps inhérent à la création et à la suppression des threads. Ce modèle est proposé dans les langages de programmation tel que Java.

Par ailleurs, la surcharge due à l'overhead lié à la synchronisation des threads peut être contournée par la mise en œuvre de threads coopératifs comme cela a été implémenté dans le paquetage Capriccio.

Modèle event-driven

Modèle Event-driven ou Système orienté message

Le modèle event-driven, qui repose sur un mécanisme de multiplexage des entrées-sorties, est organisé autour de l'exécution d’événements (par exemple arrivée d'une requête pour une page web) et permet ainsi de gérer la concurrence grâce à une boucle à événements qui va répartir l’événement sur un ou plusieurs gestionnaires qui vont prendre en charge cet événement. Ces gestionnaires peuvent à leur tour solliciter un autre gestionnaire d’événements (pour gérer par exemple une demande de lecture sur disque). Les gestionnaires communiquent entre eux par messages ou par événements. Les fonctions devront être courtes afin de rendre la main à la boucle à événements et de ne pas laisser les événements s'accumuler^{[réf. nécessaire]}.

Les systèmes event-driven sont organisés autour d'un seul thread (SPED - Single Process Event-Driven) qui gère donc des événements. Quand un programme ne peut terminer une opération car en attente d'un événement, il enregistre un rappel de service au niveau de la boucle à événements qui inspecte les événements en entrées et qui exécutera le rappel de service lorsque l’événement se produira.

Single Process Event Driven - SPED

Le modèle event-driven est adapté pour les applications hautement concurrentes. Les raisons sont que les systèmes event-driven permettent des optimisations qu'il est difficile de mettre en place dans les modèles threads-driven, des messages peuvent être traités en traitement par lots, un meilleur ordonnancement est possible, le contrôle de flux est plus flexible, et il n'y a pas de basculement de contexte.

Modèle hybride

Les deux modèles thread-driven et event-driven présentent cependant l'un et l'autre des limitations.

Le modèle par threads présente quelques difficultés relatives notamment à la gestion de la synchronisation des threads (utilisation de verrou, sémaphore, mutex, variables de condition, waitable timer – la contention de verrou peut engendrer des problèmes de performances en cas d'augmentation du nombre de threads) et des limitations relatives aux nombres de threads gérés par un système.

Le modèle par événements ne prend pas en charge le Multiprocessing (en), ne tirant ainsi pas avantage des architectures multiprocesseurs. D'autre part, la gestion par événements est dépendante de mécanismes pas forcément correctement supportés par le système d'exploitation ou le langage. Enfin les programmes sont souvent plus complexes à développer et à debugger.

Pour essayer de tirer parti des deux modèles, un modèle hybride a été conçu. SEDA est un framework s'appuyant sur les trois composants qui font la force des modèles Event Driven et Thread Driven que sont les tâches, queues et pool de threads. Ce framework utilise également une queue d’événements, un pool de threads et un gestionnaire d’événements (cf « SEDA (Staged event-driven architecture) »).

Par ailleurs, la bibliothèque logicielle libasync supporte le multi-processeurs et permet de s'affranchir de la gestion des verrous et de la coordination des exécutions de threads propre à une gestion par thread.

Le modèle AMPED (Asymmetric Multi-Process Event Driven, en français : modèle piloté par événements asymétriques à processus multiple) met en œuvre un processus principal (event dispatcher) pour le traitement des requêtes et d'autres processus ou threads pour gérer les entrées-sorties disques. Ces threads sont sollicités via un canal IPC de communication interprocess. Cette architecture est utilisée pour le serveur web Flash.

Asymmetric Multi-Process Event Driven - AMPED

La gestion des entrées-sorties

Matrice simplifiée des modèles d'Entrée-Sorties basique

Vu d’un processus, les communications sont gérées comme des fichiers, les entrées-sorties reposant sur des descripteurs de fichiers (en Anglais : Filehandler). Ainsi une émission est assimilée à une écriture sur un fichier tandis qu'une réception est assimilée à une lecture sur un fichier. À chaque processus est associé une table des descripteurs de fichiers. Il s’agit d’un tableau de pointeurs, chaque pointeur pointant indirectement sur un fichier (v-node) ou sur une communication (socket). Un serveur, web par exemple, devant gérer simultanément un très grand nombre de flux d’entrée et de flux de sortie, le problématique est les attentes actives sur plusieurs descripteurs. Quatre modèles de gestion coexistent sous Linux en fonction de leur caractère bloquant ou non-bloquant et synchrone ou asynchrone (voir Figure « Matrice simplifiée des modèles d'Entrée-Sorties basique »).

Séquence de lecture d'Entrée-Sorties Synchrone Bloquante

Entrées/Sorties bloquantes synchrones

Lorsqu'une application effectue un appel système read(), celle-ci se bloque, le contexte bascule au niveau du noyau. Tant que la réponse au read() n'est pas retournée, l'application est en attente de la réponse (fin d'exécution ou erreur). Une fois celle-ci retournée, l'application se débloque. Ce modèle reste encore le modèle le plus répandu dans les applications mais il est efficace d'un point de vue performance unitaire uniquement^{[réf. nécessaire]}.

Entrées/Sorties non-bloquantes synchrones

Dans ce modèle, la différence est que le noyau répond immédiatement afin de ne pas bloquer ; la réponse consiste en un code erreur indiquant que la commande est en attente. Cela nécessitera des appels systèmes supplémentaires de l'application pour une lecture de la réponse seulement une fois celle-ci disponible. Cette variante est moins efficace (notamment en raison de la latence entrées/sorties).

Entrées/Sorties bloquantes asynchrones

Un thread initialise une entrée-sortie via un appel système read() et délègue ensuite la tâche à un sélecteur pouvant ainsi basculer à une nouvelle tâche. Le sélecteur vérifie alors l'arrivée d'événement entrées-sorties sur le descripteur de connexions. L'intérêt étant que le sélecteur gère la notification d'un ensemble de descripteurs de connexions.

Séquence de lecture d'Entrée-Sorties ASynchrone Non-Bloquante

Entrées/Sorties non-bloquantes asynchrones (AIO)

Une réponse est immédiatement apportée à l'appel read(), celle-ci indique que le read est initialisé avec succès. L'application exécute alors d'autres tâches. Quand la réponse est prête, un signal ou un process de rappel est généré pour finaliser l'entrée-sortie. Ce modèle est une addition récente au noyau Linux puisqu'il est ajouté au standard de la version 2.6 de Linux (était un patch pour 2.4).

En pratique, les mécanismes asynchrones sont les modèles utilisés pour le développement de serveurs à haute performance car cette approche permet d'économiser des ressources en termes d'utilisation du microprocesseur.

Pour la gestion des entrées-sorties (en mode asynchrone), les premiers systèmes Unix ont implémenté des mécanismes de notification par événements tels que select() ou poll(). Ils permettent de notifier lorsque les descripteurs de fichiers sont prêts.

Un processus utilisateur qui effectue un appel système select() indique en paramètre (via des bit-maps) son intérêt dans 3 types d'événements/état d'un descripteur : readable (i.e. qui peut être lu) sans blocage, writable (i.e. qui peut être écrit) avec blocage, exception/erreur. Le noyau va alors envoyer en retour l'ensemble des descripteurs ready pour le type de descripteur demandé.

L'appel poll() a la même fonction que l'appel select() mais l'interface est différente en cela que les intérêts ne sont pas décrits avec des bit-maps mais dans un tableau de structures d'objet pollfd. Cela permet de modifier le mécanisme en attendant que l'un des descripteurs de fichier parmi un ensemble soit prêt pour effectuer des entrées-sorties. Quand le processus exécute un appel système poll(), le système d'exploitation examine si l'objet descripteur de fichier remplit les conditions définies dans le champ « event ». Si c'est le cas, il remplit alors le champ « revent » avec les résultats. Si par contre le champ « revent » est vide, l'appel est bloqué jusqu'à la fin du time-out ou jusqu'au changement d'état à la suite du remplissage du champ par exemple.

Historique

Comme Dan Kegel l'a écrit dans son article « The C10K Problem », dont la première publication date de 1999, les serveurs sont matériellement suffisamment puissants pour gérer 10k connexions simultanées. Le problème réside donc dans la mise en œuvre des systèmes d'exploitation.

août 1983

la fonction select() est introduite dans la version 4.2BSD d'Unix. Cette fonction permet de gérer les entrées-sorties non bloquantes en scrutant les arrivées des requêtes client afin de pouvoir y répondre. Elle a été ajoutée pour permettre de gérer un plus grand nombre de connexion que le modèle de flux d'Unix, read()/write().

1986

L'arrivée de la fonction poll() pour Unix permet de réduire davantage la consommation des ressources.

1997

La fonction poll() est implémentée dans le noyau Linux.

1999

• en mai, SUN implémente une nouvelle alternative à la fonction poll() à travers le descripteur de fichier /dev/poll sur Solaris 7 qui complète la fonction poll(). L'utilisation de ce descripteur permet de mieux tenir la montée en charge lors de l'ouverture d'un grand nombre de descripteurs en simultanés. En effet, il rassemble tous les descripteurs de fichiers, les surveille, et renvoie ceux qui sont prêts à travailler. L'équivalent pour linux est epoll() et pour FreeBSD et NetBSD kqueue().
• Silicon Graphics, Inc. (SGI) implémente une gestion des entrées/sorties asynchrones pris en charge par le noyau (KAIO), qui fonctionne aussi bien avec les entrées/sorties disque qu'avec les sockets. L'implémentation des AIO Linux par Ben LaHaise est introduite dans la version 2.5.32 du noyau Linux, mais ne supporte pas les sockets.

2001

• en mai, Vitaly Luban implémente un patch signal-per-fd, solution proposée par A. Chandra and D. Mosberger.

2002

• Ulrich Drepper, annonce la disponibilité de la nouvelle bibliothèque de threads Linux, POSIX, basée sur le modèle 1:1, qui doit amener une meilleure performance en termes de connexions simultanées. Pour Solaris les modèles 1:1 et M:N étaient utilisés jusqu'à la version 8. Mais seul le modèle 1:1, est disponible avec la version 9.
• en octobre, FreeBSD 4.3 et versions postérieures ainsi que NetBSD implémentent kqueue()/kevent(). kqueue()/kevent() supporte à la fois des notifications d’événements de type edge-triggered et level-triggered.
• plusieurs serveurs web ont vu le jour, permettant de dépasser les 10k connexions simultanées. Parmi eux Nginx (2002), Lighttpd (2003) et Yaws (2002).

2003

• en mai, JDK 1.3 implémenté par de nombreux fournisseurs permet de gérer 10 000 connexions en simultanées. Le micro benchmark de Volano blog liste les JVM pouvant supporter 10 000 connexions.

2006

• en juillet, Evgeniy Polyakov publie un patch qui unifie epoll et AIO. Son objectif est de supporter AIO réseau.
• en juillet, Robert Watson propose que le modèle 1:1 thread soit par défaut dans freeBsd 7.x.
• en septembre Dan Kegel remet à jour son article de 1999, qui n'a plus évolué depuis.

Limites des mécanismes standards

Certaines limitations, rendant la mise à l'échelle peu performante dès que le nombre de descripteurs de fichiers à gérer augmente - et faisant que plus ce nombre de descripteurs augmente, plus le temps nécessaire à l'application pour configurer le sélecteur et interpréter les résultats et au système d'exploitation pour fournir les résultats augmente lui aussi - sont à noter :

mécanismes sans mémoire

Entre deux appels, ils ne mémorisent pas les descripteurs qui intéressent les applications – cela est dû au fait que les deux tâches, correspondant à l'attachement à un événement et à la recherche d'un événement, sont imbriquées dans le même appel système.

mécanismes à états plutôt qu'à mécanismes à événements

c'est-à-dire qu'ils fournissent toutes les informations sur tous ses descripteurs avec chaque notification, alors qu'il faudrait uniquement remonter les changements depuis la dernière notification. Cela génère une quantité de données importante à copier entre le noyau et l'application.

manque d'optimisation

pas plus de 512 descripteurs ouverts en même temps.

limites du select()

En effet, cette fonction utilise un algorithme qui opère un parcours intégral de la table des descripteurs même si peu de sockets sont dans l'état ready Il est ainsi constaté que le coût est plus proportionnel au nombre de descripteurs de fichier impliqués dans l'appel plutôt qu'au nombre de résultats utiles c'est-à-dire d'événements découverts par l'appel.

Les sous-systèmes Entrées/Sorties de Linux ont subi plusieurs évolutions majeures pour leur permettre d'être plus réactifs quelle que soit la charge :

• RT signal qui est une extension du traditionnel signal UNIX permet de remonter des événements via la queue signal lorsque le descripteur est prêt. Cette approche ne contient pas de notion d'intérêt comme cela existait pour l'appel select() ;
• Signal-per-fd permettant de réduire le nombre d'événements fournis par le noyau et d'éviter ainsi un dépassement de capacité de la queue empilant les signaux ce qui pouvait se produire avec la solution RT signals précédente ;
• /dev/poll similaire à poll() mais apporte la mémoire qui lui manquait, en ce sens où le jeu de descripteurs qui intéresse le processus utilisateur est re-mémorisé par le système d'exploitation entre les requêtes de l'application ;
• epoll() sépare les mécanismes pour obtenir un événement (epoll_wait()) et celui pour déclarer un attachement à un événement (epoll_ctl()).

Solutions existantes

Solutions identifiées par Kegel

Stratégies entrées et sorties

La stratégie entrées-sorties, c'est-à-dire la combinaison entre la gestion des Entrées/Sorties et le modèle de communication concurrente est déterminante pour répondre aux problèmes des 10K connexions simultanées.

Kegel aborde les cinq approches suivantes sur ce sujet:

Servir plusieurs clients dans un thread avec des appels entrées et sorties non bloquantes et des notifications de type Interrupt#Level-triggered (en)

Cette approche (la plus ancienne) utilise des appels Entrées/Sorties du type select() ou poll(), mais elle a montré ses limites (voir Section Problème) en termes de gestion de la concurrence ;

Servir plusieurs clients par thread avec Entrées/Sorties non bloquantes et notifications Interrupt#Edge-triggered (en)

La principale évolution réside dans l’utilisation d’une méthode de notification d’événements de type edge-triggered, c'est-à-dire détection de transitions, qui répondent mieux au problème en présentant une meilleure résistance pour la montée en charge. Suivant les OS, ces implémentations se nomment :

kqueue : sur les systèmes FreeBSD et NetBSD

epoll() sur les systèmes Linux à partir de la version 2.6

Kevent pour Linux 2.6 également, qui reprend la philosophie de kqueue

Signal-per-fd : qui reprend le concept des signaux temps réels. Dans l'article de A.Chandra, celui-ci le compare aux appels poll() et select() sans toutefois aller jusqu’à la limite des 10k.

Servir plusieurs clients par thread avec des appels entrées et sorties asynchrones (AIO)

Les appels asynchrones sont en fait une surcouche aux opérations Entrées/Sorties standards, qui offre une interface de soumission d’une ou plusieurs requêtes Entrées/Sorties dans un seul appel système (io_submit() ) sans en attendre la fin. Une seconde interface (io_getevents() ) permet de recueillir les opérations associées.

En 2006, lorsque Kegel publie son étude, peu de systèmes d'exploitation supportaient les appels asynchrones. Mais une étude sur la performance et la robustesse des AIO montre que celles-ci ne sont pas adaptées à tous les cas d’utilisations.

Côté Linux la version 2.6 supporte également les AIO et notamment les distributions Red Hat et SUSE. Toutefois, les appels asynchrones ne peuvent ouvrir une ressource Entrée/Sortie disque sans blocage, Linus Torvalds explique cela et préconise de gérer les appels Entrées/Sorties disque dans un thread différent et de façon standard ( open() )

Côté Windows, les AIO sont appelés « I/O Completion Port

Servir un client par thread

Le problème dans cette approche est l'utilisation d’une pile entière par client, ce qui coûte beaucoup de mémoire (certaines piles peuvent avoir deux Mégaoctet)… La plupart des OS ne peuvent gérer plus de quelques centaines de threads, notamment les OS 32bits avec un espace d'adressage mémoire limité à 4 Gigaoctet. L'arrivée des OS 64 bits repousse cette limite jusqu’à 64 Gigaoctet d'adressage mémoire, ce qui permet une gestion d'un bien plus grand nombre de threads. Von Behren, Condit and Brewer sont des ardents défenseurs de cette approche et mettent en avant une plus grande simplicité de programmation par rapport à l’approche event-based programming

Introduire du code applicatif dans le noyau

deux implémentations sont largement documentées :

• Khttpd pour Linux est un serveur web intégré au noyau
• TUX pour Linux également

De nombreux débats ont eu lieu dans la liste linux-kernel, autour de ces solutions. La décision a finalement été de privilégier la limitation d'ajout au noyau pour augmenter la performance des serveurs web, plutôt que d’introduire les serveurs web dans les noyaux.

Implémentation des threads dans les systèmes d'exploitation

Comparatif du modèle 1 :1 versus modèle M :N

Il y a deux façons d'implémenter les threads dans un système d'exploitation :

1. Le modèle 1:1 Thread_(computer_science)#Models (en) ;
2. Le modèle M:N Thread_(computer_science)#Models (en).

Rob von Behren et ses partenaires, sur le contexte Capriccio, indiquent que le modèle 1:1, qui est plus facile à implémenter que le modèle M:N, est aussi bien plus performant. Par ailleurs, Capriccio a fait le choix d'une implémentation de thread utilisateur et non de thread noyau, ce qui offre l'avantage d'éliminer l'overhead de synchronisation.

Linux : LinuxThreads est le nom de la bibliothèque standard des threads Linux. Il s'agit d'une implémentation partielle des POSIX_Threads#Models pour Linux. Deux nouvelles implémentations ont vu le jour:

• Next Generation Posix Threads for Linux (NGPT) : uniquement sur le noyau Linux 2.5
• Native Posix Threads Library for Linux (NPTL) : cette implémentation a pris le pas sur NGPT. Déjà identifiée par Kegel comme étant une solution au C10K problem, Ulrich Drepper a rectifié son article en indiquant qu'il s'était trompé et qu'il s'agirait d'une fausse piste

FreeBSD : Les versions les plus anciennes supportent les LinuxThreads vus plus haut. Le modèle d'implémentation M:N a été introduit à partir de la version 5.0 sous le nom de KSE. En 2006, Robert Watson propose une implémentation du modèle 1:1 qui va devenir le modèle par défaut à partir de la version FreeBSD 7.X

NetBSD Un exemple d'implémentation sur NetBSD a été présenté à la conférence annuel FREENIX de 2002.

SUN Solaris Les versions 2 à 8 de Solaris repose sur le modèle M:N, mais dès la version 9, Solaris migre vers le modèle 1:1.

Côté Framework Java, il ne peut gérer que le modèle 1 client par thread. En 2003 quelques produits permettent de gérer les c10k (BEA Weblogic), les autres rencontrent des problèmes de OutOfMemory ou Segmentation fault.

Approches récentes

Asynchrone par transmission de message : Erlang

On peut citer les implémentations de serveurs Web basés sur Erlang, le langage d’Ericsson dédié aux développements d’application concurrente et temps réel. Ce langage propose une distribution nommée Open Telecom Platform (en) (Open Telecom Plaform) constituée de plusieurs bibliothèques offrant des fonctionnalités de distribution très avancées des traitements et de supervision des nœuds, ainsi qu'une base de données répartie. Erlang peut s’interfacer avec Java et C/C++.

La principale force d’Erlang est son architecture mémoire. Chaque thread possède son propre espace mémoire à contrario de java où tous les threads partagent un même espace. Les transmissions de données se font par échange de message via leur propre espace mémoire. Les messages sont déposés et le destinataire vient les récupérer quand il en a besoin. Jesper Wilhelmsson dans sa thèse explique que ce mode de gestion de la mémoire est très efficace pour les applications concurrentes.

Plusieurs serveurs web légers ont été développés avec Erlang dont Mochiweb, Yaws(Yet another web server), inets. Facebook Chat Application est également développée avec Erlang.

Implémentation de Mochiweb

Richard Jones, sur son blog explique comment développer une application Comet pouvant traiter 1 million de connexions en simultanées en se basant sur Mochiweb. Le modèle d’application Web Comet permet au serveur Web de faire du push vers le navigateur. Dans cette approche, chaque connexion Mochiweb est référencée par un routeur qui distribue (push) les messages à chaque utilisateur connecté en simultané. Les observations sur cette application basée sur Mochiweb montrent que pour 10 000 utilisateurs connectés en simultané pendant 24 heures, avec un taux d’émission de 1000 messages par seconde (soit 1 utilisateur recevant 1 message toutes les 10 secondes), la ressource mémoire consommée est de 80MB soit 8KB par utilisateur.

En optimisant avec une base de données de souscription telle que Mnesia (en) à la place du routeur d’origine, le serveur Mochiweb peut gérer 1 million de connexions simultanées présentant toutefois une forte consommation de mémoire 40GB, soit 40kB par connexion. Ce qui n’est pas déraisonnable vu que la mémoire est très bon marché actuellement.

Implémentation de Yaws

Yaws est un server http très performant adapté particulièrement au contenu dynamique des applications Web. Les mesures comparatives réalisées par Ali Ghodsi montre qu'Apache s’écroule totalement avec 4000 requêtes en simultanées alors que Yaws continue à fonctionner avec 90000 requêtes. Le comparatif est réalisé avec un serveur Yaws sur file system NFS, un serveur Apache sur NFS également, et un serveur Apache sur un file système local. Les serveurs reçoivent en boucle une requête 20 kbit. Dès qu’ils répondent, une nouvelle requête arrive.

SEDA (staged event-driven architecture)

SEDA, acronyme de staged event-driven architecture (en), est le sujet de thèse de Matt Wesh qui présente une nouvelle approche de développement d’une plateforme de service internet robuste, pouvant supporter de massives concurrences et plus de 10 000 connexions en simultanées. La philosophie dans SEDA est de décomposer une application événementielle complexe en un ensemble d’étapes connectées à une file d’attente. Ainsi, un traitement complexe se décompose en une suite d'opérations. Ces opérations sont elles-mêmes décomposées en un ensemble de messages à traiter. Ces messages sont ensuite aiguillés vers un ou plusieurs « workers ». Toutes ces étapes et dispatching sont gérés par un framework. Le développeur n’aura qu’à se concentrer sur l’implémentation du code métier et laisser le framework gérer la complexité technique. Cette conception permet d’éviter les overheads associés aux modèles un thread par requête (thead-based concurrency). Elle découple les événements et l’ordonnancement des threads de la logique applicative. En effectuant le contrôle d’admission à chaque file d’attente d’événements, le service peut être bien conditionné (well conditionned) pour charger, évitant ainsi que les ressources soient surexploitées lorsque la demande dépasse la capacité du service. L'architecture staged event-driven emploie un contrôle dynamique pour adapter automatiquement des paramètres d'exécution (telles que les paramètres d'ordonnancement de chaque étape), comme pour gérer la charge, par exemple. Décomposer les services en une série d'étapes permet également la réutilisation et la modularité du code. Un benchmark montrant que Haboob (serveur Web SEDA) est plus performant que Apache est présenté en page.

Les implémentations open source des architectures staged event-driven sont : Apache ServiceMix, JCyclone, Haboob et Mule (software) (en).

Node.js, un moteur de javascript serveur

Node.js est un framework JavaScript server utilisé au-dessus de Google V8, le très performant moteur Javascript open source implémenté dans le navigateur Google Chrome. Sur les mêmes principes que le serveur web lighttpd, Node.js n’utilise qu’un seul thread pour gérer des entrées/sorties non bloquantes. Node.js propose dans ses APIs uniquement des fonctions non-bloquantes. La gestion des I/O non-bloquants permet de rendre tout le code asynchrone et donc d'optimiser la gestion de la concurrence. De plus, il est très peu consommateur en mémoire car n’utilise qu’un seul thread à l’inverse d’Apache qui utilise un thread par requête. Toutes les fonctions dans Node.js fournissent en paramètre un callback. Le callback est appelé en fin de traitement de la fonction avec le résultat en paramètre et une éventuelle erreur. Ainsi, pendant le traitement d’une fonction, le thread peut être libéré pour traiter une nouvelle requête entrante. Node.js est très adapté pour la programmation évènementielle. Les spécificités de Node.js en font une excellente plate-forme de développement d’applications temps réel orientées réseau (messagerie instantanée, systèmes de notification temps réel, etc.) performantes et scalables. Ryan Dahl, le créateur de Node.js présente dans cette vidéo le moteur javascript. dans Linux Journal, Reuven M. Lerner présente un article comment implémenter un serveur d'application réseau haute performance avec Node.js pouvant gérer 10 000 requêtes en simultanées.

Bien que node.js soit encore un peu jeune, Yammer, Bocoup, Proxlet et Yahoo sont des compagnies qui l'implémentent déjà en production.

Architecture des infrastructures Web

Implémentation des serveurs web

Quelques serveurs web "légers" (Open source) ont été développés pour contrer le problème des 10k connexions simultanées. Ces serveurs web ont une architecture asynchrone, non bloquante:

nginx

nginx (à prononcer en anglais « engine x ») a été développé par Igor Sysoev en 2002, pour les besoins d’un site russe à très fort trafic (rambler.ru). Il a été connu, hors Russie, qu'à partir de 2006, après avoir été traduit du Russe par Aleksandar Lazic. Ses performances en termes de répondant, de stabilité et de consommation mémoire, lui valent rapidement une certaine renommée et son utilisation de par le web ne cesse d’augmenter depuis. La dernière étude de Netcraft (mai 2011) sur les serveurs web les plus utilisés, place nginx en 4^e position. L'architecture logicielle asynchrone de Nginx lui permet de s’adapter à la fois aux petits serveurs et aux sites gérant un nombre important de requêtes. Nginx est très modulaire, il dispose d’un noyau minimal gérant les requêtes HTTP et tout le reste est fourni par des modules. Il fait également office de proxy HTTP inverse et de proxy pour le courrier électronique. Il est notamment utilisé par des services en ligne tels que WordPress.com et FastMail.FM.

Lighttpd

Lighttpd (à prononcer en anglais « lighty »), développé en 2003 par un étudiant allemand Jan Kneschke, est l'un des serveurs ayant la plus faible trace mémoire et le plus faible usage du processeur, tout en étant très rapide pour servir les documents statiques comme dynamiques. Le module FastCGI est inclus par défaut, ce qui le rend très intéressant pour les langages comme PHP, Python ou Ruby. Lighttpd utilise un seul thread pour gérer des entrées/sorties non bloquantes. Il est d'ailleurs utilisé par de gros sites comme YouTube, SourceForge.net, ou le serveur d'image de Wikipédia. Il est en 7^e position des serveurs web les plus utilisés d'après l'étude de Netcraft. Il fait partie des logiciels fournis avec la distribution Fedora.

Cherokee

Cherokee a été développé en 2001 par Alvaro López Ortega. Il est maintenant développé et maintenu par une communauté de contributeurs. Cherokee est très rapide, flexible et rapide à configurer grâce à son interface d'administration graphique.

Tornado

Tornado est la version open source du serveur web utilisé pour l'application FriendFeed et racheté par Facebook en 2009. Son architecture asynchrone-non bloquante et l'utilisation de epoll(), lui permet de dépasser les 10k connexions simultanées, et de garder les connexions utilisateurs ouvertes pendant une longue période.

G-WAN (pour Global Wide Area Network)

G-WAN est un serveur Web gratuit freeware dont la première version été publiée en juillet 2009. G-WAN offre des scripts en Java, C, C++, C#, D, Objective-C pour générer des pages Web.

Différence de performance entre NGINX, Lighttpd, Cherokee et Apache

Architecture classique Client-Serveur

Le modèle d’architecture classique client-serveur et son extension, le modèle multi-tiers, sur lequel repose la plupart des architectures des applications web actuelles, montre des limites quant à la capacité d’absorption de la charge en termes de connexions simultanées, le C10K problem !

Architecture 3-tiers simple

Le serveur web, qui est l'élément central dans l'architecture doit pouvoir gérer simultanément:

• la réception des requêtes
• la vérification des requêtes
• la répartition vers BdD, autres services…
• l'agrégation des résultats
• la gestion des erreurs
• la création de la page de retour
• l'envoi de la réponse au client.

Si aujourd'hui les limites physiques liées au matériel sont repoussées, comme le soulignait déjà Kegel dans son introduction, le problème de la gestion des entrées-sorties et la gestion des ressources CPU et RAM reste le principal point de contention (en anglais : Bottleneck).

Scalabilité

Répartition de la charge entre n serveurs web

Une autre approche du C10K problem consiste à « diluer » la charge entre plusieurs serveurs via un équipement de répartition de charge. Cela se nomme la scalabilité horizontale. Ainsi, même si un serveur web ne peut absorber qu'un certain nombre de connexions simultanées, en augmentant le nombre de serveurs, l'architecture de la plate-forme permettra d'obtenir le nombre de connexions simultanées désiré.

L'exemple de la figure ci-contre est relativement simple, le répartiteur de charge, qui est un élément réseau de la plate-forme, donc extrêmement rapide en termes de gestion de connexion, va répartir la charge entre les serveurs web via un algorithme prédéfini. De plus, si la charge venait à augmenter, celle-ci peut être prise en compte en rajoutant de nouveaux serveurs à l'infrastructure existante.

• Un bel exemple de mise en œuvre de la scalabilité est l'architecture de la plate-forme du site ebay présentée par Randy Shoup. Cette architecture permettait de gérer jusqu'à 3 milliards de connexions par mois en 2006.

Notes et références

Bibliographie

Bibliographie référencée

• (en) Dank Kegel, « c10k problem », sans (white paper),‎ 2 septembre 2006 (lire en ligne)

• (en) Jonathan Lemon, Kqueue : A generic and scalable event notification facility, Linux Foundation (lire en ligne)

• (en) « The Proposed Linux kevent API », Linux Foundation,‎ 19 novembre 2009 (lire en ligne)

• (en) Abhishek Chandra et David Mosberger, « Scalability of Linux Event-Dispatch Mechanisms », Publication Hewlett Packard,‎ 14 décembre 2000 (lire en ligne)

• (en) Kernel Asynchronous I/O (AIO) Support for Linux, SourceForge.net (lire en ligne)

• (en) Linus Torvalds, « kernel mechanism: Compound event wait », Liste Linux-kernel,‎ 8 février 2001 (lire en ligne)

• (en) Phil Barila, « I/O Completion Ports », MSDN Library (Microsoft),‎ 12 janvier 2010 (lire en ligne)

• (en) Suparna Bhattacharya, John Tran, Mike Sullivan et Chris Mason, « Linux AIO Performance and Robustness for Enterprise Workloads », Linux Symposium 2004,‎ 2004, p. 1 (lire en ligne)
• (en) James Gosling, Bill Joy, Guy Steele et Gilad Bracha, « The Java™ Language Specification Third Edition », Sun Microsystems,‎ 2005, p. 684 (lire en ligne)

• (en) Rob Von Behren, Jeremy Condit et Eric Brewer, « Why Events Are A Bad Idea (for high-concurrency servers) », sans,‎ 26 août 2003, p. 6 (lire en ligne)

• (en) Rob Von Behren, Jeremy Condit, Feng Zhou, George C. Necula et Eric Brewer, « Scalable Threads for Internet Services », Computational Systems Seminar, SS 2004,‎ 1^er juillet 2004, p. 17 (lire en ligne)

• (en) Ulrich Drepper, « Design of the New GNU Thread Library », sans,‎ 13 avril 2004 (lire en ligne)

• (en) Bryan K. Ogawa, « A programmer's guide to thread programming on FreeBSD », sans,‎ 15 juillet 2003 (lire en ligne)

• (en) Robert Watson, « making libthr default thread implementation? », Liste freebsd-threads,‎ 3 juillet 2006 (lire en ligne)

• (en) Nathan J. Williams, « An Implementation of Scheduler Activations on the NetBSD Operating System »

• (en) « Threading », Documentation officielle SUN

• (en) John Neffenger, « The Volano Report », Volano Blog,‎ 30 mai 2003 (lire en ligne)

• (en) « kHTTPd Linux HTTP Accelerator »

• (en) Vivek Gite, « What Is Tux Web Server and How do I Use it? », FAQ nixCraft,‎ 30 avril 2008 (lire en ligne)

• (en) Matt Welsh, Steven D. Gribble, Eric A. Brewer et David Culler, « A Design Framework for Highly Concurrent Systems », Technical Report No. UCB/CSD-00-1108,‎ 2000, p. 14 (lire en ligne)

• (en) Gaurav Banga et Jeffrey C. Mogul, « Scalable kernel performance for Internet servers under realistic loads », Proceedings of the USENIX Annual Technical Conference (NO 98),‎ juin 1998, p. 12 (lire en ligne)

• (en) Niels Provos et Chuck Lever, « Scalable Network I/O in Linux », CITI Technical Report 00-4,‎ 2000, p. 11 (lire en ligne)

• (en) Hugh C. Lauer et Roger M. Needham, « On the Duality of Operating Systems Structures », Proc. Second International Symposium on Operating Systems,‎ octobre 1978, p. 19 (lire en ligne)

• (en) Louay Gammo, Tim Brecht, Amol Shukla et David Pariag, « Comparing and Evaluating epoll, select, and poll Event Mechanisms », Proceedings of the Ottawa Linux Symposium,‎ juillet 2004, p. 11 (lire en ligne)

• (en) Dong Liu et Ralph Deters, « The Reverse C10K Problem for Server-side Mashups », Service-Oriented Computing Workshops,‎ 2009, p. 12 (lire en ligne)

• (en) Fred Reiss et Elaine Cheong, Debugger Support for Single-Threaded Event-Driven Applications, 2001, 9 p. (lire en ligne)

• (en) Vivek S. Pai, Peter Druschel et Willy Zwaenepoel, « Flash: An efficient and portable Web server », Proc. of the 1999 Annual Usenix Technical Conference,‎ juin 1999, p. 13 (lire en ligne)

• (en) Will Reese, « Nginx: the High-Performance Web Server and Reverse Proxy », Linux Journal,‎ 1^er septembre 2008, p. 26 (lire en ligne)

• (en) Ted Roden, Building the Realtime User Experience, juillet 2010, 79 p. (présentation en ligne)

• (en) Carl Chenet, « Cherokee, la nouvelle tribu des serveurs Web », Linux Magazine,‎ mars 2010, p. 24 (lire en ligne)
• (en) Randy Shoup et Dan Pritchett, « The Ebay Architecture », SD Forum 2006,‎ 29 novembre 2006, p. 36 (lire en ligne)
• (en) Jesper Wilhelmsson et Konstantinos Sagonas, « Efficient memory management for concurrent programs that use message passing », Science of Computer Programming, vol. 62,‎ mai 2005, p. 120 (DOI 10.1016/j.scico.2006.02.006, lire en ligne)
• (en) Dave Bryson et Steve Vinoski, « Build Your Next Web Application with Erlang », IEEE Computer Society, vol. 13,‎ juillet 2009, p. 94 (ISSN 1089-7801, DOI 10.1109/MIC.2009.74, lire en ligne)
• (en) Kenji RIKITAKE et Koji NAKAO, « Application Security of Erlang Concurrent System », SOSP '01 Proceedings of the eighteenth ACM symposium on Operating systems principles,‎ 2001, p. 2 (lire en ligne)
• (en) Matt Welsh, David Culler et Eric Brewer, « Application Security of Erlang Concurrent System », ACM SIGOPS Operating Systems Review,‎ 5 décembre 2001, p. 231 (ISBN 1-58113-389-8, DOI 10.1145/502034.502057, lire en ligne)
• (en) Stefan Tilkov et Steve Vinoski, « Node.js: Using JavaScript to Build High-Performance Network Programs », Internet Computing, IEEE, vol. 14,‎ décembre 2010, p. 81 (ISSN 1089-7801, DOI 10.1109/MIC.2010.145, lire en ligne)
• (en) Nickolai Zeldovich, Alexander Yip, Frank Dabek, Robert T. Morris, David Mazières et Frans Kaashoek, « Multiprocessor Support for Event-Driven Programs », Technical Conference USENIX,‎ 2003, p. 14 (lire en ligne)
• (en) Frank Dabek, Nickolai Zeldovich, Frans Kaashoek, David Mazières† et Robert Morris, « Event-driven Programming for Robust Software », SIGOPS European Workshop,‎ 2002, p. 4 (lire en ligne)
• (en) Gaurav Banga, Jeffrey C. Mogul et Peter Druschel, « A Scalable and Explicit Event Delivery Mechanism for UNIX », Proceedings of the USENIX Annual Technical Conference,‎ 1999, p. 4 (lire en ligne)
• (en) Hao-Ran Liu et Tien-Fu Chen, A Scalable Event Dispatching Library for Linux Network Servers, Chiayi (Taiwan), National Chung Cheng University, Department of Computer Science, 24 p. (lire en ligne)
• (en) Rob von Behren, Jeremy Condit, Feng Zhou, GeorgeC. Necula et Eric Brewer, « Capriccio: Scalable Threads for Internet Services », Proceedings of the 19th ACM Symposium on Operating Systems Principles,‎ 2003, p. 15 (lire en ligne)
• (en) James C. Hu, Irfan Pyarali et Douglas C. Schmidt, « Measuring the Impact of Event Dispatching and Concurrency Models on Web Server Performance Over High-spedd Networks », Proceedings of the 2 nd Global Internet Conference, IEEE,‎ 1997, p. 12 (lire en ligne)
• (en) Tim Jones, « Boost application performance using asynchronous I/O », IBM developerWorks,‎ aout 2006 (lire en ligne)
• (en) Dank Kegel, « Microbenchmark comparing poll, kqueue, and /dev/poll », sans (white paper),‎ 24 octobre 2000 (lire en ligne)

Autres éléments bibliographiques

• (en) Felix Von Leitner, « Scalable Network Programming », sans (white paper),‎ 16 octobre 2003 (lire en ligne)
• (en) Matt Welsh, David Culler et Eric Brewer, « SEDA: An Architecture for WellConditioned, Scalable Internet Services », sans (white paper),‎ 16 octobre 2003 (lire en ligne)
• (en) Matt Welsh, An Architecture for Highly Concurrent, Well-Conditioned Internet Services, 2002, Ph. D. thesis (lire en ligne)
• (en) Fabien Gaud, Sylvain Genevès, Renaud Lachaize, Baptiste Lepers, Fabien Mottet, Gilles Muller et Vivien Quéma, « Mely: Efficient Workstealing for Multicore Event-Driven Systems », Publication INRIA,‎ 24 janvier 2010, p. 26 (lire en ligne)
• (en) Holger Kälberer, « Threaded Architectures for Internet Servers », RBG-Seminar WS 2008/2009,‎ 9 décembre 2008, p. 33 (lire en ligne)
• (en) Ulrich Drepper, The Need for Asynchronous, Zero-Copy Network I/O, 14 p., PDF (lire en ligne)