Chatbots, wie ChatGPT oder Gemini haben das Potential, unsere Arbeit zu optimieren und Prozesse zu automatisieren. Mit Prompts kommunizieren wir mit Chatbots mit natürlicher Sprache. Je präziser unsere Promts sind, desto besser sind die Antworten des Chatbots. Der folgende  Artikel zeigt dir, wie du mit Personas und Wiederholungen, zwei wichtigen Prompt-Patterns, den Chatbot effektiv nutzen kannst. Das Beispiel kannst du beliebig durch eigene Anforderungen ersetzen.

Das Persona-Pattern ist eines von vielen wichtigen Prompt Patterns – andere Beispiele sind In-Context-Learning und Chain of Thought.

Log-Structured Merge (LSM)-Trees sind eine innovative Art der Datenorganisation und -speicherung, die besonders für schreib-intensive Szenarien geeignet ist , und in einer ganzen Reihe verteilter Datenbanken zum Zug kommt. In diesem Blog-Post untersuchen die grundsätzliche Architektur und Funktionsweise moderner LSM-Trees.

LSM-Trees wurden 1996 von O’Neil et al  im Paper “The log-structured merge-tree (LSM-tree)” vorgeschlagen. Seither wurde die Idee weiterentwickelt und fand Eingang in einer Reihe moderner, verteilter Datenbanksysteme.

Mit Bigtable dem Paper “Bigtable: A Distributed Storage System for Structured Data” veröffentlichten in 2006 Google-Mitarbeiter ihr Konzept, wie sie über dem Google Filesystem, eine sehr schnelle NoSQL-Datenbank realisieren konnten.

Die Konzepte des Papers wurden als erste von der HBase-Community in einem Open-Source-Projekt  nachgebaut und hat seither in verschiedenen anderen OLTP-Systemen Eingang gefunden, die in sehr schnell massive Datenmengen verarbeiten können. Prominente Beispiele sind Apache Cassandra, InfluxDB und RocksDB.

Wir untersuchen in diesem Artikel diese moderne Form der LSM-Trees.

Grundstruktur eines modernen LSM-Baums

Die Hauptidee hinter LSM-Bäumen besteht in der Beobachtung, dass in sehr großen Datenbeständen die jüngsten Daten – oft als hot data bezeichnet – am häufigsten gelesen werden.

Ein LSM-Baum besteht aus mehreren Ebenen:

• Write Ahead Log oder Commit Log (WAL)
• MemTable: die jüngsten Daten befinden sich im Memory.
• SSTables (Sorted String Tables): ist die MemTable voll, dann werden die Daten in eine SSTable auf die Festplatte geflushed.

Die Grafik verdeutlicht die Struktur. Sowohl die MemTable als auch die SSTables sind mit einem Suchbaum versehen, beispielsweise mit einem B-Baum (engl. B-Tree).

Sowohl MemTable als auch SSTables enthalten Logeinträge der Datenmanipulationen, sortiert nach Timestamp des Ereignisses. Aus diesen Eigenschaften leitet sich die Bezeichnung ‘Log-Structured Merge-Trees’.

Insert und delete in einem LSM-Tree

In einem LSM-Baum unterscheiden wir zwei Schreibbefehle: insert und delete. Update ist immer delete mit anschließendem insert.

Beim Schreiben wird der Befehl zuerst  in ein sogenanntes Write Ahead Log (WAL) auf die Festplatte geschrieben, so dass sie im Fall eines Systemfehlers nicht verloren sind und fürs Recovery genutzt werden können. Manchmal ist statt von einem WAL die Rede von einem Commit Log.

Sind die Daten dort sicher angekommen, dann werden sie in die MemTable geschrieben – eine In-Memory-Tabelle im Arbeitsspeicher. Die Daten liegen dort in der Reihenfolge vor, wie sie eingetroffen sind.

Wenn die MemTable eine bestimmte Maximalgröße erreicht hat, wird nach Schlüssel sortiert. Von jedem Schlüssel, wird das jüngste Element berücksichtigt. Gelöschte Elemente sind mit einem Tombstone – also einem Delete-Flag – versehen.

