Le prix des écritures bon marché : comment RocksDB effectue-t-il ses lectures ?

Comment RocksDB lit-il une clé ?

Une lecture dans RocksDB parcourt les données des plus récentes aux plus anciennes et s’arrête à la première version de la clé trouvée. C’est tout ; tout le reste ne sert qu’à accélérer le processus.

L’ordre de recherche est fixe et reprend, en sens inverse, le chemin d’écriture décrit dans l’article précédent : il parcourt la memtable active, les memtables immuables, les fichiers SST du niveau 0, puis les fichiers SST triés du niveau 1 jusqu’aux niveaux inférieurs.

RocksDB vérifie d’abord la memtable active, car elle contient les écritures les plus récentes, réside en mémoire et utilise une skiplist. Une recherche y est donc triée, effectuée en mémoire et ne coûte presque aucune E/S. Elle s’arrête dès que la clé est trouvée.

Après la memtable active, RocksDB vérifie les memtables immuables qui sont pleines, mais n’ont pas encore été vidées sur disque. Il les examine ensuite, des plus récentes aux plus anciennes.

Le disque est ensuite vérifié. Chaque fichier du niveau 0 doit être examiné individuellement, du plus récent au plus ancien, car leurs plages de clés se chevauchent. En effet, chacun représente un instantané de ce qu’une memtable a absorbé, si bien qu’une même clé peut se trouver simultanément dans deux fichiers de niveau 0.

Chaque fichier du niveau 0 constitue un emplacement distinct où une clé peut se cacher. C’est précisément pourquoi le nombre de fichiers de niveau 0 pénalise les lectures et pourquoi RocksDB suspend les écritures pour le maintenir sous contrôle.

À partir du niveau 1, les fichiers SST d’un même niveau sont triés et ne se chevauchent pas. Un seul fichier au maximum par niveau peut donc contenir la clé. Ce fichier est trouvé par une recherche binaire dans les métadonnées, puis la recherche descend dans le fichier lui-même. Le bloc d’index localise le bon bloc de données, qui contient la clé ou indique que ce niveau ne la possède pas.

Les numéros de séquence sont importants pour le chemin de lecture de RocksDB, car ils permettent d’arrêter la recherche à la première version trouvée. Cela garantit qu’il s’agit de la version la plus récente. Si une lecture trouve une tombstone, par exemple, elle aboutit et indique que la clé a été supprimée. La recherche s’arrête donc à la tombstone et laisse l’ancienne valeur sur le disque.

Quelles opérations de lecture RocksDB propose-t-il ?

RocksDB propose quatre modes de lecture, chacun utilisant différemment le chemin de lecture : Get, MultiGet, Iterators et Snapshots.

Get

Get est la recherche ponctuelle décrite dans la section précédente. Elle consiste à trouver une clé en parcourant les versions de la plus récente à la plus ancienne, la première trouvée l’emportant.

MultiGet

MultiGet regroupe les recherches ponctuelles. Une lecture peut fournir à RocksDB un ensemble de clés, qu’il trie et regroupe selon les fichiers qu’elles pourraient consulter.

En pratique, cela permet à RocksDB d’ouvrir un seul SST, de consulter une seule fois ses blocs d’index et de filtre, et de regrouper les E/S. Le chemin de lecture est le même que pour Get, mais les coûts sont fixes et amortis sur tout le lot.

Itérateurs

Les Iterators parcourent des plages : ils se positionnent sur une clé, puis avancent ou reculent dans l’ordre de tri.

En pratique, un itérateur effectue une fusion à k voies (c’est-à-dire qu’il combine k listes triées distinctes en une seule séquence entièrement triée). Chaque source de données active — la memtable, chaque memtable immuable, chaque fichier L0 et un fichier par niveau inférieur — fournit son propre curseur trié. Un tas renvoie ensuite de manière répétée le curseur qui contient la plus petite clé suivante.

