Dieser Artikel führt Sie durch das Verständnis des Log-Structured Merge-Tree (LSM-Tree), einschließlich seiner Kernkonzepte und Struktur. Am Ende werden Sie in der Lage sein, Ihre eigene Speicher-Engine auf Basis von LSM-Tree von Grund auf zu erstellen.
Der Log-Structured Merge-Tree (LSM-Tree) ist eine Datenstruktur, die für Schreibvorgänge mit hohem Durchsatz optimiert ist. Es wird häufig in Datenbanken und Speichersystemen wie Cassandra, RocksDB und LevelDB verwendet.
Die Schlüsselidee von LSM-Tree besteht darin, Operationen zunächst in eine speicherinterne Datenstruktur zu schreiben (normalerweise eine geordnete Struktur wie eine Sprungliste oder ein AVL-Baum). Später werden diese Schreibvorgänge gestapelt und nacheinander als SSTables auf die Festplatte geschrieben, wodurch zufällige E/A minimiert werden.
Der LSM-Baum ist in zwei Hauptkomponenten unterteilt:
Typischerweise umfasst die Struktur einer SSTable mehr als nur eine Reihe geordneter Schlüssel-Wert-Paare (Datenblöcke). Es enthält außerdem einen Indexblock, einen Metadatenblock und andere Komponenten. Diese Details werden im Implementierungsabschnitt ausführlich besprochen.
Das Schreiben von Daten erfordert das Hinzufügen eines neuen Schlüssel-Wert-Paares oder das Aktualisieren eines vorhandenen. Updates überschreiben alte Schlüssel-Wert-Paare, die später während des Komprimierungsprozesses entfernt werden.
Wenn Daten geschrieben werden, werden sie zunächst in die Memtable verschoben, wo das Schlüssel-Wert-Paar zur im Speicher geordneten Datenstruktur hinzugefügt wird. Gleichzeitig wird der Schreibvorgang im WAL protokolliert und auf der Festplatte gespeichert, um Datenverlust im Falle eines Datenbankabsturzes zu verhindern.
Die Memtable hat einen definierten Schwellenwert (normalerweise basierend auf der Größe). Wenn die Memtable diesen Schwellenwert überschreitet, wird sie in den schreibgeschützten Modus geschaltet und in eine neue SSTable konvertiert, die dann auf Level 0 auf der Festplatte gespeichert wird.
Sobald die Memtable als SSTable geleert wurde, kann die entsprechende WAL-Datei sicher gelöscht werden. Nachfolgende Schreibvorgänge werden auf einer neuen Memtable (und einer neuen WAL) durchgeführt.
In LSM-Tree werden Daten nicht sofort entfernt. Stattdessen werden Löschungen mithilfe eines Mechanismus namens Tombstones durchgeführt (ähnlich wie vorläufige Löschungen). Wenn ein Schlüssel-Wert-Paar gelöscht wird, wird ein neuer Eintrag geschrieben, der mit einem „Tombstone“ markiert ist, der die Löschung des entsprechenden Schlüssel-Wert-Paares anzeigt. Die eigentliche Entfernung erfolgt während des Verdichtungsprozesses.
Diese Tombstone-basierte Löschung gewährleistet die Append-only-Eigenschaft von LSM-Tree, vermeidet zufällige E/A und behält sequentielle Schreibvorgänge auf die Festplatte bei.
Der Prozess der Datenabfrage beginnt mit einer Suche in der Memtable. Wenn das Schlüssel-Wert-Paar gefunden wird, wird es an den Client zurückgegeben. Wenn ein mit einem Tombstone markiertes Schlüssel-Wert-Paar gefunden wird, bedeutet dies, dass die angeforderten Daten gelöscht wurden, und diese Informationen werden ebenfalls zurückgegeben. Wenn der Schlüssel nicht in der Memtable gefunden wird, durchsucht die Abfrage die SSTables von Level 0 bis Level N.
Da das Abfragen von Daten möglicherweise das Durchsuchen mehrerer SSTable-Dateien erfordert und zu zufälligen Festplatten-E/A-Vorgängen führen kann, eignet sich LSM-Tree im Allgemeinen besser für schreibintensive Arbeitslasten als für leseintensive.
Eine häufige Optimierung der Abfrageleistung ist die Verwendung eines Bloom-Filters. Ein Bloom-Filter kann schnell feststellen, ob ein Schlüssel-Wert-Paar in einer bestimmten SSTable vorhanden ist, und so unnötige Festplatten-E/A reduzieren. Darüber hinaus ermöglicht die sortierte Natur von SSTables die Verwendung effizienter Suchalgorithmen, wie z. B. der binären Suche, für schnellere Suchvorgänge.
Hier stellen wir die Leveled Compaction Strategy vor, die von LevelDB und RocksDB verwendet wird.
Eine weitere gängige Strategie ist die Size-Tiered Compaction Strategy, bei der neuere und kleinere SSTables sukzessive mit älteren und größeren SSTables zusammengeführt werden.
Wie bereits erwähnt speichert eine SSTable eine Reihe von Einträgen, sortiert nach Schlüssel. In der Leveled Compaction Strategy sind SSTables in mehreren Ebenen organisiert (Ebene 0 bis Ebene N).
In Level 0 können SSTables überlappende Schlüsselbereiche haben, da sie direkt aus der Memtable gelöscht werden. In den Ebenen 1 bis N haben SSTables innerhalb derselben Ebene jedoch keine überlappenden Schlüsselbereiche, obwohl Überlappungen von Schlüsselbereichen zwischen SSTables in verschiedenen Ebenen zulässig sind.
Ein anschauliches (wenn auch nicht ganz genaues) Beispiel finden Sie unten. In Ebene 0 überlappen sich die Schlüsselbereiche der ersten und zweiten SSTables, während in Ebene 1 und Ebene 2 die SSTables innerhalb jeder Ebene disjunkte Schlüsselbereiche haben . SSTables zwischen verschiedenen Ebenen (z. B. Ebene 0 und Ebene 1 oder Ebene 1 und Ebene 2) können jedoch überlappende Schlüsselbereiche haben.
Lassen Sie uns nun untersuchen, wie die Leveled Compaction Strategy diese Organisationsstruktur aufrechterhält.
Da Level 0 ein Sonderfall ist, ist die Diskussion der Verdichtungsstrategie in zwei Teile unterteilt:
Der Hauptunterschied zwischen der Komprimierung von Level 0 bis Level 1 und der Komprimierung von Level N bis Level N 1 (N > 0) liegt in der Auswahl von SSTables auf niedrigeren Ebenen (Level 0 oder Stufe N).
Der Multi-SSTable-Komprimierungs- und Zusammenführungsprozess ist unten dargestellt. Während der Zusammenführung wird nur der neueste Wert für jeden Schlüssel beibehalten. Wenn der letzte Wert eine „Tombstone“-Markierung aufweist, wird der Schlüssel gelöscht. In der Implementierung verwenden wir den K-Way-Merge-Algorithmus, um diesen Prozess durchzuführen.
Es ist wichtig zu beachten, dass die obige Beschreibung des Verdichtungsprozesses nur einen allgemeinen Überblick bietet. Bei der eigentlichen Umsetzung müssen viele Details geklärt werden.
Wenn beispielsweise in LevelDB während der Komprimierung neue SSTables für Ebene N 1 erstellt werden und sich die neue SSTable mit mehr als 10 SSTables in Ebene N 2 überschneidet, wechselt der Prozess zum Erstellen einer weiteren SSTable. Dadurch wird die Datengröße einer einzelnen Komprimierung begrenzt.
Basierend auf der obigen Übersicht über LSM-Tree glaube ich, dass Sie jetzt ein grundlegendes Verständnis von LSM-Tree und einige Ideen zu seiner Implementierung haben. Als nächstes werden wir eine Speicher-Engine basierend auf LSM-Tree von Grund auf erstellen. Im Folgenden stellen wir nur den Kerncode vor; Den vollständigen Code finden Sie unter https://github.com/B1NARY-GR0UP/originium.
Wir werden die Implementierung von LSM-Tree in die folgenden Kernkomponenten aufteilen und diese einzeln implementieren:
Bei der Einführung des Datenschreibens haben wir erwähnt, dass der LSM-Baum Daten zunächst in eine im Speicher geordnete Datenstruktur schreibt. Einige gängige geordnete Datenstrukturen und die zeitliche Komplexität ihrer Operationen sind wie folgt:
| Data Structure | Insert | Delete | Search | Traverse |
|---|---|---|---|---|
| Skip List | O(logn) | O(logn) | O(logn) | O(n) |
| AVL Tree | O(logn) | O(logn) | O(logn) | O(n) |
| Red-Black Tree | O(logn) | O(logn) | O(logn) | O(n) |
Wir haben uns aus zwei Hauptgründen für die Skip List entschieden: Sie ist einfacher zu implementieren und zu warten (KISS-Prinzip) und die zugrunde liegende Struktur der verknüpften Liste erleichtert das sequentielle Durchlaufen, wodurch es einfacher wird, In-Memory-Daten auf der Festplatte beizubehalten.
Die vollständige Implementierung der Skip List ist unter https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/skiplist/skiplist.go verfügbar.
Eine Skip-Liste besteht aus einer verknüpften Basisliste und mehreren darauf aufbauenden Indexebenen. Bei großen Datensätzen verkürzen die Indexebenen den Suchpfad erheblich.
In unserer Implementierung ist die Kernstruktur der Skip List wie folgt definiert:
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Die Struktur der in der Skip List gespeicherten Elemente ist wie folgt definiert:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
types.Entry stellt ein Schlüssel-Wert-Paar in der Speicher-Engine dar, einschließlich Schlüssel, Wert und einem Tombstone-Flag zum Löschen.
next: Enthält Zeiger auf das nächste Element auf jeder Ebene.
Diese Struktur mag abstrakt erscheinen, also veranschaulichen wir sie anhand eines Beispiels:
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
In dieser dreistufigen Sprungliste verweisen die nächsten Zeiger des Kopfknotens auf den ersten Knoten auf jeder Ebene. Die Elemente 3 und 6 speichern das nächste Element für jede ihrer Ebenen.
Wenn wir beispielsweise den nächsten Knoten von Element 19 auf Ebene 2 finden möchten, verwenden wir e19.next[2-1].
func (s *SkipList) Set(entry types.Entry)
Der LSM-Baum verwendet Tombstones, um Löschvorgänge durchzuführen, sodass wir in der Skip-List-Implementierung keine Löschmethode benötigen. Um ein Element zu löschen, setzen Sie einfach den Tombstone des Eintrags auf true. Somit übernimmt die Set-Methode das Einfügen neuer Schlüssel-Wert-Paare, das Aktualisieren bestehender und das Löschen von Elementen.
Lassen Sie uns die Implementierung der Set-Methode untersuchen. Durch das Durchlaufen der Knoten in jeder Ebene von der höchsten wird das letzte Element, das kleiner als der festzulegende Schlüssel ist, im Update-Slice gespeichert.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Am Ende dieses Durchlaufs zeigt curr auf das letzte Element, das kleiner als der festzulegende Schlüssel in der verknüpften Liste der untersten Ebene ist. Wir müssen also nur prüfen, ob das nächste Element von curr dem Schlüssel entspricht, den wir festlegen möchten. Wenn es übereinstimmt, wurde das Element bereits eingefügt; Wir aktualisieren das vorhandene Element und kehren zurück.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Wenn das Element nicht gefunden wird, wird es als neues Element eingefügt. Mit randomLevel berechnen wir die Indexstufe dieses Elements. Wenn die aktuelle Anzahl der Ebenen in der Sprungliste überschritten wird, fügen wir den Hauptknoten zum Update-Slice hinzu und aktualisieren s.level auf die neue Ebenenanzahl.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Als nächstes konstruieren Sie das einzufügende Element und die nächsten Zeiger jeder Ebene werden aktualisiert, um das Einfügen abzuschließen.
func (s *SkipList) Set(entry types.Entry)
Die Sprungliste kann schnelle Suchvorgänge durchführen, indem sie auf mehreren Indexebenen basiert. Die verschachtelten for-Schleifen in der Implementierung stellen die indexbasierte Suchoperation dar. Wenn das entsprechende Element schließlich in der untersten verknüpften Liste gefunden wird, wird es zurückgegeben.
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Ein Grund, warum wir uns für die Sprungliste entschieden haben, ist ihr praktisches sequentielles Durchlaufen, das durch einfaches Durchlaufen der untersten verknüpften Liste ermöglicht wird.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
Die vollständige Implementierung von WAL finden Sie unter https://github.com/B1NARY-GR0UP/originium/blob/main/wal/wal.go.
Wie bereits erwähnt besteht der Zweck von WAL (Write-Ahead Logging) darin, Datenverluste in der Memtable durch Datenbankabstürze zu verhindern. Daher muss WAL Vorgänge in der Memtable aufzeichnen und die Memtable aus der WAL-Datei wiederherstellen, wenn die Datenbank neu gestartet wird.
Die Kernstruktur von WAL ist wie folgt, wobei fd den Dateideskriptor der WAL-Datei speichert:
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Da wir Vorgänge in der Memtable aufzeichnen müssen, umfasst dies im Wesentlichen das Schreiben jeder Operation (Setzen, Löschen) als Eintrag in die WAL. Die Definition der Write-Methode lautet wie folgt:
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
Wenn wir diese Einträge in die Datei schreiben, müssen wir das WAL-Dateiformat standardisieren. Das Format, das wir hier verwenden, ist Längendaten. Zuerst serialisieren wir den Eintrag, berechnen dann die Länge der serialisierten Daten und schreiben schließlich die Länge und die serialisierten Daten nacheinander in die WAL-Datei.
Der Kerncode lautet wie folgt:
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
Da wir das WAL-Dateiformat Längendaten verwenden, lesen wir beim Lesen zuerst 8 Bytes (int64), um die Länge der Daten zu erhalten, und lesen dann die Daten basierend auf dieser Länge und deserialisieren sie um den Eintrag abzurufen.
Der Kerncode lautet wie folgt:
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Die vollständige Implementierung von Memtable finden Sie unter https://github.com/B1NARY-GR0UP/originium/blob/main/memtable.go.
Die Memtable ist dafür verantwortlich, Client-Operationen in die Skip-Liste zu schreiben und sie in der WAL aufzuzeichnen. Es kann auch Daten von der WAL wiederherstellen, wenn die Datenbank gestartet wird.
Die Kernstruktur von Memtable ist wie folgt und umfasst die beiden Hauptkomponenten Skiplist und Wal:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Beim Ausführen einer Set-Operation müssen sowohl die Sprungliste als auch die WAL gleichzeitig aktualisiert werden.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Um einen Wert abzurufen, geben Sie einfach das Ergebnis des Get-Vorgangs der Skip-Liste zurück.
func (s *SkipList) Set(entry types.Entry)
Um die Memtable aus der WAL-Datei wiederherzustellen, müssen Sie zunächst die WAL-Datei lesen, dann nacheinander die Eintragsdatensätze aus der WAL-Datei auf die Memtable anwenden und schließlich die wiederhergestellte WAL-Datei löschen.
Rufen Sie die Liste der WAL-Dateien ab:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Lesen Sie die WAL und stellen Sie die Memtable wieder her:
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
In der vorherigen Einführung haben wir nur erwähnt, dass „SSTable (Sorted String Table) ein Datenspeicherformat ist, das eine Reihe geordneter Schlüssel-Wert-Paare verwaltet.“ Hier geben wir eine detailliertere Erläuterung der Struktur von SSTable.
In LevelDB besteht eine SSTable aus mehreren Blöcken mit unterschiedlichen Zwecken. Ein schematisches Diagramm ist unten dargestellt:
Die Indexinformationen sind im Wesentlichen eine Zeigerstruktur namens BlockHandle, die zwei Attribute enthält: Offset und Größe, die zum Auffinden des entsprechenden Blocks verwendet werden.
In unserer Implementierung von SSTable haben wir die LevelDB SSTable-Struktur vereinfacht. Ein schematisches Diagramm ist unten dargestellt:
Die vollständige Implementierung von SSTable finden Sie unter https://github.com/B1NARY-GR0UP/originium/tree/main/sstable.
Die Struktur des Datenblocks ist wie folgt definiert und speichert eine geordnete Folge von Einträgen.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Wir haben drei Hauptmethoden für den Datenblock implementiert:
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Wir verwenden Präfixkomprimierung, um die Schlüsselwertsequenz zu kodieren. In den Puffer schreiben wir nacheinander die Länge des gemeinsamen Präfixes, die Länge des Suffixes, das Suffix selbst, die Länge des Werts, den Wert und die „Tombstone“-Markierung.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Zuletzt komprimieren wir die Daten mit s2.
S2 ist eine leistungsstarke Erweiterung des Snappy-Komprimierungsalgorithmus.
func (s *SkipList) Set(entry types.Entry)
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Beim Dekodieren wird der Vorgang einfach umgekehrt. Das vollständige Schlüssel-Wert-Paar wird mithilfe des Präfixes und Suffixes rekonstruiert.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Die Struktur des Indexblocks ist wie folgt definiert. Es speichert den ersten und letzten Schlüssel jedes Datenblocks zusammen mit dem BlockHandle des entsprechenden Datenblocks.
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
In ähnlicher Weise implementiert der Indexblock drei Hauptmethoden: Encode, Decode und Search. Die Implementierungsideen für die Methoden „Encode“ und „Decode“ sind im Wesentlichen dieselben, daher konzentrieren wir uns auf die Methode Search.
Die Suchmethode des Datenblocks dient dazu, ein bestimmtes Schlüssel-Wert-Paar innerhalb der geordneten Schlüssel-Wert-Sequenz zu finden, die in einem einzelnen Datenblock gespeichert ist. Im Gegensatz dazu wird die Suchmethode des Indexblocks verwendet, um den Datenblock zu finden, der den angegebenen Schlüssel innerhalb der gesamten SSTable enthält.
func (s *SkipList) Get(key types.Key) (types.Entry, bool) {
curr := s.head
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < key {
curr = curr.next[i]
}
}
curr = curr.next[0]
if curr != nil && curr.Key == key {
return types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
}, true
}
return types.Entry{}, false
}
func (s *SkipList) All() []types.Entry {
var all []types.Entry
for curr := s.head.next[0]; curr != nil; curr = curr.next[0] {
all = append(all, types.Entry{
Key: curr.Key,
Value: curr.Value,
Tombstone: curr.Tombstone,
})
}
return all
}
Die Implementierungen dieser beiden Blöcke sind recht einfach, da beide nur die Methoden „Encode“ und „Decode“ erfordern.
Nachdem wir alle Blöcke in unserer SSTable eingeführt haben, umfasst die Erstellung einer SSTable lediglich den schrittweisen Aufbau jedes Blocks auf der Grundlage der Schlüssel-Wert-Paare. Abschließend werden der In-Memory-Index und die codierte SSTable zurückgegeben.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Die vollständige Implementierung von K-Way Merge ist unter https://github.com/B1NARY-GR0UP/originium/tree/main/pkg/kway verfügbar.
Im konzeptionellen Abschnitt veranschaulichen wir den Prozess des Komprimierens und Zusammenführens mehrerer SSTables anhand von Diagrammen. Dieser Prozess wird mithilfe des k-way merge-Algorithmus durchgeführt.
Der k-way-Merge-Algorithmus ist eine Methode zum Zusammenführen von k sortierten Sequenzen zu einer einzigen sortierten Sequenz mit einer zeitlichen Komplexität von O(knlogk).
Eine Implementierung dieses Algorithmus verwendet einen Min-Heap als Hilfsstruktur:
Die Standardbibliothek bietet eine Heap-Implementierung im Container/Heap. Durch die Implementierung der heap.Interface können wir einen Min-Heap erstellen.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
func (s *SkipList) Set(entry types.Entry)
Die Funktionsdefinition der Merge-Methode:
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Folgt dem K-Way-Merge-Algorithmus-Prozess.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Durchlaufen Sie abschließend die Karte, um Elemente zur Ergebniswarteschlange hinzuzufügen, und entfernen Sie alle als „Tombstones“ markierten Schlüssel-Wert-Paare. Da die Karte ungeordnet ist, muss die Ergebniswarteschlange vor der Rückgabe sortiert werden.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Die vollständige Implementierung des Bloom-Filters finden Sie unter https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/filter/filter.go.
Ein Bloom-Filter ist eine Datenstruktur, die effizient prüft, ob ein Element Mitglied einer Menge ist.
Die zeitliche Komplexität sowohl für Einfügungs- als auch für Abfragevorgänge beträgt O(k), wobei k die Anzahl der Hash-Funktionen ist. Falsch-positive Ergebnisse können auftreten (der Bloom-Filter sagt voraus, dass ein Element in der Menge vorhanden ist, dies ist jedoch nicht der Fall), aber falsch-negative Ergebnisse können nicht auftreten (der Bloom-Filter sagt voraus, dass ein Element nicht vorhanden ist). im Set, ist es aber tatsächlich).
True Positive (TP):Das System sagt ein Ereignis als „positiv“ voraus und es ist tatsächlich positiv.
False Positive (FP):Das System sagt ein Ereignis als „positiv“ voraus, in Wirklichkeit ist es jedoch negativ.
True Negative (TN):Das System sagt ein Ereignis als „negativ“ voraus, und es ist tatsächlich negativ.
Falsch Negativ (FN):Das System sagt ein Ereignis als „negativ“ voraus, aber es ist tatsächlich positiv.
Die Kernstruktur eines Bloom-Filters umfasst das Bit-Array (das für die Verwendung von uint8 optimiert werden kann) und mehrere Hash-Funktionen.
func (s *SkipList) Set(entry types.Entry)
Die Methode zum Erstellen einer Bloom-Filter-Instanz akzeptiert zwei Parameter: n (die erwartete Anzahl von Elementen) und p (die gewünschte Falsch-Positiv-Rate).
Zuerst werden die Parameter validiert. Anschließend werden die Größe des Bit-Arrays (m) und die Anzahl der Hash-Funktionen (k) mithilfe spezifischer Formeln berechnet. Abschließend werden die Bit-Array- und Hash-Funktionen basierend auf m und k initialisiert.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Beim Hinzufügen eines Elements werden alle Hash-Funktionen verwendet, um Hash-Werte für den Schlüssel zu berechnen. Diese Werte werden dann auf Indizes im Bit-Array abgebildet und die entsprechenden Positionen werden auf true gesetzt.
type Element struct {
types.Entry
next []*Element
}
// https://github.com/B1NARY-GR0UP/originium/blob/main/pkg/types/entry.go
type Entry struct {
Key string
Value []byte
Tombstone bool
}
Um zu überprüfen, ob ein Schlüssel in der Menge vorhanden ist, berechnen die Hash-Funktionen Hash-Werte und ordnen sie Indizes im Bit-Array zu. Wenn eine dieser Positionen nicht wahr ist, ist das Element nicht in der Menge und es wird „false“ zurückgegeben.
Level 3: 3 ----------- 9 ----------- 21 --------- 26 Level 2: 3 ----- 6 ---- 9 ------ 19 -- 21 ---- 25 -- 26 Level 1: 3 -- 6 -- 7 -- 9 -- 12 -- 19 -- 21 -- 25 -- 26 next of head [ ->3, ->3, ->3 ] next of Element 3 [ ->6, ->6, ->9 ] next of Element 6 [ ->7, ->9 ]
Die vollständige Implementierung von Leveled Compaction finden Sie unter https://github.com/B1NARY-GR0UP/originium/blob/main/level.go.
Nach der Implementierung von Komponenten wie K-Way Merge und Bloom Filter können wir den letzten Teil unserer Implementierung abschließen, den wichtigsten SSTable-Komprimierungsprozess in der LSM-Tree-Speicher-Engine. Diese Implementierung folgt der Leveled Compaction Strategy, die im Abschnitt „Datenkomprimierung“ beschrieben wird.
In der Leveled Compaction Strategy sind SSTables in mehreren Ebenen organisiert (Ebene 0 – Ebene N). Wir benötigen eine Struktur, um diese Informationen zu speichern und SSTables über verschiedene Ebenen hinweg zu verwalten.
Daher haben wir eine Struktur namens levelManager implementiert. Wir verwenden eine []*list.List, um SSTable-Informationen für jede Ebene zu speichern, wobei der Index des Slice der Ebene entspricht. Jedes Element im Slice ist eine list.List, eine doppelt verknüpfte Liste, die Informationen über alle SSTables in einer bestimmten Ebene enthält.
func (s *SkipList) Set(entry types.Entry)
Die Methode „compactLN“ ist für die Verdichtung von Level N bis Level N 1 (N > 0) verantwortlich. Es wählt die älteste SSTable von LN und alle SSTables von LN 1 aus, die überlappende Schlüsselbereiche mit dieser SSTable haben.
curr := s.head
update := make([]*Element, s.maxLevel)
for i := s.maxLevel - 1; i >= 0; i-- {
for curr.next[i] != nil && curr.next[i].Key < entry.Key {
curr = curr.next[i]
}
update[i] = curr
}
Die ausgewählten SSTables werden in der Reihenfolge vom ältesten zum neuesten verarbeitet. Schlüssel-Wert-Paare aus ihren Datenblöcken werden zu einem zweidimensionalen Slice hinzugefügt und dann mit dem K-Way Merge-Algorithmus zusammengeführt.
// update entry
if curr.next[0] != nil && curr.next[0].Key == entry.Key {
s.size += len(entry.Value) - len(curr.next[0].Value)
// update value and tombstone
curr.next[0].Value = entry.Value
curr.next[0].Tombstone = entry.Tombstone
return
}
Mit den zusammengeführten Schlüssel-Wert-Paaren erstellen wir einen neuen Bloom-Filter und eine neue SSTable. Die relevanten Informationen zur neuen SSTable sind am Ende von Level N 1 angehängt.
// add entry
level := s.randomLevel()
if level > s.level {
for i := s.level; i < level; i++ {
update[i] = s.head
}
s.level = level
}
Schließlich werden die alten SSTables gelöscht und die neu erstellte SSTable wird auf die Festplatte geschrieben.
e := &Element{
Entry: types.Entry{
Key: entry.Key,
Value: entry.Value,
Tombstone: entry.Tombstone,
},
next: make([]*Element, level),
}
for i := range level {
e.next[i] = update[i].next[i]
update[i].next[i] = e
}
s.size += len(entry.Key) + len(entry.Value) + int(unsafe.Sizeof(entry.Tombstone)) + len(e.next)*int(unsafe.Sizeof((*Element)(nil)))
Die Methode „compactL0“ übernimmt die Komprimierung von Level 0 bis Level 1. Im Gegensatz zu CompactLN wählt es nicht nur eine SSTable aus L0 aus, sondern auch alle überlappenden SSTables in L0. Der weitere Ablauf ist identisch mit compactLN.
Die Suchmethode findet die entsprechenden Schlüssel-Wert-Paare in allen SSTables. Es beginnt bei L0 und iteriert durch jede Ebene bis zu LN. Durch die Nutzung des Bloom-Filters und der geordneten Struktur von SSTables können SSTables, die nicht die gewünschten Schlüssel-Wert-Paare enthalten, effizient übersprungen werden.
type SkipList struct {
maxLevel int
p float64
level int
rand *rand.Rand
size int
head *Element
}
Damit haben wir alle Kernkomponenten der LSM-Tree-basierten Speicher-Engine implementiert. Indem wir diese Komponenten wie in der LSM-Tree-Einführung beschrieben zusammenstellen, können wir die Datenbankschnittstelle finalisieren.
Vollständiger Code: https://github.com/B1NARY-GR0UP/originium/blob/main/db.go
Dokumentation: https://github.com/B1NARY-GR0UP/originium?tab=readme-ov-file#usage
Wir begannen damit, LSM-Tree zu verstehen, uns mit seinen Kernkomponenten und dem Prozess der Bearbeitung von Kundenanfragen vertraut zu machen. Letztendlich haben wir unsere eigene LSM-Tree-Speicher-Engine von Grund auf erstellt.
Natürlich handelt es sich bei dieser Implementierung nur um einen Prototyp. Bei einer produktionstauglichen Speicher-Engine müssen viele weitere Details berücksichtigt werden. ORIGINIUM wird auch in Zukunft weiterhin Optimierungen und Verbesserungen erhalten. Ich hoffe, dieser Artikel und ORIGINIUM helfen Ihnen, Ihr Verständnis von LSM-Tree zu vertiefen.
Damit ist alles, was in diesem Artikel behandelt wird, abgeschlossen. Wenn es Fehler oder Fragen gibt, können Sie uns gerne per Privatnachricht kontaktieren oder einen Kommentar hinterlassen. Vielen Dank!
Das obige ist der detaillierte Inhalt vonAufbau einer LSM-Tree-Speicher-Engine von Grund auf. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
