Kategorie: Data Engineering

Veröffentlicht am von

Prompt Engineering: Personas und Wiederholungen

Prompt ProEngineering: Personas und Wiederholungen

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.

Inhalt

Personas: Die Zielgruppe definieren
Der Auftrag an den Chatbot
Beispieldialoge
Erläuterungen des Chatbots ein- und ausschalten
Promptdialog klar strukturieren
Inhaltliche Prüfung durch Chatbots
Fazit

Personas: Die Zielgruppe definieren

Mit Personas verteilst du Rollen. Du kannst dem Chatbot eine Rolle zuweisen oder auch die Rolle der Leser der generierten Texte definieren. Wir beleuchten den zweiten Fall und definieren das Zielpublikum.

Dieser Artikel vergleicht mit ein- und dieselben Prompts das Verhalten von ChatGPT und Gemini. Der Auftrag ist immer derselbe, die Personas varieren:

  • Kinder im dritten Schuljahr, die Python lernen wollen
  • Jugendliche ohne Programmierkenntnisse, die Python lernen wollen
  • Data Engineers mit Universitätsabschluss, die Python lernen wollen

Die Zielgruppen, also Personas, kannst du beliebig anpassen. Vielleicht ‘Junge Paare, die ihre Hochzeitsreise organisieren wollen’. Die Patterns funktionieren analog.

Der Auftrag an den Chatbot

Ist unser Auftrag zu wenig präzise, dann wird der Chatbot entsprechend diffus antworten.  Der Chatbot antwortet immer.

Aus unserem Prompt berechnet er die Antwort basierend auf den statistischen Wahrscheinlichkeiten, die das Large Language Model (LLM) des Chatbots während des meist tagelangen Trainings aus einer Vielzahl von Texten gelernt hat. Entspricht die Antwort in der Form nicht unserer Erwartung, dann müssen wir den Auftrag präziser formulieren.

In unserem Beispiel lautet der Auftrag:

Verbessere den folgenden Satz:

Dazu gehört natürlich auch ein Satz zum Verbessern. Vergessen wir diesen oder ist der Prompt nicht gut formuliert, dann wird der Chatbot dennoch antworten und halt irgendetwas ‘sagen’.

Wir lassen den folgenden Satz verbessern:

Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Du kannst natürlich auch einen anderen Satz verbessern lassen. Es ist wichtig, dass er zur Persona passt, die du definiert hast. Hast du keine Persona definiert, dann wird der Chatbot den Satz auch verbessern, aber halt auf unspezifische Weise.

Beispieldialoge

Im folgenden sehen wir einige Beispieldialoge. Wir setzen ChatGPT und Gemini ein. Der Zugang zu den beiden Bots ist verlinkt:

  • ChatGPT ist von OpenAI und du benötigst ein Konto. Oben links  im Dialogfenster wirst du sehen welche Version verwendet wird. ChatGPT 3.5 ist kostenlos und ChatGPT kostet eine monatliche Gebühr (zum Zeitpunkt des Verfassen des Artikels sind es ca. 20 € pro Monat).
  • Gemini ist der Chatbot von Google. Du benötigst ein Google-Konto. Gemini ist (zum Zeitpunkt des Verfassen des Artikels) kostenlos. Aktuell ist Gemini 1 Pro im Einsatz.

Es gibt auch viele andere Chatbots – diese beiden sind zur Zeit die mächtigsten, die in Mitteleuropa zugänglich sind und die für sich allein stehen. ChatGPT ist ja auch Bestandteil beispielsweise des Bing Copiloten.

Diese Chatbots basieren auf KI-Modellen – genauer auf Large Language Models (LLM). Diese werden aufwändig mit sehr vielen Daten erstellt.

Jedes LLM weist besondere Eigenschaften auf, je nach dem mit welchen Daten und welchem Vorgehen es trainiert wurde.

Die folgenden Dialoge sind Beispiele, um das Persona-Pattern und das Wiederholungs-Pattern zu zeigen. Wenn du die Beispiele nachvollziehst, wirst du jedes Mal eine andere Antwort erhalten – auch das ist eine Eigenschaft von ChatBots.

Vergleiche im folgenden die Antworten der Chatbots mit und ohne Personas und mit der Persona “Kinder im dritten Schuljahr, die Python lernen wollen”. Die Unterschiede sind erstaunlich – ein Klick auf den Thumbnail zeigt das Bild des Dialogs, den ich beim Schreiben des Blogposts mit den Chatbots geführt habe.

ChatGPT ohne Persona

Beispiel: ChatGPT 4 – ohne Persona

Prompt:

Verbessere den folgenden Satz: Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

Eine Schleife stellt die iterative Ausführung eines bestimmten Befehlssatzes dar.

 
Ob der Satz tatsächlich besser ist oder nur verändert wurde, liegt wohl im Auge des Betrachters.

Dialog mit Gemini ohne Persona

Beispiel: Gemini – ohne Persona

Prompt:

Verbessere den folgenden Satz: Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“Eine Schleife ist eine Steuerungsanweisung, die eine Befehlsfolge so oft wiederholt, wie es eine bestimmte Bedingung erfordert. Typische Schleifen sind While-Schleifen, For-Schleifen und Do-While-Schleifen. Mit einer Schleife können Sie Befehle wiederholen, ohne sie jedes Mal neu eingeben zu müssen. Stellen Sie sich eine Schleife wie ein Fließband vor, auf dem Befehle immer wieder ausgeführt werden.”

Gemini reichert noch weitere Information an und ergänzt verschiedene Arten von Schleifen.

ChatGPT 3.5 für Drittklässler

Beispiel: ChatGPT 3.5 – Zielgruppe: Drittklässler

Werfen wir auch einen Blick auf ChatGPT 3.5:

Prompt:

Verbessere den Satz für Kinder im dritten Schuljahr, die Python lernen wollen: Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“Eine Schleife bedeutet, dass du denselben Befehl oder dieselben Befehle immer wieder ausführst.”

Zielpublikum Drittklässler? Wohl kaum!

ChatGPT 4 für Drittklässler

Beispiel: ChatGPT 4 – Zielgruppe: Drittklässler

ChatGPT 4 wurde im Vergleich zu ChatGPT 3 mit mehr Daten trainiert, länger trainiert, die Architektur wurde weiter verbessert.

Prompt:

Verbessere den Satz für Kinder im dritten Schuljahr, die Python lernen wollen: Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“Eine Schleife in Python ist wie ein Kreisel, der immer wieder die gleichen Dinge macht. Stell dir vor, du hast einen Roboter, der immer und immer wieder das Gleiche tut, bis du ihm sagst, dass er aufhören soll. So funktioniert eine Schleife. Sie hilft dem Computer, bestimmte Aufgaben viele Male hintereinander zu machen, ohne dass wir jeden Schritt einzeln aufschreiben müssen.”

