Qu’est-ce qu’un arbre LSM ? Explication du Log-Structured Merge Tree

Qu’est-ce qu’un arbre LSM ?

Un log-structured merge tree (LSM), ou arbre de fusion structuré en journal, est une structure de données qui met en mémoire tampon les écritures entrantes, puis les fusionne sur disque sous forme de lots triés et immuables. Il ne modifie jamais les données sur place. À la place, il accumule les changements et reporte leur organisation, troquant ainsi la simplicité des lectures contre un meilleur débit d’écriture.

L’arbre LSM a été formalisé dans un article de 1996 de Patrick O’Neil, Edward Cheng, Dieter Gawlick et Elizabeth O’Neil, intitulé The log-structured merge-tree (LSM-tree). Il est resté pendant une dizaine d’années une structure académique relativement méconnue, avant que Google ne fonde la couche de stockage de Bigtable sur ce concept. La conception de Bigtable a donné naissance à LevelDB, LevelDB à RocksDB, et une variante de l’arbre LSM sous-tend aujourd’hui la plupart des systèmes conçus pour une ingestion intensive.  

Son nom évoque un arbre unique, ce qui est très trompeur. 

Il vaut mieux considérer un arbre LSM comme la chorégraphie de trois composants :

• Une memtable : un tampon en mémoire contenant les écritures les plus récentes
• Un write-ahead log (WAL) : un fichier sur disque en ajout seul qui rend ces écritures durables
• Une collection croissante de fichiers sorted string table (SST) : des fichiers triés et immuables qui contiennent toutes les données plus anciennes

Presque tous les aspects intéressants du comportement d’un LSM découlent de la manière dont les données circulent entre ces trois composants. Tous ces mouvements commencent par un appel de fonction unique, d’une simplicité trompeuse, généralement appelé put.

Qu’est-ce qu’un put ? 

Put est une fonction pratique qui, en interne, construit un WriteBatch contenant exactement un enregistrement et le transmet à Write(), qui gère les mutations. 

Le point de départ naturel est Put(key, value), mais, à strictement parler, cette opération n’existe pas dans RocksDB. Chaque écriture est un lot, et un put isolé est simplement un lot d’un seul élément. Les écritures atomiques multiclés sont gratuites dans RocksDB, car il s’agit d’une opération native.

Un WriteBatch est une chaîne d’octets compacte dont la structure est fixe. Il comprend un en-tête de 12 octets contenant un numéro de séquence de 8 octets et un nombre d’enregistrements de 4 octets, suivi des enregistrements eux-mêmes. Chaque enregistrement comporte une balise de type d’un octet, une clé précédée de sa longueur et, pour les écritures, une valeur précédée de sa longueur.

L’affirmation du premier article de cette série — les clés et les valeurs sont des tableaux d’octets arbitraires — devient ici littérale. L’encodage du lot ne sait pas ce que signifient les octets et ne s’en préoccupe pas. La seule structure imposée réside dans les préfixes de longueur. 

Chaque lot reçoit un compteur à croissance monotone appelé numéro de séquence. Il établit un ordre total sur toutes les écritures que la base de données a acceptées. Les numéros de séquence rendent possibles les snapshots, les lectures cohérentes et la récupération après incident. Le WAL peut être rejoué parce que chaque enregistrement qu’il contient connaît sa place dans la file.

Put, Delete, Merge

Il est important de noter qu’un Put est un kTypeValue et qu’un Delete est un kTypeDeletion, ce qui signifie qu’une suppression n’est pas un retrait. C’est plutôt une écriture — une tombstone — qui enregistre la suppression, la récupération effective de l’espace étant reportée à la compaction.

Put et Delete partagent le format WriteBatch avec kTypeMerge, écrit par l’opération Merge. Merge existe parce que le cycle lecture-modification-écriture est désastreux pour un stockage optimisé pour les écritures. Incrémenter un compteur avec Put nécessite de lire la valeur actuelle, d’y ajouter un, puis de réécrire le résultat. Cela représente deux parcours de la base de données pour modifier un seul nombre, la lecture supportant l’intégralité du coût du chemin de lecture. 

Merge évite entièrement la lecture. 

À la place, il ajoute un opérande (c’est-à-dire une description du changement, comme « ajouter un »), puis se termine. Aucun calcul n’est effectué au moment de l’écriture. La base de données combine ultérieurement les opérandes en une valeur finale à l’aide d’un opérateur de fusion fourni par l’application, soit lors de la prochaine lecture de la clé, soit lorsque la compaction rencontre la chaîne.

