Der Preis günstiger Schreibvorgänge: Wie liest RocksDB?

Wie liest RocksDB einen Schlüssel?

Ein Lesevorgang in RocksDB geht von den neuesten zu den ältesten Daten und stoppt bei der ersten gefundenen Version des Schlüssels. Das ist alles. Alles andere beschleunigt diesen Prozess.

Die Suchreihenfolge ist fest und entspricht dem im vorherigen Artikel beschriebenen Schreibpfad in umgekehrter Richtung: aktive Memtable, unveränderliche Memtables, SST-Dateien auf Level 0 und sortierte SST-Dateien ab Level 1 abwärts.

RocksDB prüft zuerst die aktive Memtable. Sie enthält die neuesten Schreibvorgänge, liegt im Arbeitsspeicher und verwendet eine Skiplist. Die Abfrage ist daher eine sortierte Suche im Arbeitsspeicher, die nahezu keine I/O-Kosten verursacht. Sobald sie den Schlüssel findet, endet die Suche.

Nach der aktiven Memtable prüft RocksDB alle unveränderlichen Memtables, die bereits voll, aber noch nicht auf die Festplatte geschrieben wurden. Es prüft sie von der neuesten bis zur ältesten.

Danach folgt die Festplatte. Jede Datei auf Level 0 muss einzeln geprüft werden, von der neuesten bis zur ältesten, da sich ihre Schlüsselbereiche überschneiden. Jede Datei ist eine Momentaufnahme dessen, was eine Memtable aufgenommen hat. Deshalb kann derselbe Schlüssel gleichzeitig in zwei Dateien auf Level 0 vorkommen.

Jede Level-0-Datei ist ein weiterer möglicher Ort für einen Schlüssel. Genau deshalb belasten viele Level-0-Dateien Lesevorgänge und RocksDB hält Schreibvorgänge an, um ihre Anzahl zu begrenzen.

Ab Level 1 sind die SST-Dateien innerhalb eines Levels sortiert und überschneiden sich nicht. Daher kann höchstens eine Datei pro Level den Schlüssel enthalten. RocksDB findet diese Datei über eine binäre Suche in den Dateimetadaten und sucht dann in der Datei selbst weiter. Der Indexblock findet den richtigen Datenblock. Dieser enthält entweder den Schlüssel oder zeigt, dass er auf diesem Level nicht vorhanden ist.

Sequenznummern sind für den Lesepfad von RocksDB wichtig, weil sie die Suche bei der ersten gefundenen Version beenden. Dadurch ist garantiert, dass diese Version die neueste ist. Findet ein Lesevorgang beispielsweise einen Tombstone, ist die Suche erfolgreich und meldet, dass der Schlüssel gelöscht wurde. Die Suche endet also am Tombstone und lässt den älteren Wert auf der Festplatte liegen.

Welche Leseoperationen bietet RocksDB?

RocksDB bietet vier Arten des Lesens, die den Lesepfad jeweils anders nutzen: Get, MultiGet, Iterators und Snapshots.

Get

Get ist die Punktabfrage aus dem vorherigen Abschnitt. Dabei wird in einer Suche von den neuesten zu den ältesten Daten ein einzelner Schlüssel gefunden. Die erste Version gewinnt.

MultiGet

MultiGet bündelt Punktabfragen. Ein Lesevorgang kann RocksDB mehrere Schlüssel übergeben. RocksDB sortiert sie und gruppiert sie nach den Dateien, auf die sie möglicherweise zugreifen.

Dadurch kann RocksDB eine einzelne SST öffnen, ihre Index- und Filterblöcke einmal abfragen und die I/O bündeln. Es ist derselbe Lesepfad wie bei Get, aber die Kosten sind fix und verteilen sich auf den gesamten Batch.

Iteratoren

Iterators durchsuchen Bereiche. Sie springen zu einem Schlüssel und bewegen sich in sortierter Reihenfolge vorwärts oder rückwärts.