Cette règle donnant la priorité à la version la plus récente s’applique à chaque étape. Si plusieurs sources proposent la même clé, la version la plus récente l’emporte et les autres sont écartées.

Les valeurs masquées et les tombstones sont ignorées à mesure que l’itérateur avance. Une plage remplie de clés supprimées doit donc être parcourue silencieusement sans rien renvoyer. Un espace de clés comportant de nombreuses suppressions ralentit les analyses d’une façon que les recherches ponctuelles ne semblent jamais remarquer.

Snapshot

Un Snapshot est un numéro de séquence capturé à un instant donné. Toute lecture qui l’utilise ignore simplement les versions dont le numéro est supérieur et renvoie la version la plus récente dont le numéro lui est inférieur ou égal. Cela permet des lectures cohérentes à un instant précis, au moyen d’une simple comparaison d’entiers.

La création d’un snapshot est pratiquement gratuite, car le coût intervient plus tard : un snapshot actif peut toujours voir des versions qui ne peuvent pas être récupérées, quel que soit leur âge.

Get et MultiGet savent exactement quelle clé ils recherchent. Ils peuvent donc poser une question moins coûteuse que « où se trouve cette clé ? » : « quels fichiers ne la contiennent certainement pas ? » Les Iterators ne bénéficient jamais de ce raccourci. Répondre à cette question moins coûteuse est l’unique fonction du filtre de Bloom.

Qu’est-ce qu’un filtre de Bloom ?

Un filtre de Bloom répond à une seule question concernant un ensemble : cet élément en est-il assurément absent ? La réponse est soit « assurément absent », soit « peut-être présent », mais jamais un oui catégorique. La recherche n’ouvre jamais un fichier qui ne contient assurément pas une clé, ce qui économise des E/S.

Lorsqu’un SST est créé, chacune de ses clés passe par plusieurs fonctions de hachage. Chaque hachage active un bit dans un tableau de bits compact (le bloc de filtre).

Lors de la lecture, la clé recherchée est hachée de la même manière et ces bits sont vérifiés. Si l’un d’eux n’est pas activé, la clé n’a jamais été insérée : elle ne se trouve donc assurément pas ici.

Si tous les bits sont activés, la clé est probablement présente — probablement, car les hachages d’autres clés peuvent avoir activé les mêmes bits.

Des faux positifs sont donc possibles : la recherche ouvre le fichier, le vérifie et ne trouve rien, consommant ainsi les E/S que le filtre devait économiser.

Avec le réglage conventionnel de RocksDB de dix bits par clé, le taux de faux positifs est d’environ un pour cent. Dix bits offrent 99 % de chances d’ignorer un fichier qui ne contient pas la clé. Le filtre d’un SST d’un million de clés occupe un peu plus d’un mégaoctet, réside en mémoire avec l’index et est consulté sans accéder au disque qu’il protège. Peu de structures en ingénierie des systèmes offrent autant pour si peu.

Cela explique aussi pourquoi l’article précédent de cette série relevait une taille nulle pour le bloc de filtre. Les filtres de Bloom sont facultatifs, configurés via filter_policy avec un nombre de bits par clé choisi par l’application, et aucun n’est défini par défaut.

Ce choix par défaut est défendable pour une bibliothèque qui ne peut pas connaître sa charge de travail. Il ne l’est pas en production, où le filtre fait la différence entre une clé absente qui coûte une vérification en mémoire par fichier et une qui coûte la lecture d’un bloc d’index par fichier.

Une limite existe : les filtres de Bloom ne sont utiles que si la recherche connaît la clé exacte. Un filtre de Bloom peut déterminer si key:0301 se trouve dans ce fichier, mais pas si le fichier contient quoi que ce soit entre key:0090 et key:0110, car le hachage détruit l’ordre.

Les Iterators, qui ne connaissent jamais leur prochaine clé à l’avance, ne tirent aucun bénéfice de cette structure. Les filtres de Bloom sont une technologie destinée aux recherches ponctuelles ; les charges de travail dominées par les plages doivent chercher ailleurs pour gagner en efficacité.