MemTables können beachtlich groß werden. Und so lohnt es sich, sie mit einer Suchstruktur zu versehen. Rot-Schwarz-Bäume sind dazu besonders gut geeignet, weil sie das Einfügen neuer Knoten und das anschließende Balancieren des Baumes im Mittel mit konstantem Aufwand und nur im Worst-Case mit O(log(n)) erfolgt.

Das Ergebnis wird auf die Festplatte geschrieben – diese Struktur wird SST, oder SSTable, also Sorted String Table genannt.

In der Grafik sehen wir das WAL – der älteste Eintrag steht zuunterst, der jüngste zuoberst.

Die MemTable und die SSTables sind auf der Grafik sehr klein, können sie doch nur zwei Elemente fassen. In produktiven Systemen sind sie größer, jedoch immer noch relativ klein, gemessen an den immensen Datenmengen, die mit dieser Architektur verarbeitet werden.

Wir sehen in der Grafik die verschiedenen SSTables, die sich bereits angesammelt haben. Die Älteste steht ganz rechts.

Lesen in einem LSM-Tree

Soll im Beispiel in der Grafik oben der Wert für 18 gelesen werden, dann wird zuerst in der MemTable gesucht, wobei nur das jüngste Element berücksichtigt wird.  Der Wert Eva wird gefunden und zurückgegeben.

Wird der Vorname für Key 22 gesucht, dann wird zuerst die Memtable konsultiert. 22 ist dort nicht vorhanden. Dann werden die SSTables durchsucht und zwar die jüngste zuerst – in unserer Grafik von links nach rechts. In der zweiten SSTable finden wir den aktuellen Wert für 22 und zwar Ana, wiederum wird das jüngste Element berücksichtigt.

Dass der Key 22 in der vierten SSTable mit einem anderen Wert auch schon vorhanden war, ist irrelevant.

Analoges passiert, wenn wir nach einem gelöschten Schlüssel suchen, beispielsweise nach 17. Diesen Key finden wir in der ältesten SSTable und er ist als gelöscht markiert.

Compaction

Das WAL und die Zahl der SSTables nehmen ständig zu. Das System würde damit ziemlich langsam werden, gerade wenn in älteren SSTables gesucht werden muss.

Die Compaction wirkt dem entgegen. Sie wird periodisch – alle paar Minuten –  vom System durchgeführt.

Bei einer Minor-Compaction werden die jüngsten SSTable zu einer einzigen SSTable zusammengefasst. Diese wird größer werden, als die bisherigen SSTables. Dabei werden jeweils die jüngsten Einträge berücksichtigt. Deletes werden gelöscht und die Elemente werden nach Key Sortiert. Ob jetzt noch eine Suchstruktur wie ein Binärbaum organisiert wird, hängt vom Systemdesign ab. Sicher hat auch die Größe dieser lompaktierten SSTables einen Einfluss darauf.

Nach der Compaction werden die kleinen SSTables gelöscht. Die kompaktierte SSTable wird beim Suchen jeweils mitberücksichtigt.

Wird diese Compaction zum Beispiel jede Minute einmal ausgeführt, dann ergeben sich bald viele kompaktierte SSTables.

Hier kommt die Major Compaction zum Zuge. Sie wird weniger oft ausgeführt und führt die kompaktierten Tabellen zusammen zu einer großen SSTable. Die Major Compaction ist auf der grafischen Darstellung nicht berücksichtigt.

Das WAL darf auch nicht zu viel Platz einnehmen. Es wird dann überflüssig, wenn wir sicher sein können, dass die Daten nicht verloren gehen können. Wen also Beispielsweise die Festplatte auf der sich die SSTables befinden crasht, dann dürfen die Daten nicht verloren gehen.