ChatGPT 4 versteht Drittklässer viel besser als ChatGPT 3.5.  Der Unterschied ist sehr deutlich und lässt erahnen, mit welchen Verbesserungen der LLM wir in Zukunft noch rechnen können.

Gemini für Drittklässler

Beispiel: Gemini- Zielgruppe: Drittklässler

Prompt:

Verbessere den Satz für Kinder im dritten Schuljahr, die Python lernen wollen: Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“Stellt euch vor, ihr müsst 10 Mal hintereinander “Hüpfen” sagen. Das wäre ganz schön langweilig, jedes Mal den Befehl einzeln einzugeben.

Genau dafür gibt es Schleifen in Python!

Mit einer Schleife könnt ihr einem Computer sagen, dass er einen Befehl so oft wiederholen soll, wie ihr es wollt.So könnt ihr ihm zum Beispiel sagen:

  • Hüpfe 10 Mal!
  • Zeige mir 5 Sterne!
  • Male 3 Kreise!

Das ist viel einfacher und schneller, als den Befehl jedes Mal einzeln einzugeben. <p “>Schleifen sind also wie ein Zauberwort, mit dem ihr dem Computer sagen könnt, dass er etwas mehrmals hintereinander tun soll.

So macht das Programmieren gleich viel mehr Spaß!”

Gemini stellt sich eindeutig am besten auf Drittklässler ein!

Erläuterungen des Chatbots ein- und ausschalten

ChatGPT präsentiert uns die bare Antwort – Gemini hingegen erläutert die ‘Überlegungen’. Ich mag nicht von ‘Intelligenz’ reden, denn auch diese ‘Überlegungen’ werden aus dem Modell generiert.

Wir können dieses Verhalten ändern.

ChatGPT soll ‘Überlegungen’ geben:

Wir verändern den Prompt und fordern ChatGPT dazu auf:

Erläutere deine Verbesserungsvorschläge. Gib deinen Erläuterungen die Überschrift: “Erläuterung der Verbesserung”.

Analog fordern wir Gemini auf, uns keine Erläuterungen zu geben.

Gib keine Erklärungen aus.

Schau dir die Beispiele an:

ChatGPT für Jugendliche ohne Erläuterungen

ChatGPT 4 mit Erläuterungen – Zielgruppe: Jugendliche

Prompt:

Verbessere den Satz für Jugendliche ohne Programmierkenntnisse, die Python lernen wollen, erläutere jeweils deine Verbesserungsvorschläge. Gib deinen Erläuterungen die Überschrift “Erläuterung der Verbesserung”:
Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“In Python kannst du mit einer Schleife einen Befehl oder eine Gruppe von Befehlen immer wieder ausführen lassen, ohne sie jedes Mal neu schreiben zu müssen”.

Die Erläuterungen, die ChatGPT generiert, sind im Bild ersichtlich (Klick auf den Thumbnail links).

Gemini für Jugendliche ohne Programmierkenntnisse und ohne Erläuterungen
Gemini generiert Codebeispiel

Gemini ohne Erläuterungen – Zielgruppe: Jugendliche

Prompt:

Verbessere den Satz für Jugendliche ohne Programmierkenntnisse, die Python lernen wollen, erläutere jeweils deine Verbesserungsvorschläge. Gib deinen Erläuterungen die Überschrift “Erläuterung der Verbesserung”:
Eine Schleife ist eine wiederholte Ausführung ein- und derselben Befehlsfolge.

Antwort (Beispiel):

“In Python kannst du mit einer Schleife einen Befehl oder eine Gruppe von Befehlen immer wieder ausführen lassen, ohne sie jedes Mal neu schreiben zu müssen”.

Die Erläuterungen, die ChatGPT generiert, sind im Bild ersichtlich (Klick auf den Thumbnail links).

Gemini generiert automatisch Varianten

In meinem Beispiel hat Gemini in einer Variante auch ein Code-Beispiel generiert. Du siehst das Ergebnis mit Klick aufs zweite Bild links.

Prompt-Dialog klar strukturieren

Je klarer wir die Struktur des Dialogs gestalten, umso mehr Möglichkeiten eröffnen sich uns, die Anforderungen noch weiter zu präzisieren.

Wir ergänzen:

  • Eine Inhaltliche Überprüfung
  • Den Wunsch, mehrere Sätze nacheinander verbessern zu lassen

Der Prompt für ChatGPT sieht wie folgt aus:

Im folgenden Dialog werde ich einzelne Sätze geben. Tue damit folgendes:
– Verbessere den Satz für Data Engineers mit Universitätsabschluss, die Python lernen wollen.
– Kontrolliere den Satz inhaltlich und gibt inhaltliche Verbesserungsvorschläge.
– Erläutere deine Verbesserungsvorschläge. Gib deinen Erläuterungen die Überschrift: “Erläuterung der Verbesserung”
– Bitte mich um den nächsten Satz.

Wir leiten ein mit: “Ich werde dir einzelne Sätze geben”. Zählen anschließend unsere Anforderungen auf, die enden mit “Bitte mich um den nächsten Satz”.
Es ist fast wie Programmieren im Pseudocode…

Hier die Beispiele – bei Gemini brauchen wir nicht um Erläuterungen zu bitten.

ChatGPT strukturierter Prompt: Zielpublikum: Data Engineers mit Universitätsabschluss

ChatGPT 4 strukturierter Dialog – Zielpublikum Data Engineers

Prompt:

Im folgenden Dialog werde ich einzelne Sätze geben. Tue damit folgendes:

  • Verbessere den Satz für Data Engineers mit Universitätsabschluss, die Python lernen wollen.
  • Kontrolliere den Satz inhaltlich und gib inhaltliche Verbesserungsvorschläge.
  • Erläutere deine Verbesserungsvorschläge. Gib deinen Erläuterungen die Überschrift: “Erläuterung der Verbesserung”
  • Bitte mich um den nächsten Satz.

Antwort (Beispiel):

“In der Programmierung ermöglicht eine Schleife die wiederholte Ausführung einer definierten Befehlssequenz, was für Data Engineers, die ihre Fähigkeiten in Python vertiefen möchten, essentiell ist.”

Die Erläuterungen von ChatGPT siehst du mit Klick auf den Thumbnail links.

Gemini verbessert Sätze für Data Engineers

Gemini strukturierter Dialog – Zielpublikum Data Engineers

Prompt:

