SSTables : stockage immuable, indexation et compaction

Les Sorted String Tables (SSTables) sont l’un des composants fondamentaux des moteurs de stockage log-structured. Même si elles peuvent sembler simples (« juste des fichiers clé-valeur triés sur disque »), leur conception permet un haut débit en écriture, des performances de lecture prévisibles, et une compaction efficace sur plusieurs niveaux de stockage. Les SSTables sont centrales non seulement dans des systèmes comme LevelDB, RocksDB et Bigtable, mais aussi dans de nombreux moteurs distribués et systèmes analytiques modernes.

Cette note explore comment les SSTables sont structurées, comment l’indexation et les Bloom filters minimisent les I/O, et pourquoi les stratégies de compaction influencent fortement la performance et la latence d’un moteur.

Ce qu’est vraiment une SSTable

Une SSTable est un fichier immuable et trié qui stocke des paires clé-valeur. Une fois écrit, il n’est jamais modifié en place. Cette immutabilité simplifie la concurrence, la reprise après crash, et les opérations de fusion, tout en permettant au moteur de stocker les données dans des layouts optimisés.

Une structure conceptuelle ressemble à ceci :

+-------------------------------+
|  Blocs de données (KV triés)  |
|  Blocs de données (KV triés)  |
+-------------------------------+
|  Bloc d’index (clé → offset)  |
+-------------------------------+
|  Bloom Filter                 |
+-------------------------------+
|  Footer (offsets & métadatas) |
+-------------------------------+

Chaque bloc est généralement compressé et autonome. L’index permet au moteur de localiser le bon bloc sans scanner tout le fichier. Le bloom filter sert de test probabiliste rapide pour déterminer si une clé est potentiellement contenue dans le fichier.

Ensemble, ces éléments permettent aux SSTables d’être à la fois compactes et efficaces, même à grande échelle.

Minimiser les I/O avec les Bloom Filters

Rechercher une clé à travers plusieurs SSTables pourrait devenir coûteux si le moteur devait examiner chaque fichier. Les Bloom filters résolvent cela en stockant des empreintes hashées des clés.

Un bloom filter répond à une question cruciale :

Cette clé n’est-elle définitivement PAS dans cette SSTable ?

Si le filtre répond non (définitivement absente), le moteur évite complètement des lectures disque coûteuses.
Si le filtre répond peut-être, le moteur consulte alors l’index et le bloc concerné.

Cela réduit drastiquement l’amplification des lectures (read amplification), notamment dans les structures LSM multi-niveaux où des dizaines de fichiers peuvent coexister dans les niveaux bas.

Les bloom filters sont des structures probabilistes : les faux positifs sont possibles, les faux négatifs ne le sont pas — ce qui en fait des compagnons idéaux du stockage immuable.

Compaction : maintenir l’ordre et supprimer la redondance

À mesure que les moteurs LSM flushent les memtables vers de nouvelles SSTables, plusieurs versions d’une même clé s’accumulent à travers les niveaux. La compaction est responsable de la fusion des fichiers, de la suppression des entrées obsolètes, et de la réorganisation des données afin de garantir un coût de lecture borné.

Deux grandes stratégies de compaction dominent dans les moteurs modernes :

Compaction par paliers (Tiered Compaction)

La compaction tiered (parfois appelée size-tiered ou level-0 style) regroupe des SSTables de tailles similaires et les fusionne lorsque certains seuils sont atteints.

Niveau 0 :
[File A] [File B] [File C]
fusion ↓
Niveau 1 :
[Fichier fusionné]

Caractéristiques :

• Moins de compactions au total
• Fusions massives mais moins fréquentes
• Amplification d’écriture plus élevée lorsque les grosses fusions arrivent
• Très adaptée aux forts débits d’écriture

Les systèmes tiered retardent le travail — mais quand la compaction survient, elle est lourde.

Compaction par niveaux (Leveled Compaction)

La compaction leveled vise une performance de lecture prévisible en maintenant une taille totale bornée par niveau. Les fichiers sont découpés en plages plus petites et non chevauchantes.

Niveau 0 : [File A]
fusion ↓
Niveau 1 : [R1][R2][R3]   (plages non chevauchantes)

Caractéristiques :

• Amplification de lecture plus faible
• Amplification d’écriture plus élevée (fusions fréquentes et incrémentales)
• Latence plus prévisible pour les point lookups
• Très utilisée dans RocksDB pour son équilibre performance/contrôle

Les systèmes leveled transforment la compaction en processus continu de fond, échangeant CPU et I/O contre une recherche plus stable.

Compromis performance / latence

Le choix de la stratégie de compaction influence profondément les performances :

Les SSTables sont des structures très efficaces, mais c’est la compaction qui détermine leur comportement dans le temps. Comprendre cette dynamique est essentiel lorsqu’on choisit ou qu’on ajuste un moteur de stockage.

Conclusion

Les SSTables incarnent les principes clés du design log-structured : immutabilité, données triées, et chemins d’accès optimisés. Avec l’aide des bloom filters et de stratégies de compaction soigneusement conçues, elles permettent aux moteurs de stockage d’atteindre un haut débit tout en maintenant des performances de lecture acceptables.

Même si leur simplicité est séduisante, leur comportement à long terme est gouverné par la compaction. Un processus indispensable mais coûteux qui façonne performances, latence et consommation de ressources. Maîtriser les SSTables, c’est comprendre à la fois leur structure interne et les algorithmes qui les rendent maintenables.

Références recommandées

1. Google — Bigtable: A Distributed Storage System for Structured Data
2. LevelDB — SSTable Format
3. RocksDB Engineering — Compaction Overview
4. O’Neil et al. — The Log-Structured Merge-Tree
5. Sears & Ramakrishnan — bLSM