Quand un cache fait plus que du cache

Par Leandro Rabindranath León · SIMYL Research · 31 mars 2026 · mis à jour le 29 octobre 2026

La plupart des gens voient un cache comme un simple accélérateur de performance : il stocke un résultat, le réutilise plus tard, et c’est tout.

Mais dans les systèmes à forte concurrence, un cache peut jouer un rôle plus important. Il peut devenir un mécanisme de coordination qui protège le reste du système contre le travail dupliqué inutile.

C’est l’idée derrière cpp-cache, fondé sur une conception créée en C++ en 1998 et qui fonctionne en production depuis plus de cinq ans dans sa version en Go. L’endroit où ce protocole est utilisé et ce qui a été mesuré sont dans la fiche d’expérience Cache et architecture pour une API de paris sportifs.

Le problème : trop de fils, le même échec (miss)

Imaginez qu’une clé populaire soit demandée exactement au moment où elle n’est pas encore dans le cache.

Si dix, cinquante ou cent fils d’exécution tombent sur ce même échec à peu près au même moment, une implémentation naïve déclenche le même calcul coûteux encore et encore. Au lieu de réduire la charge, le cache l’amplifie. On consomme plus de processeur, on met plus de pression sur le backend et la latence devient plus difficile à maîtriser.

C’est le problème classique du thundering herd (le troupeau qui se rue).

flowchart LR
    subgraph sin["Sans coordination"]
        direction TB
        T1a[Fil 1] -->|MISS| B1[Backend]
        T2a[Fil 2] -->|MISS| B2[Backend]
        T3a[Fil 3] -->|MISS| B3[Backend]
        TNa[Fil N] -->|MISS| BN[Backend]
    end
    subgraph con["Avec single-flight"]
        direction TB
        T1b[Fil 1] -->|calcule| C[Cache]
        T2b[Fil 2] -.->|attend| C
        T3b[Fil 3] -.->|attend| C
        TNb[Fil N] -.->|attend| C
        C -->|1 appel| Backend
    end

    style sin fill:#fee,stroke:#c00
    style con fill:#efe,stroke:#0a0

À gauche, chaque fil frappe le backend de son côté. À droite, un fil calcule pendant que les autres attendent — le backend ne voit qu’un seul appel.

Voici la différence en pratique :

// Sans coordination : chaque fil calcule de son côté
auto val = expensive_backend_call(key);  // x100 fils = x100 appels

// Avec cpp-cache : un fil calcule, les autres attendent et partagent
auto result = cache.get_or_compute(key);
// Un seul appel au backend. Les 100 fils obtiennent le même résultat.

if (result.is_positive())
    use(*result.value());

Un bon cache concurrent ne devrait pas se contenter de mémoriser des valeurs. Il devrait aussi empêcher le système de s’effondrer quand la valeur manque.

La solution : un calcul par clé

La propriété la plus importante de la conception est simple :

Si plusieurs fils demandent la même clé manquante, un seul d’entre eux effectue le calcul. Les autres attendent et réutilisent le résultat.

C’est ce qu’on appelle le comportement single-flight.

sequenceDiagram
    participant T1 as Fil 1
    participant C as Cache
    participant T2 as Fil 2
    participant T3 as Fil 3
    participant B as Backend

    T1->>C: get_or_compute("clé")
    Note over C: Miss → État = COMPUTING
    T2->>C: get_or_compute("clé")
    Note over C: L’état est COMPUTING
    T2-->>C: Attend sur la variable de condition
    T3->>C: get_or_compute("clé")
    T3-->>C: Attend sur la variable de condition

    C->>B: Calcul coûteux
    B-->>C: Résultat

    Note over C: État = READY
    C-->>T1: Renvoie ComputedPositive
    C-->>T2: Notifie → Renvoie HitPositive
    C-->>T3: Notifie → Renvoie HitPositive