Les suppressions reportent la récupération de l’espace, tandis que les fusions reportent le calcul. 

Toute la personnalité de l’arbre LSM transparaît dans ces trois balises de type : chaque mutation, y compris celles qui dépendent logiquement de l’état existant, devient un ajout à l’aveugle. Dans un arbre LSM, tout est un ajout. 

Explication du chemin d’écriture de l’arbre LSM

La manière la plus claire de comprendre les arbres LSM consiste à suivre un unique Put(key, value), de l’appel de fonction jusqu’au disque.

Première étape : le write-ahead log

L’écriture est d’abord ajoutée au WAL. Cet ajout intervient avant toute modification de la memtable, et cet ordre constitue le contrat de durabilité. Autrement dit, une fois l’ajout au WAL terminé, l’écriture existe sur disque sous une forme qui résistera à un crash, même si elle n’a pas encore été organisée pour la lecture.

L’ajout à un journal est l’opération disque la moins coûteuse possible, et c’est précisément l’objectif. La durabilité est obtenue au coût d’une écriture séquentielle.

RocksDB regroupe les écritures simultanées dans des validations groupées afin d’amortir davantage le coût, et l’option sync détermine si l’ajout est transféré du cache de pages du système d’exploitation vers le stockage permanent avant le retour de l’appel.

Deuxième étape : la memtable

Une fois la durabilité assurée, l’écriture est insérée dans la memtable. Par défaut, la memtable de RocksDB est une skiplist. Elle utilise une skiplist parce qu’elle doit absorber les écritures simultanées et restituer son contenu dans l’ordre trié des clés, aussi bien pour les lectures que pour le flush ultérieur.

Une skiplist prend en charge les insertions simultanées sans verrou tout en maintenant constamment le tri. C’est l’équivalent, pour une structure de données, du classement des documents dès leur arrivée plutôt que de les laisser s’empiler.

Troisième étape : la memtable se remplit

La memtable grandit jusqu’à atteindre un seuil configuré (c’est-à-dire write_buffer_size), fixé par défaut à 64 Mo. Elle est alors marquée comme immuable, remplacée par une nouvelle memtable vide, et les écritures entrantes se poursuivent sans interruption. La memtable pleine et figée attend d’être transférée sur disque en arrière-plan. 

Les écritures ne sont jamais bloquées par le flush lui-même.

Quatrième étape : le flush

Un thread en arrière-plan écrit la memtable immuable sur disque sous forme de fichier SST, au niveau 0 (L0) de l’arbre. Comme la skiplist est déjà triée, le flush consiste en un unique passage séquentiel qui parcourt les entrées dans l’ordre et les écrit.

La memtable a terminé son travail, et les entrées correspondantes du WAL peuvent finalement être supprimées. Les données sont désormais conservées sur disque sous leur forme permanente et lisible.

Que contient un fichier SST ?

Le fichier SST est l’endroit où les données passent le reste de leur existence. Il est organisé en trois blocs et un pied de page :

• Blocs de données : les entrées triées elles-mêmes, de quelques kilo-octets chacune et compressées individuellement
• Blocs d’index : ils associent les plages de clés aux offsets des blocs, afin qu’une recherche puisse accéder directement au bon bloc
• Un bloc de filtre de Bloom facultatif : un résumé probabiliste compact qui peut répondre « cette clé ne se trouve certainement pas dans ce fichier » sans rien lire d’autre
• Un pied de page : il localise tous les éléments ci-dessus

Chaque élément de cette organisation vise à permettre aux futures lectures d’accéder au moins d’octets possible, en particulier grâce à l’index et au filtre de Bloom.

Parcours du chemin d’écriture

Tout ce qui a été expliqué ci-dessus est directement observable. Cette section suit rapidement un Put dans une base de données à l’aide de ldb et sst_dump, les outils d’inspection fournis avec RocksDB. L’exemple utilise Rust et le crate rocksdb, mais n’importe quel binding convient.

Prérequis

Pour suivre l’exemple, installez les outils en ligne de commande de RocksDB et une chaîne d’outils Rust. 

Sous macOS, brew install rocksdb fournit à la fois ldb et sst_dump. Sous Debian/Ubuntu, le paquet est rocksdb-tools.

Une fois ces éléments installés, créez un nouveau projet :