Im folgenden Dialog werde ich einzelne Sätze geben. Tue damit folgendes:

  • Verbessere den Satz für Data Engineers mit Universitätsabschluss, die Python lernen wollen.
  • Kontrolliere den Satz inhaltlich und gib inhaltliche Verbesserungsvorschläge.
  • Bitte mich um den nächsten Satz.

Antwort (Beispiel):

“Schleifen ermöglichen die wiederholte Ausführung einer Befehlsfolge, um Daten effizient zu verarbeiten und komplexe Aufgaben zu automatisieren.”

Die Erläuterungen von Gemini siehst du mit Klick auf den Thumbnail links. Gemini liefert auch Verbesserungsvorschläge und begründet sie.

Inhaltliche Überprüfung durch Chatbots

Im letzten prompt haben wir auch eine inhaltliche Überprüfung verlangt. Beide ChatBots waren mit unserem Inhalt zufrieden. Probieren wir das aus mit folgendem Satz:

Python ist eine kompilierte Sprache.

Die Reaktionen der beiden ChatBots. Diese fielen nicht in jedem Anlauf gleich aus. Beide ChatBots verhalten sich vergleichbar. Je nach Anlauf ist die Antwort mehr oder weniger präzise und mehr oder weniger korrekt.

Wie immer: es liegt an uns die generierten Texte inhaltlich zu prüfen. Der Chatbot verfügt über kein belastbares Wissen und berechnet die Texte jedes Mal anders.

Vergleiche die Antworten: Beide sind sehr differenziert. Führt man den Prompt mehrfach aus, dann generieren sowohl ChatGPT 4 als auch Gemini beide Typen Antwort. Unten findest du Beispiele.

ChatGPT und inhaltliche Prüfung

ChatGPT 4 mit dem Auftrag zur inhaltlichen Korrektur

Prompt:

Verbessere den folgenden Satz für Data Engineers mit Universitätsabschluss und führe eine inhaltliche Prüfung des Satzes durch: Python ist eine kompilierte Sprache.

Antwort (Beispiel):

Die Aussage “Python ist eine kompilierte Sprache” ist technisch nicht korrekt. Python ist primär eine interpretierte Sprache, was bedeutet, dass Python-Code zur Laufzeit von einem Interpreter ausgeführt wird, anstatt zuerst in Maschinencode kompiliert zu werden. Für Data Engineers mit Universitätsabschluss, die mit technischen Details vertraut sind, könnte der Satz verbessert und korrigiert werden zu:

“Python ist eine interpretierte Hochsprache, die aufgrund ihrer einfachen Syntax und vielfältigen Bibliotheken in der Datenwissenschaft weit verbreitet ist.”

Gemini zu Python als kompilierter Sprache

Gemini mit dem Auftrag zur inhaltlichen Korrektur

Prompt:

Verbessere den folgenden Satz für Data Engineers mit Universitätsabschluss und führe eine inhaltliche Prüfung des Satzes durch: Python ist eine kompilierte Sprache.

Antwort (Beispiel):

Der Satz “Python ist eine kompilierte Sprache” ist für Data Engineers mit Universitätsabschluss falsch und irreführend.

Verbesserter Satz:

Python ist teilweise kompiliert und teilweise interpretiert.

Inhaltliche Prüfung:

  • Die Aussage “Python ist eine kompilierte Sprache” ist nicht korrekt.
  • Die Verwendung des Wortes “kompiliert” impliziert, dass der gesamte Python-Code in Maschinencode übersetzt wird, was nicht der Fall ist.
  • Die Aussage könnte zu Missverständnissen bei Data Engineers mit Universitätsabschluss führen, die mit den Interna von Python vertraut sind.

Weitere Punkte und Empfehlungen, die Gemini generiert, findest du mit Klick auf den Thumbnail links.

Fazit

Mit geschickt konstruierten Prompts beeinflussen wir das Verhalten von ChatBots. Personas und Wiederholungen sind zwei Prompt-Patterns, die uns dabei unterstützten,

Die inhaltliche Prüfung der generierten Aussagen liegt immer in unserer eigenen Verantwortung.

  • Generative KI, insbesondere Large Language Models (LLMs), haben die Welt im Sturm erobert.

    Diese riesigen Sprachmodelle bieten zahllose Möglichkeiten, um unsere Anwendungen auf die nächste Stufe zu heben.

    Abonniere meinen Newsletter und erhalte regelmäßig Tipps und Tricks zum produktiven Einsatz von LLMs.

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control
Veröffentlicht am von

LSM-Trees

LSM Bäume im Data Engineering

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.

Inhalt

Grundstruktur eines modernen LSM-Baums
Insert und Delete in einem LSM-Tree
Lesen in einem LSM-Tree
Compaction
Vorteile von LSM-Bäumen
LSM-Bäume in modernen Datensystemen
Fazit

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’.

Architektur LSM-Datenbank

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.

  • Data Engineering ist ja nicht Selbstzweck. Vielmehr dient es dazu, aus Daten Nutzen zu ziehen. Künstliche Intelligenz wurde möglich, dank sorgfältigem Data Engineering.

  • Generative KI, insbesondere Large Language Models (LLMs), haben die Welt im Sturm erobert.

    Diese riesigen Sprachmodelle bieten zahllose Möglichkeiten, um unsere Anwendungen auf die nächste Stufe zu heben.

    Abonniere meinen Newsletter und erhalte regelmäßig Tipps und Tricks zum produktiven Einsatz von LLMs.

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control
Veröffentlicht am von

Bloom Filter

Bloom Filter

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. 

Ursprung von Bloom Filter

Burton H. Bloom veröffentlichte 1970 die Grundidee der heutigen Bloom Filter in seinem Paper “Space/Time Trade-offs in Hash Coding with Allowable Errors”

Als Beispielanwendung stellte er ein Programm vor, das in der Lage sein sollte, Trennzeichen in einem Text automatisch einzufügen. Dabei sollen die meisten Fälle mit ein paar einfachen Regeln erkannt werden und nur für die wenigsten Fälle ein teures Nachschlagen in einem Dictionary notwendig sein. Er geht davon aus, dass das Dictionary nicht ins Memory passt und Disk Zugriffe notwendig sind. Eine Hash-Struktur wäre viel kleiner und würde ins Memory passen. Könnte diese Hashstruktur ausgenutzt werden, um festzustellen, ob ein Wort im Dictionary vorkommt, dann wären unnötige Festplattenzugriffe vermeidbar.

So motiviert, entwickelt er in seinem Paper das Konzept, das heute als Bloom-Filter bekannt ist und vielseitig eingesetzt wird.

Seit 1970 haben sich die Größenordnungen geändert. Lösungsansätze, die seinerzeit wegen der knappen Ressourcen der damaligen Systeme entwickelt wurden, finden heute wieder Anwendung bei der Verarbeitung massiver Datenmengen.

