Hiérarchie mémoire¶

Registres, caches, RAM, disques — chaque niveau est un compromis entre vitesse, capacité et coût.

La pyramide mémoire¶

Un système informatique ne dispose pas d'une seule mémoire, mais d'une hiérarchie de mémoires aux caractéristiques radicalement différentes. Plus une mémoire est rapide, plus elle est petite et coûteuse. Plus elle est grande, plus elle est lente et bon marche. Cette hiérarchie existe parce qu'il est physiquement et économiquement impossible de construire une mémoire à la fois rapide, grande et abordable.

graph TB
    R["Registres<br>~1 ns | ~1 KB"] --> L1["Cache L1<br>~1 ns | 32-64 KB"]
    L1 --> L2["Cache L2<br>~4 ns | 256 KB-1 MB"]
    L2 --> L3["Cache L3<br>~10 ns | 8-64 MB"]
    L3 --> RAM["RAM (DRAM)<br>~100 ns | 16-512 GB"]
    RAM --> SSD["SSD (NVMe)<br>~100 us | 1-16 TB"]
    SSD --> HDD["HDD<br>~10 ms | 1-20 TB"]
    HDD --> NET["Stockage distant<br>~1 ms+ | illimite"]

La pyramide fonctionne grâce à un principe statistique : à tout instant, un programme n'utilise qu'une petite fraction de ses données. Les données les plus récemment et les plus fréquemment utilisées remontent automatiquement vers le sommet de la pyramide (caches), tandis que les données dormantes restent en bas (disque, réseau).

Ce principe, formalise sous le nom de localité de référence, est l'une des observations les plus robustes de l'informatique. Il tient depuis les années 1960 et s'applique a tous les niveaux — du cache L1 au CDN géographique. Tanenbaum le présente comme le fondement de toute l'architecture mémoire.

Latences de référence¶

Ces chiffres sont les "constantes" que tout architecte doit connaître. Ils sont inspirés des "Latency Numbers Every Programmer Should Know" de Jeff Dean et adaptés aux matériels de 2024-2025.

Pour rendre ces chiffres intuitifs, une analogie courante consiste à les rapporter à une échelle humaine. Si un accès registre prenait 1 seconde :

• Un accès cache L1 prendrait 1 seconde
• Un accès cache L3 prendrait 10 secondes
• Un accès RAM prendrait 1 minute et 40 secondes
• Un accès SSD prendrait 1 jour et 3 heures
• Un accès HDD prendrait 115 jours
• Un round-trip réseau inter-region prendrait 1.5 an

Localité : spatiale et temporelle¶

La hiérarchie mémoire fonctionne uniquement parce que les programmes ont de la localité — ils ne tapent pas au hasard dans l'espace d'adressage. Deux formes de localité existent.

Localité temporelle¶

Si une donnée est accédée maintenant, elle sera probablement accédée à nouveau bientôt. C'est le cas des compteurs de boucle, des variables locales, et des objets "hot" en cache applicatif. La localité temporelle justifie l'existence même des caches : on garde en mémoire rapide ce qui a été utilisé récemment.

En pratique, la localité temporelle se manifeste par la règle des "80/20" : 80% des accès mémoire concernent 20% des données. Pour un cache applicatif, cela signifie qu'un cache relativement petit peut couvrir la majorité des requêtes.

Localité spatiale¶

Si une donnée à l'adresse N est accédée, les données aux adresses N+1, N+2, etc. seront probablement accédées bientôt. C'est pourquoi les caches chargent des lignes entières de 64 octets : on parie que les voisins seront utiles. Et le pari est généralement gagnant.

Le prefetcher matériel exploite la localité spatiale en détectant les patterns d'accès réguliers (stride access) et en chargeant les données suivantes avant qu'elles ne soient demandées. Un parcours séquentiel d'un tableau est quasi gratuit en latence grâce au prefetching — le cache est rempli en avance.

Pourquoi la localité bat la complexité algorithmique¶

Un fait contre-intuitif : un algorithme O(n log n) avec une bonne localité mémoire peut battre un algorithme O(n) avec une mauvaise localité. Prenons un exemple concret.

Un parcours lineaire d'un tableau de 1 million d'entiers (bonne localité spatiale) effectue ~1 million d'accès, mais la plupart sont servis depuis le cache L1 (~1 ns chacun). Un parcours d'une liste chaînée (mauvaise localité — les nœuds sont éparpillés en mémoire) effectue aussi ~1 million d'accès, mais chacun peut causer un cache miss L2 ou L3 (~10-100 ns chacun).

Tableau :  1M x 1 ns  = 1 ms   (cache hits)
Liste :    1M x 50 ns = 50 ms  (cache misses frequents)