$ cargo new lsm-trace
$ cd lsm-trace
$ cargo add rocksdb

Le crate rocksdb compile la bibliothèque C++ RocksDB depuis les sources lors de la première compilation. Attendez-vous donc à ce que le premier cargo run prenne plusieurs minutes.

Première étape : écrire et arrêter

Remplacez le contenu de src/main.rs par le code suivant :

use rocksdb::{Options, DB};

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    let db = DB::open(&opts, "/tmp/lsm-trace").unwrap();

    db.put(b"slot:0001", b"hello").unwrap();
// Deliberately no flush. Let the process exit.
}

Exécutez-le une fois avec cargo run, puis affichez le contenu du répertoire de base de données qu’il a créé :

$ ls /tmp/lsm-trace
000004.log CURRENT IDENTITY LOCK LOG MANIFEST-000005 OPTIONS-000007

CURRENT et le fichier MANIFEST suivent l’inventaire des fichiers de la base de données, tandis que OPTIONS enregistre la configuration avec laquelle elle a été ouverte. LOG, sans aucun numéro, est un journal texte lisible destiné au débogage. Il ne faut pas le confondre avec 000004.log, qui est le write-ahead log lui-même.

Les numéros exacts des fichiers varieront d’une exécution à l’autre, mais pas leur structure.

Notez que le répertoire ne contient aucun fichier .sst. L’écriture est durable, puisqu’elle a survécu à l’arrêt du processus, mais elle n’existe que sous forme d’enregistrement WAL. C’est la séparation entre durabilité et organisation en action.

Deuxième étape : examiner le WAL

Pointez ldb vers le fichier .log présent dans le répertoire :

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s) 1,1,29,0,PUT(0) : 0x736C6F743A30303031

Nous avons un lot : le numéro de séquence 1, contenant 1 enregistrement (29 octets), qui est un PUT dont la clé est l’encodage hexadécimal de slot:0001. 

La taille correspond bien à l’encodage décrit précédemment : un en-tête de 12 octets, plus un enregistrement de 17 octets comprenant une balise de type, deux préfixes de longueur, une clé de 9 octets et une valeur de 5 octets.

Troisième étape : effectuer le flush et examiner le SST

Commencez par supprimer le répertoire de la base de données (c’est-à-dire rm -rf /tmp/lsm-trace) afin que cette exécution reparte de zéro.

Ajoutez une ligne dans main.rs après le put :

db.put(b"slot:0001", b"hello").unwrap();
db.flush().unwrap();

L’appel à db.flush().unwrap(); force l’écriture de la memtable dans un fichier SST au lieu d’attendre qu’elle soit pleine.

Exécutez de nouveau le fichier, puis affichez le contenu du répertoire. 

Nous pouvons maintenant voir qu’un nouveau fichier .sst apparaît dans la sortie. Nous pouvons l’examiner avec les deux modes utiles de sst_dump, en remplaçant le nom de fichier par le nom réel :

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Notez que sst_dump affiche quelques lignes préliminaires sur le format du fichier avant le résultat de l’analyse. Elles sont omises ici et dans les sorties ci-dessous.

Voici la paire clé-valeur dans son nouvel emplacement permanent, toujours accompagnée de son numéro de séquence. 

Nous pouvons ensuite afficher ses propriétés avec la commande suivante :

$ sst_dump --file=/tmp/lsm-trace/000010.sst --show_properties

La sortie des propriétés détaille l’anatomie du SST décrite plus tôt dans l’article : nombre et taille des blocs de données, taille du bloc d’index, présence d’un filtre, algorithme de compression et nombre d’entrées. 

Même avec une seule clé, tous les éléments structurels sont répertoriés, à une exception instructive près. La taille du bloc de filtre est nulle et la politique de filtrage est indiquée comme N/A, car les filtres de Bloom sont facultatifs dans RocksDB, configurés via filter_policy, et les options par défaut n’en définissent aucun. 

Le prochain article de cette série expliquera pourquoi les déploiements en production les activent presque toujours. 

Quatrième étape : rouvrir la base et vérifier le journal

Commentez les lignes du put et du flush pour ne conserver que la ligne DB::open, puis exécutez de nouveau le programme. Le contenu du répertoire montre désormais que l’ancien 000004.log a disparu, remplacé par un nouveau journal presque vide portant un numéro plus élevé. Son contenu a été transféré dans le SST à la troisième étape. Les enregistrements sont donc devenus obsolètes, et RocksDB a supprimé le fichier lors de la réouverture.