Bloom-Filter werden in LMS-Datenbanken wie Google BigTable und Apache Cassandra verwendet, um festzustellen, ob es sich lohnt, in einer bestimmten SSTable überhaupt nach einem Key zu suchen. Jede SSTable wird von einem Bloom-Filter begleitet. Beim Lesen wird zuerst der Filter konsultiert – gibt er ein positives Ergebnis, dann wird die SSTable nach dem Key durchsucht.

Bloom-Filter werden gerne als probabilistische Datenstruktur bezeichnet. Das wird dadurch begründet, dass zu einem Bloom-Filter ein passender Hash-Algorithmus gehört und auch deshalb, weil False Positives möglich sind.

Ein sehr naiver Bloom-Filter und Murmur3

Wir stellen zuerst einen sehr naiven Bloom-Filter vor, um das Konzept zu erklären. Im folgenden Abschnitt werden wir diesen erweitern, so wie Bloom es in seinem Paper vorgeschlagen hat.

Die Struktur eines Bloom-Filters

Ein Bloom-Filter ist ein Bit-Array. Zu Beginn werden alle Bits auf 0 gesetzt.

Für jedes Element, beispielsweise für ein Key für eine SSTable, bestimmen wir einen Hashwert mit einer geeigneten Hashfunktion. 

Wir erinnern uns an die wichtigsten Eigenschaften von Hash-Algorithmen:

  • Durchläuft ein Wert einen Hash-Algorithmus mehrmals, dann ergibt sich immer derselbe Wert. Der Algorithmus ist also deterministisch. 
  • Aus dem Hash-Wert kann der Ausgangswert nicht eindeutig bestimmt werden.
  • Und zwei Wert können denselben Hash-Wert haben.

Diese Eigenschaften sind Grundlage für das Funktionieren des Bloom-Filters.

Murmur3-Hash

Murmur3 ist eine geeignete Hashfunktion. Murmurhash wurde 2008 von Austin Appleby entwickelt – der Algorithmus wurde verbessert und liegt heute als Murmur3 vor: Hier die Referenzimplemenation: https://github.com/aappleby/smhasher

Im Wesentlichen werden bitweise Operationen wie Rotationen, Shift-Left und XOR durchgeführt. Murmur3 werden 32, 64, oder 128 Bit-Arrays erzeugen. Der Name Murmur ist abgeleitet von den wichtigsten Operationen: Multiply (also Shift-Left) und Rotate.

Beim Aufruf von Murmur3 geben wir einen Seed-Wert mit. Das ist eine ganze Zahl, mit der in der Folge die Multiplikationen und Rotationen beeinflusst werden.

Wollen wir mit Hilfe des so aufgebauten naiven Bloom-Filters prüfen, ob ein Key in unserem System vorhanden ist, dann bilden wir zuerst den Hashwert des Keys und verknüpfen dessen Bitfolge mit AND mit dem Filter. Resultiert der Key unverändert, dann können wir davon ausgehen, dass dieser in unserem System bereits bekannt ist.

Hier ein Code-Beispiel in Python für diesen naiven Bloom-Filter – wir benötigen dazu die mmh3 Library.

pip install mmh3

>>> import mmh3
>>> 
>>> h42=mmh3.hash('42', signed=False)
>>> h42
3159925814
>>> bin(h42)
'0b10111100010110001010010000110110'
>>> 
>>> h53=mmh3.hash('53', signed=False)
>>> h53
222179750
>>> bin(h53)
'0b1101001111100011000110100110'
>>> 
>>> # Den Filter erstellen
>>> filter = h53 | h42
>>> bin(filter)
'0b10111101011111101011010110110110'
>>> 
>>> # Ist 42 im Filter vorhanden?
>>> hq1=mmh3.hash('42', signed=False)
>>> hq1 & filter == hq1
True
>>> 
>>> # Ist 13 im Filter vorhanden
>>> hq2=mmh3.hash('13', signed=False)
>>> hq2 & filter == hq2
False
>>>

Dabei kann es zu False Positive kommen – der Filter meint also, der Key sei in der SSTable, obwohl er dort nicht vorhanden ist.

Doch das ist nicht weiter schlimm – kommt es selten vor, dann wird die SSTable selten überflüssig durchsucht.

Mit diesem naiven Verfahren werden schon mit wenigen Keys alle Bits im Bloom-Filter auf 1 stehen: Das Beispiel zeigt einen 32-bit Bloom-Filter. Nur mit 2 Werten sind schon 22 der Bits auf 1 gesetzt. Es liegt auf der Hand, dass dieser kleine Bloom-Filter nicht effektiv ist, wenn wir mit sehr vielen Keys arbeiten müssen:  – sehr schnell würden alle Bits auf 1 stehen  und der Filter versagt.

Bloom-Filter – die Original-Idee

Auch der Original-Bloom-Filter ist ein Bit-Array. Dessen Länge kann je nach Bedarf unterschiedlich festgelegt werden.

Die Requisiten

Es kommen mehrere, voneinander unabhängige Hash-Algorithmen zum Zuge. Murmur3 wird ja mit einem Seed-Wert aufgerufen und mit verschiedenen Seed-Werten erhalten wir für ein und denselben Key jeweils verschiedene Hash-Werte.

Mit Murmur3 können wir diese Voraussetzung für einen Bloom-Filter mit nur einem Algorithmus erfüllen. Mehr als 12 verschiedene Hash-Algorithmen kommen selten zum Zuge.

Der Wertebereich der Hash-Funktion sollte die Länge des Bit-Array nicht übersteigen. Ist der Bit-Array kleiner als der Wertebereich der Hashfunktion, dann kann jeder Hashwert mit dem Modulo-Operator passend gemacht werden – einfach Hash-Wert modulo Array-Länge nehmen.

Das sind die Requisiten für den Bloom-Filter.

Einen Key in den Bloom-Filter einfügen

Wird ein Wert in den Bloom-Filter eingefügt, dann kommt der folgende Algorithmus zum Zug:

  • Wiederhole für alle Hash-Funktionen:
    • Für jede der Hash-Funktion resultiert eine Zahl, die als Index im Bit-Array des Bloom-Filters dient. Das entsprechende Bit wird auf 1 gesetzt.

 

Den Bloom-Filter befragen

Ist ein Key gegeben, und der Bloom-Filter soll die Frage beantworten, ob der Key in unserem System bereits bekannt ist, dann wird analog verfahren:

  • Wiederhole für alle Hash-Funktionen:
    • Bilde den Hashwert und prüfe, ob das entsprechende Bit im Array auf 1 gesetzt ist.
      • Wenn für einen Hash-Operator das Bit auf 0 ist, dann ist der Wert sicher nicht in der Ursprungsmenge vorhanden.
      • Wenn alle Hash-Operationen 1 liefern, dann ist die Wahrscheinlichkeit groß, dass der Wert in der Menge vorhanden ist.

