Warum benötigt LevelDB mehr als zwei Ebenen?

Question

Ich denke, nur zwei Ebenen (Level-0 und Level-1) ist in Ordnung, warum benötigt LevelDB Level-2, Level-3 und mehr?

Answer 1

Ich werde Sie in Richtung einiger Artikel auf LevelDB und seine zugrunde liegende Speicherstruktur zeigen.

So in der documentation for LevelDB diskutiert es Zusammenführungen zwischen den Ebenen. Diese Zusammenführungen haben die Wirkung, neue Aktualisierungen von der jungen Ebene schrittweise auf die größte Ebene zu migrieren, indem nur Massenlese- und -schreibvorgänge verwendet werden (d. H. Teure Suchen minimiert werden).

LevelDB ähnelt in der Struktur Log Structured Merge Trees. Der Artikel diskutiert die verschiedenen Ebenen, wenn Sie an der Analyse interessiert sind. Wenn Sie durch die Mathematik kommen, ist es am besten, die Datenstruktur zu verstehen.

Ein viel einfacher analysis von LevelDB spricht über die Datenspeicher Beziehung zu LSM Bäume zu lesen, aber in Bezug auf Ihre Fragen zu den Ebenen alles sagt, es ist:

Schließlich On-Disk-SSTables Hunderte von mit ist auch keine großartige Idee, daher werden wir regelmäßig einen Prozess zum Zusammenführen der SSTables auf der Festplatte ausführen.

Wahrscheinlich die LevelDB-Dokumentation bietet die beste Antwort: (Maximierung der Größe der Schreib- und Lesevorgänge, da LevelDB auf der Festplatte (langsamer Suche) Datenspeicher ist).

Viel Glück!

Answer 2

Ich denke, es ist vor allem mit einfachen und schnellen Verschmelzung von Ebenen zu tun.

In Leveldb hat Level- (i + 1) ca. 10 Mal die Daten im Vergleich zu Level-i. Dies ist eher analog zu einer mehrstufigen Cache-Struktur, in der, wenn die Datenbank 1000 Datensätze zwischen den Schlüsseln x1 bis x2 aufweist, 10 der am häufigsten aufgerufenen in diesem Bereich in Level-1 und 100 im selben Bereich liegen würden in Level-2 und Ruhe in Level-3 (das ist nicht exakt, aber nur um eine intuitive Vorstellung von Levels zu geben). In diesem Setup müssen wir, um eine Datei in level-i zu verschmelzen, höchstens 10 Dateien in level- (i + 1) betrachten und alles in den Speicher bringen, eine schnelle Zusammenführung machen und zurückschreiben. Dies führt zum Lesen relativ kleiner Datenblöcke für jede Verdichtungs-/Mischoperation.

Auf der anderen Seite, wenn Sie nur zwei Ebenen hatten, könnte der Schlüsselbereich in einer Ebene-0-Datei möglicherweise Tausende von Dateien in Ebene-1 entsprechen und alle von ihnen müssen für die Zusammenführung geöffnet werden, die sein wird ziemlich langsam. Beachten Sie, dass eine wichtige Annahme hier ist, dass wir Dateien mit fester Größe haben (sagen wir 2 MB). Mit Dateien variabler Länge in Level-1 könnte Ihre Idee noch funktionieren und ich denke, eine Variante davon wird in Systemen wie HBase und Cassandra verwendet.

Nun, wenn Sie Bedenken haben, ist Nachschlagen Verzögerung mit vielen Ebenen, wieder ist dies wie eine Multi-Level-Cache-Struktur, zuletzt geschriebenen Daten würden in höheren Ebenen, um mit typischen Ort der Referenz zu helfen.

Answer 3

Level 0 ist Daten im Speicher andere Ebenen sind Daten auf der Festplatte. Der wichtige Teil ist, dass die Daten in den Ebenen sortiert sind. Wenn level1 aus 3 2Mb Dateien besteht, dann sind es in file1 die Schlüssel 0.50 (sortiert) in file2 150..200 und in file3 300..400 (als Beispiel). Wenn also der Speicher voll ist, müssen wir seine Daten auf die effizienteste Art und Weise auf die Festplatte schreiben, was sequenzielles Schreiben ist (mit so wenig Suchvorgängen wie möglich).Stellen Sie sich vor, wir haben die Schlüssel 60-120, cool, wir schreiben sie einfach sequentiell als Datei, die in Level1 zu Datei2 wird. Sehr effizient! Aber jetzt stellen Sie sich vor, dass Level1 viel größer als Level0 ist (was vernünftig ist, da Level0 Speicher ist). In diesem Fall gibt es viele Dateien in Level1. Und jetzt gehören unsere Schlüssel im Speicher (60-120) zu vielen Dateien, da der Schlüsselbereich in Level1 sehr feinkörnig ist. Um nun Level0 mit Level1 zusammenzuführen, müssen wir viele Dateien lesen und viele zufällige Suchen durchführen, neue Dateien im Speicher erstellen und sie schreiben. Das ist der Punkt, an dem die Idee vieler Ebenen einsetzt, wir werden viele Ebenen haben, jede etwas größer als die vorherige (x10), aber nicht viel größer. Wenn wir also Daten von i-1 zur i-ten Ebene migrieren müssen, haben wir eine gute Chance, die wenigsten Dateien lesen zu müssen.

Da Daten sich möglicherweise ändern, müssen sie möglicherweise nicht auf höhere teurere Schichten übertragen werden (sie könnten geändert oder gelöscht werden), und so vermeiden wir teure Zusammenführungen. Die Daten, die auf der letzten Ebene landen, ändern sich statistisch am wenigsten wahrscheinlich, sodass sie am besten für die Schicht mit der höchsten Schicht geeignet sind, die am teuersten ist.