Voilà l’intégralité du couplage entre les cycles de vie du WAL et de la memtable. 

Pour descendre d’un niveau supplémentaire, nous pouvons exécuter le binaire de la première étape sous strace -e trace=write,fdatasync sur Linux afin d’observer le contrat de durabilité à la frontière des appels système. Les appels write séquentiels ajoutent des données au fichier .log, tandis que fdatasync n’apparaît que lorsque WriteOptions.sync est défini.

Cinquième étape : supprimer la clé et observer ce qui reste

L’affirmation précédente selon laquelle une suppression est une écriture peut être observée directement. 

Modifiez main.rs pour supprimer la clé et forcer un nouveau flush :

db.delete(b"slot:0001").unwrap();
db.flush().unwrap();

Exécutez-le, puis affichez le contenu du répertoire. 

Il contient désormais deux fichiers .sst. Le plus ancien est intact, car il est immuable : il contient donc toujours la clé et sa valeur. Nous pouvons le vérifier avec une analyse :

$ sst_dump --file=/tmp/lsm-trace/000010.sst --command=scan
'slot:0001' seq:1, type:1 => hello

Analysez maintenant le fichier le plus récent :

$ sst_dump --file=/tmp/lsm-trace/000014.sst --command=scan
'slot:0001' seq:2, type:0 =>

Il s’agit de la même clé, mais avec un numéro de séquence supérieur. Elle est de type:0 au lieu de type:1 et ne contient aucune valeur. C’est une tombstone : l’enregistrement kTypeDeletion de la section WriteBatch, transféré dans son propre SST. La base de données contient maintenant à la fois la valeur et l’enregistrement de sa suppression, côte à côte dans des fichiers distincts.

La lecture de la clé résoudra la contradiction en faveur de la tombstone. 

Nous pouvons le vérifier en ajoutant une recherche au programme :

match db.get(b"slot:0001").unwrap() {
    Some(v) => println!("found: {:?}", v),
    None => println!("not found"),
}

Il affichera not found, car le chemin de lecture vérifie d’abord les données les plus récentes, et un numéro de séquence de 2 l’emporte sur un numéro de séquence de 1. Du point de vue de la base de données, la valeur a disparu, mais elle se trouve encore sur le disque dans l’ancien fichier SST. 

Aucun espace n’a été récupéré : la suppression a seulement été enregistrée. Elle continuera à masquer la valeur jusqu’à ce que la compaction fusionne finalement les deux fichiers et supprime à la fois la tombstone et la valeur masquée.

Sixième étape : supprimer la clé et observer ce qui reste

Le type d’enregistrement Merge peut lui aussi être observé. Il nécessite de configurer un opérateur de fusion, car RocksDB ne peut pas savoir ce que signifie un opérande sans cet opérateur.

Supprimez une nouvelle fois le répertoire de la base de données et remplacez main.rs par le code suivant :

use rocksdb::{Options, DB, MergeOperands};

fn add(_key: &[u8], existing: Option<&[u8]>, operands: &MergeOperands) -> Option<Vec<u8>> {
    let mut total: i64 = existing
        .and_then(|v| std::str::from_utf8(v).ok())
        .and_then(|s| s.parse().ok())
        .unwrap_or(0);
    for op in operands {
        total += std::str::from_utf8(op).ok().and_then(|s| s.parse().ok()).unwrap_or(0);
    }
    Some(total.to_string().into_bytes())
}

fn main() {
    let mut opts = Options::default();
    opts.create_if_missing(true);
    opts.set_merge_operator_associative("add", add);
    let db = DB::open(&opts, "/tmp/lsm-merge").unwrap();

    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    db.merge(b"counter", b"1").unwrap();
    println!("{:?}", db.get(b"counter").unwrap());
}

L’examen du WAL montre trois enregistrements MERGE distincts. Autrement dit, trois ajouts au lieu d’une seule lecture :

$ ldb dump_wal --walfile=/tmp/lsm-trace/000004.log --header
Sequence,Count,ByteSize,Physical Offset,Key(s)
1,1,23,0,MERGE(0) : 0x636F756E746572
2,1,23,30,MERGE(0) : 0x636F756E746572
3,1,23,60,MERGE(0) : 0x636F756E746572

L’opérateur de fusion a combiné la chaîne au moment de la lecture, avec les résultats sous forme d’octets bruts. Le programme affiche Some([51]), car 51 est le code ASCII du caractère 3. Là encore, cela s’explique par le fait que les clés et les valeurs sont des tableaux d’octets arbitraires.

