Xavier de Labouret

Ceci est la traduction libre des Notes de l’Architecte de Varnish, que l’on peut trouver ici:

http://varnish.projects.linpro.no/wiki/ArchitectNotes

Varnish est un programme de cache HTTP. Ces Notes de l’architecte décrivent des choix de conception liés à une bonne connaissance des mécanismes d’accès disque et mémoire pour un système d’exploiation. L’architecte de Varnish, Poul-Henning Kamp, est en effet un programmeur de longue date du noyau FreeBSD. J’ai trouvé cet article tellement passionnant que j’en ai fait une petite traduction. Bonne lecture!

Xavier

Notes de l’architecte

Lorsque vous commencerez à vous pencher sur le code source de Varnish, vous remarquerez que Varnish n’est pas une application courante.

Ce n’est pas une coïncidence.

J’ai passé de nombreuses années à travailler sur le noyau de FreeBSD, et je suis rarement allé m’aventurer à programmer dans l’espace utilisateur (NdT: userland), mais quand j’ai eu l’occasion de le faire, j’ai toujours constaté que les gens programmaient toujours comme si nous étions en 1975.

C’est pourquoi, quand j’ai été approché pour le projet Varnish, je n’étais pas vraiment intéressé, jusqu’à ce que je réalise que ce serait une bonne occasion d’employer à bon escient toutes mes connaissances sur le fonctionnement du matériel et des noyaux, et maintenant que nous avons atteint le stade alpha, je peux dire que cela m’a vraiment plu.

Qu’est-ce qui cloche avec la programmation à la 1975 ?

La réponse la plus courte est que les ordinateurs n’ont plus aujourd’hui deux types de stockage différents.

Il était un temps où vous aviez le stockage primaire, ce qui pouvait représenter n’importe quoi, de tout un bazar rempli de mercure à de la RAM dynamique, en passant par des tores magnétiques et des transistors.

Et puis il y avait le stockage secondaire, papier, bandes magnétiques, disques gros comme des maisons, puis comme des machines à laver, et aujourd’hui si petits que les filles sont déçues si elles pensaient attraper autre chose que votre lecteur MP3 dans la poche de votre pantalon.

Et les gens programment comme cela.

Ils ont des variables “en mémoire” et copient les données depuis et vers “le disque”.

Prenez Squid par exemple, un programme à la 1975 s’il en est: vous lui dites combien de RAM il peut utiliser, et de combien d’espace disque il peut se servir. Il va passer un temps considérable à tenir le compte des objets HTTP qui sont en RAM et de ceux qui sont sur le disque, et il va les déplacer de l’un à l’autre en se basant sur des modèles de trafic.

Eh bien, aujourd’hui, les ordinateurs n’ont en réalité qu’un seul type de stockage, et il s’agit en général d’une sorte de disque, le système et le matériel gérant la mémoire virtuelle utilisent la RAM comme cache pour le stockage sur disque.

Donc ce qui se passe avec la gestion de mémoire sophistiquée de Squid, c’est qu’elle rentre en conflit avec la gestion de mémoire sophistiquée du noyau, et comme dans toute guerre civile, cela ne mène à rien.

Voila ce qui se passe: Squid crée un objet HTTP en “RAM”, et celui-ci est utilisé un certain nombre de fois, peu de temps après sa création. Puis, après un certain temps, il n’est plus accédé, et le noyau s’en rend compte. C’est alors que quelqu’un essaie de demander de la mémoire au noyau pour ses propres besoins, et le noyau décide de renvoyer toutes ces pages mémoire inutilisées vers le swap, afin d’employer la RAM-cache plus efficacement pour des données qui sont vraiment utilisées par un programme. Cependant, ceci est fait sans que Squid le sache. Squid pense toujours que ces objets HTTP sont en RAM, et ils le seront, au moment précis où il essaiera d’y accéder, mais jusque-là, la RAM est utilisée pour quelque chose de productif.

C’est à cela que sert la Mémoire Virtuelle.

Si Squid ne faisait rien d’autre, tout irait bien, mais c’est là que la programmation à la 1975 entre en jeu.

Après un certain temps, Squid remarque lui aussi que ces objets sont inutilisés, et il décide de les copier vers le disque, afin que la RAM puisse être utilisée pour des données plus actives. Donc Squid prend en charge le problème, crée un fichier, puis il écrit les objets HTTP dans le fichier.

Une photo de l’action à pleine vitesse nous montre que Squid appelle write(2), l’adresse qu’il fournit est une “adresse virtuelle” et le noyau l’a marquée comme “pas chez elle”.

