SSTables : formats, indexation et compaction

Les Sorted String Tables, ou SSTables, sont au cœur des moteurs de stockage log-structured. Derrière leur apparente simplicité — des fichiers triés et immuables — se cache un mécanisme qui permet d’absorber de forts débits d’écriture tout en préservant des performances de lecture acceptables. Les SSTables constituent la brique fondamentale des moteurs comme Bigtable, LevelDB ou RocksDB.

Cette note décrit leur structure interne, leur logique d’indexation, l’utilisation des bloom filters, ainsi que les stratégies de compaction qui déterminent leur comportement à long terme.

Structure interne d’une SSTable

Une SSTable stocke des paires clé-valeur triées, réparties en blocs, avec des métadonnées regroupées en fin de fichier.

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

L’immuabilité garantit qu’aucune mise à jour n’altère le fichier : toute modification se fait par création d’un nouveau fichier, ce qui simplifie la concurrence et la récupération après crash.

Bloom filters : éviter les lectures inutiles

Dans un moteur LSM, plusieurs SSTables peuvent contenir des versions différentes d’une même clé. Pour limiter les accès disque inutiles, chaque SSTable inclut un bloom filter permettant de répondre à la question :

Cette clé est-elle certainement absente du fichier ?

Si le bloom filter indique non, le moteur s’épargne une lecture.
Si la réponse est peut-être, l’index et le bloc correspondant sont consultés.

Cette approche réduit drastiquement le coût des lectures dans les niveaux profonds de la hiérarchie.

Compaction : maintenir l’ordre et éliminer le bruit

Au fur et à mesure des flushs, les SSTables se multiplient et accumulent des clés obsolètes. La compaction fusionne les fichiers, élimine les anciennes versions, et réorganise les données.

Deux grandes stratégies dominent :

Compaction tiered (ou size-tiered)

Les fichiers de taille similaire sont regroupés puis fusionnés lorsque leur nombre dépasse un seuil.

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

Caractéristiques :

• Écritures très performantes
• Compactions moins fréquentes mais plus lourdes
• Amplification d’écriture modérée
• Convient aux charges très actives en écriture

Compaction leveled

Chaque niveau impose une taille maximale et des plages de clés non chevauchantes.

Niveau 0 : [A]
↓ merge
Niveau 1 : [R1][R2][R3]

Caractéristiques :

• Latence de lecture plus stable
• Amplification d’écriture plus élevée
• Compaction continue et granulaire
• Très utilisé dans RocksDB

Impact sur performance et latence

Les choix de compaction déterminent fortement le comportement du moteur :

Comprendre les SSTables revient donc à comprendre non seulement leur structure interne, mais aussi la dynamique des compactions qui les transforment.

Conclusion

Les SSTables illustrent parfaitement les principes log-structured : immuabilité, données triées, accès séquentiels, et séparation claire entre écriture et réorganisation. Elles constituent la pierre angulaire des moteurs LSM modernes.

Leur efficacité dépend toutefois des mécanismes de compaction, qui conditionnent la latence, le coût CPU et l’impact sur l’espace disque. Maîtriser ces interactions est essentiel pour analyser ou concevoir un moteur log-structured performant.

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