Eine eigene Datenbank erstellen

• Erläutert die Grundprinzipien und den Implementierungsprozess einer Key-Value-Datenbank
• Beginnt mit der Dateisystem-basierten dauerhaften Speicherung und Suchweise
• Zeigt Ineffizienzen bei den Operationen Einfügen, Aktualisieren und Löschen auf
• Entwickelt sich schrittweise weiter zu effizienteren Strukturen wie Append-Only-Dateien, Indexen, Sortierung und Segment-Compaction
• Führt schließlich zu modernen Strukturen wie der LSM-Tree und wird in realen Systemen im großen Maßstab eingesetzt

---

Einleitung: Der Start beim Bau einer eigenen Datenbank

Wenn man annimmt, dass es den Datenbankbegriff nicht gibt, wird schrittweise untersucht, wie man eine eigene Datenbank erstellen kann.
Wir betrachten den Prozess zur direkten Implementierung der einfachsten Form einer Key-Value-Datenbank.

Grundidee: Permanente Speicherung mit Dateien

• Zweck einer Datenbank ist es, Daten dauerhaft zu speichern und sie später effizient zu durchsuchen
• Die häufigste Methode ist, jedes Key-Value-Paar mit Hilfe des Dateisystems in eine Datei zu schreiben
• Beim Speichern wird beispielsweise der Inhalt mit $ db set 1 "Lorem ipsum" am Ende der Datei angehängt
• Zur Suche wird jedes Key-Value-Paar in der Datei sequentiell geprüft, bis der gewünschte Key gefunden wird
• Bei einer Aktualisierung wird der Wert des entsprechenden Schlüssels direkt in der Datei ersetzt, bei einer Löschung wird der Datensatz aus der Datei entfernt

Problem: Ineffiziente In-Place-Änderung

• Direktes Ändern und Löschen in Dateien ist äußerst ineffizient
• Eine Datei ist ein einfacher Byte-Stream, daher ist das Ändern von Daten in der Mitte mit dem Verschieben aller nachfolgenden Daten verbunden
• Ändert man beispielsweise einen bestimmten Datensatz auf einen neuen Wert mit anderer Länge, müssen alle folgenden Inhalte verschoben werden
• Je mehr Daten vorhanden sind, desto stärker wirken sich diese Muster auf Tempo und Effizienz aus

Verbesserung 1: Append-Only-Dateistruktur

• Bei Updates und Löschungen werden bestehende Daten unverändert gelassen und nur neue Datensätze am Dateiende angehängt
• Bei jeder Änderung wird ein neuer Datensatz hinzugefügt und der Suchalgorithmus so angepasst, dass der zuletzt geschriebene Wert eines Keys gelesen wird
• Löschungen werden durch einen speziellen „Tombstone“-Wert (z. B. null) markiert
• Vorteil: Effizientes Schreiben ohne Verschieben bestehender Daten
• Nachteil: Die Datei wächst durch Duplikate und Löschmarkierungen zunehmend
• Die Suchgeschwindigkeit bleibt jedoch langsam, da ein kompletter Durchlauf nötig bleibt

Verbesserung 2: Dateigrößenverwaltung und Compaction

• Um das unbegrenzte Wachstum von Dateien zu verhindern, wird bei Erreichen einer bestimmten Größe auf eine neue Datei (Segment) gewechselt, und im vorherigen Segment werden überflüssige Daten (Duplikate, gelöschte Daten) im Rahmen der Compaction entfernt, um die Größe zu reduzieren
• Bei der Compaction bleiben nur wirklich benötigte Daten erhalten; veraltete Datensätze oder ausschließlich Löschmarkierungen werden entfernt
• Damit entsteht eine Verwaltung mit mehreren Segmentdateien, die bei Bedarf zusammengeführt (merge) werden kann

Verbesserung 3: Schnelle Suche per Index

• Ein In-Memory-Hash-Table-Index mit Dateioffsets je Key wird aufgebaut, um schnelle Suchen zu ermöglichen
• Bei der Suche wird zuerst der Index konsultiert und dann direkt die entsprechende Position in der Datei gelesen
• Trade-off: Die Suchgeschwindigkeit steigt, aber da der Index im Speicher liegt, stößt man bei vielen Keys an Speichergrenzen
• Durch die Indexpflege verschlechtert sich die Schreibleistung etwas

Verbesserung 4: Sortierte String-Tabellen und Sparse Index

• Wenn Daten immer sortiert nach Key gespeichert werden, ist bei Bereichsabfragen (Range Queries) eine hohe Effizienz möglich
• Durch die Sortierung reicht es, den Index nur für einen Teil der Keys (Sparse Index) statt für alle Keys zu speichern
• Durch die Anpassung der Indexdichte kann man den Kompromiss zwischen Speicherverbrauch und Suchgeschwindigkeit steuern

Implementierung: Kombination aus In-Memory und On-Disk plus Persistenzsicherung

• Neue Daten werden zunächst in einer sortierten In-Memory-Liste abgelegt und zusätzlich in einer Append-Only-Datei geschrieben, die als Backup dient
• Wenn die In-Memory-Liste wächst, wird sie als sortierte On-Disk-Datei (SST) gespeichert und der Index aktualisiert
• Bei der Abfrage wird zuerst der Speicher geprüft; fehlt der Key dort, wird mit dem Index auf der Festplatte gesucht
• On-Disk-Dateien werden als immutable verwaltet; Updates und Löschungen werden ebenfalls durch das Anhängen neuer Daten abgewickelt
• Nicht mehr benötigte Duplikate und gelöschte Daten werden regelmäßig im Rahmen der Compaction entfernt, um die Dateigröße zu kontrollieren

Entstehung der LSM-Tree