Alors l’unité du CPU en charge de la pagination va générer un trap, une sorte d’interruption pour le système d’exploitation qui lui dit “veuillez remettre en ordre la mémoire”.

Le noyau essaie de trouver une page libre, s’il n’y en a pas, il va prendre quelque part une page peu utilisée, probablement un autre objet Squid peu utilisé, et l’écrire sur l’espace disque de pagination (le “swap”). Quand cette écriture est terminée, il va lire à un autre endroit de la mémoire paginée les données qu’il veut restaurer dans la page de RAM qu’il vient de libérer, il met à jour les tables de pages, et tente de réexécuter l’instruction qui a échoué.

Squid ne sait rien de tout cela, pour Squid c’était juste un simple accès mémoire tout à fait banal.

Donc, maintenant, Squid a l’objet dans une page de RAM ainsi que sur le disque à deux endroits: une copie dans l’espace de pagination du système d’exploitation, et une copie dans le système de fichiers.

Squid utilise à présent cette RAM pour autre chose, mais après quelque temps, l’objet HTTP est accédé, donc Squid a de nouveau besoin de le restaurer.

D’abord Squid a besoin d’un peu de RAM, donc il peut décider de copier un autre objet HTTP vers le disque (voir plus haut), puis il lit depuis le système de fichiers vers la RAM, et ensuite il envoie les données sur la socket de la connexion réseau.

Ca ne ressemblerait pas à du travail en pure perte?

Voici comment Varnish procède :

Varnish alloue de la mémoire virutelle, il dit au système d’exploitation d’adosser cette mémoire à de l’espace pris dans un fichier. Quand il a besoin d’envoyer l’obet au client, il se réfère simplement à cette zone de mémoire virtuelle, et confie le reste aux bons soins du noyau.

Si/quand le noyau décide qu’il a besoin d’utiliser la RAM pour autre chose, la page sera écrite dans le fichier sous-jacent et la page de RAM réutilisée par ailleurs.

Quand Varnish fait de nouveau référence à la mémoire virtuelle, le système d’exploitation va trouver la page de RAM, peut-être en libérer une, et lire le contenu depuis le fichier sous-jacent.

Et c’est tout. Varnish ne cherche pas vraiment à contrôler ce qui est en RAM et ce qui ne l’est pas, le noyau a le code et le support matériel pour bien le faire, et il le fait bien.

Varnish a aussi un unique fichier sur le disque, alors que Squid met chaque objet dans un fichier séparé. Les objets HTTP ne sont pas utilisés en tant qu’objets du système de fichier, donc il n’y a aucune raison de perdre du temps dans l’espace de nommage du système de fichiers (répertoires, noms de fichiers et tout et tout) pour chaque objet, tout ce dont nous avons besoin dans Varnish, c’est d’un pointeur en mémoire virtuelle et d’une taille, le noyau fait le reste.

La mémoire virtuelle a été conçue pour faciliter la programmation quand la quantité de données est plus grande que la taille de la mémoire physique, mais les gens ne s’en sont toujours pas rendu compte.

D’autres caches

Mais d’autres caches entrent en jeu, la mafia du silicone est plus ou moins bloquée à 4GHz d’horloge CPU, et déja, pour atteindre cette limite, ils ont du mettre des caches de niveau 1, 2 et parfois 3 entre le CPU et la RAM (qui est le cache de niveau 4), il y a aussi d’autres choses, comme des buffers en écriture, le pipeline et les accès en mode page qui servent tous à rendre moins lent le fait d’aller chercher quelque chose en mémoire.

Et comme ils ont atteint la barre des 4GHz, mais que l’augmentation de finesse de gravure leur donne plus de transistors à utiliser, les architectures multiprocesseurs sont devenue une panacée, en dépit du fait qu’elles correspondent à un modèle de programmation très pénible.

Les systèmes multi-processeurs ne sont pas nouveaux, mais écrire des programmes qui utilisent plus d’un processeur à la fois a toujours été une tâche délicate, et ça l’est toujours.

Ecrire des programmes qui tournent efficacement sur des systèmes multiprocesseurs est même encore plus dur.

Imaginons que j’aie deux compteurs statistiques:

unsigned    n_foo;
unsigned    n_bar;

Un processeur est en train de tourner et doit exécuter n_foo++ .

Pour faire cela, il lit n_foo, puis il réécrit n_foo. Cela peut induire ou non un chargement sur un registre CPU, mais ça n’a pas d’importance.