Le meilleur de cette approche est qu’elle ne sacrifie pas la concurrence globale. Les fils qui demandent des clés différentes continuent d’avancer de façon indépendante. La coordination se fait là où elle doit se faire : sur la clé disputée, pas sur tout le cache.

Le verrou global qui protège la table de hachage et la liste LRU n’est conservé que pour des opérations structurelles de l’ordre de la microseconde : recherche, insertion, réordonnancement. Toutes les requêtes le prennent brièvement, y compris les succès (recherche et passage de l’entrée en tête de la LRU), mais il n’est jamais conservé pendant que le « solver » (le calculateur) s’exécute. Le travail coûteux se fait donc sans verrou, et des clés différentes peuvent réellement être calculées en parallèle.

block-beta
    columns 4
    A["Phase 1\nMutex global\nrecherche/insertion"]:1
    B["Phase 2\nSANS VERROU\nExécution du solver"]:1
    C["Phase 3\nMutex de l’entrée\nfixer l’état + notifier"]:1
    D["Phase 4\nMutex global\nréordonnancement LRU"]:1

    style A fill:#fcc,stroke:#900
    style B fill:#cfc,stroke:#090
    style C fill:#ccf,stroke:#009
    style D fill:#fcc,stroke:#900

Le point essentiel : la phase 2 (où se fait le vrai travail) ne tient aucun verrou. C’est pourquoi plusieurs clés peuvent être résolues de façon concurrente malgré un mutex global unique.

Conçu aussi pour les échecs du monde réel

Un autre aspect remarquable du cache est qu’il traite les échecs comme des résultats significatifs.

Les résultats réussis comme les résultats en échec peuvent être stockés dans le cache, chacun avec son propre TTL.

Pourquoi est-ce important ? Prenons un scénario concret : votre backend renvoie un 404 pour une ressource qui n’existe pas. Sans cache négatif, chacune des requêtes pour cette ressource interroge de nouveau le backend. Sous un trafic élevé, une clé inexistante peut générer autant de charge qu’une clé populaire — peut-être plus, car il n’y a jamais de résultat en cache pour absorber les requêtes.

Avec le cache négatif, le premier échec appelle le « solver », obtient une erreur et stocke cette erreur pendant 30 secondes (ou le TTL négatif défini). Pendant les 30 secondes suivantes, toutes les requêtes ultérieures voient immédiatement l’échec stocké. Le backend est protégé.

C’est une petite fonctionnalité au bénéfice très concret, surtout dans les systèmes où l’ensemble des clés « absentes connues » est grand, ou bien où une défaillance du backend est temporaire et où la réessayer des centaines de fois par seconde ne sert à rien.

sequenceDiagram
    participant T1 as Fil 1
    participant C as Cache
    participant T2 as Fil 2
    participant B as Backend

    T1->>C: get_or_compute("clé-inexistante")
    C->>B: Appel au solver
    B-->>C: 404 / nullptr
    Note over C: État = FAILED (TTL=30s)
    C-->>T1: ComputedNegative

    T2->>C: get_or_compute("clé-inexistante")
    Note over C: FAILED, dans le TTL
    C-->>T2: HitNegative (instantané, sans appel au backend)

Le backend est appelé une fois. Pendant les 30 secondes suivantes, chaque requête pour cette clé obtient immédiatement l’échec en cache — sans appels redondants.

Des durées de vie plus sûres en concurrence

La conception sépare la validité logique de la durée de vie physique.

Les valeurs en cache sont exposées par des shared_ptr : une valeur peut être évincée ou invalidée par le cache sans devenir immédiatement dangereuse pour le code qui l’utilise encore.

Pourquoi est-ce important, concrètement ? Sans cette séparation, un fil qui lit une valeur en cache pourrait planter si un autre fil l’évince au mauvais moment. C’est une erreur d’« utilisation après libération » (use-after-free), l’une des classes d’erreurs mémoire les plus dangereuses en C++, qui ne se manifesterait en production que dans des conditions de synchronisation précises.