• Die beschriebenen Weiterentwicklungen werden heute weit verbreitet unter dem Namen LSM-Tree genutzt
• Die Kombination aus In-Memory-Memtable und On-Disk-SST (Sorted String Table) ist schnell und für große Umgebungen geeignet
• In großen Key-Value-Datenbanksystemen wie LevelDB und Amazon DynamoDB ist es die zentrale Datenstruktur
• Es gibt Nachteile und Unterschiede zu anderen Strukturen (z. B. B-Tree-basierte relationale DBs), doch im Hochlast- und Skalierungsszenario zeigt es hervorragende Performance

Fazit

• Aus einem einfachen Dateibasierten Ansatz werden schrittweise bessere Datenbankentwürfe durch Append-Only, Index, Sortierung, Segment-Compaction und die Kombination aus In-Memory und On-Disk
• Durch den eigenen Implementierungsprozess lässt sich das interne Verhalten und die strukturelle Logik einer Datenbank direkt nachvollziehen
• Die LSM-Tree-Architektur übernimmt in modernen großskaligen Datensystemen eine Standardrolle
• In Zukunft bleibt Raum, weitere Ansätze wie die B-Tree-Struktur relationaler Datenbanken zu untersuchen

[GN⁺]

Hacker News Kommentare

• Das Design und die Beispiele in diesem Beitrag gefallen mir wirklich. Die leserfreundliche Struktur ist beeindruckend; die Übung selbst ist auch eine sehr spannende Erfahrung. Wenn man bei null anfängt, kann man sich wirklich verifizieren, wie viel man tatsächlich weiß.
  • Ich hatte früher selbst die voreilige Haltung: „Baue keine eigene Datenbank, verwende keine KV-Datenbank, nutze einfach SQL.“ Doch dieser Gedanke kam genau dann auf, als ich versuchte, selbst eine eigene DB zu entwerfen oder nur eine KV-Datenbank zu nutzen und dabei SQL letztlich nur halbherzig neu zu erfinden. Der Lernwert durch eigenes Erleben ist klar da.
  • Ein kleiner Wermutstropfen ist, dass als Beispiel Lorem Ipsum verwendet wurde. Dadurch neigt man eher dazu, es nur flüchtig zu lesen, statt sich wirklich zu konzentrieren. Echte Beispieldaten wären deutlich interessanter. Abgesehen davon ist es wirklich ein tolles Stück.
• Der Satz „LSM-Trees sind die grundlegende Datenstruktur, die in DynamoDB etc. eingesetzt wird, und zeigen in großen Umgebungen sehr gute Leistung ... bis zu 80 Millionen RPS“ ist etwas missverständlich: LSM wird auf der Ebene der Storage-Engine pro Node verwendet. Wie sich das gesamte verteilte System auf 80 Millionen RPS skalieren lässt, wird dabei nicht erklärt. Soweit ich weiß, nutzte das ursprüngliche Dynamo-Paper BerkeleyDB (B-Tree oder LSM), und in der 2012er Version ist vollständig auf eine LSM-basierte Engine umgestellt worden.
• Ich habe einige Artikel aus der Beitragsliste angeklickt; das Design und die Animationen sind wirklich wunderschön.
• Im Abschnitt „Sorting in Practice“ scheint das erste Beispiel kaputt zu sein. In der Beschreibung steht, dass nach dem Sortieren im Speicher die Daten im sortierten Zustand auf die Festplatte geschrieben werden sollen, aber im tatsächlichen Beispiel wird beim Schreiben auf die Festplatte die Sortierung wieder gelöst. Dasselbe gilt für das flush-Beispiel im Recap-Teil (das zweite), dort ist ebenfalls formuliert, dass in sortiertem Zustand in die Datei geschrieben wird.
• Spannender Beitrag. Ich modelliere gerade Entwickleraktivitäten als ein Timeseries-Key-Value-System, mit dem Entwickler als Schlüssel und dem Commit als Wert. Ich stoße auf ein ähnliches Problem: Das Log wächst schnell, der Index wird schwergewichtig, Bereichsabfragen werden langsam. Beim Komprimieren von Segmenten frage ich mich, wie entschieden wird, welche Daten verworfen werden. Es fühlt sich schwierig an, die Balance zwischen Aktualität und Aufbewahrungszeit zu treffen.
• Ich habe mich in den letzten 4 Wochen intensiv darauf konzentriert, einen Triple Store selbst zu schreiben. Hätte dieser Beitrag etwas früher erscheinen können, hätte ich ein paar Einblicke früher verstanden. Schade.
• Falls der Autor diese Seite liest: Ich frage mich, ob er einen RSS-Feed hinzufügen kann; ich würde ihn gern über Feedly abonnieren.
• Wenn du deine eigene Datenbank bauen willst, kann ich dieses kostenlose Online-Buch unbedingt empfehlen.
  • Ich erinnere mich, dass hier vorher ein Artikel vorgestellt wurde, der die Grundkonzepte einer Datenbank mit Bash-Beispielen erklärte (z. B. „DB mit Bash bauen“), aber ich kann ihn nicht mehr finden. Falls jemand den Link kennt, würde ich mich freuen, wenn er geteilt werden könnte.
• Die Seite ist bereits nicht erreichbar, weil der Traffic zu hoch ist.
  • Es wird wohl eine schnellere Datenbank benötigt.
• Mir gefällt dieser schrittweise Aufbau von den First Principles aus wirklich sehr gut. Wenn man dem Beitrag folgt, wird in jedem Schritt klar, welches Problem entsteht, und welche zusätzlichen Probleme beim Lösen wieder auftreten. Dadurch erreicht man wirklich eine befriedigende Lösung.