Ein Iterator ist im Grunde ein k-Wege-Merge. Er kombiniert also k verschiedene sortierte Listen zu einer einzigen, vollständig sortierten Sequenz. Jede aktive Datenquelle – die Memtable, jede unveränderliche Memtable, jede L0-Datei und eine Datei pro tieferem Level – steuert einen eigenen sortierten Cursor bei. Ein Heap gibt wiederholt den Cursor mit dem nächstkleineren Schlüssel aus.

Die Regel „neueste Version zuerst“ gilt bei jedem Schritt. Bieten mehrere Quellen denselben Schlüssel an, gewinnt die neueste Version und die übrigen werden verworfen.

Überschriebene Werte und Tombstones werden beim Durchlaufen des Iterators übersprungen. Einen Bereich voller gelöschter Schlüssel muss der Iterator daher unbemerkt durchlaufen, ohne etwas zurückzugeben. Viele Löschungen im Schlüsselraum verlangsamen Scans auf eine Weise, die Punktabfragen nicht wahrnehmen.

Snapshot

Ein Snapshot ist eine zu einem bestimmten Zeitpunkt erfasste Sequenznummer. Jeder Lesevorgang mit dieser Nummer ignoriert einfach neuere Versionen und gibt die neueste Version mit dieser oder einer kleineren Nummer zurück. So entstehen konsistente zeitpunktbezogene Lesevorgänge, umgesetzt als Ganzzahlvergleich.

Das Erstellen eines Snapshots ist praktisch kostenlos, weil die Kosten später entstehen. Solange ein Snapshot aktiv ist, müssen selbst sehr alte Versionen erhalten bleiben, die er noch sehen kann.

Sowohl Get als auch MultiGet kennen den gesuchten Schlüssel genau. Deshalb kann die Suche eine günstigere Frage stellen als „Wo ist dieser Schlüssel?“, nämlich: „Welche Dateien enthalten ihn definitiv nicht?“ Iterators erhalten diese Abkürzung nie. Genau diese günstigere Frage beantwortet der Bloom-Filter.

Was ist ein Bloom-Filter?

Ein Bloom-Filter beantwortet eine Frage über eine Menge: Ist dieses Element definitiv nicht darin enthalten? Die Antwort lautet entweder definitiv nicht oder vielleicht, aber nie mit Sicherheit ja. Eine Datei, die einen Schlüssel definitiv nicht enthält, muss die Suche nicht öffnen. Das spart I/O.

Beim Erstellen einer SST durchläuft jeder Schlüssel mehrere Hashfunktionen. Jeder Hash setzt ein Bit in einem kompakten Bit-Array, dem Filterblock.

Beim Lesen hasht die Abfrage den gesuchten Schlüssel auf dieselbe Weise und prüft diese Bits. Ist eines davon nicht gesetzt, wurde der Schlüssel nie eingefügt und befindet sich definitiv nicht hier.

Sind alle Bits gesetzt, ist der Schlüssel wahrscheinlich vorhanden. Nur wahrscheinlich, weil die Hashes anderer Schlüssel zufällig dieselben Bits abdecken können.

Dadurch sind falsch positive Ergebnisse möglich: Die Suche öffnet die Datei, prüft sie und findet nichts. Damit verursacht sie genau die I/O-Kosten, die der Filter vermeiden soll.

Bei der üblichen RocksDB-Einstellung von zehn Bits pro Schlüssel liegt die Falsch-Positiv-Rate bei ungefähr einem Prozent. Zehn Bits bieten eine Wahrscheinlichkeit von 99 %, eine Datei zu überspringen, die den Schlüssel nicht enthält. Der Filter für eine SST mit einer Million Schlüsseln ist etwas größer als ein Megabyte, liegt zusammen mit dem Index im Arbeitsspeicher und wird abgefragt, ohne auf die geschützte Festplatte zuzugreifen. Nur wenige Strukturen im Systems Engineering bieten mehr für weniger.

Das erklärt auch, warum der vorherige Artikel dieser Reihe eine Filterblockgröße von null ermittelt hat. Bloom-Filter müssen explizit aktiviert werden. Sie werden über filter_policy mit einer von der Anwendung gewählten Anzahl von Bits pro Schlüssel konfiguriert. Standardmäßig gibt es keinen Filter.

