Grundlagen von Datenbanken

Die Grundlagen von bashdb

• Das einfachste Datenbankprogramm, bashdb, besteht aus zwei Bash-Funktionen.
• Die Funktion db_set fügt Daten an eine Datei an, und die Funktion db_get ruft Daten ab.
• Zu den Problemen von bashdb gehören Dauerhaftigkeit, Atomarität, Isolation und Performance.

bashdb mit ACID verbessern

• ACID bezeichnet die Eigenschaften von Datenbanktransaktionen: Atomarität, Konsistenz, Isolation und Dauerhaftigkeit.
• Um die Dauerhaftigkeit von bashdb zu verbessern, wird dem Befehl db_set der Befehl sync hinzugefügt.
• Für Isolation wird das Programm flock verwendet, um Dateisperren hinzuzufügen.

Dauerhaftigkeit

• fsync und fdatasync sind Systemaufrufe, die Schreibpuffer auf die Festplatte flushen.
• Der Befehl sync flusht alle „dirty“ Pages auf die Festplatte, und das Flag -d ruft fdatasync auf.

Isolation

• Mit flock erhält bashdb Isolation zwischen mehreren Prozessen.
• flock ist ein Linux-Programm für Dateisperren; mit dem Flag -s sind gleichzeitige Lesezugriffe möglich.

Schlechte Nachrichten

• Für bashdb lässt sich keine einfache Methode finden, um Atomarität zu garantieren.
• Für bessere Performance muss der O(n)-Algorithmus verbessert werden.

Storage Engine

• Der Zweck einer Storage Engine besteht darin, eine Abstraktion zum Lesen und Schreiben von Daten in persistentem Storage bereitzustellen.
• Das Design einer Storage Engine zielt darauf ab, Disk-I/O und Disk-Seeks zu minimieren.

Veränderlicher B-Baum

• Ein B-Baum ist eine Variante des BST mit räumlicher Lokalität, die Disk-I/O und Suchvorgänge minimiert.
• Ein B-Baum ist ein verallgemeinerter BST, bei dem ein Knoten mehr Kinder haben kann.

Unveränderlicher LSM-Baum

• Ein LSM-Baum ist eine unveränderliche, sequenziell geschriebene Datenstruktur, die sich für schreiblastige Workloads eignet.
• Ein LSM-Baum puffert Daten im Speicher und flusht sie beim Erreichen einer bestimmten Größe als sortierte SSTable.

Bloom-Filter

• Ein Bloom-Filter ist eine probabilistische Datenstruktur, mit der sich effizient prüfen lässt, ob ein Element nicht in einer Menge enthalten ist.
• Bloom-Filter arbeiten mit Hash-Funktionen und haben eine Platzkomplexität von O(log n).

Write-Ahead-Log

• Ein WAL ist eine spezielle Datei, die alle Transaktionsoperationen protokolliert und beim Start des Datenbankprozesses den Zustand rekonstruiert.

Isolation

• Um Isolation zu erreichen, können pessimistische Sperren, optimistische Sperren oder MVCC verwendet werden.
• Der ANSI/ISO-Standard SQL 92 definiert verschiedene Lese-Isolationsstufen.

Verteilte Systeme

• Verteilte Systeme erhöhen die Komplexität und können Daten für Verfügbarkeit und horizontale Skalierung auf mehrere Maschinen verteilen.
• Nach dem CAP-Theorem kann ein System nur zwei von drei Eigenschaften garantieren: Konsistenz, Verfügbarkeit und Partitionstoleranz.

Konsistentes Hashing

• Konsistentes Hashing ist eine Methode zur Datenpartitionierung, die beim Hinzufügen oder Entfernen von Knoten die Menge der zu migrierenden Elemente reduziert.

GN⁺-Meinung:

• Das Verständnis der grundlegenden Probleme von Datenbanken und der ACID-Eigenschaften ist zentral für Database Engineering.
• Das Beispiel bashdb hilft dabei, Probleme zu verstehen, die in realen Datenbanksystemen auftreten.
• Das Design von Storage Engines und verteilten Systemen ist ein entscheidender Faktor für Performance und Zuverlässigkeit von Datenbanken.

[GN⁺]

Hacker-News-Kommentare