Le cache maintient aussi un compteur de références atomique interne dans chaque entrée. Une entrée ne peut pas être évincée si un fil est en train de travailler avec elle. Cet invariant est codé dans le modèle formel (nous y revenons plus bas).

sequenceDiagram
    participant A as Fil A
    participant C as Cache
    participant E as Évinceur

    A->>C: get_or_compute(clé)
    Note over C: acquire() → refcount = 2
    A->>A: Utilise la valeur (sûr)
    E->>C: Je dois évincer cette entrée
    Note over C: refcount = 2 > 1 → on passe !
    E->>C: Évince une autre entrée à la place
    A->>C: Terminé → release() → refcount = 1
    Note over C: Entrée évinçable plus tard

Le compteur de références sert de bouclier : tant qu’un fil utilise une entrée, l’évinceur l’ignore. C’est précisément l’une des propriétés que le modèle formel vérifie pour le protocole.

Un cache aux états explicites

En interne, les entrées passent par des états explicites : en calcul, prête, en échec et invalidée.

stateDiagram-v2
    [*] --> EMPTY
    EMPTY --> COMPUTING: Échec de cache
    COMPUTING --> READY: Réussite
    COMPUTING --> FAILED: Échec
    READY --> READY: Succès (rafraîchir le TTL)
    FAILED --> FAILED: Succès (rafraîchir le TTL)
    READY --> INVALIDATED: invalidate()
    FAILED --> INVALIDATED: TTL expiré
    INVALIDATED --> EMPTY: Éviction LRU
    READY --> EMPTY: TTL expiré + éviction

Remarquez les boucles sur Ready et Failed : chaque succès de cache rafraîchit le TTL, ce qui met en œuvre une fenêtre glissante qui maintient en vie les entrées consultées souvent.

C’est un choix de conception dont il faut garder la conséquence en tête : le TTL glissant limite l’inactivité, pas l’âge de la donnée. Une clé consultée plus souvent que son TTL n’expire jamais, et il en va de même pour un résultat négatif : si une ressource qui n’existait pas apparaît à l’origine, une clé négative très consultée continuera de répondre « n’existe pas ». Pour des données qui changent à l’origine, la fraîcheur se contrôle en appelant invalidate() quand l’origine signale un changement. Notez que si l’origine change pendant qu’une clé est en cours de calcul (Computing), invalidate() renverra faux ; il faut invalider la clé de nouveau une fois le calcul terminé pour ne pas continuer à servir un résultat périmé. Pour des données immuables ou de référence, le TTL glissant est exactement ce qu’il faut.

Avoir des états explicites compte.

L’implémentation en devient plus disciplinée, les règles de concurrence plus faciles à raisonner et le comportement attendu plus facile à vérifier.

Vérification formelle du protocole

Ce qui rend ce projet particulièrement intéressant pour moi, c’est qu’il ne s’arrête pas aux tests.

Le dépôt contient un modèle formel Promela/SPIN du protocole de concurrence (formal/cache_model.pml), avec des assertions de sûreté et dix propriétés LTL de vivacité (liveness), dont la terminaison, l’absence de famine et la garantie que chaque clé demandée finit par être calculée.

Il faut préciser ce qu’il démontre et ce qu’il ne démontre pas. Le modèle est borné (capacité de 2 entrées, 3 clés et 6 fils) et représente le comportement du protocole, pas une traduction ligne à ligne du code C++ ; l’expiration y est modélisée de façon abstraite. La vérification établit que le protocole respecte ces propriétés dans cet espace d’états. Elle ne couvre ni le modèle mémoire de C++, ni le compilateur, ni les exceptions, et la correspondance entre modèle et code est maintenue par revue, avec des tests de concurrence et Valgrind en complément.