Qu’en est-il des recherches par préfixe de RocksDB ?

Pour atténuer en partie le problème des analyses, RocksDB modifie ce qui est haché. Un extracteur de préfixe indique à RocksDB que les clés possèdent une structure significative, par exemple les huit premiers octets ou tout ce qui précède un séparateur. Une fois le préfixe identifié, RocksDB peut créer des filtres de Bloom sur les préfixes, à la place ou en complément des clés entières. Un filtre capable de déterminer si un fichier contient une clé commençant par un préfixe donné peut aider un itérateur.

Ce raccourci ne fonctionne toutefois qu’avec un seul préfixe.

Une analyse limitée à un préfixe donné peut ignorer des fichiers et des blocs comme le font les recherches ponctuelles. Une analyse qui passe d’un préfixe au suivant ne bénéficie pas de la même aide. Le maintien des garanties d’ordre d’itération entre les préfixes mérite une étude approfondie des subtilités de configuration qui le rendent possible.

La recherche par préfixe ne rend pas les analyses de plages peu coûteuses en général.

Elle rend plutôt peu coûteuse une forme précise et extrêmement courante d’analyse de plage pour un préfixe donné.

Qu’est-ce que le cache de blocs de RocksDB ?

Le cache de blocs est un cache en mémoire de blocs non compressés. Lorsqu’un bloc de données est lu depuis un SST, il est décompressé et conservé. La lecture suivante qui a besoin du même bloc le trouve donc sans accéder au disque. Les clés fréquemment consultées se regroupent ainsi dans des blocs fréquemment consultés, qui cessent de coûter des E/S.

Les filtres de Bloom cherchent donc à éviter que les recherches n’entrent dans les fichiers, tandis que le cache de blocs rend peu coûteuse la revisite des fichiers qu’elles doivent ouvrir.

Une subtilité tient à l’existence de deux caches.

Le cache de blocs appartient à RocksDB et contient les blocs non compressés qu’il gère explicitement. En dessous se trouve le cache de pages du système d’exploitation, qui contient les pages de fichiers brutes et compressées récemment lues par RocksDB. Les mêmes données peuvent occuper simultanément les deux caches, non compressées dans le cache de blocs et compressées dans le cache de pages. C’est pourquoi l’empreinte mémoire réelle de RocksDB est systématiquement sous-estimée et pourquoi les discussions sur le dimensionnement du cache qui ignorent le cache de pages ne tiennent compte que de la moitié du système.

Les blocs d’index et de filtre bénéficient d’un traitement particulier. Ils sont petits, consultés lors de presque chaque lecture qui atteint leur fichier et extrêmement coûteux en cas d’absence du cache. Les conserver en mémoire est donc pratiquement incontournable.

Leur intégration au budget du cache de blocs ou leur stockage hors de celui-ci, dans la mémoire propre aux lecteurs de tables, relève d’un choix de configuration (c’est-à-dire cache_index_and_filter_blocks).

Quel est le coût des tombstones et des chaînes de fusion pour les lectures ?

Les tombstones et les chaînes de fusion sont des types d’enregistrements issus du chemin d’écriture qui affectent le chemin de lecture, mais seule la compaction peut les résoudre. Les tombstones s’accumulent jusqu’à ce que la compaction les supprime avec les données qu’elles masquent. Les chaînes de fusion s’allongent jusqu’à ce que la compaction les réduise en valeurs définitives.

Une tombstone est peu coûteuse pour la recherche ponctuelle qui la trouve. La recherche s’arrête et renvoie la réponse, puisque « supprimée » constitue un résultat valide. Un itérateur ne peut cependant pas s’arrêter à une tombstone. Il doit la résoudre, ignorer les versions qu’elle masque et continuer jusqu’à trouver la prochaine clé active. Un espace de clés comportant de nombreuses suppressions est un champ de mines d’entrées qui doivent être parcourues et écartées sans rien renvoyer. Son analyse peut exiger beaucoup de travail arbitraire pour produire peu de résultats. Les recherches ponctuelles ne le remarquent jamais, tandis que les analyses de plages sont sans défense face à ce problème.

