Radixox
Store clé-valeur compatible Redis, écrit en Rust depuis zéro. io_uring, Adaptive Radix Trees, allocateur bitmap hiérarchique maison — et 2× les performances de Redis en benchmark fair fight.
Genèse
Je cherchais un projet à la fois techniquement stimulant et démonstratif — quelque chose qui touche à plusieurs couches de la pile système sans être trivial. Au fil de la réflexion, l’idée d’un store clé-valeur compatible Redis s’est imposée. Pas pour réinventer Redis, mais pour comprendre de l’intérieur pourquoi il est rapide, où il a des limites, et ce qu’on peut faire différemment avec les outils modernes du kernel Linux.
Le langage : Rust, sans surprise. Contrôle mémoire total, zéro garbage collector, et un système de types qui force à penser les invariants dès la conception.
Les premiers choix
io_uring et monoio
Le premier vrai choix architectural : comment gérer les I/O réseau ?
L’approche classique — epoll + thread pool — est bien rodée mais comporte un overhead fondamental : chaque syscall (read, write, accept) est une transition userspace ↔ kernel. Sur un serveur qui traite des milliers de requêtes par seconde, ces transitions s’accumulent.
io_uring change le modèle. Au lieu de syscalls individuels, on soumet des opérations I/O dans une ring buffer partagée entre userspace et kernel. Le kernel les traite et dépose les résultats dans une autre ring buffer. Résultat : on peut envoyer un batch de lectures/écritures en un seul syscall, voire zéro avec SQPOLL (le kernel poll lui-même la submission queue depuis un thread dédié).
Ce mécanisme s’accorde parfaitement avec un modèle monothread : une seule boucle d’événements, pas de locks, pas de contention. C’est exactement ce que propose monoio, le runtime async Rust construit nativement sur io_uring.
Avantage supplémentaire : monoio est compatible avec le crate bytes qui permet une gestion des buffers en zero-copy. Le buffer de lecture est partagé entre le réseau et le parser sans copie intermédiaire.
Protobuf — puis RESP2
Pour le protocole de communication, l’objectif initial était la neutralité linguistique : un protocole que n’importe quel client pourrait implémenter sans dépendre d’une bibliothèque Rust. Protobuf cochait toutes les cases : moderne, compact, langage-agnostique, bien supporté.
Sauf que… un protocole maison, aussi bien conçu soit-il, reste un protocole que personne ne connaît. Pour qu’un outil soit vraiment utilisable, il faut un écosystème. Redis a des clients dans chaque langage, des outils de benchmark (redis-benchmark, memtier_benchmark), des dashboards, des drivers d’intégration.
La décision s’est imposée : implémenter RESP2, le protocole de Redis. Si Radixox parle RESP2, n’importe quel redis-cli, n’importe quel client Redis existant fonctionne sans modification. Drop-in replacement.
OxidArt — la structure de données
Pourquoi un Radix Tree ?
Le choix de la structure d’indexation n’est pas neutre. Un HashMap donne O(1) en lecture/écriture, ce qui semble idéal. Mais Redis supporte des commandes comme KEYS user:* — retourner toutes les clés qui matchent un pattern. Sur un HashMap, cette opération impose d’itérer sur l’ensemble des clés. Sur 10 millions d’entrées, c’est 10 millions de comparaisons pour retourner peut-être 10 résultats.
Un arbre par radical (Radix Tree / ART) maintient les clés ordonnées lexicographiquement dans sa structure même. KEYS user:* se traduit en “descendre jusqu’au nœud user:, puis collecter tous les descendants”. On ne visite que les nœuds pertinents. L’opération passe de O(N) à O(préfixe + résultats).
Le trade-off : on passe de O(1) à O(k) pour les opérations de base, où k est la longueur de la clé. En pratique, k est borné (les clés Redis font rarement plus de quelques dizaines d’octets), ce qui rend ce coût négligeable.
La compression de chemin
Un arbre naïf lettre-par-lettre crée un nœud pour chaque caractère. user:1 et user:2 partagent le préfixe user: — sans compression, ça représente 6 nœuds juste pour le préfixe commun.
La compression de chemin (path compression) collapse les chaînes de nœuds à enfant unique en un vecteur de caractères stocké directement dans le nœud. user: devient une seule entrée de compression, et les deux enfants 1 et 2 partent de là.
L’approche incrémentale
La compression de chemin est élégante mais non triviale à implémenter, surtout pour les opérations d’insertion/suppression qui peuvent nécessiter de scinder ou fusionner des nœuds compressés.
Plutôt que de tout attaquer d’un coup, j’ai délibérément commencé sans compression : un nœud par caractère, simple et testable. L’objectif était d’avoir quelque chose qui fonctionne rapidement, qu’on peut tester et mesurer, avant d’ajouter de la complexité.
Cette approche — build dirty and fast first, then make it right — s’est révélée payante. Elle permet d’avancer en continu, de valider chaque étape, et d’éviter de se retrouver bloqué sur un mur de complexité sans rien de fonctionnel.
Le problème des pointeurs en Rust
En C, stocker des références entre nœuds d’un arbre est trivial : des pointeurs bruts. En Rust, c’est une autre histoire. Le borrow checker interdit les références mutuelles et les cycles — exactement ce qu’une structure d’arbre avec liens parent-enfant crée naturellement.
La solution : les slab allocators. Plutôt que de stocker des pointeurs vers des nœuds, on stocke des indices entiers (u32) dans une structure qui agit comme un tableau dense. Avantages :
- Satisfait le borrow checker : on emprunte la slab, pas les nœuds individuellement
- Debugging simplifié : un index est imprimable, un pointeur brut ne l’est pas
- Bonus inattendu : permet le versioning
Le problème ABA et les slabs générationnelles
Pour le TTL, j’ai besoin de maintenir une liste des clés qui expirent avec leurs timestamps. Problème : si je stocke l’index 42 dans cette liste, puis que la clé à l’index 42 est supprimée et qu’une nouvelle clé prend la même place, mon évictor va expirer la mauvaise entrée.
Ce problème classique s’appelle ABA. La solution : les slabs générationnelles. Chaque slot porte un compteur de génération. L’index devient une paire (idx: u32, gen: u32). Si le slot 42 est libéré et réalloué, il passe à gen: 2. L’évictor qui détient (42, gen: 1) détecte la discordance et ignore l’opération.
HiSlab — l’allocateur maison
Pour le TTL, j’avais besoin d’une capacité que les slabs classiques n’offrent pas : le tirage aléatoire. L’évictor de Redis fonctionne par échantillonnage probabiliste — il tire N clés au hasard parmi celles qui ont un TTL, expire celles dont le délai est dépassé, et répète si le taux d’expiration dépasse un seuil. Simple et efficace.
Problème : aucune slab dans l’écosystème Rust ne supporte le random picking sur un sous-ensemble (les clés avec TTL). Il a fallu en écrire une.
Autre problème avec les slabs classiques : elles gèrent la liste des slots libres par chaînage — chaque slot libre pointe vers le suivant. Sur des nœuds alignés à 64 octets, stocker un simple index de 4 octets gaspille 60 octets. Et le chaînage lui-même implique des accès mémoire non-linéaires — des cache misses.
Bitmap hiérarchique
HiSlab résout les deux problèmes avec un bitmap à plusieurs niveaux.
L’idée : partitionner la slab en blocs de 512 éléments. Un bloc de 512 bits (64 octets — exactement une cache line) sert de bitset de présence : 1 = occupé, 0 = libre.
Si les 512 premiers éléments sont tous occupés, on le note d’un seul bit au niveau supérieur. Ainsi un niveau N résume 512^N états. Avec 4 niveaux :
- Niveau 1 : 512 éléments → 1 bloc
- Niveau 2 : 512² = 262 144 éléments → 512 blocs
- Niveau 3 : 512³ = 134 millions → 512² blocs
- Niveau 4 : couvre ~2^32 éléments — suffisant pour un index
u32
Pour allouer : descendre du niveau 4 vers le niveau 1 en cherchant le premier bit libre à chaque étape (instruction tzcnt — un cycle). Écrire l’élément, marquer le bit à 1, remonter si le bloc devient plein. Maximum 8 sauts — O(1) garanti.
Pour le random picking : dupliquer la hiérarchie de présence en une hiérarchie de “tagged” (clés avec TTL). À chaque descente, choisir aléatoirement parmi les branches qui ont au moins un élément tagué. On obtient un tirage pas parfaitement uniforme mais statistiquement suffisant pour l’éviction probabiliste.
V1 → Première mesure → Douche froide
L’architecture V1 est en place : monoio, protobuf, OxidArt sans compression, slab générationnelle. Les tests locaux (sans réseau) donnent 1.5M ops/sec sur OxidArt. Très encourageant.
Premier test réseau : insérer puis récupérer les ~370 000 mots de la langue française.
36 000 ops/sec.
Douche froide. Un facteur 40 d’écart. L’enquête est rapide : chaque opération fait un aller-retour TCP séquentiel. Le client attend la réponse avant d’envoyer la prochaine requête. Sur un loopback, la latence par RTT est infime mais elle s’accumule — et l’absence de batching détruit complètement le débit.
Solution : un client qui envoie des commandes en batch, et un serveur qui lit et répond en batch plutôt que requête par requête.
Après optimisation du batching côté client et côté serveur :
700 000 ops/sec.
Radixox a sa première alpha fonctionnelle.
V2 — Réécriture propre
Fort de ces résultats, j’attaque la compression de chemin sur V1. Et là, la réalité rattrape l’architecture.
En V1, les enfants d’un nœud sont stockés dans des pools séparées par taille (Small/4, Medium/8, Large/32, Huge/128). Quand un nœud passe de 4 à 5 enfants, il faut : allouer un bloc Medium, copier les données de Small vers Medium, mettre à jour le nœud parent qui détient le lien. Tracker le parent pour chaque opération, gérer les promotions en cascade — un cauchemar.
La leçon de V1 : ne jamais faire modifier une opération sur le nœud courant le nœud parent. On redesigne complètement.
V2 adopte un modèle plus simple et plus solide :
- 10 enfants inline dans le nœud lui-même, quoi qu’il arrive
- Un index vers un bloc de débordement de 117 enfants si les 10 sont occupés
- La liste d’enfants et la valeur sont clairement séparées
Et surtout : V2 est conçu directement en mode compressé, sans passer par une version intermédiaire non-compressée. L’expérience de V1 a fourni assez de recul pour attaquer la compression dès le départ avec le bon modèle.
Cette phase a marqué un changement de workflow : j’ai commencé à travailler avec des LLM pour accélérer. Je définis les structures de données, les invariants, les signatures des méthodes — et je laisse l’IA générer l’implémentation. Ce qui a suivi naturellement : une masse de tests unitaires, indispensables pour valider chaque comportement d’une structure aussi complexe.
Le moment cache line
V2 connecté au serveur réseau, même benchmark qu’avant.
1.2M ops/sec. Pour apprécier ce chiffre, il faut le replacer dans son contexte : V1 tournait à 1.5M ops/sec, mais c’était mesuré en appel de fonction direct, sans réseau, sans pile TCP, sans sérialisation RESP, sans event loop. V2 atteint 1.2M ops/sec sur le réseau réel, avec toute la pile. Ce n’est pas une régression — c’est une victoire déguisée.
Pendant cette période, je fais de la veille sur la programmation bas niveau et les interactions avec l’OS. Un détail s’impose : les cache lines font généralement 64 octets. Si une structure dépasse 64 octets, accéder à un seul champ peut nécessiter de charger deux cache lines — deux accès mémoire au lieu d’un.
Les nœuds d’OxidArt font légèrement moins de 64 octets. En ajoutant #[repr(align(64))] — une ligne de code — chaque nœud est aligné sur une cache line exacte. Plus aucun nœud à cheval sur deux lines.
Résultat : 1.5M ops/sec sur le réseau. Même chiffre que V1 en appel local. Autrement dit : la totalité de l’overhead réseau + protocole + event loop est absorbée par l’alignement mémoire.
C’est le moment qui a tout changé dans ma façon de penser le projet. Une ligne d’annotation, +25% de performances. Le cache n’est pas un détail — c’est le facteur limitant sur ce type de workload. Chaque cache miss sur un nœud d’arbre coûte ~100 cycles d’attente mémoire. Les nœuds font maintenant exactement 128 octets (2 cache lines), avec les données du hot path groupées dans la première.
Fair fight contre Redis
Switch vers RESP2. Radixox peut maintenant répondre à redis-cli, à redis-benchmark, à n’importe quel client Redis existant.
Premier benchmark avec Redis dans Docker : 140K ops/sec pour Radixox, 70K ops/sec pour Redis. 2×. Mais la comparaison est biaisée — Radixox tourne en natif, Redis traverse la couche réseau Docker. Naïvement satisfaisant, pas scientifique.
Benchmark équitable : même machine, même conditions. Radixox sans SQPOLL — initialement activé, il monopolise un thread kernel dédié ce qui complique la comparaison iso-ressource et, surtout, crée des problèmes d’ordonnancement CPU qui dégradent le p99 et p99.9. Retiré. Valkey (le fork community de Redis) 8.1.4, persistence désactivée. YCSB Workload A, 1M records, 2M opérations, 100 threads.
| Métrique | Valkey 8.1.4 | Radixox |
|---|---|---|
| Load throughput | 79 693 ops/sec | 99 591 ops/sec |
| Load p99 | 2 347 µs | 1 119 µs |
| Run throughput | 197 413 ops/sec | 224 895 ops/sec |
| READ avg | 501 µs | 442 µs |
| READ p95 | 545 µs | 454 µs |
| READ p99 | 978 µs | 553 µs |
| READ p99.9 | 3 073 µs | 843 µs |
| READ p99.99 | 5 235 µs | 4 795 µs |
+14% de throughput en run. p99 divisé par 1.8. p99.9 divisé par 3.6.
Le chiffre le plus significatif est le p99.9 : 843 µs contre 3 073 µs. Redis accumule des spikes de latence sous charge que l’architecture io_uring + event loop monothread absorbe structurellement mieux — pas de context switch, pas de contention entre workers.
KEYS sous stéroïdes
KEYS user:* sur Redis est O(N) — N étant le nombre total de clés. Redis lui-même recommande de ne pas l’utiliser en production.
Sur un Radix Tree, on peut faire beaucoup mieux. L’idée : compiler le pattern glob en un DFA (Deterministic Finite Automaton), puis co-parcourir l’arbre et l’automate simultanément. À chaque nœud de l’arbre, on avance l’état du DFA. Si l’état devient “mort” (le pattern ne peut plus matcher dans cette branche), on élague — on ne visite pas les descendants.
admin:* retourne tous les admins en O(k + résultats) plutôt que O(N). La différence peut être de plusieurs ordres de grandeur sur une base de données large.
Pour les patterns simples (prefix*), un fast path évite même le DFA : on descend directement jusqu’au nœud préfixe et on collecte tout en dessous.
État actuel
Radixox implémente aujourd’hui la majorité des commandes Redis courantes :
- Strings / Keys : GET, SET (avec EX/PX/NX/XX), MGET, MSET, DEL, EXISTS, TTL, EXPIRE, PERSIST, KEYS, DBSIZE, FLUSHDB, INCR/DECR
- Hash : HSET, HGET, HGETALL, HDEL, HEXISTS, HLEN, HKEYS, HVALS, HINCRBY
- Set : SADD, SREM, SISMEMBER, SCARD, SMEMBERS, SPOP
- ZSet : ZADD, ZCARD, ZRANGE, ZSCORE, ZREM, ZINCRBY
- Pub/Sub : SUBSCRIBE, UNSUBSCRIBE, PUBLISH
Le modèle monothread garantit l’atomicité de toutes les opérations sans lock.
Et après ?
Le benchmark donne de bons résultats en throughput et en latence — mais il y a un problème concret que les chiffres ne montrent pas : la mémoire.
Sur 10M de clés, Radixox consomme 7.8 Go. Redis en consomme 4.0 Go. Presque 2× plus. Sur des workloads larges, c’est rédhibitoire — d’autant que la RAM est chère et que réduire le footprint mémoire améliore aussi le taux de cache hit (moins de données → plus de choses tiennent en L3).
La cause est structurelle : chaque nœud de l’arbre embarque sa valeur inline dans une enum Value. Cette enum est dimensionnée par sa plus grande variante (ZSet avec double-index). Un nœud qui stocke un simple entier paie le prix d’un ZSet.
Le modèle data-driven : ne plus stocker les valeurs inline dans les nœuds, mais uniquement un index vers une slab séparée par type. Les nœuds tombent à 64 octets (une cache line), et chaque type de valeur est stocké dans sa propre slab — on ne paie que ce qu’on utilise.
Huge pages : 1M nœuds × 128 bytes = ~128 MB. Avec des pages 4KB, le TLB doit gérer ~32 000 entrées — thrashing garanti sur un workload qui saute partout dans l’arbre. Avec des huge pages 2MB : 64 pages, le STLB contient tout. Le backing store du HiSlab (actuellement un Vec) sera remplacé par mmap + MAP_HUGETLB — zéro TLB miss au prix d’un changement purement interne à HiSlab.