Wir sehen: je mehr Hashoperatioen zum Zuge kommen, um so verlässlicher arbeitet der Filter. Doch er wird damit auch langsamer.

Wie wir schon beim sehr naiven Bloom-Filter beobachten konnten, sind False Positives möglich. Es kann also sein, dass wir zu oft vergeblich in unserem System nach einem Key suchen werden.

False Negatives sind jedoch nicht möglich – wir werden wegen des Bloom-Filters keinen Key verpassen.

Fazit

Bloom-Filter eignen sich hervorragend, um die Mitgliedschaft eines Keys in einer Menge zu prüfen. Sie wurden bereits 1970 entwickelt und fanden in jüngerer Zeit Eingang in viele Systeme, um Zugriffszeiten zu optimieren.

 

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

  • Data Engineering ist ja nicht Selbstzweck. Vielmehr dient es dazu, aus Daten Nutzen zu ziehen. Künstliche Intelligenz wurde möglich, dank sorgfältigem Data Engineering.

  • Generative KI, insbesondere Large Language Models (LLMs), haben die Welt im Sturm erobert.

    Diese riesigen Sprachmodelle bieten zahllose Möglichkeiten, um unsere Anwendungen auf die nächste Stufe zu heben.

    Abonniere meinen Newsletter und erhalte regelmäßig Tipps und Tricks zum produktiven Einsatz von LLMs.

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control
Veröffentlicht am von — Schreib einen Kommentar

B-Baum als Datenbankindex

B-Trees in Databases

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. 

Inhalt

Datenbank Seiten (DB-Page)
Ursprung und Einsatz von B-Bäumen
Grundstruktur eines B-Baums
Einsatz eines B-Baums
Optimieren mit B-Tee
Insert und Delete in B-Bäumen
Warum B-Bäume
Beispielanwendung: B-Bäume in der Praxis
Fazit und Ausblick

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.

Datenbank Seiten (DB-Page)

Die Daten selbst werden in der Datenbank auf Seiten (Database Pages, DB-Pages) gespeichert. Die Größe der Seite kann im create table oder im create tablespace Statement definiert werden. Üblich sind Größen von 4KB, 8KB, etc 32KB. Eine DB-Page bildet eine Verwaltungseinheit.

Schematische Darstellung einer DB-Page wie sie in vielen RDBMS gebräuchlich ist

Der Header enthält Meta-Information, beispielsweise über Anzahl Zeilen, verfügbaren Platz, Anzahl Löschungen.

Je nach Datenbank-Produkt sind im Header auch IDs und Offsets zu den entsprechenden Zeilen gespeichert – unser Bild zeigt diese Variante.

Die Inhalte einer Zeile liegen nebeneinander – wir untersuchen zeilenbasierte Datenbanken, die zur Zugriffsoptimierung einen Index benötigen. 

Wird eine Zeile gelöscht, dann wird sie zuerst geflaggt. Sie belegt weiterhin Platz, bis das DBMS die Seite in sich reorganisiert. Dazu dient der leere Platz.

Die Zeilen sind über die Datenbankseiten hinweg zufällig verteilt und auch innerhalb einer Seite liegen die Zeilen ungeordnet. 

Der Index in Form des B-Baumes verhilft zum schnellen Zugriff.

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.

Knoten in einem B+-Baum

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:

B-Tree-Index in einer Datenbank

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 logd+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”

  • Data Engineering ist ja nicht Selbstzweck. Vielmehr dient es dazu, aus Daten Nutzen zu ziehen. Künstliche Intelligenz wurde möglich, dank sorgfältigem Data Engineering.

  • Generative KI, insbesondere Large Language Models (LLMs), haben die Welt im Sturm erobert.

    Diese riesigen Sprachmodelle bieten zahllose Möglichkeiten, um unsere Anwendungen auf die nächste Stufe zu heben.

    Abonniere meinen Newsletter und erhalte regelmäßig Tipps und Tricks zum produktiven Einsatz von LLMs.

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control
Veröffentlicht am von

Optimistisches Concurrency Control

Trade-Offs bei Transaktionen in relationalen Datenbanken

Optimistisches Concurrency Control als Rettungsanker?

Wer mit Datenbanken arbeitet, verwendet zwangsläufig Transaktionen und muss dabei Trade-Offs berücksichtigen. Optimistisches Concurrency Control ist der Versuch, die Trade-Offs der Datenbank zu mildern. Es lohnt sich, darüber nachzudenken, wenn man den Lesevorgang und den anschließenden Schreibvorgang in zwei unterschiedlichen Datenbanktransaktionen durchführen muss, beispielsweise, weil dazwischen eine langdauernde Benutzerinteraktion stattfindet. 

So funktioniert’s: Wir ergänzen jede Tabelle mit einem zusätzlichen Feld, beispielsweise version int. Die Applikation liest immer auch die Version mit. Und jeder Update wird ergänzt, beispielsweise so:

update test set ... version = version + 1 where version = alte_version; Statt alte_version setzen wir den Wert ein, den wir vorher gelesen haben.

Die Überlegung ist einfach: So können wir sicher stellen, dass wir mit unserem Update-Befehl nicht die Daten verändern, die in der Zwischenzeit eine anderer User verändert hat.

Die Erwartung ist ebenso einfach formuliert: Wir möchten nicht nur keine Updates verlieren, sondern sicher sein, dass es zu keinen Deadlocks und zu keinen blockierten Transaktionen kommt.

Ein weitverbreiteter Irrglaube: Transaktionen der Datenbank kann man nicht umgehen –  Jede Operation in einer Datenbank findet innerhalb einer Transaktion statt – ausnahmslos. Und so wird die Erwartung enttäuscht: In relationalen Datenbanken kann es trotz Optimistischen Concurrency Controls zu blockierten Transaktionen kommen.

Der Artikel untersucht das Optimistische Concurrency Control, illustriert dessen Grenzen mit einem Beispiel und zeigt eine sinnvolle Anwendungsmöglichkeit.

Optimistisches Concurrency Control ist nicht zu verwechseln mit dem Multiversion Concurrency Control (MVCC), das beispielsweise PostgreSQL einsetzt, um ACID-Transaktionen auf Zeilenebene zu verwalten. Wir untersuchen dessen Verhalten im zweiten Beispiel in diesem Artikel.

Inhalt