Le tableau est 50x plus rapide, même avec le même nombre d'opérations. C'est pourquoi les praticiens préfèrent les structures contigues en mémoire (vecteurs, arrays) aux structures chaînées, sauf quand l'insertion/suppression en milieu de sequence est une opération dominante.

Impact sur le choix de structures de données¶

Mémoire virtuelle et pagination¶

Chaque processus voit un espace d'adressage virtuel continu, typiquement de 48 bits (256 TB) sur x86-64. Le système d'exploitation et le matériel (MMU — Memory Management Unit) traduisent les adresses virtuelles en adresses physiques.

La mémoire virtuelle résout plusieurs problèmes :

• Isolation : chaque processus a son propre espace d'adressage, impossible d'accéder à la mémoire d'un autre processus sans autorisation
• Abstraction : le programme voit un espace continu même si la mémoire physique est fragmentee
• Protection : les pages peuvent être marquées read-only, no-exécuté, etc.
• Overcommit : on peut allouer plus de mémoire virtuelle que de RAM physique disponible

Pages¶

La mémoire est découpée en pages de taille fixe :

Table des pages¶

La traduction d'une adresse virtuelle en adresse physique passe par une table des pages hierarchique. Sur x86-64, la table a 4 niveaux (5 avec la pagination a 57 bits). Chaque traduction nécessité potentiellement 4 accès mémoire en cascade — c'est pourquoi le TLB est critique.

graph LR
    VA["Adresse virtuelle"] --bits 47-39--> PML4["PML4"]
    PML4 --bits 38-30--> PDPT["PDPT"]
    PDPT --bits 29-21--> PD["Page Directory"]
    PD --bits 20-12--> PT["Page Table"]
    PT --offset--> PA["Adresse physique"]

TLB (Translation Lookaside Buffer)¶

Le TLB est un cache pour les traductions d'adresses virtuelles vers physiques. Un TLB miss déclenche un parcours de la table des pages en mémoire — une opération coûteuse (4 accès mémoire séquentiels dans le pire cas).

graph LR
    CPU["CPU"] --adresse virtuelle--> TLB["TLB"]
    TLB --hit--> PHYS["Adresse physique"]
    TLB --miss--> PT["Page Table<br>(en RAM)"]
    PT --traduction--> PHYS
    PT --maj TLB--> TLB

Avec des pages de 4 KB et un TLB de 1536 entrees (typique sur les processeurs récents), on couvre 6 MB de mémoire avant de déclencher des TLB miss. Pour une base de données manipulant des dizaines de GB, les huge pages (2 MB) permettent de couvrir 3 GB avec le même TLB — une amélioration majeure des performances.

Swap et over-commit¶

Quand la RAM physique est pleine, l'OS déplacé des pages vers le disque (swap). Sur un SSD, un accès swap coute ~100 us au lieu de ~100 ns — un facteur 1000x. Sur un HDD, c'est ~10 ms — un facteur 100 000x. Dans un contexte serveur, le swap est généralement un signal de sous-dimensionnement, pas un filet de sécurité.

L'over-commit mémoire (autoriser les processus a allouer plus que la RAM disponible) est le comportement par défaut de Linux. En théorie, cela fonctionne parce que les processus n'utilisent pas toute leur allocation simultanément. En pratique, quand la mémoire physique est épuisée, le kernel invoque l'OOM killer qui tue le processus le plus consommateur — souvent la base de données, ce qui est rarement le résultat souhaite.

DRAM vs SRAM¶

Les caches (L1, L2, L3) utilisent de la SRAM (Static RAM). La mémoire principale utilise de la DRAM (Dynamic RAM). La différence est fondamentale.

La DRAM doit être rafraichie périodiquement parce que les condensateurs se dechargent. Ce rafraichissement consomme de la bande passante et introduit des pauses — c'est l'une des raisons pour lesquelles la latence DRAM est irreductible en dessous de certains seuils.

Le coût explique tout : a ~500 USD/GB pour la SRAM contre ~4 USD/GB pour la DRAM, mettre 64 MB de SRAM (cache L3) coute déjà ~32 000 USD. Un serveur avec 512 GB de DRAM coute ~2 000 USD en mémoire. Utiliser de la SRAM comme mémoire principale est économiquement impossible.

Générations DDR¶

