SIEVE, un nouvel algorithme open source développé par des informaticiens de l’Université Emory, de l’Université Carnegie Mellon et de la Fondation Pelikan, simplifie et améliore la gestion du cache Web. Cet algorithme décide efficacement quelles données doivent être expulsées d’un cache, améliorant ainsi l’efficacité du système et réduisant considérablement le taux d’échec par rapport à d’autres algorithmes.
Le nouvel algorithme open source a le potentiel de révolutionner la gestion du trafic Web à grande échelle.
Les informaticiens ont développé un algorithme très efficace, mais incroyablement simple, pour décider quels éléments supprimer d’un cache Web pour faire de la place à de nouveaux. Connu sous le nom de SIEVE, le nouvel algorithme open source a le potentiel de transformer la gestion du trafic Web à grande échelle.
SIEVE est un projet conjoint d’informaticiens de l’Université Emory, de l’Université Carnegie Mellon et de la Fondation Pelikan. L’article de l’équipe sur SIEVE sera présenté au 21St Symposium USENIX sur la conception et la mise en œuvre de systèmes en réseau (NSDI) à Santa Clara, Californie, en avril.
Une préimpression du journal fait déjà des vagues.
« SIEVE est plus grand que nous », déclare Yazhuo Zhang, doctorant à Emory et co-premier auteur de l’article. « Il fonctionne déjà bien, mais nous recevons beaucoup de bonnes suggestions pour l’améliorer encore. C’est la beauté du monde open source.
Zhang partage la paternité de l’article avec Juncheng (Jason) Yang, qui a obtenu sa maîtrise en informatique à Emory et est maintenant doctorant à Carnegie Mellon.
Un logo pour SIEVE, créé par Yazhuo Zhang, représente les objets les plus chauds dans des tons de rouge et les plus froids dans des tons de bleu. Zhang a également conçu un site Web pour SIEVE, comprenant un graphique animé démontrant son fonctionnement. Crédit : Yazhuo Zhang
« SIEVE est une amélioration simple d’un algorithme d’éviction de cache éprouvé qui est utilisé depuis des décennies, ce qui équivaut littéralement à des siècles dans le monde de l’informatique », déclare Ymir Vigfusson, professeur agrégé au département d’informatique d’Emory.
Vigfusson est co-auteur principal de l’article, avec Rashmi Vinayak, professeur agrégé au département d’informatique de Carnegie Mellon. Yao Yue, ingénieur informaticien à la Fondation Pelikan, est également co-auteur.
Outre sa rapidité et son efficacité, un facteur clé qui suscite l’intérêt pour SIEVE est sa simplicité, qui lui confère son évolutivité.
« La simplicité est la sophistication ultime », déclare Vigfusson. « Plus les éléments d’un système conçu pour servir des milliards de personnes en une fraction de seconde sont simples, plus il est facile de mettre en œuvre et de maintenir efficacement ce système. »
Garder les « objets chauds » à portée de main
De nombreuses personnes comprennent l’importance de réorganiser régulièrement leur garde-robe. Les objets qui ne sont jamais utilisés peuvent être jetés et ceux qui sont rarement utilisés peuvent être déplacés vers le grenier ou dans un autre endroit éloigné. Cela laisse les articles les plus couramment portés à portée de main afin qu’ils puissent être trouvés rapidement, sans fouiller.
Un cache est comme un placard bien organisé pour les données informatiques. Le cache est rempli de copies des objets les plus populaires demandés par les utilisateurs, ou « objets chauds » dans la terminologie informatique. Le cache conserve cette petite collection d’objets chauds séparément de la base de données principale d’un réseau informatique, qui est comme un vaste entrepôt rempli de toutes les informations pouvant être fournies par le système.
La mise en cache des objets chauds permet à un système en réseau de fonctionner plus efficacement, en répondant rapidement aux demandes des utilisateurs. Une application Web peut gérer efficacement plus de trafic en se plaçant dans un placard pratique pour récupérer la plupart des objets souhaités par les utilisateurs plutôt que de se rendre à l’entrepôt et de rechercher dans une énorme base de données pour chaque demande.
« La mise en cache est partout », explique Zhang. « C’est important pour toute entreprise, grande ou petite, qui utilise des applications Web. Chaque site Web a besoin d’un système de cache.
Et pourtant, la mise en cache est relativement peu étudiée dans le domaine informatique.
Comment fonctionne la mise en cache
Même si la mise en cache peut être considérée comme une armoire bien organisée pour un ordinateur, il est difficile de savoir ce qui doit se trouver dans cette armoire lorsque des millions de personnes, aux besoins en constante évolution, l’utilisent.
La mémoire rapide du cache est coûteuse à exécuter mais essentielle à une bonne expérience pour les utilisateurs Web. L’objectif est de conserver les informations futures les plus utiles dans le cache. D’autres objets doivent être continuellement éliminés, ou « expulsés » dans la terminologie technologique, pour faire place à la gamme changeante d’objets chauds.
Les algorithmes d’expulsion du cache déterminent quels objets lancer et quand le faire.
FIFO, ou « premier entré, premier sorti », est un algorithme d’expulsion classique développé dans les années 1960. Imaginez des objets alignés sur un tapis roulant. Les objets nouvellement demandés entrent à gauche et les objets les plus anciens sont expulsés lorsqu’ils atteignent la fin de la ligne à droite.
Dans l’algorithme LRU, ou « algorithme le moins récemment utilisé », les objets se déplacent également le long de la ligne vers l’expulsion à la fin. Cependant, si un objet est à nouveau demandé pendant qu’il descend sur le tapis roulant, il est replacé en tête de ligne.
Il existe des centaines de variantes d’algorithmes d’expulsion, mais ils ont tendance à devenir plus complexes pour gagner en efficacité. Cela signifie généralement qu’ils sont opaques et nécessitent une maintenance élevée, en particulier lorsqu’il s’agit de charges de travail massives.
« Si un algorithme est très compliqué, il a tendance à contenir davantage de bogues, et tous ces bogues doivent être corrigés », explique Zhang.
Une idée simple
Comme LRU et certains autres algorithmes, SIEVE apporte une simple modification au schéma FIFO de base.
SIEVE qualifie initialement un objet demandé de « zéro ». Si l’objet est à nouveau demandé au fur et à mesure qu’il descend le long de la bande, son statut passe à « un ». Lorsqu’un objet étiqueté « un » arrive à la fin de la ligne, il est automatiquement réinitialisé à « zéro » et expulsé.
Un pointeur, ou « main en mouvement », scanne également les objets à mesure qu’ils se déplacent le long de la ligne. Le pointeur commence à la fin de la ligne puis saute vers la tête en se déplaçant dans un cercle continu. Chaque fois que le pointeur touche un objet étiqueté « zéro », l’objet est expulsé.
« Il est important d’expulser les objets impopulaires le plus rapidement possible, et SIEVE est très rapide dans cette tâche », explique Zhang.
En plus de cette rétrogradation rapide des objets, SIEVE parvient à maintenir les objets populaires dans le cache avec un effort de calcul minimal, connu sous le nom de « promotion paresseuse » dans la terminologie informatique. Les chercheurs pensent que SIEVE est l’algorithme d’éviction de cache le plus simple pour obtenir efficacement à la fois une rétrogradation rapide et une promotion paresseuse.
Un taux d’échec inférieur
Le but de la mise en cache est d’obtenir un faible taux d’échecs, c’est-à-dire la fraction des objets demandés qui doivent être récupérés depuis « l’entrepôt ».
Pour évaluer SIEVE, les chercheurs ont mené des expériences sur les traces de cache Web open source provenant de Meta, Wikimedia, X et de quatre autres grands ensembles de données. Les résultats ont montré que SIEVE atteint un taux d’échec inférieur à celui de neuf algorithmes de pointe sur plus de 45 % des traces. Le deuxième meilleur algorithme a un taux d’échec inférieur de seulement 15 %.
La facilité et la simplicité de SIEVE soulèvent la question de savoir pourquoi personne n’a inventé cette méthode auparavant. L’attention portée par l’équipe SIEVE à l’évolution des modèles de trafic Web au cours des dernières années a peut-être fait la différence, théorise Zhang.
« Par exemple, dit-elle, les nouveaux articles deviennent rapidement « chauds » mais disparaissent aussi rapidement. Les gens perdent continuellement tout intérêt pour les choses parce que de nouvelles choses continuent d’apparaître. »
Les charges de travail du cache Web ont tendance à suivre ce que l’on appelle les distributions Zipfian généralisées, dans lesquelles un petit sous-ensemble d’objets représente une grande proportion des requêtes. SIEVE a peut-être atteint un point idéal Zipfian pour les charges de travail actuelles.
« Il s’agit clairement d’un moment de transformation pour notre compréhension de l’expulsion du cache Web », déclare Vigfusson. « Cela change une construction qui a été utilisée aveuglément pendant si longtemps. »
Même une infime amélioration d’un système de mise en cache Web, ajoute-t-il, peut permettre à un grand centre de données d’économiser des millions de dollars.
Zhang et Yang sont en passe de recevoir leur doctorat en mai.
« Ils font un travail incroyable », déclare Vigfusson. « On peut affirmer sans se tromper qu’ils font désormais tous deux partie des experts mondiaux en matière d’expulsion du cache Web. »
Réunion : Symposium USENIX sur la conception et la mise en œuvre de systèmes en réseau
La recherche a été financée par la National Science Foundation.