Optimistisches Concurrency Control – Das Experiment
Zwei gleichzeitige Sessions mit Optimistischem Concurrency Control
Der Effekt des Optimistischen Concurrency Control
MVCC und Snapshot Isolation
Die Grenzen des MVCC – der Einsatz des Optimistischen Concurrency Control
Select for update – die Datenbank arbeiten lassen
Auswirkungen für Applikationsprogramm
Gesperrte Einheiten
Andere Transaction Isolation level
Fazit
Empfehlungen für Transaktionen in Relationen Datenbanken
NoSQL Datenbanken

Optimistisches Concurrency Control – Das Experiment

Wir arbeiten mit PostgreSQL. Das Beispiel lässt sich mit jedem beliebigen relationalen System wiederholen.

Zuerst die Vorbereitungen: Wir arbeiten mit einem Datenbankschema my_database und mit zwei Sessions im PSQL-Client.

Zuerst definieren wir eine einfache Tabelle mit der diskutierten Spalte version. Wir fügen gleich eine Zeile ein:

my_database=> create table test (version int);
CREATE TABLE
my_database=> insert into test values (1);
INSERT 0 1
my_database=>

Der Einfachheit halber belassen wir es dabei und zeigen den Effekt mit dieser einen Tabelle mit einer Zeile und einer Spalte. In einem produktiven Beispiel müssen wir natürlich alle Spalten aufzählen und die vom Update betroffenen Zeilen in der Where-Klausel korrekt auswählen.

Zwei gleichzeitige Sessions mit Optimistischem Concurrency Control

Jetzt haben wir Minimalvoraussetzungen geschaffen, um den Effekt des Optimistischen Concurrency Control zu untersuchen.

Wir haben zwei gleichzeitige Sessions in unterschiedlichen Applikationsprogrammen und zwar diejenige von Alice und diejenige von Bog. Beide arbeiten zur gleichen Zeit mit denselben Daten.

Alice arbeitet mit autocommit, also jedes einzelne Statement wird sofort automatisch committed und sie verwendet Transaction Isolation Level ‘Read Committed’:

my_database=> \echo :AUTOCOMMIT
on
my_database=> SHOW TRANSACTION ISOLATION LEVEL;
transaction_isolation
———————–
read committed
(1 row)
my_database=>

Bob hingegen hat autocommit ausgeschaltet – der Befehl lautet \set AUTOCOMMIT off und auch er verwendet  Read Committed:

my_database=> \echo :AUTOCOMMIT
off
my_database=> SHOW TRANSACTION ISOLATION LEVEL;
transaction_isolation
———————–
read committed
(1 row)
my_database=*>

Zusammenfassend:

  • Beide Sessions verwenden das voreingestellte Transaction Isolation Level von PostgreSQL: Read Committed.
  • Der Unterschied der Sessions liegt im Commit-Verhalten.

Die Grafik zeigt zuerst das Beispiel, das wir anschließend Zeile für Zeile unter die Lupe nehmen. Der Einfachheit halber betrachten wir eine Tabelle test mit genau einer Zeile und genau einer Spalte.

Optimistic Concurrency Control

Gehen wir das Beispiel jetzt Schritt für Schritt durch.

Bob’s Transaktion dauert lange, er führt beispielsweise lange Analysen durch und ganz wichtig – commit erfolgt erst ganz am Schluss nach mehreren Datenbankoperationen. Das mag konstruiert erscheinen, ist in der Praxis oft anzutreffen. Zuerst liest Bob den Inhalt der Tabelle – wir konzentrieren uns nur auf die Spalte ‘Version’, weil diese ja fürs Optimistische Concurrency Controll maßgebend ist, alle anderen Spalten hängen vom jeweiligen Anwendungsfall ab:

my_database=*> select * from test;
version
———
1
(1 row)
my_database=*>

Achtung – kein Commit bei Bob.

Alice kann ungehindert die Daten in derselben Tabelle verändern. Erinnere: Alice verwendet autocommit:

my_database=> update test set version=version+1 where version=1;
UPDATE 1
my_database=>

Das funktioniert wie erwartet. Immerhin hat Bob bisher ja ‘nur’ gelesen.

Bob wiederholt den Lesevorgang:

my_database=*> select * from test;
version
———
2
(1 row)
my_database=*>

Das ist korrekt – Read Committed liefert ja immer immer die letzten, durch commit bestätigten Werte. Die anderen Transaction Isolation Leven werden wir später beleuchten.

Jetzt will Bob die Werte verändern:

my_database=*> update test set version=version+1 where version=2;
UPDATE 1
my_database=*> select * from test;
version
———
3
(1 row)
my_database=*>

Beachte – noch immer kein Commit in Bob’s Transaktion. Zuerst wird der Wert verändert und danach gelesen. Postgres geht davon aus, dass Bob in seiner Transaktion mit den selbst veränderten Werten weiterarbeiten will und liefert diese aus, obwohl sie noch nicht bestätigt wurden. Auch hierzu setzt Postgres auf MVCC.

Jetzt wird Alice wieder aktiv – sie arbeitet noch immer mit autocommit:

Der Effekt des Optimistischen Concurrency Control

Alice führt jetzt eine Veränderung an den Daten mit Hilfe von Optimistischem Concurrency Control durch:

Alice liest zuerst die Werte:

my_database=> select * from test;
version
———
2
(1 row)
my_database=>

Es ist korrekt dass Alice für die Version den Wert 2 erhält: Auch ihre Transaktion funktioniert mit Read Committed und Bob hat die Veränderungen seiner Transaktion ja noch nicht bestätigt. Postgres setzt auch hierzu MVCC ein: lesende und schreibende Transaktionen blockieren einander nicht gegenseitig.

Alice berechnet jetzt eine Veränderung an den Daten und will mit Hilfe der Where-Klausel und dem Versionsfeld sicherstellen, keine Daten anderer Transaktionen zu verändern.

Lassen wir Alice eine extreme Erhöhung des Werts vornehmen – so wird der Effekt des Testbeispiels besser sichtbar – Alice erhöht die Version um 100 und erwartet als Ergebnis 102:

my_database=> update test set version=version+100
where version=2;

Hier bleibt die Transaktion stehen – das funktioniert wie erwartet, denn Bob hat ja noch immer keinen commit gemacht und hält jetzt Schreibsperren auf der Zeile, die Alice verändern möchte. Zwei Transaktionen dürfen nicht gleichzeitig dieselbe Zeile schreiben.

Die Transaktion steht ziemlich lange still. Ich habe die Zeit nicht gemessen und auch nicht nachgelesen, wie lange es dauert, bis ein Timeout auftritt. Sicher kann ich berichten, dass ich den berühmten Kaffe trinken war und sich bis zu meiner Rückkehr nichts bewegt hat – mehrere Minuten waren es sicher – untragbar für einen produktiven Mehrnutzerbetrieb.