Les opérandes de fusion présentent le même coût, mais dans l’autre sens. La lecture d’une clé fusionnée ne peut pas s’arrêter à l’enregistrement le plus récent, car un opérande est une description d’une modification, et non une valeur. La recherche doit donc continuer à collecter les opérandes jusqu’à atteindre une valeur complète, une tombstone ou le bas de l’arbre, puis réduire la chaîne à l’aide de l’opérateur de fusion.

L’exemple détaillé de l’article précédent réduisait une chaîne de trois éléments, mais rien dans la conception ne limite cette chaîne à trois. Un compteur fusionné dix mille fois entre deux compactions impose une lecture qui collecte et réduit dix mille opérandes, sans que le chemin d’écriture n’ait rien fait pour l’empêcher.

Le triangle d’amplification

Le triangle d’amplification est un compromis à trois dimensions qui régit chaque arbre LSM : l’amplification des écritures, des lectures et de l’espace. Améliorer deux dimensions dégrade la troisième.

Athanassoulis et al. ont formalisé ces compromis dans la conjecture RUM (2016). Selon celle-ci, une méthode d’accès peut minimiser au maximum deux éléments parmi le surcoût de lecture, le surcoût de mise à jour et le surcoût de mémoire ou d’espace, le troisième absorbant le coût. Les arbres B occupent une position — lectures peu coûteuses, mises à jour coûteuses — tandis que les arbres LSM en occupent une autre — mises à jour peu coûteuses, lectures coûteuses. Le triangle cartographie l’espace qui les sépare.

Tout cet article montre l’un des sommets du triangle en train de se défendre.

L’amplification des écritures est le rapport entre le nombre d’octets physiquement écrits sur disque et celui des octets logiquement écrits par l’application. Un même Put est écrit une fois dans le WAL, une fois lors de son vidage vers L0, puis chaque fois qu’une compaction le fait descendre d’un niveau. Une écriture logique peut donc couramment devenir dix à trente écritures physiques au cours de sa vie dans un LSM nivelé comportant une douzaine de niveaux. Si l’article précédent se réjouit que chacune de ces écritures soit séquentielle, celui-ci le déplore.

L’amplification des lectures désigne le nombre d’emplacements qu’une requête doit vérifier pour trouver sa réponse. Pour une recherche ponctuelle, le pire cas comprend chaque memtable, chaque fichier L0 et un fichier par niveau inférieur — autrement dit, la recherche décrite au début de cet article. Le coût réel correspond à ce qui subsiste après les filtres de Bloom et le cache de blocs. Pour une analyse de plage, il s’agit de la fusion à k voies qui maintient toutes les sources ouvertes simultanément. L’amplification des lectures constitue l’essentiel du sujet de cet article : filtres, caches et extracteurs de préfixes sont les mécanismes qui permettent de la réduire.

L’amplification de l’espace est le rapport entre l’espace disque consommé et les données logiques stockées. Les anciennes versions en attente de compaction, les tombstones et les données qu’elles masquent, les chaînes de fusion non réduites et chaque version conservée par un snapshot actif occupent de l’espace disque pour des données que l’application ne peut plus lire ou ne veut plus. Une compaction nivelée bien réglée maintient ce rapport autour de 1,1x, tandis que d’autres configurations acceptent un coût nettement supérieur.

Selon le triangle, améliorer deux sommets dégrade le troisième. Autrement dit :

• Effectuer des compactions agressives : les lectures accélèrent et l’espace se resserre, mais chaque clé est constamment réécrite et l’amplification des écritures augmente
• Effectuer des compactions peu fréquentes : les écritures sont fluides, mais les fichiers s’accumulent et doivent être vérifiés lors des lectures, tandis que les données mortes persistent sur le disque
• Consacrer de la mémoire aux filtres : les caches et les lectures gagnent en efficacité, mais la mémoire est la discrète quatrième ressource sur laquelle enchérissent tous les sommets du triangle