• Zusammenfassung des ersten Kommentars:

  • Eine der Eigenschaften von LSM-basierten Datenbanken ist, dass gelöschte Datensätze oder Tombstones lange bestehen bleiben.
  • Tombstones sollten nur auf der letzten Ebene übersprungen werden, nicht auf allen Ebenen.
  • Andernfalls können Tombstones aus höheren Ebenen entfernt werden und Einträge aus niedrigeren Ebenen wieder sichtbar werden.
  • Datenbanken wie RocksDB versuchen, dieses Problem durch Optimierungen zu lösen.

• Zusammenfassung des zweiten Kommentars:

  • Es kann riskant sein, zu vermeiden, verteilte Systeme zu lernen.
  • Tatsächlich ist jedes nichttriviale Produktionssystem ein verteiltes System.
  • Wenn eine Datenbank ein Replikations-Set ist, dann ist sie ein verteiltes System.
  • Wer mehr über verteilte Systeme lernen möchte, sollte sich jepsen.io und raft.github.io ansehen.

• Zusammenfassung des dritten Kommentars:

  • Bei Konsistenz gibt es Datenbankkonsistenz und Anwendungskonsistenz.
  • In einer einzelnen Tabelle kann ACID (Atomarität, Konsistenz, Isolation, Dauerhaftigkeit) erreicht werden, bei Schreibvorgängen über mehrere Tabellen hinweg kann es aber scheitern.
  • Wenn Transaktionen behandelt werden, die mehrere Tabellen gleichzeitig aktualisieren, sollten entweder alle Tabellen gleichzeitig aktualisiert werden oder keine.

• Zusammenfassung des vierten Kommentars:

  • Dies ist ein hervorragender Überblick über die verschiedenen Konzepte, die beim Aufbau einer Datenbank eine Rolle spielen.
  • Behandelt wird alles, von der Leistungssteigerung auf einer einzelnen Maschine mit SIMD bis hin zu Konsensalgorithmen.
  • Es gibt einen Hinweis auf formale Methoden, die auf Datenbankzuverlässigkeit und verteilte Systeme angewendet werden.
  • Es gibt eine interessante Arbeit darüber, wie das Amazon-S3-Team TLA+ für die Modellierung verwendet.

• Zusammenfassung des fünften Kommentars:

  • Viele Menschen lernen SQL und lernen so Datenbanken, aber durch das Verständnis von B-Bäumen kann man die Stärken und Schwächen von RDBMS besser verstehen.
  • Man versucht, Datenbanken durch das Hinzufügen von Indizes schneller zu machen, aber in Wirklichkeit verdeckt das nur das Problem.
  • Einige Probleme eignen sich gut für B-Bäume, viele jedoch nicht.
  • SQL ist nur eine Query-Schnittstelle für ein entferntes B-Baum-System.

• Zusammenfassung des sechsten Kommentars:

  • Viele Entwickler durchlaufen irgendwann die Phase, ihre eigene kleine Datenbank zu bauen.
  • Durch diesen Prozess kann man viel darüber lernen, was nicht funktioniert.
  • Eine eigene Datenbank zu bauen hilft dabei, den Respekt vor bestehenden Lösungen zu erhöhen.
  • Daten schnell und zuverlässig von der Festplatte zu übertragen, ist schwierig.

• Zusammenfassung des siebten Kommentars:

  • In der Bash-Version kann Atomarität erreicht werden, indem man die Datei in eine temporäre Datei kopiert, sie dann bearbeitet und sync; mv; sync verwendet.

• Zusammenfassung des achten Kommentars:

  • Ein sehr cooles Design, bei dem die Dokument-API MongoDB ähnelt, die leaderlose Replikation Cassandra ähnelt und die Core-pro-Thread-Architektur ScyllaDB ähnelt.
  • All das wurde in Rust implementiert.

• Zusammenfassung des neunten Kommentars:

  • Das Buch "Database Internals" ist erstaunlich gut und bietet eine tiefgehende Untersuchung der Interna.
  • Es wird gefragt, ob es andere ähnliche Bücher gibt.

• Zusammenfassung des zehnten Kommentars:

  • Das Buch "Database Design and Implementation" ist ebenfalls sehr lesenswert und enthält viele in Java geschriebene Beispiele.
  • Für tatsächliche Forschung werden Arbeiten von Andy (Pavlo), Viktor Leis, Thorsten Grust, Thomas Neumann und anderen empfohlen.