Nous pouvons également ajouter db.flush().unwrap(); avant la recherche, supprimer le répertoire et exécuter de nouveau le programme. Une analyse du SST montre un seul enregistrement :

'counter' seq:3, type:2 => 3

Le flush a appliqué l’opérateur et les a regroupés en un seul opérande.

Pourquoi le niveau 0 est-il particulier ?

Les nouveaux fichiers SST arrivent au niveau 0. Ce sont des snapshots directs des memtables, chacun couvrant la plage de clés que la memtable correspondante a absorbée. Les fichiers L0 peuvent donc se chevaucher, et c’est souvent le cas. Ils diffèrent ainsi des fichiers de tous les niveaux inférieurs, qui ne se chevauchent pas : chaque fichier possède une plage de clés distincte, si bien qu’un seul fichier au maximum par niveau peut contenir une clé donnée.

Par conséquent, chaque fichier L0 est un emplacement distinct où une clé peut se cacher, ce qui fait du nombre de fichiers L0 un coût direct pour les performances de lecture. C’est pourquoi RocksDB surveille étroitement le nombre de fichiers L0 et commence à ralentir, voire à suspendre, les écritures lorsqu’il devient trop élevé.

Maintenir un petit nombre de fichiers L0 est l’une des principales fonctions de la compaction.

Pourquoi les arbres LSM surpassent-ils les arbres B pour les écritures ?

Les arbres B paient le coût de l’organisation au moment de l’écriture, afin que les lectures trouvent chaque élément exactement à sa place. Les arbres LSM, eux, reportent l’organisation à la compaction en arrière-plan, dont le coût est payé ultérieurement par lots.

L’arbre B est la structure qui sous-tend la plupart des bases de données traditionnelles. Il met à jour les données sur place : chaque écriture trouve la page propriétaire de la clé, la lit, la modifie, puis la réécrit. Les pages concernées sont dispersées sur le disque. Un flux d’écritures logiquement aléatoires devient donc un flux d’E/S physiquement aléatoires.

L’arbre LSM refuse de payer au moment de l’écriture. Il ajoute des données au WAL, les met en mémoire tampon dans la memtable et les regroupe lors des flushes. Chaque écriture disque est séquentielle, et la dette d’organisation est reportée à la compaction. Le travail ne disparaît pas. Il est plutôt effectué ultérieurement par lots, regroupé sous une forme que les disques gèrent très efficacement.

Cela compte beaucoup sur les SSD, car ils ne peuvent pas du tout écraser les données sur place. 

Le stockage flash est effacé en grands blocs, dont la taille va de centaines de kilo-octets à plusieurs mégaoctets, et écrit en pages plus petites. Par conséquent, chaque petite réécriture aléatoire force la couche de traduction flash (FTL) du disque à déplacer les données actives et à effacer des blocs en arrière-plan. 

Les écritures de pages aléatoires d’un arbre B obligent constamment la FTL à effectuer ce travail. L’amplification d’écriture imposée par le périphérique s’ajoute à celle que la structure de données génère elle-même, aux dépens du débit comme de la durée de vie du disque. Les grandes écritures séquentielles d’un arbre LSM sont proches du scénario idéal pour le matériel flash.

La meilleure façon de comprendre ce compromis est de le considérer comme un emprunt. L’organisation différée devient exigible sous forme d’E/S de compaction, et les lectures doivent consulter plus d’emplacements qu’avec un arbre B. L’arbre LSM achète donc du débit d’écriture maintenant et le rembourse plus tard sous forme d’amplification de lecture et d’espace. 

Pour une analyse plus approfondie de la comparaison entre l’arbre LSM et l’arbre B en matière d’amplification de lecture, d’écriture et d’espace, consultez Arbre B ou arbre LSM. 

Que se passe-t-il après un crash de RocksDB ?

La memtable réside dans une mémoire volatile, ce qui signifie qu’un crash l’efface. C’est précisément la raison d’être du WAL.

Au redémarrage, RocksDB rejoue toutes les écritures qui avaient été confirmées, mais pas encore transférées dans un SST. Il les insère dans une nouvelle memtable afin de reconstruire l’état antérieur au crash. Le coût de la récupération est proportionnel au volume de données non transférées, d’où le lien entre les cycles de vie du WAL et de la memtable. Une fois le contenu d’une memtable transféré en toute sécurité dans un SST, les entrées correspondantes du journal deviennent obsolètes et le WAL peut être tronqué.