Il n’existe aucun réglage nommé « rapide ». Il n’existe que des positions sur le triangle qui correspondent, ou non, à une charge de travail donnée.

Parcours détaillé du chemin de lecture

La suite réutilise le projet du parcours détaillé de l’article précédent, avec les statistiques activées.

Remplacez le contenu de src/main.rs par :

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

fn main() {
	let with_bloom = std::env::args().nth(1).as_deref() == Some("bloom");
	let path = if with_bloom { "/tmp/read-bloom" } else { "/tmp/read-nobloom" };

	let mut opts = Options::default();
	opts.create_if_missing(true);
	opts.enable_statistics();

	if with_bloom {
		let mut bbt = BlockBasedOptions::default();

		bbt.set_bloom_filter(10.0, false);
		opts.set_block_based_table_factory(&bbt);
	}

	let db = DB::open(&opts, path).unwrap();

	// Three L0 SSTs with fully overlapping ranges: file b holds keys where
	// key % 4 == b, all spanning 0..600. Keys where key % 4 == 3 exist nowhere
	for batch in 0..3u64 {
		let mut k = batch;

		while k < 600 {
			let key = format!("key:{:04}", k);
			db.put(key.as_bytes(), b"value").unwrap();
			k += 4;
		}

		db.flush().unwrap();
	}

	// key:0404 lives only in the oldest file, meaning the search must get past
	// the two newer files to reach it
	let hit = db.get(b"key:0404").unwrap();
	println!("get(key:0404) = {:?}", hit.map(|b| String::from_utf8(b).unwrap()));

	// key:0303 is inside every file's range and inside no file
	let miss = db.get(b"key:0303").unwrap();
	println!("get(key:0303) = {:?}", miss);

	if let Some(stats) = db.property_value("rocksdb.options-statistics").unwrap() {
		for line in stats.lines() {
			if line.contains("bloom.filter.useful")
				|| line.contains("bloom.filter.full.positive")
				|| line.contains("block.cache.data") {
				println!("{}", line);
			}
		}
	}
}

Nous avons ci-dessus trois fichiers L0 vidés dont les plages de clés se chevauchent entièrement. Aucun fichier ne peut donc être exclu sur la seule base des métadonnées de plage, car les deux clés pourraient se cacher dans chacun d’eux.

Le résultat positif (c’est-à-dire key:0404) ne se trouve que dans le fichier le plus ancien. La recherche du plus récent au plus ancien doit donc traiter deux fichiers qui ne le contiennent pas avant d’atteindre celui qui le contient.

Le résultat négatif (c’est-à-dire key:0303) se situe dans la plage de chaque fichier, mais n’est présent dans aucun d’eux. Seul un filtre de Bloom pourrait donc éviter le coût de cette lecture.

Exécutez le programme tel quel, puis avec l’argument bloom.

Sans filtre, la sortie est la suivante :

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 3
rocksdb.block.cache.data.hit COUNT : 3
rocksdb.bloom.filter.useful COUNT : 0

Il faut six accès à des blocs de données pour répondre à deux recherches. Le résultat positif a lu un bloc de données dans chacun des trois fichiers, dont deux étaient inutiles, pour un coût de trois lectures disque. Le résultat négatif a ensuite vérifié les trois mêmes fichiers. Ses trois accès aux blocs de données ont été servis par le cache uniquement parce que la première recherche venait de le réchauffer. Le cache de blocs a rempli son rôle, et il a été le seul à le faire.

Avec des filtres, la sortie est la suivante :

get(key:0404) = Some("value")
get(key:0303) = None
rocksdb.block.cache.data.miss COUNT : 1
rocksdb.block.cache.data.hit COUNT : 0
rocksdb.bloom.filter.useful COUNT : 5
rocksdb.bloom.filter.full.positive COUNT : 1