Wann wir uns dessen sicher sein können, hängt auch wieder vom Design des Systems ab. LSM-Trees kommen in verteilten Systemen zum Einsatz. Dort werden die Daten zur Sicherheit repliziert. Können wir also sicher sein, dass alle Daten repliziert sind, an kann das WAL ebenfalls gekürzt werden – um diejenigen Daten, die sicher repliziert wurden.

Vorteile von LSM-Bäumen

LSM-Trees sind sehr effizient beim Schreiben  und können für sehr große Tabellen mit vielen Zeilen und Spalten eingesetzt werden.

LSM-Bäume werden gerne dort eingesetzt, wo ehesten die gerade geschriebenen Daten – gelesen werden. Diese befinden sich noch in der Memtable oder in den jüngeren SSTables.

LSM-Bäume in modernen Datensystemen

• Apache Cassandra ist ein weit verbreitetes Open-Source-Datenbanksystem, das für seine hohe Skalierbarkeit und Ausfallsicherheit bekannt ist. Cassandra verwendet LSM-Bäume, um Daten effizient zu speichern und schnelle Schreibvorgänge zu ermöglichen. Dies macht es ideal für Anwendungen mit hohem Schreibvolumen und verteilten Daten.
• ScyllaDB wurde nach den gleichen Prinzipien gebaut wie Apache Cassandra und soll mit Cassandra kompatibel sein. Die hohe Performanz erreicht ScyllaDB auch dank LSM-Bäumen.
• InfluxDB, die beliebte Zeitreihendatenbank verwendet mit TSM (Time-Structured Merge Tree) eine Variante von LSM-Bäumen.
• Apache AsterixDB ist ein hochskalierbares und sehr flexibles Big Data Management System, dessen Storage Library unter anderem auf LSM-Bäumen basiert. 
• RocksDB ist eine eingebettete Datenbank-Engine, die von Facebook entwickelt wurde und häufig als Grundlage für andere Anwendungen und Systeme dient. Sie basiert auf LSM-Bäumen und bietet eine hohe Leistung und Skalierbarkeit, was sie für viele Anwendungsfälle in der Softwareentwicklung attraktiv

Fazit

Zusammenfassend haben wir gesehen, wie moderne LSM-Trees die Balance zwischen Schreibeffizienz und Leseleistung schaffen. Die jüngsten Daten werden im Memory-Cache gehalten und ältere Daten werden auf der Festplatte von Hintergrundprozessen kompaktiert.

Besonders bemerkenswert ist die Anpassungsfähigkeit von LSM-Trees auf verschiedene Datenbank-Typen, die Spannweite reicht  vom Wide-Column Store, über Zeitreihendatenbanken bis hin zum verteilten Cache.

Bloom-Filter beschleunigen in vielen Systemen die Zugriffszeiten. Sie wurden bereits 1970 entwickelt und finden in jüngerer Zeit vielseitige Verwendung, wenn es um die Optimierung von Systemen geht. Bloom-Filter finden viele Anwendungsgebiete, so unter anderem in LSM-Trees und damit in verteilten OLTP-Datenbanken. Wir untersuchen Bloom-Filter, entwerfen zuerst einen naiven Filter, um danach den eigentlichen Bloom-Filter zu beleuchten. 

B-Bäume sind mehr als nur eine Datenstruktur – sie sind eine zentrale Komponente zur Optimierung in vielen Datenbanksystemen und spielen eine Schlüsselrolle in der Leistung und Effizienz moderner Datenbankarchitekturen. Diese Strukturen sind geschickt entworfen, um Gleichgewicht und Schnelligkeit in der Datenmanipulation zu gewährleisten. Sie sind das Rückgrat effizienter Indexierungsmechanismen.

In diesem Artikel tauchen wir tief in die Welt der B-Bäume ein, beleuchten die Details ihrer Architektur und Funktionsweise und zeigen, wie sie als Index in einem Datenbanksystem zum Zuge kommen. Beispiele sind relationale Datenbanken, LSM-Datenbanken und andere mehr. 

Wenden wir uns als erstes der Frage zu, wie viele relationale und NoSQL-Datenbanken die Daten auf der Festplatte speichern. Gerade in relationalen Datenbanken sind Datenbankseiten, also DB-Pages, ein wichtiges Struktur-Element.