Für eine Bibliothek, die ihre Workload nicht kennen kann, ist diese Voreinstellung vertretbar. In der Produktion ist sie es nicht. Dort entscheidet der Filter darüber, ob ein fehlender Schlüssel eine Speicherprüfung pro Datei oder das Lesen eines Indexblocks pro Datei kostet.

Eine Einschränkung besteht darin, dass Bloom-Filter nur helfen, wenn die Suche den genauen Schlüssel kennt. Ein Bloom-Filter kann beantworten, ob key:0301 in dieser Datei vorkommt. Er kann aber nicht beantworten, ob die Datei etwas zwischen key:0090 und key:0110 enthält, da Hashes die Reihenfolge zerstören.

Iterators, die ihren nächsten Schlüssel nie im Voraus kennen, profitieren nicht von dieser Struktur. Bloom-Filter sind eine Technologie für Punktabfragen. Workloads mit vielen Bereichsabfragen müssen sich anders behelfen.

Was ist mit Präfix-Suchen in RocksDB?

RocksDBs Teillösung für das Scan-Problem besteht darin, andere Daten zu hashen. Ein Präfix-Extraktor teilt RocksDB mit, dass Schlüssel eine relevante Struktur haben, beispielsweise die ersten acht Bytes oder alles vor einem Trennzeichen. Sobald RocksDB ein Präfix erkennen kann, kann es Bloom-Filter über Präfixe statt oder zusätzlich zu vollständigen Schlüsseln erstellen. Ein Filter, der erkennt, ob eine Datei einen Schlüssel mit einem bestimmten Präfix enthält, kann einem Iterator helfen.

Diese Abkürzung funktioniert jedoch nur mit einem einzigen Präfix.

Ein Scan für ein bestimmtes Präfix kann Dateien und Blöcke genauso überspringen wie eine Punktabfrage. Ein Scan, der von einem Präfix zum nächsten wechselt, erhält nicht dieselbe Unterstützung. Wie sich die Garantien für die Iterationsreihenfolge über mehrere Präfixe hinweg einhalten lassen, verdient eine eigene ausführliche Betrachtung der dafür nötigen Konfigurationsdetails.

Prefix Seek macht Bereichsscans nicht generell günstig.

Stattdessen macht es eine bestimmte, sehr häufige Form des Bereichsscans für ein gegebenes Präfix günstig.

Was ist der RocksDB-Block-Cache?

Der Block-Cache ist ein Cache für unkomprimierte Blöcke im Arbeitsspeicher. Wird ein Datenblock aus einer SST gelesen, wird er dekomprimiert und aufbewahrt. Benötigt ein späterer Lesevorgang denselben Block, findet er ihn ohne Festplattenzugriff. Häufig verwendete Schlüssel sammeln sich dadurch in häufig verwendeten Blöcken, die keine weiteren I/O-Kosten verursachen.

Bloom-Filter versuchen also, Suchen von Dateien fernzuhalten. Der Block-Cache sorgt dagegen dafür, dass erneute Zugriffe auf unvermeidbare Dateien günstig sind.

Eine Feinheit dabei: Es gibt zwei Caches.

Der Block-Cache gehört RocksDB selbst und enthält unkomprimierte Blöcke, die RocksDB explizit verwaltet. Darunter liegt der Page-Cache des Betriebssystems. Er enthält die rohen, komprimierten Dateiseiten, die RocksDB kürzlich gelesen hat. Dieselben Daten können gleichzeitig in beiden liegen: unkomprimiert im Block-Cache und komprimiert im Page-Cache. Deshalb wird der tatsächliche Speicherbedarf von RocksDB regelmäßig unterschätzt. Diskussionen zur Cache-Größe, die den Page-Cache ignorieren, betrachten nur die Hälfte des Systems.

Index- und Filterblöcke werden gesondert behandelt. Sie sind klein, werden bei fast jedem Lesevorgang abgefragt, der ihre Datei erreicht, und ein Cache-Miss ist extrem teuer. Sie im Speicher zu halten, ist daher praktisch unverzichtbar.

Ob sie innerhalb des Budgets des Block-Caches oder außerhalb davon im eigenen Speicher der Table Reader liegen, ist eine Konfigurationsentscheidung, nämlich cache_index_and_filter_blocks.