Nous n’avons qu’un seul accès à un bloc de données au total. Nous pouvons vérifier manuellement le calcul qui donne 5 pour useful :

• Le résultat positif a consulté le filtre du fichier le plus récent et celui du deuxième fichier, qui ont tous deux répondu non. Le filtre du fichier le plus ancien a renvoyé l’unique full.positive, qui s’est avéré être un vrai positif. Nous obtenons donc deux fichiers ignorés
• Le résultat négatif a consulté les trois filtres et reçu trois réponses négatives. Nous avons donc trois fichiers ignorés et aucun fichier ouvert

En additionnant le résultat positif et le résultat négatif, nous obtenons cinq vérifications de fichiers. Les cinq vérifications auxquelles les filtres ont répondu en mémoire correspondent aux cinq lectures de blocs de données que l’exécution sans filtre a dû effectuer. Dix bits par clé ont donc transformé six accès à des blocs en un seul.

Il s’agit du triangle d’amplification à plus petite échelle. L’exécution sans filtre a payé l’intégralité de l’amplification des lectures. Celle avec filtres l’a payée en mémoire — quelques centaines d’octets de filtre par fichier — et le chemin d’écriture n’a rien payé dans les deux cas. Chaque décision de réglage dans RocksDB représente ce compromis à plus grande échelle.

Comment Solana met-il le chemin de lecture sous pression ?

L’article précédent présentait le validateur comme le test de résistance du chemin d’écriture : des shreds arrivant indéfiniment au débit nominal. Le chemin de lecture représente l’autre moitié du marché, car un registre que personne ne peut relire n’est qu’un moyen coûteux de réchauffer un centre de données.

Toutes les affirmations de cet article concernant l’ordre de recherche, les filtres et la conception des clés se retrouvent dans la façon dont les données de Solana sont réellement interrogées.

Dans le validateur, les lectures du Blockstore prennent deux formes différentes : répondre aux demandes de réparation et rejouer ou diffuser un bloc.

Répondre aux demandes de réparation signifie que d’autres validateurs réclament les shreds qu’ils ont manqués. Il s’agit d’une recherche ponctuelle par (slot, index). Rejouer ou diffuser l’équivalent d’un bloc du registre consiste en une analyse de plage sur un slot donné.

Comme les clés des shreds commencent par le numéro de slot, tous les shreds d’un slot sont contigus sur le disque. « Donnez-moi le slot n » devient donc un parcours séquentiel compact avec un itérateur, plutôt qu’une série dispersée de lectures ponctuelles.

La conception des clés du chemin d’écriture optimise le chemin de lecture. La même organisation commençant par le slot, qui permettait aux vidages de produire des fichiers L0 se chevauchant à peine, transforme les lectures de blocs en un seul balayage contigu.

La couche RPC pose des questions plus difficiles. getTransaction effectue une recherche ponctuelle par signature dans les données d’état des transactions. C’est précisément le cas d’usage des filtres de Bloom : l’absence d’une signature dans un SST donné devrait coûter une vérification en mémoire pour l’exclure, et non une lecture d’index.

getSignaturesForAddress correspond à l’analyse par préfixe évoquée plus haut. L’index qui associe les adresses aux signatures commence par l’adresse. L’historique complet d’un compte occupe donc une plage de clés contiguë, et toute l’activité d’une adresse prend la forme d’analyse de plage que la structure gère efficacement.

Les questions réellement posées par les applications reposent toutefois sur les deux mécanismes. Il n’existe aucune primitive pour « Donnez-moi toutes les transactions de cette adresse ». Ce type de question devient une analyse par préfixe pour trouver les signatures, suivie d’une recherche ponctuelle par signature pour récupérer les transactions.