Ursprung und Einsatz von B-Bäumen

Der B-Baum ist eine Weiterentwicklung des Binärbaums. B-Bäume wurden von Rudolf Bayer und Edward M. McCreight in den 1970er Jahren entwickelt. Das Originalpaper veröffentlichten sie im Juli 1970 unter dem Titel “Organisation and Maintenance of Large Ordered Indices”.

Diese Datenstruktur ist darauf ausgelegt, die effiziente Verwaltung und Abfrage großer Datenmengen zu ermöglichen.

Die Namensgebung und die Definition sind nicht eindeutig. B-Bäume werden manchmal auch B+-Bäume oder B*-Bäume genannt. Je nach Autor sind auch die Definitionen leicht unterschiedlich. Wir halten uns hier an die Definition von Bayer und McCreight.

Werfen wir zuerst einen Blick auf die Struktur eines B-Baumes:

Grundstruktur eines B-Baums

Ein B-Baum ist eine hierarchische Baumstruktur, die aus Knoten und Blättern besteht. Die Knoten dienen als Indexeinträge und verweisen auf die Blätter, in denen die tatsächlichen Daten gespeichert sind. Hier sind einige wichtige Merkmale eines B-Baums.

Knoten: Jeder Knoten im B-Baum enthält eine geordnete Liste von Wegweiser-Schlüsseln und Zeigern auf die darunter liegenden Knoten oder Blätter. Die Anzahl der Schlüssel in einem Knoten kann variabel sein, aber sie liegt normalerweise zwischen einem Minimum (z.B. d/2) und einem Maximum (d, wobei d die Ordnung des Baums ist). Ist m die Anzahl vorhandener Schlüssel auf einem Knoten, dann gibt es dazu m+1 Zeiger zu Nachfolgerkonten. 

Blätter: Die Blätter des B-Baums enthalten tatsächliche Daten oder Verweise auf Datensätze in einer Datenbank oder einem Dateisystem. Die Blätter sind in einer sortierten Reihenfolge angeordnet und sind über doppelt verkettete Listen miteinander verbunden.

Ordnung des Baums: Die Ordnung eines B-Baums ist die maximale Anzahl von Schlüsseln, die in einem Knoten gespeichert werden können. Sie beeinflusst die Höhe des Baums und somit die Geschwindigkeit von Suchoperationen.

In einem Datenbanksystem werden weit mehr als 4 Schlüssel auf einem Knoten Platz finden. Die Knoten werden  so organisiert, dass sie eine Index-Seite belegen. 

Einsatz eines B-Baums

Wir illustrieren den Einsatz eines B-Baum-Index mit einem konkreten Beispiel. Dabei gehen wir aus von einer Tabelle mit der Bezeichnung Personen und zwei Spalten PersonenId und Vorname.
Wir lassen uns den Inhalt ausgeben mit select * from Personen und erhalten das folgende Ergebnis:

Ohne order by Klausel wird das Ergebnis unsortiert dargestellt. Das DBMS scannt die DB-Seiten und gibt die Ergebnisse der Reihe nach aus.

Suchen wir jetzt nach dem Vornamen einer bestimmten Person, beispielsweise mit PersonenId=35, dann wird das DBMS ebenfalls die DB-Seiten scannen, bis es die gesuchte Zeile findet. Ist diese nicht vorhanden, dann scannt das DBMS sämtliche DB-Seiten bis zum Ende.

Dieser Full Table Scan ist gerade in großen Tabellen nicht performant. Hier kommen Indizes zum Zug. Das folgende Bild zeigt die schematische Darstellung eines B-Baum-Indexes der Ordnung 3 über die Beispieltabelle:

Die Anordnung der Schlüssel und Zeiger geht Hand in Hand mit dem Suchalgorithmus. Suchen wir in dieser Darstellung nach dem Vornamen der Person mit Id 35.