Was kosten Tombstones und Merge-Ketten beim Lesen?

Tombstones und Merge-Ketten sind Datensatztypen des Schreibpfads, die den Lesepfad belasten, aber nur durch Kompaktierung bereinigt werden können. Tombstones sammeln sich an, bis die Kompaktierung sie und die von ihnen verdeckten Überreste entfernt. Merge-Ketten wachsen, bis die Kompaktierung sie zu endgültigen Werten zusammenfasst.

Ein Tombstone ist für die Punktabfrage, die ihn findet, günstig. Die Suche stoppt und liefert das Ergebnis, da „gelöscht“ ein gültiges Resultat ist. Ein Iterator kann an einem Tombstone jedoch nicht stoppen. Er muss den Tombstone auflösen, die von ihm verdeckten Versionen überspringen und weiterlaufen, bis er den nächsten aktiven Schlüssel findet. Ein stark gelöschter Schlüsselraum ist ein Minenfeld aus Einträgen, die durchlaufen und verworfen werden müssen, ohne etwas zurückzugeben. Scans können dadurch viel beliebige Arbeit für wenig Ausgabe leisten. Punktabfragen bemerken das nicht, Bereichsscans sind ihm schutzlos ausgeliefert.

Merge-Operanden verursachen dieselbe Rechnung, aber in die andere Richtung. Das Lesen eines zusammengeführten Schlüssels kann nicht beim neuesten Datensatz stoppen, weil ein Operand eine Beschreibung einer Änderung und kein Wert ist. Die Suche muss daher weitere Operanden sammeln, bis sie einen vollständigen Wert, einen Tombstone oder das Ende des Baums erreicht. Danach verarbeitet sie die Kette mit dem Merge-Operator.

Im Beispiel des vorherigen Artikels wurde eine Kette aus drei Elementen zusammengeführt. Das Design begrenzt die Kette jedoch nicht auf drei. Wurde ein Zähler zwischen Kompaktierungen zehntausendmal zusammengeführt, muss ein Lesevorgang zehntausend Operanden sammeln und verarbeiten. Der Schreibpfad hat nichts getan, um das zu verhindern.

Das Amplifikationsdreieck

Das Amplifikationsdreieck beschreibt einen dreifachen Zielkonflikt, der für jeden LSM-Baum gilt: Schreibamplifikation, Leseamplifikation und Speicherplatzamplifikation. Jede Verbesserung an zwei Seiten verschlechtert die dritte.

Athanassoulis et al. formalisierten diese Zielkonflikte als RUM-Vermutung (2016). Demnach kann eine Zugriffsmethode höchstens zwei der drei Faktoren Leseaufwand, Aktualisierungsaufwand und Arbeitsspeicher- oder Speicherplatzaufwand minimieren. Der dritte trägt die Kosten. B-Bäume liegen an einer Position – günstige Lesevorgänge, teure Aktualisierungen –, LSM-Bäume an einer anderen – günstige Aktualisierungen, teure Lesevorgänge. Das Dreieck bildet den Bereich dazwischen ab.

Alles in diesem Artikel zeigt, wie eine Ecke des Dreiecks sich selbst verteidigt.

Die Schreibamplifikation ist das Verhältnis der physisch auf die Festplatte geschriebenen Bytes zu den Bytes, welche die Anwendung logisch schreibt. Ein einzelnes Put wird einmal in das WAL geschrieben, einmal beim Flush nach L0 und jedes Mal, wenn die Kompaktierung es ein Level weiter nach unten verschiebt. In einem mehrstufigen LSM mit einem Dutzend Levels kann aus einem logischen Schreibvorgang über seine Lebensdauer regelmäßig das Zehn- bis Dreißigfache an physischen Schreibvorgängen werden. Der vorherige Artikel feiert, dass all diese Schreibvorgänge sequenziell sind. Dieser Artikel beklagt ihre Menge.

