Contexte et objectifs

Valkey, le fork open‑source de Redis, propose depuis longtemps les sorted sets (ZSET) comme structure de données clé‑valeur ordonnée. Leur implémentation repose sur un skiplist, un graphe probabiliste qui offre des performances logarithmiques en moyenne mais impose un coût mémoire important : chaque entrée conserve plusieurs pointeurs de niveau variable. La version 9.2 introduit un index B+ tree dédié aux ensembles triés de grande taille, avec l’objectif explicite de réduire l’empreinte mémoire tout en conservant les mêmes garanties fonctionnelles.

Architecture du nouvel index

Le B+ tree de Valkey 9.2 regroupe les clés dans des nœuds contigus, ce qui améliore la densité de stockage. Chaque nœud est aligné sur des blocs de 64 bytes et exploite les instructions SIMD (Single Instruction, Multiple Data) du processeur pour comparer plusieurs clés en une seule opération. Cette approche contraste avec le skiplist, où chaque niveau nécessite une structure de pointeur distincte et où les sauts aléatoires empêchent l’utilisation efficace du cache. En outre, le B+ tree supprime la redondance des pointeurs en ne conservant que les références aux feuilles, ce qui diminue le nombre d’accès mémoire lors des recherches et des insertions.

Évaluation quantitative

Le communiqué de version indique qu’un test réalisé sur un ensemble de cinq millions d’éléments montre une réduction de l’overhead d’index par élément comprise entre 36 % et 43 %. Concrètement, si le skiplist consommait 24 bytes par entrée, le B+ tree utilise entre 13,7 et 15,4 bytes. Le comportement des commandes ZADD, ZRANGE, ZREM et similaires reste inchangé, ce qui signifie que les API existantes continuent de fonctionner sans adaptation. Le benchmark ne mentionne pas de gain de latence notable, ce qui suggère que la principale amélioration porte sur la densité mémoire plutôt que sur la vitesse brute.

Implications, limites et état de la version

La réduction d’overhead est particulièrement pertinente pour les déploiements où les ensembles triés atteignent plusieurs dizaines de millions d’éléments, par exemple les classements en temps réel ou les flux d’événements. Un index plus compact réduit la pression sur le garbage collector du serveur et diminue le risque d’échanges de pages, ce qui peut indirectement améliorer la latence sous forte charge. Cependant, la version 9.2 est encore en candidate testing : elle n’est pas encore recommandée en production, et aucune métrique de performance (temps de recherche, débit d’insertion) n’est fournie dans le communiqué. De plus, le recours aux instructions SIMD implique que les gains seront limités aux architectures x86‑64 modernes ; les processeurs plus anciens ou ARM pourraient ne pas bénéficier du même facteur d’accélération.