• Wir suchen das Wurzelelement im Memory, ist es nicht vorhanden, lesen wir den entsprechenden Block von der Festplatte.
• Wir fragen den ersten Wegweiser-Schlüssel: Ist 35 < 42? Das trifft zu und so folgen wir dem linken Pointer.
• Wir suchen die entsprechende DB-Seite im Memory, ist sie nicht vorhanden, dann lesen wir sie von der Festplatte ein.
• Hier fragen wir erneut
• Ist 35 < 13 nein – wir fragen den nächsten Wegweiser-Schlüssel im Knoten
• Ist 35 < 22 nein
• Da der nächste Wegweiser-Schlüssel unbelegt ist, folgen wir dem rechten Pointer.
• Damit gelangen wir schon zum Blattknoten, auch diesen suchen wir im Memory. Ist er nicht vorhanden, dann lesen wir diesen von der Festplatte.
• Jetzt traversieren wir diesen Blattknoten, in dem die Elemente sortiert sind,  solange der Eintrag im Blattelement <=35 ist.
• Finden wir das gesuchte Element, dann folgen wir dem Pointer in die Datenbankseite. Diese holen wir von der Festplatte und durchsuchen die Liste im Header nach PersonenId=35. Dort finden wir das Offset in der gesuchten Zeile und können jetzt den zugehörenden Vornamen lesen.

Optimierung mit B-Baum Index

Gerade in großen Tabellen wird der Zugriff auf ein bestimmtes Element massiv beschleunigt. Um im Index zum Blattknoten zu gelangen, benötigen wir log_d+1(n) Zugriffe, plus einen Zugriff auf die DB-Page. Das ist sehr viel weniger Festplattenzugriffe als ein Full Table Scan, was sich in einem signifikaten Zeitgewinn auszahlt.

Insert und Delete in B-Bäumen

In normalen binären Bäumen beobachten wir, dass sie sehr schnell aus der Balance geraten, wenn Veränderungen vorgenommen werden. Damit verlieren wir die guten Eigenschaften eines Suchbaums, weil es zu nachteilig langen Suchpfaden kommen kann.

B-Bäume sind so konstruiert, dass sie immer balanciert sind und auch so, dass alle Blattknoten dieselbe Tiefe haben.

Der Füllgrad der einzelnen inneren Knoten ermöglicht das. Ein innerer Knoten hat zwischen d/2 und d Einträgen – wobei d die Ordnung ist. Dasselbe gilt für die Blattknoten.

Einfügen eines Elements in einen B-Baum

Diese Flexibilität im Füllgrad ermöglicht es oft, neue Elemente einzufügen, ohne den Baum reorganisieren zu müssen. Wird ein Element eingefügt und einer der Knoten überläuft, dann wird er in zwei Knoten aufgespalten bevor das neue Element wird. Die Aufspaltung in zwei Knoten wird nach oben propagiert. Der übergeordnete Knoten hat vielleicht noch genug Platz für den neuen Wegweiser-Schlüssel. Falls nicht, dann wird auch dieser in zwei Knoten aufgespalten und die Veränderung wird nach oben propagiert.

Löschen eines Elements aus einem B-Baum

Soll ein Element gelöscht werden, dann wird dieses zuerst gesucht. Wird es gefunden, dann kann es in den meisten Fällen einfach aus dem Blattknoten entfernt werden.

Wir sehen, dass dies dazu führen kann, dass in den inneren Knoten Wegweiser-Schlüssel stehen können, die in den Blattknoten nicht mehr vorkommen. Sie bleiben so lange stehen, bis reorganisiert werden muss. Das kommt beim Einfügen vor, wie wir oben gesehen haben und es kommt auch beim Löschen vor und zwar dann, wenn in einem inneren Knoten oder in einem Blattknoten weniger als d/2 Elemente verbleiben.