Die Leseamplifikation bezeichnet die Anzahl der Orte, die eine Abfrage prüfen muss, um ihre Antwort zu finden. Bei einer Punktabfrage umfasst der schlimmste Fall jede Memtable, jede L0-Datei und eine Datei pro tieferem Level – also die am Anfang dieses Artikels beschriebene Suche. Die tatsächlichen Kosten hängen davon ab, was die Bloom-Filter und den Block-Cache übersteht. Bei einem Bereichsscan ist es der k-Wege-Merge, der alle Quellen gleichzeitig offen hält. Die Leseamplifikation ist im Wesentlichen das Thema dieses Artikels: Filter, Caches und Präfix-Extraktoren sind die Mechanismen, die sie reduzieren.

Die Speicherplatzamplifikation ist das Verhältnis zwischen belegtem Festplattenspeicher und logisch gespeicherten Daten. Alte Versionen, die auf die Kompaktierung warten, Tombstones und die von ihnen verdeckten Überreste, nicht zusammengeführte Merge-Ketten sowie jede von einem aktiven Snapshot festgehaltene Version belegen Speicherplatz für Daten, die die Anwendung nicht mehr lesen kann oder nicht mehr benötigt. Eine gut abgestimmte mehrstufige Kompaktierung hält diesen Faktor nahe 1,1x. Andere Anordnungen benötigen deutlich mehr.

Das Dreieck besagt, dass jede Verbesserung an zwei Ecken die dritte verschlechtert. Konkret:

• Aggressiv kompaktieren: Lesevorgänge werden schneller und der Speicherbedarf sinkt, aber jeder Schlüssel wird ständig neu geschrieben und die Schreibamplifikation steigt
• Selten kompaktieren: Schreibvorgänge laufen reibungslos, aber die zu prüfenden Dateien häufen sich und tote Daten bleiben auf der Festplatte
• Arbeitsspeicher für Filter einsetzen: Caches und Lesevorgänge profitieren, aber Arbeitsspeicher ist die stille vierte Ressource, um die alle Ecken des Dreiecks konkurrieren

Es gibt keine Einstellung namens „schnell“. Es gibt nur Positionen im Dreieck, die zu einer bestimmten Workload passen oder nicht.

Schritt für Schritt durch den Lesepfad

Das folgende Beispiel verwendet das Projekt aus der Schritt-für-Schritt-Anleitung des vorherigen Artikels erneut und aktiviert Statistiken.

Ersetze den Inhalt von src/main.rs durch:

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);
			}
		}
	}
}

Wir haben hier drei auf L0 geschriebene Dateien, deren Schlüsselbereiche sich vollständig überschneiden. Die Bereichsmetadaten allein können daher keine Datei ausschließen, weil beide Schlüssel in jeder Datei verborgen sein könnten.

Der Treffer, also key:0404, liegt nur in der ältesten Datei. Die Suche von der neuesten zur ältesten Datei muss daher zunächst zwei Dateien verarbeiten, die ihn nicht enthalten, bevor sie die richtige erreicht.

Der Fehlschlag, also key:0303, liegt innerhalb des Bereichs jeder Datei, aber in keiner Datei selbst. Nur ein Bloom-Filter kann diesen Lesevorgang vermeiden.

Führe das Beispiel unverändert und danach mit dem Argument bloom aus.

Ohne Filter lautet die Ausgabe:

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

Für zwei Abfragen erfolgen sechs Zugriffe auf Datenblöcke. Der Treffer liest einen Datenblock aus jeder der drei Dateien. Zwei davon helfen nicht, sodass drei Festplattenzugriffe anfallen. Der Fehlschlag prüft anschließend dieselben drei Dateien. Seine drei Datenblockzugriffe sind nur deshalb Cache-Treffer, weil die erste Abfrage den Cache gerade aufgewärmt hat. Der Block-Cache hat seine Aufgabe erfüllt – und nur er.

Mit Filtern lautet die Ausgabe:

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

Insgesamt erfolgt nur ein Zugriff auf einen Datenblock. Wir können die Berechnung für useful mit dem Wert 5 von Hand prüfen:

• Der Treffer fragt den Filter der neuesten und den der zweiten Datei ab. Beide antworten mit Nein. Der Filter der ältesten Datei liefert das eine full.positive, das sich als tatsächlich positiv erweist. Damit überspringen wir zwei Dateien
• Der Fehlschlag fragt alle drei Filter ab und erhält dreimal Nein. Damit überspringen wir drei Dateien und öffnen keine einzige