DDR5 double la bande passante et introduit des canaux indépendants par barrette (deux canaux de 32 bits au lieu d'un canal de 64 bits), ce qui amélioré la concurrence d'accès. Pour les serveurs NUMA à haute densite de cœurs, la bande passante mémoire par cœur est souvent le facteur limitant — et DDR5 repousse cette limite.

Bande passante mémoire¶

La latence n'est pas le seul critère — la bande passante mémoire compte aussi. Un serveur avec 8 canaux DDR5-4800 offre ~300 GB/s de bande passante. Avec 64 cœurs, cela donne ~5 GB/s par cœur. Pour des charges memory-intensive (analytics, machine learning), cette bande passante peut devenir le goulot.

Les technologies emergentes comme HBM (High Bandwidth Memory), utilisées dans les GPU et certains accelerateurs, offrent des bandes passantes de 1 a 3 TB/s en empilant la mémoire directement sur le processeur.

ECC et fiabilité¶

En environnement serveur, la mémoire est généralement ECC (Error-Correcting Code). Un bit de parite supplémentaire par octet permet de détecter et corriger les erreurs single-bit, et de détecter les erreurs double-bit.

Les erreurs mémoire ne sont pas rares : Google a rapporte un taux de ~8% de barrettes DRAM affectees par au moins une erreur corrigeable par an. Ces erreurs sont causees par les rayons cosmiques, l'interference electromagnetique et le vieillissement des composants. Sans ECC, elles se manifestent par des corruptions de données silencieuses — un risque inacceptable pour un serveur de production.

Les mémoires de type Chipkill (AMD) ou SDDC (Intel) vont plus loin : elles tolèrent la panne complète d'une puce mémoire sur une barrette, permettant au serveur de continuer a fonctionner jusqu'au remplacement de la barrette defaillante.

Technologies emergentes¶

Persistent Memory (PMEM)¶

Intel Optane DC Persistent Memory (désormais arrêté) a ouvert la voie a une mémoire persistante avec des latences proches de la DRAM (~300-400 ns) mais qui conserve les données après un redémarrage. Bien qu'Intel ait abandonne le produit, le concept survit dans CXL Memory.

CXL (Compute Express Link)¶

CXL est un protocole base sur PCIe qui permet de connecter de la mémoire externe au processeur avec des latences moderees (~150-300 ns). CXL permet :

• Le memory pooling : partager un pool de mémoire entre plusieurs serveurs
• Le memory expansion : ajouter de la mémoire au-delà des limites des slots DIMM
• Le disaggregated memory : séparer le compute de la mémoire dans le datacenter

Mesurer le comportement mémoire¶

Comprendre la hiérarchie mémoire est utile ; la mesurer sur votre système est indispensable. Les outils suivants permettent d'observer le comportement mémoire en production.

Compteurs hardware (perf)¶

# Taux de cache miss L1 et L3
perf stat -e L1-dcache-load-misses,L1-dcache-loads,LLC-load-misses,LLC-loads ./mon_programme

# Resultat typique :
# 1 200 000  L1-dcache-load-misses  (2.4% de tous les loads)
# 50 000 000 L1-dcache-loads
# 150 000    LLC-load-misses        (12.5% des loads L3)
# 1 200 000  LLC-loads

Un taux de L1 miss de 2-5% est normal. Un taux de LLC (Last Level Cache) miss supérieur à 10-20% indique un working set trop grand pour le cache L3 ou une mauvaise localité.

Outils de diagnostic mémoire¶

Implications pour l'architecte¶

La hiérarchie mémoire guide plusieurs décisions d'architecture :

1. Taille du working set : si vos données chaudes tiennent en cache L3 (dizaines de MB), la performance est radicalement différente de quand elles debordent en RAM. Mesurer le working set réel (pas la mémoire allouee) est la première étape d'un dimensionnement serieux.

2. Cache applicatif : Redis, Memcached et les caches in-process existent précisément parce que la RAM est 1000x plus rapide que le SSD. Le choix entre cache local (in-process, ~100 ns) et cache distant (Redis, ~500 us) dépend du ratio latence/cohérence. Un cache local est 5000x plus rapide mais ne partage pas ses données entre instances.

3. Dimensionnement mémoire : un processus Java avec 32 GB de heap dont 2 GB sont actifs ne beneficie pas de 64 GB de RAM supplémentaire. Inversement, une base PostgreSQL avec un working set de 30 GB et 16 GB de shared_buffers aura un taux de cache hit trop bas — augmenter la RAM a un impact direct.

4. Choix de base de données : une base in-memory (Redis, VoltDB) opère dans la zone ~100 ns. Une base sur SSD (PostgreSQL bien configurée) opère dans la zone ~100 us. Une base sur HDD opère dans la zone ~10 ms. Trois ordres de grandeur separent ces choix — et ils déterminent fondamentalement ce qui est faisable en latence.

5. Structures de données : choisir un HashMap plutôt qu'un TreeMap, un ArrayList plutôt qu'un LinkedList, ou un format binaire (Protobuf) plutôt que textuel (JSON) sont des décisions de localité autant que de complexité algorithmique.

Chapitre suivant : Entrees/sorties et bus — DMA, interruptions et ordonnancement des I/O.