Lire une adresse mémoire signifie qu’il faut l’avoir dans le cache CPU de niveau 1. Il est peu probable qu’elle s’y trouve à moins qu’elle ne soit fréquemment utilisée. Ensuite on interroge le cache de niveau 2, et considérons que la recherche échoue aussi.

S’il s’agit d’un système monoprocesseur, la partie s’arrête là, on va chercher l’adresse en RAM et on repart.

Dans un système multi-processeurs, et il n’y a pas de différence entre le fait que les CPU partagent le même socket ou non, il faut d’abord vérifier si les autres CPU ont une copie modifiée de n_foo dans leurs caches, donc on lance une transaction spéciale sur le bus pour cela, et si un CPU se présente et dit “OK, c’est moi qui l’ai”, ce CPU l’écrit dans la RAM. Lorsque le matériel est de qualité, notre CPU va écouter sur le bus pendant cette opération d’écriture, sur les matériels mal conçus il faudra relire la mémoire après cela.

A présent le CPU peut augmenter la valeur de n_foo, et l’écrire. Mais il est peu probable que cela parte directement en mémoire, on pourrait en avoir besoin rapidement, donc la valeur modifiée est stockée dans notre propre cache de niveau 1 et à un certain moment, elle finira en RAM.

Maintenant, imaginez qu’un autre CPU veut faire n_bar++ au même moment, peut-il le faire? Non. Le cache ne travaille pas sur les octets mais sur des “lignes” d’octets, typiquement de 8 à 128 octets à chaque ligne. Donc le premier CPU était en train de travailler sur n_foo, le second CPU réclame la même ligne de cache, il va devoir attendre, même s’il s’agit d’une variable différente.

Vous voyez l’idée?

Oui, tout cela est laid.

Comment faire?

Il faut éviter le plus possible les opérations sur la mémoire.

Voici comment Varnish essaie de procéder :

Quand on a besoin de gérer une requête ou une réponse HTTP, on utilise un tableau de pointeurs et un espace mémoire de travail. On n’appelle pas malloc(3) pour chaque en-tête. On l’appelle une fois pour l’espace mémoire de travail dans son ensemble, et c’est de cela que l’on se sert pour les en-têtes. L’avantage, c’est que l’on libère un en-tête tout entier en une passe, et on peut faire cela simplement en repositionnant un pointeur au début de l’espace mémoire de travail.

Quand on a besoin de copier un en-tête HTTP d’une requête à une autre (ou d’une réponse à une autre), on ne fait pas de copie de chaîne, on copie juste le pointeur vers cette chaîne. A partir du moment où on ne change pas et on ne libère pas la mémoire de ces en-têtes, cela est complètement sûr, un bon exemple est la copie d’une requête client vers la requête que l’on envoie au serveur en backend.

Dans le cas où le nouvel en-tête a une durée de vie plus longue que celui de départ, il faut le copier. Par exemple, quand on stocke des en-têtes dans un objet en cache. Mais dans ce cas, on construit le nouvel en-tête dans un espace mémoire de travail, et une fois que l’on sait quelle doit être sa taille, on fait un simple malloc(3) pour obtenir la mémoire, et on place tout l’en-tête dans cet espace.

On essaie aussi de réutiliser la mémoire susceptible de se trouver dans les caches.

Les threads workers sont utilisés avec la politique du “plus récemment utilisé”, quand un thread worker devient disponible, il se retrouve en tête de file, là où il a le plus de chance de récupérer la prochaine requête, de façon que toute la mémoire qu’il a mise en cache, la pile, les variables etc, peuvent être réutilisées tant qu’elles sont dans le cache, au lieu d’avoir à faire de coûteux accès en RAM.

On donne aussi à chaque thread worker un ensemble de variables privées dont il est susceptible d’avoir besoin, toutes allouées sur la pile du thread. De cette manière, on est certain qu’elles vont occuper une page de RAM qu’aucun autre CPU ne pensera même à toucher, aussi longtemps que ce thread s’exécute sur son propre CPU. Ainsi il n’y aura pas de dispute sur les lignes de cache.

Si tout cela vous semble étrange, je peux vous assurer que ça marche: on utilise moins de 18 appels système pour servir un hit de cache, et en plus, la plupart de ces appels servent à obtenir des timestamps pour les statistiques.

Par ailleurs, ces techniques n’ont rien de nouveau, nous les avons utilisées dans le noyau pendant plus d’une décennie, maintenant c’est à vous de les apprendre

Alors, bienvenue à Varnish, un programme à l’architecture 2006.

Poul-Henning Kamp, architecte et programmeur de Varnish.