La valeur pratique du modèle tient à sa confrontation avec l’implémentation : chaque garde du modèle, comme la vérification du compteur de références avant d’évincer une entrée, doit aussi exister dans le code, et cette revue croisée fait partie du travail. Les résultats d’une exécution de SPIN sur le modèle actuel (version du vérificateur, commit, espace d’états exploré et propriétés vérifiées) sont publiés avec leur sortie complète et expliqués dans Vérification formelle d’un cache C++ avec SPIN/Promela, qui détaille la portée du modèle et présente les chiffres de l’exécution.

Un regard honnête sur les compromis

Aucune conception n’est exempte de compromis, et il importe de les reconnaître.

Mutex global : le verrou unique qui protège la structure fonctionne bien quand le calcul est le vrai goulot d’étranglement (ce qui est en général le cas), mais il pourrait devenir un point de contention avec des milliers de fils et des taux d’échec très élevés. Un découpage en N sous-caches (sharding) est prévu.
Dépendance à Aleph-w : le cache utilise les structures de données intrusives d’Aleph-w pour gagner en performance, mais cela rend l’intégration plus difficile que celle d’une bibliothèque sans dépendances. Un mode autonome est à l’étude.
Benchmarks : le protocole a été validé en 2023 jusqu’à 100K requêtes par seconde dans des environnements contrôlés avec son implémentation en Go (gateway_cache). En 2026, nous avons publié de nouvelles mesures de cpp-cache et de gateway_cache avec le même protocole, sur une machine déclarée et avec les données brutes : Benchmarks. Ce sont des chiffres de bibliothèque, pas de l’architecture complète ni de production.

Ce sont des limites réelles. Elles ne remettent pas en cause la conception de fond, mais elles conditionnent son adoption aujourd’hui.

Pourquoi cela vaut la peine de s’en soucier

Une infrastructure comme celle-ci attire rarement autant d’attention que les fonctionnalités visibles par le client, mais son effet de levier est énorme.

Un meilleur cache concurrent peut signifier :

moins d’appels dupliqués au backend,
moins de gaspillage lors des rafales de trafic,
une latence plus prévisible,
un comportement mémoire plus sûr,
et plus de confiance dans la correction — non seulement grâce aux tests, mais aussi grâce à la vérification formelle du protocole.

C’est le genre d’amélioration d’ingénierie qui aide discrètement tout ce qui est construit au-dessus.

Et ensuite

Le projet est disponible en accès libre dans lrleon/cpp-cache. Si vous voulez l’essayer, les instructions de compilation montrent comment compiler et lancer les tests en moins de cinq minutes.

Les prochaines étapes prévues sont :

des benchmarks avec un nombre de fils, un espace de clés et un taux d’échec configurables ;
un découpage (sharding) pour une montée en charge linéaire avec les cœurs ;
une variante try_find() qui rende la main immédiatement si une entrée est en cours de calcul ;
une option de compilation autonome sans Aleph-w.

Les contributions, les commentaires et les critiques constructives sont les bienvenus.

Réflexion finale

Ce que j’aime le plus dans cette version de cpp-cache, c’est qu’elle reflète une idée mûre de l’ingénierie de la performance.

Il ne s’agit pas seulement de stocker des résultats plus vite. Il s’agit de maîtriser la contention avec intelligence, de protéger le système contre l’effet de troupeau et de traiter la correction comme une partie du travail de performance, pas comme une question secondaire.

Disposer d’un modèle formel du protocole, et le confronter au code, est le genre d’investissement dans la rigueur qui en vaut la peine. Tous les projets n’ont pas besoin d’un modèle Promela — mais quand on construit une infrastructure concurrente dont d’autres systèmes dépendent, le coût d’une erreur subtile en production dépasse de loin celui de la construction d’un modèle.

C’est exactement le genre d’investissement d’infrastructure qui porte ses fruits avec le temps.

Si votre système dépend d’une infrastructure concurrente semblable, voici comment nous travaillons : conseil technique en performance et architecture et développement de backends et d’API à haute performance.