Dann werden von den Nachbarknoten Elemente ausgeliehen. Es gibt verschiedene Algorithmen, wie das genau erreicht werden kann. Üblicherweise werden die Elemente mit dem linken Knoten verschmolzen – gibt es keinen linken Knoten, dann wird der rechte Knoten beigezogen. Diese Wegweiser im übergeordneten Knoten werden nachgeführt. Enthält der verschmolzene Knoten mehr als d Elemente, dann wird er in zwei gleich große Knoten aufgeteilt und die Infos über die neuen Wegweiser werden nach oben weitergegeben.

Dieser variable Füllgrad erlaubt es in vielen Fällen insert und delete-Operationen vorzunehmen, ohne dass gleich der ganze Baum reorganisiert werden muss.

Vorteile von B-Bäumen

Warum überhaupt sind B-Bäume im Data Engineering so wichtig? Hier einige Beispiele:

Effiziente Suche dank B-Tree-Index

Wie auch in binären Bäumen werden in B-Bäumen die Suchanfragen in logarithmischer Zeit verarbeitet. Um präzise zu sein, die maximale Anzahl Zugriffe um den Knoten mit dem gesuchten Element zu finden, beträgt O(log(n)), wobei n die Anzahl Knoten sind. Das ist viel effizienter, als die lineare Suche über alle Datenbankseiten.

Bereichsanfragen dank B-Index

B-Bäume sind ideal für Bereichsanfragen, bei denen Sie Datensätze in einem bestimmten Wertebereich suchen. Das verdanken wir der Eigenschaft, dass die Blätter sortiert sind und in einer doppelt verketteten Liste vorliegen.

Das DBMS such den Startwert in der doppelt verketteten Liste der Blattknoten und traversiert einfach die Blätter, bis der Endwert erreicht ist. Enthalten die Blätter zusätzlich alle Daten, die abgefragt werden, dann erfolgt nicht einmal ein Zugriff auf die Datenbank-Seiten.

Sortierung und Indexierung mit Hilfe von B-Bäumen

Die Tatsache, dass die Blätter alle Datenwerte in sortierter Reihenfolge enthalten, kommt auch beim sortieren der Ergebnisse bei Datenbankabfragen gelegen, natürlich nur dann, wenn das Sortierkriterium dem Indexierungskriterum entspricht.

Beispielanwendung: B-Bäume in der Praxis

Relationale Systeme legen automatisch einen B+-Baum für den Primär-Schlüssel und für alle Fremdschlüssel an. Mit create index können wir über jede Spalte einen zusätzlichen Index legen und damit kritische Suchanfragen – also langsame select-Statements – optimieren.

Hier ein Beispiel: Um die Bedeutung von B-Bäumen in der Praxis zu verdeutlichen, werfen wir einen Blick auf eine typische Anwendung: eine Kundendatenbank.

Stellen wir uns vor, wir haben eine Kundendatenbank mit Hunderttausenden von Kunden, und wir möchten nach Kunden suchen, die in einem bestimmten Postleitzahlenbereich leben. Dank eines B-Baums als Index über der Spalte ‘Postleistzahl’ können wir diese Abfrage in kürzester Zeit durchführen, unabhängig von der Größe der Datenbank.

Der Index-Baum führt uns schnell zu den relevanten Datensätzen, ohne unnötige Daten zu durchsuchen:

Das Datenbanksystem steigt beim Wurzel-Element des Baumes ein und sucht nach dem kleinsten Wert im Postleitzahlenbereich. Das sind O(log n) Operationen. Ab hier profitiert das System davon, dass die Werte des Indexes, also die Postleitzahlen, in den Blattknoten als doppelt verkettete Liste vorliegt. Jetzt werden die Blattknoten gescannt und zwar so lange, bis der höchste Wert des gesuchten Postleitzahlenbereichs überschritten wird.

Fazit

B-Bäume werden gerne als Suchbäume eingesetzt gerade in Datenbanken, die eine Bereichssuche erlauben. Das ist in allen relationalen Datenbanken der Fall und auch in vielen NoSQL-Datenbanken. Zudem erlauben B-Bäume relativ sparsame insert- und delete-Operationen.

Dieser Artikel ist ein Auszug aus dem E-Book “Datenstrukturen für Data Engineers”