Die Situation kann aufgelöst werden, indem Bob endlich commit sagt:

my_database=*> commit;
COMMIT
my_database=>

Jetzt geht auch Alices Transaktion zu Ende. Erwartungsgemäss wird der Update nicht durchgeführt – immerhin wurde ja der Wert in Version von Bob verändert und Alice findet keine Zeile mehr mit version=2. Das anschließende Select-Statement findet den Wert, den Bob hinterlassen hat.

my_database=> update test set version=version+100
where version=2;
UPDATE 0
my_database=> select version from test;
version
———
3
(1 row)
my_database=>

Die Arbeit von Alice wurde also in der Datenbank nicht festgehalten. Alice muss ihre Transaktion nochmals durchführen – ein gut geschriebenes Applikationsprogramm wird sie dabei unterstützen und in einer verständlichen Systemmitteilung auch den Grund erklären, so dass Alice versteht, warum sie doppelt Arbeiten muss. Je nach Anwendungsfall wird das Programm die Transaktion vielleicht automatisch wiederholen können. Ob in unserem Beispiel Alice das Endergebnis verstehen würde? Immerhin erwartet sie 102 und erhält aber 3…

MVVC und Snapshot Isolation

In unserem Beispiel führten wir bisher mit der Spalte Version eine Art selbstgebautes Concurrency Control ein – diese wird auch Optimistisches Concurrency Control genannt.

PostgreSQL verwendet MVCC – Multiversion Concurrency Control. Damit wird garantiert, dass lesende Transaktionen keine schreibenden behindern und umgekehrt. Dazu führt Postgres verschiedene Versionen (Snapshots)  ein- und derselben Zeile und merkt sich, welcher Transaktion welche Version der Zeile ausgeliefert wurde.

Die folgende Grafik zeigt das Verhalten von PostgreSQL mit Hilfe desselben Beispiels, doch diesmal ohne die Where-Klausel, also mit reinem MVCC ohne den von der Applikation ergänzten Zusatz des Optimistischen Concurrency Control.

Die Session-Einstellungen für Alice und Bob lassen wir unverändert: Alice verwendet autocommit, Bob nicht und beide arbeiten mit dem Transaction Isolation Level ‘Read Committed’.

Diesmal hat unsere Tabelle eine einige Spalte zahl int und eine einzige Zeile.

Multiversion Concurrency Control MVCC

Die allerletzte Zeile zeigt den einzigen Unterschied: Alice erwartete zwar den Wert 102 – immerhin sah sie den Wert 2, bevor sie sich entschloss, diesen um 100 zu erhöhen. Nach dem Commit ihrer Transaktion, sieht sie aber den Wert 103.

Aus Sicht der Datenbank ist der Wert 103 jedoch der korrekte: Die Datenbank hat einen “Lost Update” verhindert, und die Erhöhung der Transaktion von Bob mit einbezogen.

Ob Alice als Person das auch so sieht, steht auf einem anderen Blatt geschrieben.

Die Grenzen des MVCC – der Einsatz des Optimistischen Concurrency Control

Unser bisheriges Beispiel zeigte, dass MVCC ausreichend ist und der Aufwand des Optimistischen Concurrency Control überflüssig.

Jetzt verändern wir das Beispiel und wir arbeiten mit einer neuen Tabelle:

create table test (stadt varchar(20), land varchar(20));

Der Einfachheit halber bleiben wir bei einer einzelnen Zeile:

Der Ablauf ist gleich, wie im vorherigen Beispiel. Doch diesmal werden andere Felder verändert. Aus Sicht der Datenbank ist alles in Ordnung: nur bestätigte Werte werden ausgeliefert und keine Transaktion überschreibt die Werte einer anderen Transaktion.

Inhaltlich jedoch ist alles schief gelaufen und die Datenbank enthält jetzt sinnlose Daten – die ewige Stadt liegt ja nicht in der Schweiz.

Diese Situation hätte mit Optimistischem Concurrency Control verändert werden können.

  1. In der Tabelle Test das Feld ‘version int’ ergänzen.
  2. Beim Insert der Version den Wert 1 geben
  3. Beim jedem Update konsequent Version um 1 erhöhen

Was wäre passiert:

  1. Beim Insert wäre Version auf 1 gesetzt worden
  2. Bob hätte Version auf 2 gesetzt
  3. Alice hätte Version = 1 gelesen
  4. Bob hätte Version 2 bestätigt
  5. Alice hätte ihr Update mit where version=1 versucht und hätte keine Zeile verändert.
  6. Das Applikationsprogramm hätte das erkannt und Alice gemeldet und einen benutzerfreundlichen Dialog gestartet.

select for update – die Datenbank arbeiten lassen

Bisher gingen wir davon aus, dass wir gute Gründe haben, den Lese- und Schreibvorgang bei Alice in zwei verschiedenen Datenbanktransaktionen ablaufen zu lassen. Die Datenbank geht immer davon aus, dass wir als Anwenderinnen und Anwender wissen, was wir tun, und unterstützt uns dabei.

Und selbstverständlich bietet uns eine moderne Datenbank wie PostgreSQL auch die notwendigen Bordmittel, ohne den Overhead des Optimistischen Concurrency Controls zu arbeiten.

Das folgende Beispiel zeigt, wie es geht:

Was wurde verändert:

  • Alice schaltet autocommit aus. Bob hatte ja autocommit immer ausgeschaltet.
  • Jede schreibwillige Transaktion liest die später zu schreibenden Daten mit select for update.

Mit select for update versieht die Datenbank die betroffenen Daten schon beim Lesen mit einer Schreibsperre.

So wird erreicht, dass Alice die von Bob veränderten Daten nicht zu sehen bekommt, bis Bob diese bestätigt hat und so wird Alice auch auf inhaltlich korrekten und konsistenten Daten arbeiten.

Auswirkungen fürs Applikationsprogramm

Select for update und der anschließende Update müssen in ein- und derselben Transaktion stattfinden. Auch wenn dazwischen ein Benutzer eine lange Denkpause einlegt. Die betroffenen Daten bleiben solange gesperrt für Veränderungen anderer Transaktionen, können aber noch gelesen werden.

Eine Transaktion ist immer an eine Datenbanksession gebunden. Handelt es sich beim Applikationsprogramm um eine Webanwendung, dann muss die Datenbanksession korrekt den jeweiligen Requests und Responses zugeordnet werden, was wiederum bedeutet, dass die Datenbanksession im zugehörenden Serverseitigen Web-Sessionobjekt gehalten werden muss.