Une écriture devient durable dès que l’ajout au journal atteint le disque. Elle devient ensuite peu coûteuse à lire lorsque le flush l’organise. Les arbres B couplent ces opérations, tandis que les arbres LSM les séparent. L’essentiel du caractère de la structure découle de cette séparation. 

Comment Solana met-elle le chemin d’écriture à rude épreuve ?

Le premier article de cette série expliquait comment Agave stocke le registre de Solana dans RocksDB. Du point de vue du chemin d’écriture, cette charge de travail ressemble à un test de résistance conçu sur mesure. Les shreds, c’est-à-dire les unités brutes des données du registre, arrivent continuellement par le réseau à pleine vitesse, et chacun d’entre eux doit parcourir le chemin d’ajout au WAL et d’insertion dans la memtable avant que la couche de stockage du validateur ait terminé son travail.

Le mécanisme utilisé est exactement celui suivi dans cet article, mais à l’échelle de la production. Lorsque les shreds arrivent, le chemin d’insertion du Blockstore dans Agave valide un lot entier de shreds entrants, tente une récupération Reed-Solomon pour ceux qui manquent et prépare l’ensemble — charges utiles des shreds, métadonnées de slots, métadonnées d’effacement et mises à jour des index — dans un unique WriteBatch RocksDB avant de le valider en une seule écriture atomique.

Version simplifiée de insert_data_shred :

// We don't want only a subset of these changes going through.
write_batch.put_bytes::<cf::ShredData>((slot, index), &shred.payload)?;
update_slot_meta(/* ...metadata updates */);
data_index.set_present(index, true);

Ce commentaire résume en neuf mots, sous la plume des ingénieurs d’Agave, l’idée de cet article : le lot est l’unité d’atomicité, et un crash du validateur au milieu d’une insertion ne doit jamais laisser le registre partiellement mis à jour. 

Le lot d’un seul élément suivi dans l’exemple devient, au sein d’un validateur, un lot de milliers d’éléments : des shreds et leurs métadonnées répartis entre plusieurs familles de colonnes, une plage de numéros de séquence, un ajout au WAL et une validation groupée.

L’avantage est toutefois que les shreds commencent par le numéro de slot — le tuple (slot, index) de l’extrait de code simplifié est la clé ShredData — et que les slots augmentent de manière presque monotone. Chaque memtable absorbe donc une bande étroite et essentiellement consécutive de l’espace de clés, et les flushes produisent des fichiers L0 qui se chevauchent à peine.

Nous ressentons directement les effets de ce chemin d’écriture. 

Les systèmes d’archivage que nous exploitons chez Helius ingèrent l’intégralité de l’historique des transactions de Solana dans RocksDB — des centaines de téraoctets dans une charge de travail dominée par les ajouts et en croissance permanente — et la migration à l’origine de cette architecture est documentée dans notre article sur la migration de ClickHouse vers RocksDB.

Conclusion

Un arbre LSM est un compromis conclu avec le matériel. Toutes les écritures deviennent séquentielles en échange du report du travail nécessaire pour maintenir les données organisées. Le chemin de lecture doit donc rechercher les données dans davantage d’emplacements qu’avec un arbre B, par exemple. La memtable absorbe, le WAL garantit et les SST s’accumulent. Sur du stockage flash, où les réécritures aléatoires sont doublement pénalisées, c’est un excellent compromis.

Cependant, les écritures sont la partie facile. Le prix de cette conception se paie lors des lectures, car la valeur actuelle d’une clé peut se trouver dans la memtable, dans un fichier L0 ou à n’importe quel niveau inférieur. Le mécanisme qui limite ce coût est précisément là où l’ingénierie LSM devient particulièrement intéressante. 

Le prochain article de la série parcourra le chemin de lecture et abordera les memtables, les filtres de Bloom, le cache de blocs et le triangle d’amplification en action.

Si suivre une seule paire clé-valeur à travers quatre structures de données distinctes vous semble être une excellente façon de passer un après-midi, venez construire avec nous. Les systèmes décrits dans cette série sont ceux que nous déployons, exploitons et optimisons à l’échelle des marchés de capitaux sur Internet. Nous recrutons dans toute notre équipe d’ingénierie. Découvrez tous nos postes à pourvoir sur helius.dev/careers.