Zusammen ergeben Treffer und Fehlschlag fünf Dateiprüfungen. Die fünf Dateiprüfungen, die Filter aus dem Arbeitsspeicher beantwortet haben, entsprechen den fünf Datenblock-Lesevorgängen, die der Lauf ohne Filter ausführen musste. Zehn Bits pro Schlüssel reduzieren sechs Blockzugriffe auf einen.

Im Kleinen ist das das Amplifikationsdreieck. Der Lauf ohne Filter trägt die volle Leseamplifikation. Der gefilterte Lauf bezahlt sie mit Arbeitsspeicher, also einigen Hundert Bytes Filterdaten pro Datei. Der Schreibpfad bezahlt in beiden Fällen nichts. Jede Optimierungsentscheidung in RocksDB ist derselbe Handel in größerem Maßstab.

Wie belastet Solana den Lesepfad?

Der vorherige Artikel stellte den Validator als Belastungstest für den Schreibpfad dar: Shreds kommen für immer mit voller Leitungsgeschwindigkeit an. Der Lesepfad ist die andere Hälfte des Geschäfts, denn ein Ledger, das niemand auslesen kann, ist nur eine teure Methode, ein Rechenzentrum aufzuwärmen.

Alle Aussagen dieses Artikels über Suchreihenfolge, Filter und Schlüsseldesign spiegeln sich darin wider, wie Solanas Daten tatsächlich abgefragt werden.

Im Validator treten die Lesevorgänge des Blockstore in zwei verschiedenen Formen auf: Reparaturanfragen beantworten und einen Block wiedergeben oder streamen.

Bei Reparaturanfragen bitten andere Validatoren um Shreds, die ihnen fehlen. Das ist eine Punktabfrage nach (slot, index). Das Wiedergeben oder Streamen der Ledger-Daten eines Blocks ist ein Bereichsscan über einen bestimmten Slot.

Da Shred-Schlüssel mit der Slot-Nummer beginnen, liegen alle Shreds eines Slots zusammenhängend auf der Festplatte. „Gib mir Slot n“ ist daher ein enger, sequenzieller Iterator-Durchlauf statt einer Streuung von Punktabfragen.

Das Schlüsseldesign des Schreibpfads optimiert den Lesepfad. Dasselbe Slot-zuerst-Layout, durch das Flushes L0-Dateien mit kaum überlappenden Bereichen erzeugen, macht das Lesen von Blöcken zu einem einzigen zusammenhängenden Durchlauf.

Die RPC-Schicht stellt schwierigere Fragen. getTransaction ist eine Punktabfrage nach Signatur in den Transaktionsstatusdaten. Genau für diesen Fall gibt es Bloom-Filter: Eine Signatur, die in einer bestimmten SST fehlt, sollte sich mit einer einzigen Speicherprüfung ausschließen lassen statt einen Indexzugriff zu erfordern.

getSignaturesForAddress ist der zuvor beschriebene präfixbasierte Scan. Der Index von Adressen zu Signaturen beginnt mit der Adresse. Daher belegt der gesamte Verlauf eines Accounts einen zusammenhängenden Schlüsselbereich, und sämtliche Aktivitäten einer Adresse bilden genau die Art von Bereichsscan, welche die Struktur gut verarbeitet.

Die Fragen, die Anwendungen tatsächlich stellen, bauen jedoch auf beiden Verfahren auf. Es gibt kein Primitiv für „Gib mir alle Transaktionen für diese Adresse“. Eine solche Frage wird zu einem Präfix-Scan nach den Signaturen und anschließend zu je einer Punktabfrage pro Signatur nach den Transaktionen.

Eine Bereichsabfrage fächert sich damit in Hunderte oder Tausende Gets auf. Genau für diese Workload gibt es die Batch-Verarbeitung von MultiGet: Signaturen sortieren, nach den betroffenen Dateien gruppieren und Index sowie Filter jeder Datei nur einmal abfragen.