Ist das nicht möglich, dann ist Optimistisches Concurrency Control ein Ausweg, der jedoch Disziplin seitens der Entwickler erfordert, die konsequent die Spalte ‘Version’ nachführen müssen.

Gesperrte Einheiten

Viele moderne relationale Datenbanken arbeiten standardmäßig mit Row-Level-Locking. Ist das nicht der Fall, dann werden größere Einheiten gesperrt, beispielsweise eine Datenbank-Seite oder die ganze Tabelle.

Beim Page-Level-Locking werden sämtliche Zeilen gesperrt, die sich auf derselben Datenbank-Seite befinden, wie die von der Transaktion tatsächlich verarbeitete Zeile. Wieviele Zeilen das sind, und welche, können wir nicht wissen. In dem Fall kann es aus Sicht der Benutzer zu unerklärlichen Wartezeiten und unerklärlichen Deadlocks kommen.

Table-Level-Locking ist sehr ungünstig für einen Mehrnutzerbetrieb und wird meistens nur für Wartungsarbeiten verwendet.

Andere Transaction Isolation Level

Viele relationale Datenbanken verwenden Read Committed als das Standard-Transaction Isolation Level. Den Effekt haben wir im Beispiel gesehen: Bob’s Transaktion erhält die Werte gezeigt, die Alice verändert hat. Alice jedoch kann keine Werte verändern, solange Bob’s Transaktion die Schreibsperren nicht freigibt. Dieses Verhalten ist oft wünschenswert.

Mit Repeatable Read könnte Bob erreichen, dass seine Transaktion bei wiederholtem Lesen derselben Daten jeweils dieselben Werte gezeigt erhält – eigene Änderungen inklusive. Bob könnte jedoch keine Änderungen vornehmen, wenn Alice inzwischen Änderungen an denselben Daten vorgenommen hat.

Zusätzlich würde Bob bei wiederholtem Lesen die Effekte von Insert- und Delete-Statements bemerken, die Alice inzwischen vorgenommen hat: Würde Alice Zeilen eingefügt haben, die auf die Where-Klauseln von Bob’s wiederholtem Select antworten, dann würde Bob diese zu sehen bekommen. Man spricht in diesem Zusammenhang von Phantomen.

Mit Serializable wird das Verhalten von Repeatable Read noch verschärft. Da könnte Alice keine Änderungen vornehmen, wenn Bob die Daten gelesen hat. Mit diesem Transaction Isolation Level treten oft ungewünschte Blockaden und gar Deadlocks auf, gerade dann, wenn Transaktionen, wie diejenige von Bob vorhanden sind.

Read Uncommitted ist die vierte Möglichkeit. Je nach Datenbanksystem werden dabei tatsächlich Sperren umgangen und noch unbestätigte und damit möglicherweise inkonsistente Werte geliefert.

Setzt man mit PostgreSQL die Transaktion von Alice auf Read Uncommitted und führt unsere Beispiele durch, dann wird man dasselbe Verhalten beobachten, wie mit Read Committed. PostgreSQL behandelt Read Uncommitted gleich wie Read Committed und verhindert damit einen ungewollt inkonsistenten Zustand der Daten.

Fazit

Es führt kein Weg daran vorbei: Ein Applikationsprogramm muss vorsehen, dass eine Transaktion wiederholt werden muss.

Der Einsatz von Optimistischem Concurrency Control ist eine Notlösung, wenn eine Transaktion zwischen dem Lesen und anschließenden Schreiben nicht aufrecht erhalten werden kann.

Verlässlicher ist es, sich auf die Werkzeuge der Datenbank zu verlassen und mit select for update zu arbeiten. Dank MVCC ist in modernen Datenbanken das Transaction Serialisation Level ‘Read Committed’ die beste Wahl für Anwendungen mit User-Interaktionen.

Problematisch wird es, wenn komplexe Transaktionen Daten wiederholt lesen, Berechnungen vornehmen und Daten schreiben aufgrund der Ergebnisse der Berechnungen. Bob’s Transaktion simuliert dieses Verhalten. Solche Transaktionen benötigen unter Umständen Repeatable Read oder gar Serializable als Isolation Level und behindern damit den reibungslosen Mehrnutzerbetrieb.

Empfehlungen für Transaktionen in Relationalen Datenbanken

Allgemeine Empfehlungen zum Transaktionshandling möchte ich nur sehr oberflächlich abgeben:

  • Kenne deine Datenbank;
  • Kenne deine Applikation und alle anderen Applikationen auf denselben Datenbanktabellen;
  • Halte alles so einfach, wie möglich;
  • Entkopple Abhängigkeiten in den Daten;
  • Verwende Standard-Verfahren der Datenbank;
  • Halte alle Transaktionen kurz;
  • Lagere Analysen aus in Data Warehouses oder Date Lakehouses;
  • Erwäge NoSQL-Datenbanken.

NoSQL Datenbanken

Auch in nicht-relationalen Datenbanken finden alle Operationen innerhalb einer Transaktion statt. Doch anders als bei relationalen Datenbanken finden wir in NoSQL-Datenbanken viele unterschiedliche Ausprägungen des Transaktionsverhaltens vor.

Durch die nicht-relationale Datenorganisation werden auch Abhängigkeiten verringert – mit dem Preis, dass Redundanz eingeführt wird und Daten inhaltlich inkonsistent werden können. Die Verantwortung über die inhaltliche Datenintegrität bleibt in den Händen der Entwicklerinnen und Entwickler der Applikationen.

In unserem Beispiel blieb die eine Session stehen, weil beide Sessions ja als READ COMMITTED-Transaktionen liefen. Mit einer geeigneten NoSQL-Datenbank können wir mit der gezeigten Art des Optimistischen Concurrency Control arbeiten, ohne dass es zu blockierten Sessions kommt.

Doch auch bei NoSQL-Datenbanken gilt: Man kenne die Datenbank – denn diese ‘Freiheit’ kommt mit einem Trade-Off, den man kennen sollte, bevor man ihn eingeht. Welches der Trade-Off ist hängt ab von vom Datenbankprodukt und von der eigenen Applikation.

  • Chatbot als Lernassistent
  • Prompt Engineering Personas und Wiederholungen
  • EBook Tutorial: Cluster aus virtuellen Maschinen
  • Ebook: Apache ZooKeeper
  • Ebook: Realtime Streaming Pipelines
  • LSM-Trees: Log Structured Merge Trees
  • Aufbau einer Enterprise Search
  • Zeit Stream Analytics
  • B-Tree-Index in Datenbanken
  • Ordering Guarantee in Apache Kafka
  • CAP Theorem
  • MapReduce Funktionale Programmierung
  • Konzepte des HDFS
  • Optimistisches Concurrency Control