En pratique, une requête de plage se ramifie en centaines ou milliers d’appels Get. C’est précisément la charge de travail pour laquelle le regroupement de MultiGet existe : trier les signatures, les regrouper selon les fichiers qu’elles consultent, puis consulter une seule fois l’index et les filtres de chaque fichier.

Une requête qui ressemble de l’extérieur à un seul appel API déclenche successivement, sur le chemin de lecture, tous les mécanismes décrits dans cet article : itérateur, ordre par préfixe, filtres de Bloom, amortissement par lots et cache de blocs.

Nous avons créé cet appel API.

Auparavant, les développeurs devaient exécuter côté client une boucle composée de getSignaturesForAddress et de n appels getTransaction, avec la logique de nouvelle tentative que les schémas n+1 finissent toujours par exiger.

getTransactionsForAddress réduit cette boucle à une seule méthode et propose diverses fonctionnalités adaptées aux mécanismes du chemin de lecture abordés dans cet article.

Les ordres de tri croissant et décroissant correspondent aux deux directions de l’itérateur. La pagination par curseur renvoie un jeton de la forme slot:position, qui représente une position de clé. Reprendre une requête paginée consiste donc à repositionner une analyse à l’endroit où la précédente s’est arrêtée. Les filtres de slot et de temps délimitent le travail au lieu d’écarter les résultats après coup.

Le système d’archivage qui sert cette méthode conserve l’historique complet des transactions de Solana dans RocksDB, soit des centaines de téraoctets. Nous l’avons migré de ClickHouse vers RocksDB, et c’est la raison d’être de cette série : le moteur de stockage décrit dans ces articles est celui que nous avons réglé, famille de colonnes par famille de colonnes, afin que toute la durée de vie d’un compte forme une analyse contiguë et que la recherche d’une signature ne nécessite qu’une seule vérification en mémoire. Voilà pourquoi nous disposons du système d’archivage le plus performant de tout Solana.

Conclusion

Le chemin de lecture est l’échéancier de remboursement de l’arbre LSM, et cet article le présente sous la forme d’une facture détaillée. Une recherche parcourt les données de la plus récente à la plus ancienne, à travers la memtable, L0 et tous les niveaux triés, puis s’arrête à la première version trouvée. Toutes les autres fonctionnalités et tous les outils visent à minimiser le nombre d’accès requis : les filtres de Bloom déterminent en mémoire si une clé est assurément absente d’un fichier, afin que celui-ci reste fermé ; le cache de blocs rend peu coûteuse la réouverture des fichiers qui doivent l’être ; et la conception des préfixes transforme la seule forme abordable d’analyse de plage en celle dont les applications ont réellement besoin.

Le triangle d’amplification est le registre qui comptabilise tout cela : le coût des lectures est réduit grâce à la mémoire, tandis que celui des écritures est payé plus tôt, par versements séquentiels. Le coût de l’espace s’accumule discrètement dans chaque tombstone et chaque version masquée que la recherche doit franchir.

Notez que chaque structure présentée dans cet article ne fait que gérer le coût des fichiers accumulés, des versions mortes et des chaînes de fusion non réduites. Rien de ce qui est abordé ici ne le supprime réellement. Le mécanisme qui s’en charge s’exécute continuellement en arrière-plan, et le choix de son niveau d’agressivité constitue la décision de réglage la plus déterminante dans RocksDB. Le prochain article de cette série portera sur la compaction : son fonctionnement, les trois stratégies proposées par RocksDB et les raisons pour lesquelles le Blockstore de Solana a changé de stratégie avant de revenir à la précédente.

Si passer votre après-midi à lire un guide détaillé sur le chemin de lecture d’une base de données vous tente, venez construire avec nous. Le chemin de lecture décrit ici est celui que nous exploitons sur l’historique complet de Solana, où la différence entre la consultation d’un filtre de Bloom et l’ouverture d’un fichier se mesure en matériel réel et en argent réel. Nous recrutons dans toute notre équipe d’ingénierie. Consultez tous les postes à pourvoir sur helius.dev/careers