Eine Abfrage, die von außen wie ein einzelner API-Aufruf aussieht, aktiviert auf dem Lesepfad nacheinander jeden in diesem Artikel beschriebenen Mechanismus: Iterator, Präfix-Sortierung, Bloom-Filter, Batch-Amortisierung und Block-Cache.

Wir haben diesen API-Aufruf entwickelt.

Früher mussten Entwickler clientseitig eine Schleife aus getSignaturesForAddress und n Aufrufen von getTransaction ausführen – einschließlich der Wiederholungslogik, die n+1-Muster letztlich immer benötigen.

getTransactionsForAddress fasst diese Schleife in einer einzigen Methode zusammen. Sie bietet verschiedene Funktionen, die zu den in diesem Artikel behandelten Mechanismen des Lesepfads passen.

Aufsteigende und absteigende Sortierung entsprechen den beiden Richtungen des Iterators. Cursorbasierte Paginierung gibt ein Token der Form slot:position zurück. Da es eine Schlüsselposition ist, setzt eine paginierte Abfrage ihren Scan dort fort, wo der letzte aufgehört hat. Slot- und Zeitfilter begrenzen die Arbeit, statt Ergebnisse erst nachträglich zu verwerfen.

Das Archivsystem hinter dieser Methode speichert Solanas vollständigen Transaktionsverlauf in RocksDB – Hunderte Terabytes. Wir haben es von ClickHouse zu RocksDB migriert. Diese Migration ist der Grund für diese Artikelreihe: Wir haben die hier beschriebene Storage Engine Column Family für Column Family optimiert. So wird die gesamte Lebensdauer eines Accounts zu einem zusammenhängenden Scan und die Suche nach einer Signatur zu einer einzelnen Speicherprüfung. Deshalb betreiben wir das leistungsstärkste Archivsystem in ganz Solana.

Fazit

Der Lesepfad ist der Tilgungsplan des LSM-Baums. Dieser Artikel schlüsselt seine Rechnung auf. Eine Abfrage durchläuft die Daten von den neuesten zu den ältesten – durch die Memtable, L0 und alle sortierten Levels – und stoppt bei der ersten gefundenen Version. Alle anderen Funktionen und Tools minimieren die Anzahl der nötigen Zugriffe: Bloom-Filter beantworten aus dem Arbeitsspeicher, ob sich ein Schlüssel definitiv nicht in einer Datei befindet, sodass diese geschlossen bleibt. Der Block-Cache macht das erneute Öffnen unvermeidbarer Dateien günstig. Das Präfixdesign macht die eine erschwingliche Form des Bereichsscans zu der Form, die Anwendungen tatsächlich benötigen.

Das Amplifikationsdreieck ist das Hauptbuch, in dem all das festgehalten wird: Lesekosten werden mit Arbeitsspeicher beglichen, Schreibkosten vorab in sequenziellen Raten. Speicherplatzkosten sammeln sich unbemerkt mit jedem Tombstone und jeder überschriebenen Version an, welche die Suche überspringt.

Beachte, dass jede Struktur in diesem Artikel die Kosten angesammelter Dateien, toter Versionen und nicht verarbeiteter Merge-Ketten lediglich verwaltet. Nichts davon entfernt sie tatsächlich. Der Mechanismus, der sie entfernt, läuft kontinuierlich im Hintergrund. Wie aggressiv er arbeitet, ist die folgenreichste Optimierungsentscheidung in RocksDB. Der nächste Artikel dieser Reihe behandelt die Kompaktierung: was sie macht, welche drei Varianten RocksDB bietet und warum Solanas Blockstore bekanntermaßen die Variante wechselte und später wieder zurückwechselte.

Wenn du gern einen Nachmittag mit einer Schritt-für-Schritt-Erklärung des Lesepfads einer Datenbank verbringst, dann entwickle mit uns. Den hier beschriebenen Lesepfad betreiben wir für Solanas vollständigen Verlauf. Ob ein Bloom-Filter abgefragt oder eine Datei geöffnet wird, schlägt sich dort in echter Hardware und echten Kosten nieder. Wir stellen in unserem gesamten Engineering-Team ein. Alle offenen Stellen findest du unter helius.dev/careers