Cloudflare a récupéré plus de 100 téraoctets de mémoire RAM sur l’ensemble de son réseau mondial après avoir repensé une partie de l’algorithme de répartition des requêtes de son service Pingora Backend Router (PBR). L’amélioration résulte d’une combinaison de la compression de la représentation des points de hachage, de la réduction de leur nombre sur la base d’une analyse statistique et du déploiement progressif d’une transition qui a préservé la stabilité du cache et du trafic vers les serveurs d’origine.
Le problème de la répartition des requêtes
Cloudflare utilise la bibliothèque pingora-ketama pour appliquer le hachage cohérent, une méthode qui aide à acheminer, autant que possible, les requêtes pouvant être mises en cache vers le même serveur. Cela permet de conserver une seule copie du fichier dans le centre de données et de fournir un chemin d’accès stable.
Mais l’utilisation d’un seul point de hachage par serveur peut entraîner de grandes disparités dans la taille des plages détenues par les serveurs sur l’anneau de hachage, et donc des charges de travail inégales. Pingora utilise donc un grand nombre de hachages virtuels par serveur, avec des pondérations liées à la capacité de stockage, tandis que des anneaux distincts sont créés pour différents ensembles de propriétés et de contraintes. L’accumulation de ces anneaux a entraîné une consommation pouvant atteindre 6 gigaoctets par processus dans certains cas.
Améliorer la représentation des données et réduire le nombre de points de hachage
Chaque élément représentant un point de l’anneau se composait d’une valeur de hachage de 32 bits et d’un index de 32 bits vers le serveur, soit huit octets en mémoire. L’équipe de Cloudflare a estimé que l’index n’avait en pratique pas besoin de plus de 16 bits, car le service ne coordonnerait pas plus d’environ 65 000 serveurs simultanément.
La réduction du type de l’index ne suffisait toutefois pas à elle seule en raison des règles d’alignement de Rust, puisque la structure aurait conservé une taille de huit octets. Cloudflare a donc stocké la valeur et l’index dans un tableau brut de six octets, avec des fonctions permettant d’accéder à chacun d’eux. Ce changement a réduit de 25 % la consommation mémoire liée au hachage.
Le gain le plus important est toutefois venu de la révision du nombre de points de hachage. Le service utilisait une valeur de base de 160 points par serveur, multipliée par le poids du serveur lié à sa capacité de stockage. L’analyse a montré que les fortes augmentations du nombre de points de hachage produisaient une amélioration décroissante de la marge d’erreur ; dans l’exemple présenté par Cloudflare, l’ajout des 90 000 derniers points de hachage n’a réduit l’erreur que d’environ 0,7 %.
De plus, l’utilisation de valeurs de hachage de 32 bits rend les collisions plus probables à mesure que le nombre de points augmente, ce qui peut ajouter une erreur imprévisible à la répartition. Sur la base de calculs et de simulations, Cloudflare a réduit de 90 % le nombre de points de hachage par serveur sans augmentation notable de l’erreur, ce qui a contribué aux économies finales.
Qu’est-ce qui change concrètement ?
Remplacer l’anneau de hachage à l’échelle du réseau en une seule fois n’était pas une option sûre, car cela aurait redistribué les requêtes et entraîné une perte effective d’une grande partie de l’efficacité du cache, avec un risque d’augmentation du trafic vers les serveurs d’origine. PBR a donc temporairement conservé en mémoire les deux anneaux, l’ancien et le nouveau, et choisissait entre eux pour chaque requête, offrant ainsi une voie de retour clairement définie.
La transition a été réalisée par étapes, en commençant par de petits sites de validation, puis par des centres de données plus importants. Le contrôle de la proportion de requêtes utilisant le nouvel anneau a également été séparé de la détermination des centres de données autorisés à participer. Cloudflare a surveillé les effets du choix du serveur, les versions des anneaux, les erreurs de connexion, la consommation mémoire, le temps de démarrage, le comportement du cache et le trafic vers les serveurs d’origine avant de supprimer l’ancien chemin.
Portée pour l’ingénierie
Cette expérience montre que des optimisations de bas niveau, comme le choix de la taille d’un champ dans une structure de données ou la détermination d’un nombre approprié de points de hachage, peuvent avoir des effets considérables lorsqu’elles sont appliquées à un réseau comprenant des milliers de serveurs. En même temps, le résultat ne signifie pas que la réduction de la mémoire est sûre dans tous les systèmes ; la précision de la répartition, les probabilités de collision, les pondérations des serveurs, les contraintes liées aux fonctionnalités et la méthode de déploiement de la transition sont autant de facteurs qui doivent être mesurés avant toute modification.
Les modifications sont désormais disponibles dans le paquet pingora-ketama via une fonctionnalité Cargo actuellement non annoncée. La version v2 prend en charge le format de stockage compact, une méthode de tri plus rapide et la possibilité de régler le nombre de base de points de hachage, tout en conservant la version v1 et en permettant d’exécuter les deux anneaux simultanément et de prendre la décision au niveau de la requête.